Curious how bitcoin works? Bitfloor founder spells it out on video ( 28:08)

http://5in5nyc.com/2012/06/20/5in5nyc-ep-07-10gen-friends-mongodb-bitfloor-nextbigsound-crowdtap-art-sy/

by ericskiff • 14 years ago

11 6 14 years ago

5in5nyc.com

redthrowaway• 14 years ago

The video isn't loading for me; is there a mirror kicking around?

tzs3• 14 years ago

The Udacity "Applied Cryptography" course covers Bitcoin at the end of Unit 6. Here are the videos:

http://www.youtube.com/watch?v=CdsS8jFVv2c

http://www.youtube.com/watch?v=zJxVXyvccgI

http://www.youtube.com/watch?v=4UF9zYU0jZI

http://www.youtube.com/watch?v=JRPu-vUdJU0

They range from under two minutes to a bit over 3 minutes.

PS: that course is excellent. If you are at all interested in cryptography, I highly recommend it.

tptacek2• 14 years ago

What did you like about it?

tzs3• 14 years ago

Several things. The instructor, David Evans of the University of Virginia, has a really infections goofy enthusiasm that keeps your interest. He covered a good range of topics, with a nice mix of practical, historical, and theoretical. Here's very short summary from the syllabus:

Unit 1: Perfect Ciphers. What makes certain ciphers perfect, how the Lorenz Cipher was broken

Unit 2: Symmetric Encryption. Sending messages when two people share a secret

Unit 3: Key Exchange. Technics to establish a shared secret

Unit 4: Asymmetric Encryption. Exchanging information using public key cryptosystems

Unit 5: Public Key Protocols. Encrypted key exchange, certificates, secure commerce

Unit 6: Using Cryptographic Primitives. How cryptography can be useful for anonymizing communication, voting, and digital cash

Unit 7: Secure Computation. Computing without exposing data

In a little more detail:

Unit 1 introduced the subject, covering OTP and giving an interesting historical account of the Lorenz cipher and the development of Colossus.

Unit 2 talked about Kolmogorov complexity, randomness, PRNGs, block cipher modes, hash function, password storage.

Unit 3 was about key exchange, mostly Diffie Hellman.

Unit 4 covered asymmetric systems, concentrating on RSA.

Unit 5 covered EKE, ssh, TLS, and certificates.

Unit 6 covered traffic analysis, onion routing, TOR, voting (Mixnet), centralized digital cash (based on blind signatures and an identity list scheme to deanonymize double spenders), decentralized digital cash (Bitcoin).

Unit 7 covered secure computation. In particular the garbled circuit protocol to let Alice and Bob evaluate a logic circuit together without revealing their inputs to each other.

Each unit had around 5 or 6 homework problems. Most were multiple choice, but there were several that involved programming.

There were also several optional challenge problems. These were instructive and a lot of fun. Here is a description of the challenge problems:

From unit 1: We were given two bit strings of the same length, about 700 bits each, and told they were the result of running two messages encoded as 7-bit ASCII through a one time pad, where the operator goofed and used the same pad for both messages. Figure out the messages.

From unit 2: we were given a list of 126 32-bit numbers, and asked to figure out the next number. Based on the material in unit 2, it was obvious this was supposed to be a weak PRNG. It turned out to be weaker then they intended--it was periodic with period 64, making it easy to solve the challenge by inspection.

From unit 3: we were given the public information from a Diffie-Hellman key exchange between Alice and Bob, AND we were told the number of multiplications that were required when Alice computed the shared key from the her secret and the data from Bob. Our task was to decrypt the message that Alice and Bob then exchanged.

From unit 4: we were given 16 separate public RSA keys, and for each we were given the cipher text of a message encrypted with that key. Our challenge was to find the plain text. This was a particularly fun challenge. I'll describe it in more detail later.

From unit 5: this was a simplified version of the BEAST attack from last year against SSL. They set up a server that operated as follows:

* It contained a secret message, M.

* We could open a session, and receive a session token.

* We could then send the server a message. The server takes our message, appends its secret message, encrypts the result with AES in CBC mode, and sends the cipher text back to us. For a given session, the server uses a fixed key, and the IV each time is the last block of the cipher text from the previous exchange.

Our task: find out M.

The final challenge was released with the final exam. Alice and Bob wish to communicate, but need our help. They each have a server. There are four commands we can do via CGI on their server:

* Open a session. That gets us a token and half of a Diffie-Hellman exchange to establish a key for that session.

* Send half of a Diffie-Hellman exchange.

* Get a message from the server.

* Send a message to the server.

We were given the URLs for the servers. Our initial task was to connect to both, establish sessions, and relay the Diffie-Hellman parameters between them, and then use get and sent to pass any messages between them.

A lot of people were a bit puzzled by this, as there were no instructions included on how to submit your answer, and since we had no idea HOW Alice and Bob are using the key they establish via DH, we can't really do a man-in-the-middle and spy on their messages. All we can do is watch the cipher text...and that turned out to be useful, because soon after they start talking, Alice would send this, in plain text:

> Eve: I need your help. My friends Alex and Betty are also using Diff ie Hellman to exchange a key and then send encrypted messages. I think that Betty and Bob have a hint; can you find it for me? I've given you the information I know about their system: http://cs387.udacity-extras.appspot.com/pdf/final_challenge..... Hopefully you can find a way to break it. Alex is also trying to help me. Can you arrange for him and I to exchange messages? Thanks so much for your help.

Aha. That document explained how they were using the key. Now we had enough to man-in-the-middle everyone and read all the messages. What we found then was quite interesting.

Bob had a message he didn't know what to do with. Betty offered to help. Bob encrypted the message and sent it to Betty. Alex and Alice know about this, and want to know the content of the message.

Alex tells Alice that Bob has a PRNG he likes to use for OTP keys, and that he thinks Bob's PRNG is similar to A5.1 GSM. Also, Alex has a file with 1000 bits from Bob's PRNG, and he sends the URL to Alice.

Alex asks Bob if Bob is "still using that PRNG?", and Bob says "Yes; but I was only able to use one LFSR".

With this and some Googling, the diligent student can figure out Bob's PRNG, decrypt the message Bob sent to Betty, and then start a session with Alice as Eve (instead of as someone Eve is trying to impersonate). Alice asks what Eve has found. Eve can give Alice the message. Alice understands it, and tells Eve what to do to get credit for the challenge.

I think it is toss up whether that challenge or the RSA breaking challenge was more interesting.

For the RSA challenge, one message fell very fast because it was a short message and had no padding, and the public exponent was 3, and m^3 was less than n, so taking a simple integer cube root broke it. The message was "Chinese Remainder Theorem". Another also fell to taking a cube root, although this was a little tricker because m^3 was > n, but it was less than 2n.

That first message was a hint, and it turned out that there were 3 where the same message, without padding, had been encrypted with three different keys, all with exponent 3. An application of CRT broke those 3. The message of those was a recommendation to read a particular blog entry at "Freedom to Tinker" which talked about Lenstra et al's recent paper on low entropy in public keys.

Taking that as a hint and checking for pairs of moduli that are not relatively prime gave a factor of two of the keys. The message from one of these linked to this: http://pastebin.com/hNz9gZbe and asked what could go wrong? At that URL, you'll find some code to generate an RSA modulus, but it is doing a very bad thing with its random number generation, and it turns out that there are only about 32000 possible moduli that it can generate.

Brute force checking all of those breaks two more. One of those gives a message that talks about Fermat being a smart guy who might have some hints about factoring. As this hint suggests, a couple of the moduli turn out to have p and q that aren't too far apart, and so are easily factored.

Curious how bitcoin works? Bitfloor founder spells it out on video ( 28:08)

Related Stories