The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl - PDF

Description
The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl Florian Mendel 1 and Christian Rechberger 1 and Martin Schläffer 1 and Søren S. Thomsen 2 1 Institute for Applied Information Processing

Please download to get full document.

View again

of 17
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Brochures

Publish on:

Views: 24 | Pages: 17

Extension: PDF | Download: 0

Share
Transcript
The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl Florian Mendel 1 and Christian Rechberger 1 and Martin Schläffer 1 and Søren S. Thomsen 2 1 Institute for Applied Information Processing and Communications (IAIK) Graz University of Technology, Inffeldgasse 16a, A-8010 Graz, Austria 2 Department of Mathematics, Technical University of Denmark Matematiktorvet 303S, DK-2800 Kgs. Lyngby, Denmark Abstract. In this work, we propose the rebound attack, a new tool for the cryptanalysis of hash functions. The idea of the rebound attack is to use the available degrees of freedom in a collision attack to efficiently bypass the low probability parts of a differential trail. The rebound attack consists of an inbound phase with a match-in-the-middle part to exploit the available degrees of freedom, and a subsequent probabilistic outbound phase. Especially on AES based hash functions, the rebound attack leads to new attacks for a surprisingly high number of rounds. We use the rebound attack to construct collisions for 4.5 rounds of the 512-bit hash function Whirlpool with a complexity of compression function evaluations and negligible memory requirements. The attack can be extended to a near-collision on 7.5 rounds of the compression function of Whirlpool and 8.5 rounds of the similar hash function Maelstrom. Additionally, we apply the rebound attack to the SHA-3 submission Grøstl, which leads to an attack on 6 rounds of the Grøstl-256 compression function with a complexity of and memory requirements of about Keywords: Whirlpool, Grøstl, Maelstrom, hash function, collision attack, near-collision 1 Introduction In the last few years the cryptanalysis of hash functions has become an important topic within the cryptographic community. Especially the attacks and tools for the MD4 family of hash functions (e.g. MD5, SHA-1) have reduced the security provided by these commonly used hash functions [2, 3, 4, 24, 26, 27]. Most of the existing cryptanalytic work has been published for this particular line of hash function design. In the NIST SHA-3 competition [19], whose aim is to find an alternative hash function to SHA-2, many new hash function designs have been proposed. This is the most recent and most prominent case showing that it is very important to have tools available to analyze other design variants as well. Our work contributes to this toolbox. 1.1 Preview of Results Our main result is the introduction of a technique for hash function cryptanalysis, which we call the rebound attack. We apply it to both block cipher based and permutation based constructions. In the rebound attack, we consider the internal cipher of a hash or compression function as three sub-ciphers. Let E be a block cipher, then E = E fw E in E bw. Alternatively, for a permutation based construction, we decompose a permutation P into three sub-permutations P = P fw P in P bw. E bw E in E fw outbound inbound outbound Fig. 1. A schematic view of the rebound attack. The attack consists of an inbound and two outbound phases. The rebound attack can be described by two phases (see Fig. 1): Inbound phase: Is a meet-in-the-middle phase in E in (or P in ), which is aided by the degrees of freedom that are available to a hash function cryptanalyst. We term the combination of meet-in-the-middle technique and exploitation of degrees of freedom leading to very efficient matches match-inthe-middle approach. Outbound phase: In this second phase, we use truncated differentials in both forward- and backward direction through E fw and E bw (or P fw and P bw ) to obtain desired collisions or near-collisions. If the truncated differentials have a low probability in E fw and E bw, we can repeat the inbound phase to obtained more starting points for the outbound phase. We apply the rebound attack on several concrete hash functions where the application on Whirlpool is probably the most relevant. Whirlpool is the only hash function standardized by ISO/IEC :2003 (since 2000) that does not follow the MD4 design strategy. Furthermore, Whirlpool has been evaluated and approved by NESSIE [20]. Whirlpool is commonly considered to be a conservative block-cipher based design with an extremely conservative key schedule. The employed wide-trail design strategy [5] makes the application of differential and linear attacks seemingly impossible. No cryptanalytic results on the hash function Whirlpool have been published since its proposal 8 years ago. Offsprings of Whirlpool are Maelstrom and to some extent several SHA-3 candidates, including Grøstl. The results of the attack on these hash functions are summarized in Table 1. For the types of attacks, we adopt the notation of [15]. 2 Table 1. Summary of results of the attacks on reduced hash functions Whirlpool, Grøstl-256 and Maelstrom. The full versions have 10 rounds each. All attacks, except the attacks on Grøstl-256, have negligible memory requirements. hash computational memory rounds function complexity requirements Whirlpool type collision semi-free-start collision semi-free-start near-collision 3 Grøstl semi-free-start collision 4 section Maelstrom free-start collision A free-start near-collision A 1.2 Related Work The rebound attack can be seen to have ancestors from various lines of research, often related to block ciphers: Firstly, differential cryptanalysis of block cipher based hash functions. Rijmen and Preneel [23] describe collision attacks on 15 out of 16 rounds on hash functions using DES. For the case of Whirlpool, there is an observation on the internal block cipher W by Knudsen [13]. Khovratovich et al. [11] studied collision search for AES-based hash functions. Secondly, inside-out techniques. As an application of second order differential attacks, inside-out techniques in block-cipher cryptanalysis were pioneered by Wagner in the Boomerang attack [25]. Thirdly, truncated differentials. In the applications of the rebound technique, we used truncated differentials in the outbound parts. Knudsen [12] proposed truncated differentials as a tool in block cipher cryptanalysis, which recently have been applied to the hash function proposal Grindahl [14] by Peyrin [21]. 1.3 Outline of the Paper In the following section, we start with a description of the attacked hash functions. For the sake of presentation and concreteness, we immediately apply the rebound attack to the hash function Whirlpool in Sect. 3. In Sect. 4, we apply the rebound attack on Grøstl. The application of the attack to Maelstrom is postponed to App. A. We conclude in Sect Description of the Hash Functions In this section we give a short description of the hash functions to be analyzed in the remainder of this paper. We describe the hash function Whirlpool first, and continue with the description of the hash function Grøstl. 3 2.1 The Whirlpool Hash Function Whirlpool is a cryptographic hash function designed by Barreto and Rijmen in 2000 [1]. It is an iterative hash function that processes 512-bit input message blocks with compression functions and produces a 512-bit hash value. The Whirlpool compression function basically consists of two parts: the key schedule and the state update transformation. The underlying block cipher W operates in the Miyaguchi-Preneel mode [17] as shown in Fig. 2. A detailed description of the hash function is given in [1]. M t H t-1 State Update Key Schedule Block cipher W + H t Fig. 2. A schematic view of the Whirlpool compression function. The block cipher W is used in Miyaguchi-Preneel mode. The 512-bit block cipher W uses a 512-bit key and is similar to the Advanced Encryption Standard (AES) [18]. Both the state update transformation and the key schedule of W update an 8 8 state S of 64 bytes in 10 rounds each. The round transformations are very similar to the AES round transformations and are briefly described here: the non-linear layer SubBytes () applies an S-Box to each byte of the state independently the cyclical permutation ShiftColumns () rotates the bytes of column j downwards by j positions the linear diffusion layer MixRows () multiplies the state by a constant matrix the key addition AddRoundKey () adds the round key and/or the round constants c r () of the key schedule In each round, the state is updated by round transformation r i as follows: r i. 4 In the remainder of this paper, we will use the outline of Fig. 3 for one round. We denote the resulting state of round transformation r i by S i and the intermediate states after SubBytes by S i, after ShiftColums by S i and after MixRows by S i. The initial state prior to the first round is denoted by S 0. K i S i-1 S i ' S i '' S i ''' S i Fig. 3. One round r i of the Whirlpool compression function with 8 8 states S i 1, S i, S i, S i, S i and round key input K i. After the last round of the state update transformation, the initial value or previous chaining value H t 1 = S 0, the message block M t, and the output value of the last round S 10 are XORed, resulting in the final output of the Whirlpool compression function, H t = H t 1 M t S The Grøstl Hash Function Grøstl was proposed by Gauravaram et al. as a candidate for the SHA-3 competition [9], initiated by the National Institute of Standards and Technology (NIST). Grøstl is an iterated hash function with a compression function built from two distinct permutations (see Fig. 4). Grøstl is a wide-pipe design with proofs for the collision and preimage resistance of the compression function [8]. H t-1 M t + P Q + H t Fig. 4. The compression function of Grøstl. P and Q are 2n-bit permutations for an n-bit hash value. 5 The two permutations P and Q are constructed using the wide trail design strategy and borrow components from the AES. The design of the two permutations is very similar to the block cipher W used in Whirlpool instantiated with a fixed key input. Both permutations update an 8 8 state of 64 bytes in 10 rounds each. The round transformations are very similar to the AES round transformations and are briefly described here: AddRoundConstant () adds different one-byte round constants to the 8 8 states of P and Q the non-linear layer SubBytes () applies the AES S-Box to each byte of the state independently the cyclical permutation ShiftBytes () rotates the bytes of row j left by j positions the linear diffusion layer MixBytes () multiplies the state by a constant matrix In each round, the state is updated by round transformation r i as follows: r i 3 Rebound Attack on Whirlpool In this section, we present details of the rebound attacks applied to the hash function Whirlpool. First, we will give an overview of the attack strategy which is the basis for the attacks on 4.5, 5.5 and 7.5 rounds. The main idea of the attacks is to use a 4-round differential trail [6], which has the following sequence of active S-boxes: Note that the differential probability in each round is proportional to the number of active S-boxes. Using the Rebound Attack we can cover the most expensive middle part using an efficient matchin-the-middle approach (inbound phase). In the outbound phase, the trail is extended and the two ends of the trail are linked using the feed-forward of the hash function. 3.1 Attack Overview The core of the attack is a 4 round trail of the form This trail has the minimum number of active S-boxes and has the best differential probability according to the wide trail design strategy. In the rebound attack, we first split the block cipher W into three sub-ciphers W = E fw E in E bw, such that most expensive part of the differential trail is covered by the efficient inbound phase E in. Then, the outbound phase (E fw, E bw ) has a relatively low probability and can be fulfilled in a probabilistic way: E bw = E in = E fw = The two phases of the rebound attack consists of basically four steps: 6 Inbound phase Step 1: start with 8-byte truncated differences at the MixRows layer of round r 2 and, and propagate forward and backward to the S-box layer of round. Step 2: connect the input and output of the S-boxes of round to form the three middle states of the trail. Outbound phase Step 3: extend the trail both forward and backward to give the trail through MixRows in a probabilistic way. Step 4: link the beginning and the end of the trail using the feed-forward of the hash function. If the differences in the first and last step are identical, they cancel each other through the feed-forward. The result is a collision of the round-reduced compression function of Whirlpool. See Fig. 5 for an overview of the attack. E bw E in E fw K 1 K 2 K 3,K 4 M t S 0 S 1 S 2 '' S 2 S 3 ' S 3 ''' S 4 r 1 r 2 r 2,r 4 + H t Step 4 Step 3 Step 3 Step 1 Step 2 Step 1 Step 3 Step 4 Fig. 5. A schematic view of the attack on 4 rounds of Whirlpool with round key inputs and feed-forward. Black state bytes are active. 3.2 Collision Attack for 4.5 Rounds The collision attack on 4.5 rounds of Whirlpool is the starting point for all subsequent attacks. If the differences in the message words are the same as in the output of the state update transformation, the differences cancel each other through the feed-forward. In other words, we will construct a fixed-point (in terms of differences) for the block cipher in the state update. The outline of the attack is shown in Fig. 5 and the sequence of truncated differences has the form: 1 r1 8 r2 64 r3 8 r4 1 r4.5 1 In the following, we analyze the 4 steps of the attack in detail. Precomputation. In the match-in-the-middle part (Step 2) we need to find a differential match for the SubBytes layer. In a precomputation step, we compute a lookup table for each S-box differential (input/output XOR difference table). Note that only about 1/2 of all S-box differentials exist. For each 7 possible S-box differential, there are at least two (different) values such that the differential holds. A detailed description of the distribution of S-box differentials is given in App. B. Step 1. We start the attack by choosing a random difference with 8 active bytes of state S 2 prior to the MixRows layer of round r 2. Note that all active bytes have to be in the diagonal of state S 2 (see Fig. 5). Then, the differences propagate forward to a full active state at the input of the next SubBytes layer (state S 2 ) with a probability of 1. Next, we start with another difference and 8 active bytes in state S 3 after the MixRows transformation of round and propagate backwards. Again, the diagonal shape ensures that we get a full active state at the output of SubBytes of round. Step 2. In Step 2, the match-in-the-middle step, we look for a matching input/output difference of the SubBytes layer of round using the precomputed S-box differential table. Since we can find a match with a probability of 1/2 for each byte, we can find a differential for the whole active SubBytes layer with a probability of about Hence, after repeating Step 1 of the attack about 2 64 times, we expect to find a SubBytes differential for the whole state. Since we get at least two state values for each S-box match, we get about 2 64 starting points for the outbound phase. Note that these 2 64 starting points can be constructed with a total complexity of about In other words, the average computational cost of each match-in-the-middle step is essentially the respective computation of the round transformations. Step 3. In the outbound phase, we further extend the differential path backward and forward. By propagating the matching differences and state values through the next SubBytes layer, we get a truncated differential in 8 active bytes for each direction. Next, the truncated differentials need to follow a specific active byte pattern. In the case of the 4 round Whirlpool attack, the truncated differentials need to propagate from 8 to one active byte through the MixRows transformation, both in the backward and forward direction. The propagation of truncated differentials through the MixRows transformation is modelled in a probabilistic way. The transition from 8 active bytes to one active byte through the MixRows transformation has a probability of about 2 56 (see App. C). Note that we require a specific position of the single active byte to find a match in the feed-forward (Step 4). Since we need to fulfill one 8 1 transitions in the backward and forward direction, the probability of the outbound phase is = In other words, we have to repeat the inbound phase about times to generate starting points for the outbound phase of the attack. Step 4. To construct a collision at the output of this 4 round compression function, the exact value of the input and output difference has to match. Since 8 only one byte is active, this can be fulfilled with a probability of 2 8. Hence, the complexity to find a collision for 4 rounds of Whirlpool is = Note that we can add half of a round (,) at the end for free, since we are only interested in the number of active bytes. Remember that we can construct up to starting points in the inbound phase of the attack, hence we have enough degrees of freedom for the attack. Note that the values of the key schedule are not influenced. Hence, the attack works with the standard IV and we can construct collisions for 4.5 rounds of the hash function of Whirlpool. 3.3 Semi-Free-Start Collision Attack for 5.5 Rounds We can extend the collision attack on 4.5 rounds to a semi-free-start collision attack on 5.5 rounds of Whirlpool. The idea is to add another full active state in the middle of the trail. We use the additional degrees of freedom of the key schedule to fulfill the difference propagation through two full active S-box transformations. Note that the outbound part of the attack stays the same and the new sequence of active S-boxes is: 1 r1 8 r2 64 r3 64 r4 8 r5 1 r5.5 1 K 2 K 3 S 2 '' S 2 ''' S 2 S 3 ' S 3 S 4 ' S 4 ''' r 2 r 2 r 4 r 4 Step 1 Step 1 Step 2b Step 2a Step 2a Step 1 Fig. 6. In the attack on 5.5 rounds we first choose random values of the state S 4 to propagate backwards (Step 2a) and then, use the degrees of freedom from the key schedule to solve the difference propagation of the S-box in round (Step 2b). Step 1. Figure 6 shows the inbound part of the attack in detail. Again, we can choose from up to 2 64 initial differences with 8 active bytes at state S 2 and S 4 each, and linearly propagate forward to S 2 and backward to S 4 until we hit the first S-box layer. Then, we need to find a matching SubBytes differential of two consecutive S-box layers in the match-in-the-middle phase. Step 2. To pass the S-box of round r 4 in the backward direction, we choose one of possible values for state S 4. This also determines the input values and differences of the SubBytes layer (state S 3 ). Then, we propagate the difference further back to state S 3, which is the output of the S-box in round. The 512 9 degrees of freedom of the key schedule input K 3 between the two S-boxes allow us to still assign arbitrary values to the state S 3. Hence, the correct difference propagation of the S-box in round can be fulfilled by using these additional degrees of freedom to choose the state S 3 as well. The complexity of the attack does not change and is determined by the trials of the outbound phase. The outbound phase (Step 3 and Step 4) of the 5.5 round attack is equivalent to the 4.5 round case. However, we cannot choose the round keys, and hence the chaining values, anymore since they are determined by the difference propagation of the S-box of round. Therefore, this 5.5 round attack is only a semi-free-start collision attack on the hash function of Whirlpool. 3.4 Semi-Free-Start Near-Collision Attack for 7.5 Rounds The collision attack on 5.5 rounds can be further extended by adding one round at the beginning and one round and at the end of the trail (see Fig. 7). The result is a semi-free-start near-collision attack on 7.5 rounds of the hash function Whirlpool with the following number of active S-boxes: 8 r1 1 r2 8
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x