Paper 2008/271

A Combinatorial Analysis of Recent Attacks on Step Reduced SHA-2 Family

Somitra Kumar Sanadhya and Palash Sarkar

Abstract

We perform a combinatorial analysis of SHA-2 compression function. This analysis explains in a unified way the recent attacks against reduced round SHA-2. We start with a general class of local collisions and show that the previously used local collision by Nikolić and Biryukov (NB) and Sanadhya and Sarkar (SS) are special cases. The study also clarifies several advantages of the SS local collision over the NB local collision. Deterministic constructions of up to 22-round SHA-2 collisions are described using the SS local collision and up to 21-round SHA-2 collisions are described using the NB local collision. For 23 and 24-round SHA-2, we describe a general strategy and then apply the SS local collision to this strategy. The resulting attacks are faster than those proposed by Indesteege et al using the NB local collision. We provide colliding message pairs for 22, 23 and 24-round SHA-2. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family. \footnote{This work builds upon and subsumes previous work done by us. Whereas the previous works focused on obtaining collisions for fixed number of rounds, the current work provides the combinatorial framework for understanding how such collisions arise.}

Note: This is a substantially revised version.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
CryptanalysisSHA-2 hash familyreduced round attacks
Contact author(s)
somitra_r @ isical ac in
History
2008-12-03: last of 3 revisions
2008-06-18: received
See all versions
Short URL
https://ia.cr/2008/271
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/271,
      author = {Somitra Kumar Sanadhya and Palash Sarkar},
      title = {A Combinatorial Analysis of Recent Attacks on Step Reduced SHA-2 Family},
      howpublished = {Cryptology ePrint Archive, Paper 2008/271},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/271}},
      url = {https://eprint.iacr.org/2008/271}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.