When Balinese dancers are performing the Ramayana monkey chant dance, they move their hands and arms percussively.
Secury Hashing Algorithms are a family of cryptographic hash functions published by NIST, a United States laboratory for the promotion of American innovation and industrial competitiveness by means of… you guessed it, establishing standards.
SHA-0 (fka “original SHA”), SHA-1, SHA-2 and SHA-3 are all a part of SHA. All of the algorithms up until SHA-3 (excluding), were designed by the NSA and all of them use the Merkle–Damgård construction method for building collision-resistant hashes (1979). SHA-3 is different, though. Read on.
The Merkle–Damgård construction used in SHA-{0,1,2} builds on one-way compression functions. It takes an initialization vector (IV), each block of the input a multiple of a fixed number (e.g., 512) and an (MD-compliant) padding. Sequentially, it will take the last result with the next block to create another result (by means of some function f). Once the final block (plus necessary padding, if any) is reached, finalisation is performed to output the final hash.
Phase outs of SHA-{0,1} started happening only long after various attacks on these SHA variants came to light, especially flaws related to collision resistance – known M1 and M2, H(M1)=H(M2), or pre-image resistance – given known hash h, hard to find H(M1)=h.
In 2007, NIST announced an open competition for the creation of a better hash function, the natural successor to SHA-{0,1} and competitor to SHA-2 (many versions of it accepted as secure still today). Five years and 64 submissions later, 5 finalists were found:
- BLAKE (Aumasson et al.)
- Grøstl (Knudsen et al.)
- JH (Hongjun Wu)
- Skein (Schneier et al.)
- Keccak (Keccak team, Daemen et al.)
In 2012, it was annouced that the winner was Keccak. Keccak revealed “large security margin after significant cryptanalytic effort” and “much better throughput/area performance in hardware [than competitors]”.
And hence, Keccak became SHA-3.
SHA-3, uses a sponge construction at its core. It is split into two phases: absorbing and squeezing. The absorbing phase runs for the whole padded blocks of input, interleaving applications of the function f. Squeezing happens afterwards where bits of the resulting state are again interleaved with applications of the function f to generate an arbitrary number of output blocks.
Circling back to the title, the name “Keccak” is a variant spelling of “Kecak”, the aforementioned type of Balinese dance. The story goes that in Kecak dancers move their hands fast and it looks like they are chopping and mixing something, and this reminded one of the co-authors of the algorithm about an hash function.
The Keccak team is Michaël Peeters, Guido Bertoni, Joan Daemen, Ronny Van Keer, Gilles Van Assche and Seth Hoffert.