Curious how bitcoin works? Bitfloor founder spells it out on video ( 28:08)(5in5nyc.com)
5in5nyc.com
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/
2 comments
What did you like about it?
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.
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.
That sounds really fun. We build an internal application (which I was going to release publicly but instead keep rewriting and rewriting because I don't trust my code enough) that does a lot of this, but at much more nitty-gritty level (ie, use inference techniques to figure out block cipher modes, that sort of thing). If you're ever interested in more challenges like this, drop me a line; I have 'em.
(I watched some of the video stuff last night, and I agree, he's really engaging; moreso than Dan Boneh was for the Stanford crypto course).
How good was the block cipher coverage? Did you end up understanding what you might look for if you had to break someone else's (say) CTR mode stream encryptor, that kind of stuff?
(I watched some of the video stuff last night, and I agree, he's really engaging; moreso than Dan Boneh was for the Stanford crypto course).
How good was the block cipher coverage? Did you end up understanding what you might look for if you had to break someone else's (say) CTR mode stream encryptor, that kind of stuff?
There was not a lot of low level stuff on block ciphers. In an early unit, he said that while it is interesting to go into how block ciphers work at the low level, he was going to omit that to get on to application of cryptography (I believe the official title of the course is "Applied Cryptograph"). He emphasized that very very few people should be designing their own block ciphers or doing their own implementation of existing designs--almost everyone should be using a library implementation that has been well tested by experts.
I haven't taken the Stanford course (I'd like to--but my schedule has just not worked out to allow it yet), but I did go look at the slides from a few of the lectures there and it appeared that they go into more detail at the lower level on ciphers and hashes. I got the impression that the Stanford course and the Udacity course would compliment each other quite a bit.
As far as breaking someone's encryptor goes, there would be some mention of how things could be exploited if the thing you were attacking had certain flaws, usually as motivation to explain why things were done a certain way. E.g., if you don't have a random nonce here, someone will be able to do this and that will reveal something about your plaintext...that kind of thing.
For the specific example of trying to break someone's system that is using a block cipher in CTR mode to make a stream encryptor, I think a student finished the Udacity course and did well would know enough to:
(1) recognize that CTR mode is essentially using the block cipher to generate the key for a OTP, so flipping bits in the ciphertext flips the corresponding bits in the decrypted plaintext. Hence, if the attacker can find out through some means enough information about the structure of the messages so as to predict what is in the plaintext (account number to receive the deposit, for instance) he can make meaningful changes (assuming the system does not include some kind of check on the message integrity).
(2) recognize that if the key and counter sequence are ever reused the consequences are essentially the same as reusing a OTP key, and so focus on how the keys and counters are being initialized.
I haven't taken the Stanford course (I'd like to--but my schedule has just not worked out to allow it yet), but I did go look at the slides from a few of the lectures there and it appeared that they go into more detail at the lower level on ciphers and hashes. I got the impression that the Stanford course and the Udacity course would compliment each other quite a bit.
As far as breaking someone's encryptor goes, there would be some mention of how things could be exploited if the thing you were attacking had certain flaws, usually as motivation to explain why things were done a certain way. E.g., if you don't have a random nonce here, someone will be able to do this and that will reveal something about your plaintext...that kind of thing.
For the specific example of trying to break someone's system that is using a block cipher in CTR mode to make a stream encryptor, I think a student finished the Udacity course and did well would know enough to:
(1) recognize that CTR mode is essentially using the block cipher to generate the key for a OTP, so flipping bits in the ciphertext flips the corresponding bits in the decrypted plaintext. Hence, if the attacker can find out through some means enough information about the structure of the messages so as to predict what is in the plaintext (account number to receive the deposit, for instance) he can make meaningful changes (assuming the system does not include some kind of check on the message integrity).
(2) recognize that if the key and counter sequence are ever reused the consequences are essentially the same as reusing a OTP key, and so focus on how the keys and counters are being initialized.
The video isn't loading for me; is there a mirror kicking around?
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.