Paper 2010/607

How to Improve Rebound Attacks

María Naya-Plasencia

Abstract

Rebound attacks are a state-of-the-art analysis method for hash functions. These cryptanalysis methods are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this paper we study rebound attacks in detail and find for a large number of cases that the complexities of existing attacks can be improved. This is done by identifying problems that optimally adapt to the cryptanalytic situation, and by using better algorithms to find solutions for the differential path. Our improvements affect one particular operation that appears in most rebound attacks and which is often the bottleneck of the attacks. This operation, which varies depending on the attack, can be roughly described as {\em merging} large lists. As a result, we introduce new general purpose algorithms for enabling further rebound analysis to be as performant as possible. We illustrate our new algorithms on real hash functions. More precisely, we demonstrate how to reduce the complexities of the best known analysis on four SHA-3 candidates: JH, Gr\o{}stl, ECHO and {\sc Lane} and on the best known rebound analysis on the SHA-3 candidate Luffa.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. This is the extended version of the article published at CRYPTO 2011
Keywords
hash functionsSHA-3 competitionrebound attacksalgorithms
Contact author(s)
maria naya plasencia @ gmail com
History
2011-05-26: last of 2 revisions
2010-11-27: received
See all versions
Short URL
https://ia.cr/2010/607
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/607,
      author = {María Naya-Plasencia},
      title = {How to Improve Rebound Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/607},
      year = {2010},
      url = {https://eprint.iacr.org/2010/607}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.