SHA-3 Finalists Announced

  • Well, CubeHash didn't pass, keeping Daniel J. Bernstein (mostly) out of the running for SHA-3. Oh well. Meanwhile:

    * BLAKE combines DJB's ChaCha stream cipher core with Eli Biham's HAIFA framework; HAIFA, like Merkle Damgard (MD), isn't a hash function but rather a scheme for turning things like the core of another cipher into a hash function; HAIFA is a response to MD that (among other things) eliminates length-extension attacks. I hope BLAKE wins.

    * Grøstl (meaning "hash", in the "corned beef" sense) is a hash that borrows heavily from the internal components of AES, and includes among its contributors one of Vincent Rijmen's (of AES nee' Rijndael fame) gra students.

    * JH is a Singaporean design similar to Grøstl in the sense of borrowing AES machinery, and is optimized for hardware.

    * Keccak is a hash built on "sponge model", which (like HAIFA) is an alternative to the classical MD construction, and was co-designed by Joan Daemen (also of Rijndael fame). Keccak looks like the most interesting design in the contest.

    * Skein is Furgusen and Schneier's design, based on their Threefish block cipher function (which they designed for the hash). Threefish is said to be similar to DJB's Salsa20 stream cipher; the Skein hash combines it with "UBI", a custom version of the Matyas-Meyer-Oseas compression function (which is extremely simple; just Wikipedia it). Skein appears to have more real cryptanalysis results against it than the others, and maybe a little less theory and a little more practicality.

    Colin will I'm sure chime in with more math details, which go right over my head.

    SHA256 is widely considered sound as it stands today. The big problem with it is that it's bulky and slow. So the first thing you'd hope to get from SHA3 is speed.

    SHA256 is a classical Merkle-Damgard design. The MD construction is widely considered outmoded. So the other thing you expect to get from SHA3 is a cipher that uses a different fundamental construction for taking a block function and turning it into a hash.

    A nice side effect of getting rid of MD is that you no longer have length-extension attacks. It's shocking when this sinks in, but the output of (say) SHA1 is simply the internal state of the SHA1 hash at the point where the input starts. The SHA1 design starts with a series of 32 bit registers and grinds plaintext through them; a SHA1 hash is simply the resulting 32 bit registers, catted together. What this means is that attacks can feed more plaintext to through SHA1, without knowing what the original plaintext was, simply by using the output of a SHA1 hash as the initial values of the SHA1 registers. Bad! This, by the way, is the reason you use HMAC-SHA1 and never SHA1 to authenticate messages.

    I hope BLAKE wins, but if it doesn't, I hope Keccak wins, because its design seems to be the furthest from what we have today (HAIFA seems like a direct evolution of MD, and Matyas-Meyer-Oseas basically seems like calling CBC-MAC a hash function). But I am not the least bit qualified to hold this opinion! I just break shit.

    Interesting how likely it is that either Vincent Rijmen or Joan Daemen (or both) will have their fingerprints on both AES and SHA3.