Blog
NIST Announces SHA3 Winner Keccak
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[1][2] and attacks on WEP using CRC32's lack of an avalanche characteristic, among others[3]. The Flame malware that targeted Middle Eastern countries appears to have used a MD5 collision in code signing to infiltrate systems[4].
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[5]:
- 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.[6][7]
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.[8] 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.[9]
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.
References
[1] Schneier, Bruce. Forging SSL Certificates. 31 December 2008. http://www.schneier.com/blog/archives/2008/12/forging_ssl_cer.html
[2] Sotirov, Alexander et al. MD5 considered harmful today: Creating a rogue CA certificate. 30 December 2008. http://www.win.tue.nl/hashclash/rogue-ca/
[3] Borisov, Nikita et al. (In)Security of the WEP algorithm. 2001. http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html
[4] 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/
[5] 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.
[6] Coron, Jean-Sebastian et al. "Merkle-Damgard Revisited : how to Construct a Hash Function."
[7] 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
[8] http://sponge.noekeon.org, particularly http://sponge.noekeon.org/CSF-0.1.pdf section 1.3
[9] 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.
Engaged!
I proposed to my girlfriend Aubrey late last month!
I proposed in the Getty Museum's gardens high atop LA. Below is Aubrey trying on her ring for the first time! (I hired Chris Miller, an awesome LA-area photographer, to take pictures.)
Right afterward, we raced down the 405 to Long Beach and sailed off to Catalina for a couple super relaxing days at the Inn on Mt Ada (aka the Wrigley Mansion).
It was all super great! If we're Facebook or Twitter friends, there are a couple albums to peruse.
So my final 2012 goal is to plan (and save for) an awesome wedding in summer 2013.
2012 Goals
My 2012 goals are pretty simple. Most of them are focused on professional development. But I genuinely enjoy software engineering, so it's enjoyable to dedicate time to it.
Finish my Master's from BU
I started this degree in January 2010, alongside a full-time job. I'm now three classes away from the degree — Computer Networks, Operating Systems and an elective. I can finish it this year, and I will do so.
My pace (heretofore and forward) probably means abandoning the MA in humanities (art history) for which I attended U Chicago 2007-2008. I am ok with that. I began that degree not knowing what I wanted to do professionally. It helped me see that my interest in the humanities is better served as a hobby than a career. I should write more about my experiences there in another post.
Learn Emacs
I am very interested in Clojure and in Lisps in general, so I think it will help to learn Emacs at some point soon. I learned to code with pico/nano as my editor. I use Eclipse (STS actually) for the most part now. I'm excited to get the best of both approaches with Emacs and Emacs Lisp.
Continue professional development
Separate from finishing the Master's, I'd like to continue learning new languages and better engineering practices. I'd also like to get some leadership experience on projects. In the fall, I'd like to attend Strange Loop and Clojure/conj. Maybe I'll also spend some time learning another language, like Haskell, Erlang, Prolog, IO or Smalltalk; all of those are on the list.
Get in better shape
I need to start being more active. I would love to run a 5k and start training for longer races. Hopefully within the next three years I will be able to run a marathon on Catalina. It's such a beautiful island and a fun idea. I'd love to do it. It's hard to do this in New Hampshire, though, because the weather sucks most of the year.
Spend more time on the NHJUG
I need to spend more time on the NHJUG. We need to redo the website and line up speakers for most of 2012.
And finally a surprise goal!
I will post about it in a couple days. I realize this sounds like a Nixon 1968 campaign plank.
