Thanks to everyone who came to my cryptography talk at the NH Alpha Loft's Web Dev meetup this past week. It was a lot of fun and the questions were great! Below are the slides. You're free to reuse them under CC 3.0 Attribution license. Please do contact me with any questions -- Twitter is the best way, @thesleepyvegan.
This Fall I'm excited to be going to a few conferences. My job has changed from Java to mostly Ruby with some Java and the opportunity to add in new languages. I'm still focused on back-end development. I'm looking forward to learning more about Ruby, perhaps finally writing production Clojure code and generally moving toward functional programming. Anyway, here's where I'm going:
- September: Commercial Users of Functional Programming
- October: Wicked Good Ruby
- November: Clojure Conj
Hope to see you there!
On Tuesday, 2 October, NIST announced Keccak as the winner of the SHA3 hash competition. SHA3 will be the new standard to replace SHA1 and SHA2. The SHA family of hash functions are cryptographically secure and bear government endorsement for use in security-sensitive applications.
A cryptographically secure hash function must possess certain security characteristics beyond that of a simple hash function or one-way compression function: two forms of preimage resistance and collision avoidance. Specifically, it must be computationally infeasible to find two plaintexts that hash to the same digest (collision), or to find a plaintext given a digest (preimage).
There have been significant prior exploits that hinged on the use of insecure hash functions, such as forged SSL certificates using MD5 collisions and attacks on WEP using CRC32's lack of an avalanche characteristic, among others. The Flame malware that targeted Middle Eastern countries appears to have used a MD5 collision in code signing to infiltrate systems.
MD5, SHA1 and SHA2 all share the same basic construction of their hash algorithms. The construction is called Merkle-Damgard and uses a number of rounds of permutation to plaintext to create its digest. Wikipedia describes the shortcomings of this approach in very clear and terse language:
- Length extension — once an attacker has one collision, he can find more very cheaply.
- Second preimage attacks against long messages are always much more efficient than brute force.
- Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
For this reason, many cryptographers have suggested significantly modifying Merkle-Damgard construction or abandoning it.
The winner of the SHA3 competition, Keccak, uses a different construction. Called a "sponge," it involves a number of rounds of input "absorption" and then a number of rounds of "squeezing" to create the digest. The authors of Keccak created a great picture of sponge operation:
As depicted above, the input plaintext is only used during the absorption rounds. In each of these rounds, the amount of plaintext considered also varies based on digest parameters ("rate of absorption"). The rounds of squeezing entirely use round constants and the existing sponge contents carried throughout the process,with no access to the input plaintext. This means the final rounds do not involve the input plaintext in any way. In cryptanalysis provided by the authors, they discuss how this method better invokes the random oracle model and hopefully leads to a more secure construction.
Shortly after the SHA3 announcement, the NIST hash forum list was taken over by analyses of how long it will take for an attack on SHA1 to become viable. The results are sobering. Jesse Walker, an architect at Intel responsible for much of the crypto internals of Ivy Bridge, wrote: "a collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018 (~$173k), and a university research project by 2021 (~$43k)." He estimates that the attach at present would cost $2.2 million dollars, so at least we're mostly safe for now.
It will be very interesting to see how the new construction impacts its long-term security and the applicability of past attacks on it. The accessibility of a significant SHA1 attack underscores the importance of a new standard and the new construction.
 Schneier, Bruce. Forging SSL Certificates. 31 December 2008. http://www.schneier.com/blog/archives/2008/12/forging_ssl_cer.html
 Sotirov, Alexander et al. MD5 considered harmful today: Creating a rogue CA certificate. 30 December 2008. http://www.win.tue.nl/hashclash/rogue-ca/
 Borisov, Nikita et al. (In)Security of the WEP algorithm. 2001. http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html
 Stiennon, Richard. "Flame's MD5 collision is the most worrisome security discovery of 2012." Forbes. 14 June 2012. http://www.forbes.com/sites/richardstiennon/2012/06/14/flames-md5-collision-is-the-most-worrisome-security-discovery-of-2012/
 http://en.wikipedia.org/wiki/Merkle–Damgård_construction . This was the most accessible discussion of the flaws of Merkle Damgard construction I found. All others assumed significant prior theoretical knowledge.
 Coron, Jean-Sebastian et al. "Merkle-Damgard Revisited : how to Construct a Hash Function."
 Bibam, Eli et al. "A Framework for Iterative Hash Functions — HAIFA." Authors submitted the SHAvite-3 function to the SHA3 competition, based on the HAIFA construction defined in this paper. It advanced to the second round of the competition but was not a finalist. No significant issues were found during cryptanalysis. More information on SHAvite-3 can be found at http://ehash.iaik.tugraz.at/wiki/SHAvite-3
 http://sponge.noekeon.org, particularly http://sponge.noekeon.org/CSF-0.1.pdf section 1.3
 While membership to the NIST hash forum list is open to the public, archives are only available to subscribers. Bruce Schneier excerpted Jesse Walker's message in a blog post at http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html.