Rebound attack
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The rebound attack is a tool in the cryptanalysis of cryptographic hash functions. The attack was first published in 20091 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 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. Finding values fulfilling the characteristic is achieved by splitting the primitive E into three parts such that E = E_\text{fw} \circ E_\text{in} \circ E_\text{bw} . E_\text{in} is called the inbound phase and E_\text{fw} and E_\text{bw} 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 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 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. S(x) \oplus S(x \oplus a) = b , where a represents the input difference and b 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 shows 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. Cryptanalysis of AES based hash functions A PHd theses by Martin Schläffer
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373143503 under CC BY-SA 4.0; modifications have been made.