Security Review Summary of NIST SHA-3 Round 1 146
FormOfActionBanana writes "The security firm Fortify Software has undertaken an automated code review of the NIST SHA-3 round 1 contestants (previously Slashdotted) reference implementations. After a followup audit, the team is now reporting summary results. According to the blog entry, 'This just emphasizes what we already knew about C, even the most careful, security conscious developer messes up memory management.' Of particular interest, Professor Ron Rivest's (the "R" in RSA) MD6 team has already corrected a buffer overflow pointed out by the Fortify review. Bruce Schneier's Skein, also previously Slashdotted, came through defect-free."
Re:ANSI C (Score:3, Interesting)
Why do they even have a reference implementation for a hash function in a programming language? Wouldn't just defining the function mathematically be less error prone and just as effective?
Disclaimer (Score:2, Interesting)
I should add that I work for Fortify and that I initiated the SHA-3 review in my spare time as a private project. The Slashdot article on December 21 caught my interest.
Re:this is why... (Score:3, Interesting)
Read something about http://research.microsoft.com/en-us/groups/os/singularity/ [microsoft.com] :)
Re:Disclaimer (Score:3, Interesting)
Yeah, both very good points.
People do make mistakes. Even geniuses, when they're trying really hard to be careful. Personally, I see recognizing that as a validation for code review (including the automated code review that I do).
I want the winning entry for this competition to be flawless to the extent that's feasible. Right now, my job includes finding SHA-1 for cryptographic key generation, and telling people to replace that with something better. I don't want to be pulling out SHA-3 in a couple years, too.
cryptol (Score:4, Interesting)
But that just raises the question of how to define a hash function mathematically? The lambda calculus, Godel Numbers? Things like cryptographic hash functions don't tend to be nice algebraic thingies like f(x)=x*x+7, especially since they're usually iterative and deliberately messy - the pretty functions are likely to be less secure.
On the other hand, there are things like cryptol [galois.com] in which you may be able to specify hash functions more mathematically. For example, here is a cryptol implementation of skein [galois.com].
Re:ANSI C (Score:3, Interesting)
I hate to have to repeat it for the thousandth time, but Java's so-called virtualization comes crashing right down if you have even a single threading bug. Let me explain how it works.
Java gets compiled to machine code at runtime. Unlike machine code made from C code, the machine code really does have some nice protections from address and type confusion, with a generally acceptable performance penalty.
However it does NOT have ANY protections from threaded race conditions, so if you make any mistake in this, all bets are off as the results are completely undefined. It could be as simple as a missed increment, or it could cause an internal JVM data structure to be corrupted, either in the Java or C++ components.
At least with C you see and control all of the code that gets run at runtime, all with debug symbols right down to the system calls, and can largely detect and sometimes even trace problems, but with the monstrously large JVM running under your code, you'd be lucky to get a meaningful stack trace.
The same applies right back to security. Threading bugs are generally much more difficult to diagnose and solve than memory management bugs, so if a developer gets memory wrong, they'll get threading wrong too. In a kernel it's worst of all. A Java kernel does little to solve this, and in fact would include a lot of JVM code which must also be debugged.
DJB threw his hash in the ring, too (Score:3, Interesting)
MD6 by Rivest and Skein by Schneier et. al. seem to be getting a lot of attention, but another celebrity cryptographer, Dan J. Bernstein, also has a hash in this race, called "CubeHash."
DJB continued his tradition of offering cash rewards for people to find security problems with his code, giving out (so far) monthly prizes of 100 Euros to the most interesting cryptanalysis of CubeHash.
So far, the primary criticism of CubeHash is that it's slow, running some 10 to 20 times slower than many of the others in the competition. Dan brushes off this criticism by stating on his site [cr.yp.to]: "for most applications of hash functions, speed simply doesn't matter."
To be honest, when compared efforts like MD6 and Skein, with their mathematic proofs of security, VHDL and other in-hardware reference implementations, and their amazing optimizations in both speed and efficiency (Skein can process half a GByte of data per second on modern hardware, and consumes only 100 bytes) -- entries like CubeHash seem to have that longshot underdog appeal, like a New Zealand soccer World Cup team.
Re:ANSI C (Score:3, Interesting)
With security out of the way, the most important criterion that will be used to choose the winner is performance.
Probably no one will ever see this self-reply, but I just noticed that the Skein site makes a good argument that the paring down of the candidate list should (will?) happen in the other order.
The idea is that since it's a huge amount of work to cryptanalyze a hash function, and since it's easy to measure performance (in time and space), the thing to do is to first toss out all of the slow and/or memory-hungry candidates. Obviously, if all of the fast and tight candidates were found to have security flaws, then the field would have to be widened to again include some of the slower candidates.
In all probability, though, the fast candidates will provide good security, so there's no need to even bother looking at the slow ones.