Grøstl Implementation Guide

v1

The hash function Grøstl was designed in 2008 as a candidate for the SHA-3 competition [18], organized by the National Institute of Standards and Technology (NIST). In 2010, Grøstl was selected as one of five finalists in the competition. Grøstl borrows components from the AES block cipher, which became a United States federal government standard in 2001 [17]. The AES is known for its good performance on a wide variety of platforms, which is due to a large amount of flexibility in the choice of implementation methods. Recently, Intel introduced an instruction set extension for computing AES rounds [9], which makes encryption using the AES on CPUs implementing this instruction set very efficient. Although several underlying components in Grøstl differ from the ones used in the AES, Grøstl still enjoys many of the same implementation benefits as the AES. Even the AES instruction set extension can be used to significantly speed up Grøstl. In this paper, we describe various software implementation techniques for Grøstl suitable for platforms ranging from 8-bit microcontrollers to processors with SIMD and AES instruction set extensions. All these implementations can be downloaded from http://www.groestl.info/.

Description of Grøstl

The Grøstl hash function iterates an underlying compression function in a variant of the Merkle-Damg˚ard construction [7,15], where the size of the state (or chaining value) passed on from one iteration to the next is at least twice as large as the final hash value. The final hash value is computed from the last chaining value using an output transformation. Hence, Grøstl is known as a wide pipe design.

The compression function and the output transformation are based on permutations using round transformations similar to those of the AES [16]. For the final round of the competition, Grøstl was tweaked in order to increase its security margin. The initial submission is called Grøstl-0. In the following, we describe the components of the (tweaked) Grøstl hash function in more detail. 

2.1 The Hash Function
Grøstl comes in several variants with different output sizes. We denote by n the number of bits in the output, and the variant returning n bits is denoted Grøstl-n. Here, we focus on Grøstl-256 and Grøstl512. Variants returning less than 256 bits differ from Grøstl-256 only in the initial value and in the final truncation to produce the hash value. Similarly, variants returning more than 256 bits differ from Grøstl-512 in the same two respects. The input message M is padded and split into blocks M1,M2,...,Mt of ` bits with ` = 512 for Grøstl256, and ` = 1024 for Grøstl-512. The initial value IV , the intermediate hash values Hi, and the permutations P and Q are of size ` bits as well. (The exact definition of the IV can be found in [8]). The message blocks are processed via the compression function f(Hi−1,Mi), which accepts two `-bit inputs and outputs an `-bit value. After all t message blocks have been processed, an output transformation Ω(Ht) is applied which outputs the final n-bit hash value h:
H0 = IV Hi = f(Hi−1,Mi) for 1 ≤ i ≤ t h = Ω(Ht).
For all variants, ` is at least twice as large as n.

2.2 The Compression Function
The compression function f is based on two `-bit permutations P and Q. The compression function is defined as follows: f(Hi−1,Mi) = P(Hi−1 ⊕Mi)⊕Q(Mi)⊕Hi−1. The construction of the compression function of Grøstl is shown in Figure 1.

2.3 The Output Transformation
After the last call to the compression function, an output transformation Ω is applied to Ht to give the final hash value of size n: Ω(Ht) = truncn(P(Ht)⊕Ht), where truncn(x) discards all but the least significant n bits of x. The output transformation is also shown in Figure 2.