SHA-3 Finalists Announced
jonkatz.wordpress.com
jonkatz.wordpress.com
* 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.
Sorry to reply belatedly, but after reading the HAIFA paper I'm a little confused. When the message is a multiple of the block length, doesn't HAIFA still depend on padding for protecting against length extension attacks? At the bottom of page 4 the paper says, "If this value [the number of bits processed so far] is not a multiple of a block, then the resulting digest does not equal the chaining value that is needed to the expansion of the message. If the message is a multiple of a block, then an additional block is hashed (with the padding) with the same number of bits hashed so far." Later they also mention that they use basically the same padding scheme as in MD: "The padding scheme used in HAIFA is very similar to the one used in the Merkel-Damgaard construction, i.e. the message is padded with 1, as many needed 0s, the length of the message encoded in a fixed number of bits, and the digest size."
My impression from my admittedly cursory reading of the paper is that protection against extension attacks wasn't a motivating factor for designing HAIFA. The major motivation, at least going by the paper's internal evidence, seems to be protecting against a kind of pre-image attack based on finding fixed points of the one-way compression function.