View source for Associate family

The '''Rebound Attack''' is a tool in the [[cryptanalysis]] of [[cryptographic hash function]]s. The attack was first published in 2009 by Florian Mendel, Christian Rechberger, Martin Schläffer and Søren Thomsen. It was conceived to attack [[Advanced Encryption Standard|AES]] like functions such as [[Whirlpool (cryptography)|Whirlpool]] and [[Grøstl]], but was later shown to also be applicable to other designs such as [[Keccak]], [[JH (hash function)|JH]] and [[Skein (hash function)|Skein]].

== The Attack ==
The Rebound Attack is a type of statistical attack on [[Cryptographic hash function|hash functions]], using techniques such as [[Rotational cryptanalysis|rotational]] and [[differential cryptanalysis]] to find collisions and other interesting properties. 

The basic idea of the attack is to observe a certain [[Differential cryptanalysis|differential characteristic]] in a [[block cipher]] (or in a part of it), a [[permutation]] or another type of [[Cryptographic primitive|primitive]]. Finding values fulfilling the characteristic is achieved by splitting the primitive <math>E</math> into three parts such that <math>E = E_{fw} \circ E_{in} \circ  E_{bw}</math>. <math>E_{in}</math> is called the inbound phase and <math>E_{fw}</math> and <math>E_{bw}</math> together are called the outbound phase. The attacker then chooses values that realize part of the differential characteristic in the inbound phase deterministically, and fulfill the remainder of the characteristic in a probabilistic manner.

Thus, the rebound attack consists of 2 phases:
# '''''The inbound (or match-in-the-middle) phase''''', covers the part of the differential characteristic that is difficult to satisfy in a probabilistic way. The goal here is to find many solutions for this part of the characteristic with a low average [[Time complexity|complexity]]. To achieve this, the corresponding system of equations, which describes the characteristic in this phase, should be underdetermined. When searching for a solution, there are therefore many degrees of freedom, giving us many possible solutions. The inbound phase may be repeated several times to obtain a sufficient number of starting points so that the outbound phase is likely to succeed.
# In ''''' the outbound phase ''''' each solution of the inbound phase is propagated outwards in both directions, while checking whether the characteristic also holds in this phase. The probability of the characteristic in the outbound phase should be as high as possible. 

The advantage of using an inbound and two outbound phases is the ability to calculate the difficult parts of the differential characteristic in the inbound phase in an efficient way. Furthermore it ensures a high probability in the outbound phase. The overall probability of finding a differential characteristic thus becomes higher than using standard differential techniques.

== Detailed description of the attack on hash functions with AES-like compression functions ==
Consider a [[Cryptographic hash function|hash function]] which uses an [[Advanced Encryption Standard|AES]]-like substitution-permutation block cipher as its [[One-way compression function|compression function]]. This [[One-way compression function|compression function]] consists of a number of rounds composed of [[S-Box]]es and linear transformations. The general idea of the attack is to construct a differential characteristic that has its most computationally expensive part in the middle. This part will then be covered by the inbound phase, whereas the more easily achieved part of the characteristic is covered in the outbound phase. The system of equations, which describe the characteristic in the inbound, phase should be [[Underdetermined system|underdetermined]], such that many starting points for the outbound phase can be generated. Since the more difficult part of the characteristic is contained in the inbound phase it is possible to use standard differentials here, whereas [[Truncated differential cryptanalysis|truncated differentials]] are used in the outbound phase to achieve higher probabilities. 

The inbound phase will typically have a few number of active state [[byte]]s ([[byte]]s with non-zero differences) at the beginning, which then propagate to a large number of active [[byte]]s in the middle of the round, before returning to a low number of active [[byte]]s at the end of the phase. The idea is to have the large number of active [[byte]]s at the input and output of an [[S-Box]] in the middle of the phase. Characteristics can then be efficiently computed by choosing values for the differences at the start and end of the inbound phase, propagating these towards the middle, and looking for matches in the input and output of the [[S-Box]]. For [[Advanced Encryption Standard|AES]] like ciphers this can typically be done row- or column-wise, making the procedure relatively efficient. Choosing different starting and ending values leads to many different differential characteristics in the inbound phase.

In the outbound phase the goal is to propagate the characteristics found in the inbound phase backwards and forwards, and check whether the desired characteristics are followed. Here, [[Truncated differential cryptanalysis|truncated differentials]] are usually used, as these give higher probabilities, and the specific values of the differences are irrelevant to the goal of finding a [[Collision attack|collision]]. The probability of the characteristic following the desired pattern of the outbound phase depends on the number of active [[byte]]s and how these are arranged in the characteristic. To achieve a [[Collision attack|collision]], it is not enough for the differentials in the outbound phase to be of some specific type; any active [[byte]]s at the start and end of the characteristic must also have a value such that any feed-forward operation is cancelled. Therefore, when designing the characteristic, any number of active [[byte]]s at the start and end of the outbound phase should be at the same position. The probability of these [[byte]]s cancelling adds to the probability of the outbound characteristic. 

Overall, it is necessary to generate sufficiently many characteristics in the inbound phase in order to get an expected number of correct characteristics larger than one in the outbound phase. Furthermore, near-collisions on a higher number of rounds can be achieved by starting and ending the outbound phase with several active [[byte]]s that do not cancel.

== Example Attack on Whirlpool ==
The Rebound Attack can be used against the [[Cryptographic hash function|hash function]] [[Whirlpool (cryptography)|Whirlpool]] to find [[Collision attack|collisions]] on variants where the [[One-way compression function|compression function]] (the [[Advanced Encryption Standard|AES]] like [[block cipher]] W) is reduced to 4.5 or 5.5 rounds. Near-collisions can be found on 6.5 and 7.5 rounds. Below is a description of the 4.5 round attack.

=== Pre-computation ===
{| class="wikitable" style="float: right;" border="1"
|-
! Number of solutions !! Frequency
|-
| 0 || 39655
|-
| 2 || 20018
|-
| 4 || 5043
|-
| 6 || 740
|-
| 8 || 79
|-
| 256 || 1
|}

To make the rebound attack effective, a look-up table for [[S-Box]] differences is computed before the attack. Let <math>S:\{0,1\}^8\to\{0,1\}^8</math> represent the [[S-Box]]. Then for each pair <math>(a,b) \in \{0,1\}^8</math>  we find the solutions <math> x </math> (if there are any) to the equation

<math>S(x) \oplus S(x\oplus a) = b </math>,

where <math>a</math> represents the input difference and <math> b </math> represents the output difference of the [[S-Box]]. This 256 by 256 table (called the difference distribution table - DDT) makes it possible to find values that follow the characteristic for any specific input/output pairs that go through the [[S-Box]]. The table on the right show the possible number of solutions to the equation and how often they occur. The first row describes impossible differentials, whereas the last row describes the zero-differential.

=== Performing the attack ===
To find a [[Collision attack|collision]] on 4.5 rounds of [[Whirlpool (cryptography)|Whirlpool]], a differential characteristic of the type shown in the table below must be found. This characteristic has a minimum of active bytes (bytes with non-zero differences), marked in red. The characteristic can be described by the number of active bytes in each round, e.g. 1 → 8 → 64 → 8 → 1 → 1. 

{| class="wikitable"
|+ align="bottom" style="caption-side: bottom" | ''Truncated differential characteristic on 4.5 rounds Whirlpool hash function.''
|-
| <math>E_{bw}</math>||  [[File:TruncatedDifferentialCharacteristicWhirlpoolBW.png]]
|-
| <math>E_{in}</math>|| [[File:TruncatedDifferentialCharacteristicWhirlpoolIn.png]]
|-
| <math>E_{fw}</math>|| [[File:TruncatedDifferentialCharacteristicWhirlpoolFw.png]]
|}

==== The Inbound Phase ====
The goal of the inbound phase is to find differences that fulfill the part of the characteristic described by the sequence of active bytes 8 → 64 → 8. This can be done in the following three steps:

# Choose arbitrary non-zero difference for the 8 active bytes at the output of the [[Whirlpool_(cryptography)#Internal_Structure|MixRows]] operation in round 3. These differences are then propagated backwards to the output of the [[Whirlpool_(cryptography)#Internal_Structure|SubBytes]] operation in round 3. Due to the properties of the [[Whirlpool_(cryptography)#Internal_Structure|MixRows]] operation, a fully active state is obtained. Note that this can be done for each row independently.
# Choose a difference for each active byte in the input of [[Whirlpool_(cryptography)#Internal_Structure|MixRows]] operation in round 2, and propagate these differences forward to the input of the [[Whirlpool_(cryptography)#Internal_Structure|SubBytes]] operation in round 3. Do this for all 255 non-zero differences of each byte. Again, this can be done independently for each row. 
# In the '''''match-in-the-middle step''''', we use the DDT table to find matching input/output differences (as found in step 1 and 2) to the [[Whirlpool_(cryptography)#Internal_Structure|SubBytes]] operation in round 3. Each row can be checked independently, and the expected number of solutions is 2 per [[S-Box]]. In total, the expected number of values that follow the differential characteristic is 2<sup>64</sup>. 

These steps can be repeated with 2<sup>64</sup> different starting values in step 1, resulting in a total of 2<sup>128</sup> actual values that follow the differential characteristic in the inbound phase. Each set of 2<sup>64</sup> values can be found with a [[Time complexity|complexity]] of 2<sup>8</sup> round transformations due to the precomputation step.

==== The Outbound Phase ====
The outbound phase completes the differential characteristic in a probabilistic way. The outbound phase uses [[Truncated differential cryptanalysis|truncated differentials]], as opposed to the inbound phase. Each starting point found in the inbound phase is propagated forwards and backwards. In order to follow the desired characteristic, 8 active bytes must propagate to a single active byte in both directions. One such 8 to 1 transition happens with a probability of 2<sup>−56</sup>,<ref>Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 18</ref> so fulfilling the characteristic has a probability of 2<sup>−112</sup>. To ensure a [[Collision attack|collision]], the values at the start and end of the characteristic have to cancel during the feed-forward operation. This happens with a probability of approximately 2<sup>−8</sup>, and the overall probability of the outbound phase is therefore 2<sup>−120</sup>. 

To find a [[Collision attack|collision]], 2<sup>120</sup> starting points have to be generated in the inbound phase. Since this can be done with an average [[Time complexity|complexity]] of 1 per starting point,<ref>Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 22</ref> the overall [[Time complexity|complexity]] of the attack is 2<sup>120</sup>.

=== Extending the attack ===
The basic 4.5 round attack can be extended to a 5.5 round attack by using two fully active states in the inbound phase. This increases the [[Time complexity|complexity]] to about 2<sup>184</sup>.<ref>Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 25</ref> 

Extending the outbound phase so that it begins and ends with 8 active bytes leads to a near-collision in 52 bytes on [[Whirlpool (cryptography)|Whirlpool]] reduced to 7.5 rounds with a [[Time complexity|complexity]] of 2<sup>192</sup>.<ref>Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 25</ref> 

By assuming that the attacker has control over the chaining value, and therefore the input to the key-schedule of [[Whirlpool (cryptography)|Whirlpool]], the attack can be further extended to 9.5 rounds in a semi-free-start near-collision on 52 bytes with a [[Time complexity|complexity]] of 2<sup>128</sup>.<ref>Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 31</ref>

== Notes ==
{{Reflist}}

== References ==
* [http://www2.mat.dtu.dk/people/S.Thomsen/MendelRST-fse09.pdf The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl] by Florian Mendel, Christian Rechberger, Martin Schlaffer, and Soren S. Thomsen (Fast Software Encryption 2009: 260-276)
* [http://www.cosic.esat.kuleuven.be/publications/article-1362.pdf The Rebound Attack on Reduced Grøstl Hash Function] by Florian Mendel, Christian Rechberger, Martin Schlaffer, and Soren S. Thomsen (The Cryptographer's Track at RSA Conference 2010: 350-365)
* [http://eprint.iacr.org/2011/420 Unaligned Rebound Attack - Application to Keccak] by Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (IACR Cryptology ePrint Archive Year 2011 / 420 )
* [http://eprint.iacr.org/2010/607.pdf How to Improve Rebound Attacks] by María Naya-Plasencia FHNW, Windisch, Switzerland (CRYPTO'11 Proceedings of the 31st annual conference on Advances in cryptology Pages 188-205)
* [http://eprint.iacr.org/2010/198.pdf The Rebound Attack and Subspace Distinguishers: Application to Whirlpool] by Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen, and Martin Schläffer( IACR Cryptology ePrint Archive, Year. 2010 /198).
* [https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=58178 Cryptanalysis of AES based hash functions] A PHd theses by Martin Schläffer

[[Category:Cryptographic attacks]]