Sharing my progress and solutions to the the matasano crypto challenges. Obviously, this is one big spoiler. You have been warned.
Current status: on hiatus
- Set 1
- Convert hex to base64 - Done
- Fixed XOR - Done
- Single-byte XOR cipher - Done
- Detect single-character XOR - Done
- Implement repeating-key XOR - Done
- Break repeating-key XOR - Done
- AES in ECB mode - Done
- Detect AES in ECB mode - Done
- Set 2 9. Implement PKCS#7 padding - Done 10. Implement CBC mode - Done 11. An ECB/CBC detection oracle - Done 12. Byte-at-a-time ECB decryption (Simple) - Done 13. ECB cut-and-paste - Done 14. Byte-at-a-time ECB decryption (Harder) - Done 15. PKCS#7 padding validation - Done 16. CBC bitflipping attacks - Done
- Set 3 17. The CBC padding oracle - Done 18. Implement CTR, the stream cipher mode - Done 19. Break fixed-nonce CTR mode using substitutions - Skipped (for now) 20. Break fixed-nonce CTR statistically - Done 21. Implement the MT19937 Mersenne Twister RNG - Done 22. Crack an MT19937 seed - Done 23. Clone an MT19937 RNG from its output - Done 24. Create the MT19937 stream cipher and break it - Done
- Set 4 25. Break "random access read/write" AES CTR - Done 26. CTR bitflipping - Done 27. Recover the key from CBC with IV=Key - Done 28. Implement a SHA-1 keyed MAC - Done 29. Break a SHA-1 keyed MAC using length extension - Done 30. Break an MD4 keyed MAC using length extension - Done 31. Implement and break HMAC-SHA1 with an artificial timing leak - Done 32. Break HMAC-SHA1 with a slightly less artificial timing leak - Probably done
- Set 5 33. Implement Diffie-Hellman - Done 34. Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection - Done 35. Implement DH with negotiated groups, and break with malicious "g" parameters - Done 36. Implement Secure Remote Password (SRP) - Done 37. Break SRP with a zero key - Done 38. Offline dictionary attack on simplified SRP - Protocol done, no cracking attempted (for now) 39. Implement RSA - Done 40. Implement an E=3 RSA Broadcast attack - Done
All of the code here is 100% genuine own code, done by me. No looksees, copy & paste (unless that was a part of the exercise) etc. I might have looked up the theory of some topics in proper literature though (you should too, probably).
The challenges are now run by Travis. Note that my code requires a modern Ruby - 2.1.5 should work, 1.9.3 and below probably won't.
There are also unit tests for the library (rake test:unit:all, but note that some are non-deterministic where a failure doesn't necessarily mean the code is wrong).
The general idea is to have the unit tests not depend on the challenges data inputs. This might not be exactly the case for now. (I've also noted that some of my assert_equals are backwards, oh well, conventions...)
Ruby really kicks ass when it comes to hacking and learning new things. Go not so much, but I've learned that Unicode-centric approach is problematic for hacking ASCII-based crypto. I don't see any real speed difference between my Ruby code and my Go code.
I've deleted the Go sources as I'm not going to get back to them.
Having done the first four sets: this stuff is both amazingly eye-opening and scary at the same time. Are you seeding your PRNGs with current time (in NTP-synchronized world...)? Do you think SHA1(key || msg) is a secure way to do a MAC? Well, if so you're doing it very wrong, and that's just the tip of the proverbial iceberg.
Note: last update around end of Set 2.
Reading code is one thing, knowing the right output is another. If you believe knowing the right outputs is really the thing that will help you understand what's going on have a looksee here. There are also some spoilerific/sanity-ensuring notes.
Licensed under CC BY-NC-SA, see LICENSE.txt for details.
Copyright (c) 2014 - 2015 Piotr S. Staszewski