The rebound attack is a tool in the cryptanalysis of cryptographic hash functions.
The attack was first published in 2009 by Florian Mendel, Christian Rechberger, Martin Schläffer and Søren Thomsen.
It was conceived to attack AES like functions such as Whirlpool and Grøstl, but was later shown to also be applicable to other designs such as Keccak, JH and Skein.
The basic idea of the attack is to observe a certain differential characteristic in a block cipher (or in a part of it), a permutation or another type of primitive.
This compression function consists of a number of rounds composed of S-boxes 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.
The idea is to have the large number of active bytes 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 AES like ciphers this can typically be done row- or column-wise, making the procedure relatively efficient.
Here, 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.
To achieve a collision, it is not enough for the differentials in the outbound phase to be of some specific type; any active bytes 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 bytes at the start and end of the outbound phase should be at the same position.
Furthermore, near-collisions on a higher number of rounds can be achieved by starting and ending the outbound phase with several active bytes that do not cancel.
To find a collision on 4.5 rounds of Whirlpool, a differential characteristic of the type shown in the table below must be found.
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.
Each set of 264 values can be found with a complexity of 28 round transformations due to the precomputation step.
Each starting point found in the inbound phase is propagated forwards and backwards.
To ensure a collision, the values at the start and end of the characteristic have to cancel during the feed-forward operation.
To find a collision, 2120 starting points have to be generated in the inbound phase.