Grøstl
Encyclopedia
Grøstl is a cryptographic hash function
submitted to the NIST hash function competition
by Praveen Gauravaram, Lars Knudsen
, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. Grøstl was chosen as one of the five finalists of the competition. It uses the same S-box as AES
in a custom construction. The authors claim speeds of up to 21.4 cycles per byte
on an Intel Core 2 Duo
.
According to the submission document, the name "Grøstl" is a multilingual play-on-words, referring to an Austrian dish that is very similar to hash (food)
.
Like other hash function in the MD5/SHA family, Grøstl divides the input into blocks and iteratively computes hi = f(hi−1, mi). However, Grøstl maintains a hash state at least twice the size of the final output (512 or 1024 bits), which is only truncated at the end of hash computation.
The compression function f is based on a pair of 256- or 512-bit permutation functions P and Q, and is defined as:
The permutation functions P and Q are heavily based on the Rijndael (AES) block cipher, but operate on 8×8 or 8×16 arrays of bytes, rather than 4×4. Like AES, each round consists of four operations:
Unlike Rijndael, all rounds are identical and there is no final AddRoundKey operation. 10 rounds are recommended for the 512-bit permutation, and 14 rounds for the 1024-bit version.
The final double-width hash receives a final output transformation of
and is then truncated to the desired width. This is equivalent to applying a final iteration of the compression function using an all-zero message block m, followed by a (cryptographically insignificant) exclusive-or with the fixed constant Q(0).
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
submitted to the NIST hash function competition
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
by Praveen Gauravaram, Lars Knudsen
Lars Knudsen
Lars Ramkilde Knudsen is a Danish researcher in cryptography, particularly interested in the design and analysis of block ciphers, hash functions and message authentication codes .-Academic:...
, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. Grøstl was chosen as one of the five finalists of the competition. It uses the same S-box as AES
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
in a custom construction. The authors claim speeds of up to 21.4 cycles per byte
Cycles per byte
Cycles per byte is a unit of measurement which indicates the number of clock cycles a microprocessor will perform per byte of data processed in an algorithm. It is commonly used as a partial indicator of real-world performance in cryptographic functions....
on an Intel Core 2 Duo
Intel Core 2
Core 2 is a brand encompassing a range of Intel's consumer 64-bit x86-64 single-, dual-, and quad-core microprocessors based on the Core microarchitecture. The single- and dual-core models are single-die, whereas the quad-core models comprise two dies, each containing two cores, packaged in a...
.
According to the submission document, the name "Grøstl" is a multilingual play-on-words, referring to an Austrian dish that is very similar to hash (food)
Hash (food)
Hash is a dish consisting of meat, potatoes, and spices, that are mashed together into a smooth, creamy consistency, and then cooked either alone or with other ingredients such as onions....
.
Like other hash function in the MD5/SHA family, Grøstl divides the input into blocks and iteratively computes hi = f(hi−1, mi). However, Grøstl maintains a hash state at least twice the size of the final output (512 or 1024 bits), which is only truncated at the end of hash computation.
The compression function f is based on a pair of 256- or 512-bit permutation functions P and Q, and is defined as:
- f(h, m) = P(h ⊕ m) ⊕ Q(m) ⊕ h
The permutation functions P and Q are heavily based on the Rijndael (AES) block cipher, but operate on 8×8 or 8×16 arrays of bytes, rather than 4×4. Like AES, each round consists of four operations:
- AddRoundKey (the Grøstl round keys are fixed, but differ between P and Q)
- SubBytes (this uses the Rijndael S-box, allowing sharing with AES implementations)
- ShiftBytes (expanded compared to AES, this also differs between P and Q, and 512- and 1024-bit versions)
- MixColumns (using an 8×8 matrix rather than Rijndael's 4×4)
Unlike Rijndael, all rounds are identical and there is no final AddRoundKey operation. 10 rounds are recommended for the 512-bit permutation, and 14 rounds for the 1024-bit version.
The final double-width hash receives a final output transformation of
- Ω(h) = h ⊕ P(h)
and is then truncated to the desired width. This is equivalent to applying a final iteration of the compression function using an all-zero message block m, followed by a (cryptographically insignificant) exclusive-or with the fixed constant Q(0).