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østl, ECHO and {\sc Lane} and on the best known rebound analysis on the SHA-3 candidate Luffa.
Category / Keywords: hash functions, SHA-3 competition, rebound attacks, algorithms Publication Info: This is the extended version of the article published at CRYPTO 2011 Date: received 26 Nov 2010, last revised 26 May 2011 Contact author: maria naya plasencia at gmail com Available format(s): PDF | BibTeX Citation Version: 20110526:185325 (All versions of this report) Short URL: ia.cr/2010/607 Discussion forum: Show discussion | Start new discussion