The Matasano crypto challenges ======== 48 practical programming exercises using real-world cryptography. A good way to test them all is `make > /dev/null`. For more information, see http://cryptopals.com/ 1. Convert hex to base64 2. Fixed XOR 3. Single-byte XOR cipher 4. Detect single-character XOR 5. Implement repeating-key XOR 6. Break repeating-key XOR 7. AES in ECB mode 8. Detect AES in ECB mode 9. Implement PKCS#7 padding 10. Implement CBC mode 11. An ECB/CBC detection oracle 12. Byte-at-a-time ECB decryption (Simple) 13. ECB cut-and-paste 14. Byte-at-a-time ECB decryption (Harder) 15. PKCS#7 padding validation 16. CBC bitflipping attacks 17. CBC padding oracle 18. Implement CTR 19. Fixed-nonce CTR using substitutions 20. Fixed-nonce CTR using statistics 21. Implement MT19937 22. Get MT19937 seed 23. Clone a MT19937 24. MT19937 stream cipher 25. Break "random access read/write" AES CTR 26. CTR bitflipping 27. Recover the key from CBC with IV=Key 28. Implement a SHA-1 keyed MAC 29. Break a SHA-1 keyed MAC using length extension 30. Break an MD4 keyed MAC using length extension 31. Implement and break HMAC-SHA1 with an artificial timing leak 32. Break HMAC-SHA1 with a slightly less artificial timing leak 33. Implement Diffie-Hellman 34. Implement MITM key-fixing attack on D-H with parameter injection 35. DH with negotiated groups, and break with malicious "g" parameters 36. Implement Secure Remote Password (SRP) 37. Break SRP with a zero key 38. Offline dictionary attack on simplified SRP 39. Implement RSA 40. Implement an E=3 RSA Broadcast attack 41. Implement unpadded message recovery oracle 42. Bleichenbacher's e=3 RSA Attack 43. DSA key recovery from nonce 44. DSA nonce recovery from repeated nonce 45. DSA parameter tampering 46. RSA parity oracle 47. Bleichenbacher's PKCS 1.5 Padding Oracle (Simple Case) 48. Bleichenbacher's PKCS 1.5 Padding Oracle (Complete Case) Challenge 1-8 are basics. Then 9-16, 17-24, and 25-32 deal mainly with block ciphers. After that it gets into number-theoretic methods. I went to Python starting with #17, just for fun & experience. Some of my implementations use stdin; others carry their inputs with them or open a filename hard-coded in. A couple input files are "handcrafted:" `unknown_key.txt` came from random.org, and `17.txt` was cut and pasted from http://cryptopals.com/sets/3/challenges/17 . I decided to commit *most* of the input files to this repo, with the exception of `8.txt` because it's big. Times noted in makefile are from MacBook Pro (8,1 early 2011, OS X, 2.7 GHz Intel Core i7), or iMac7,1 (Intel Core 2 Duo, 2.0-2.4 GHz circa 2007) running Ubuntu. Conclusions / insights -------- * When analyzing repeating-key XOR, be more accurate about picking the best key size, and about the metric (for evaluating whether putative plaintext fits English letter distributions). * ECB cut-and-paste: had to figure out "user\x04\x04.." which allowed finding "...role=". Then had to figure out "admin\x04\x04.." * ECB decryption: Once you align on a block, it's somewhat simple comparing (short block + unknown char) to (short block + try each known char). * CBC bitflip (inserts into CBC): Know where your initial string lies within the block. Then know how to flip your initial string into your final string. * CBC padding (decrypts CBC): It helped to write some pseudocode first, but I still had to be very careful with the arithmetic. Don't guess \x01 as the last char, or else the last block will always falsely show up with valid padding, ruining the rest of the last-block guesses. Instead skip to \x02; it's very unlikely (1/65,536) to see a real block ending in \x02\x02 even in line-noise type plaintext. Less likely still in a natural language. * Chosen plaintext attacks are everywhere. * Don't seed a RNG off of the current UNIX time in seconds. * Don't use the key as the IV; IV is trivially recoverable. * So what are CBC and CTR good for? * Wow, web.py makes it *really* easy to roll a tiny app, even for someone who has never done any web programming. * 8 milliseconds per character in a string-compare is breakable. 7 ms is breakable with manual help. Specifically, set T to 6 and fill in some text from some replicates. This all feels a *lot* like DNA sequencing. 6 ms similarly; set T to 5 ms, fill in by hand. I can break 4ms by an automated try-try-again and tracking the longest guess on record. 3.7 ms is a good threshold for that. Probably will require some sort of voting, graphics, and/or statistics to get lower than that. Signal to noise is going to decrease toward the end of the string. Averaging seems to allow me to bring down T and the back-up parameter. Also this results in thousands and thousands of server requests: something like 100 per character of the hash. It is somewhat cheating to know in advance what is the server's delay. I can break 3.5 ms with no help, with T=3.0, backup=1, and N=10 replicates of each timing measurement! Probably helps to have the server as quiet as possible in terms of CPU. * Diffie-Hellman parameter injection feels weird and kind of hard to understand or unrealistic? * I am surprised that my offline dictionary attack on SRP with a stolen hash (HMAC) doesn't go faster. See `chal38.py` or `srp.py`, class `Server` when `mitm=True`, specifically method `validate_hash()`. Only 50 - 60 guesses per second? * SRP with zero key is indeed fun. * RSA implementation and several of the challenges about it were fun. * RSA without padding is bad. RSA that doesn't fully check for proper padding or other compliance is also bad. * Once again, don't reuse your nonce, hence the name. When it comes to DSA, I guess you can't even give it away or make it easy to guess? * Don't provide a mechanism to give away even one bit of your RSA plaintext. Not in error messages, not in any way. Seriously. And if you use an implementation written by someone who accidentally does provide such a mechanism, then everything's ruined if Mallory finds this mechanism. * When translating intricate paper methods to code, it helps to do it first using a toy case that runs really fast. Also, I finally graduated from Print Statement High School and matriculated as a freshman at Debugger University.