Cryptology ePrint Archive: Report 2013/359

A heuristic for finding compatible differential paths with application to HAS-160

Aleksandar Kircanski and Riham AlTawy and Amr M. Youssef

Abstract: The question of compatibility of differential paths plays a central role in second order collision attacks on hash functions. In this context, attacks typically proceed by starting from the middle and constructing the middle-steps quartet in which the two paths are enforced on the respec- tive faces of the quartet structure. Finding paths that can fit in such a quartet structure has been a major challenge and the currently known compatible paths extend over a suboptimal number of steps for hash functions such as SHA-2 and HAS-160. In this paper, we investigate a heuristic that searches for compatible differential paths. The application of the heuristic in case of HAS-160 yields a practical second order collision over all of the function steps, which is the first practical result that covers all of the HAS-160 steps. An example of a colliding quartet is provided

Category / Keywords: secret-key cryptography /

Date: received 7 Jun 2013

Contact author: akircanski at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20130610:140945 (All versions of this report)

Short URL: ia.cr/2013/359

Discussion forum: Show discussion | Start new discussion