SHA-3 originated amidst fears that SHA-2, the current NIST hashing standard, was wounded after the breakthrough Wang attacks on MD4, MD5, and SHA-1. Furthermore, SHA-2, like its predecessors, suffered from the common flaws of the Merkle-Damgård (MD) construction, among which are length-extension attacks, faster-than-theoretical preimages and multicollisions. All SHA-3 finalists fixed these flaws, as a submission requirement.
The winner, Keccak, strays quite drastically from the SHA-2 design. Keccak uses the sponge construction, which relies on a fixed-width permutation \(f\) as the main building block, unlike the more common compression function from the MD designs. The sponge works in two phases: absorption and squeezing. Here's a picture:
 |
| The sponge construction |
During the absorption phase, \(r\) bits from the message are injected into the state, after which the whole state (\(r+c\) bits) is permuted using \(f\). Once we're done with all the message bits (plus padding), we simply output the first l bits of the state as the final hash, applying the permutation repeatedly if necessary.
The strength of the sponge construction comes from the indifferentiability of f from a random permutation. Keccak is not perfect in this regard: an observation by Duan and Lai distinguishes the full Keccak permutation from random in expected \(2^{1579}\) time, down from \(2^{1599}\) — not a real attack.
Performance was taken seriously in this competition. Keccak is a curious selection in that it is rather unbalanced towards hardware speed, while it is somewhat lacking in the software speed department. eBASH shows that on high-end processors, Keccak is slower than SHA-2 by up to 2x. Meanwhile, Keccak wipes the floor in hardware speed and die area.
For certain applications, this particular performance profile can give the advantage to an attacker. Consider the scenario of password storage, where the defender switches from PBKDF2-HMAC-SHA-2 to PBKDF2-HMAC-SHA-3. This reduces the cost of an attacker while increasing the cost of the defender, for the same number of PBKDF2 iterations. That said, this is a rather fringe case, and the defender would be better served by switching to a memory-hard key-derivation function if possible.
SHA-3 comes with a completely different design which not only provides diversity, but also fixes some of the standing issues with the aging MD construction. It is a very elegant design, very efficient in hardware, but that sadly suffers from low software performance. Perhaps chip makers will give us a hand there, or perhaps better ways to compute Keccak will arise in the meantime.
