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 2^120 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 2^120 and memory requirements of about 2^64.
Original language | English |
---|---|
Title of host publication | Fast Software Encryption : 16th International Workshop, FSE 2009 Leuven, Belgium, February 22-25, 2009 Revised Selected Papers |
Editors | Orr Dunkelman |
Publisher | Springer |
Publication date | 2009 |
Pages | 260-276 |
DOIs | |
Publication status | Published - 2009 |
Event | Fast Software Encryption 2009 - Leuven, Belgium Duration: 22 Feb 2009 → 25 Feb 2009 Conference number: 16 http://www.informatik.uni-trier.de/~ley/db/conf/fse/fse2009.html |
Conference
Conference | Fast Software Encryption 2009 |
---|---|
Number | 16 |
Country/Territory | Belgium |
City | Leuven |
Period | 22/02/2009 → 25/02/2009 |
Internet address |
Series | Lecture Notes in Computer Science |
---|---|
Number | 5665 |