Paper 2008/270

New Collision attacks Against Up To 24-step SHA-2

Somitra Kumar Sanadhya and Palash Sarkar

Abstract

In this work, we provide new and improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The success probability of our 22-step attack is 1 for both SHA-256 and SHA-512. The computational efforts for the 23-step and 24-step SHA-256 attacks are respectively $2^{11.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. The corresponding values for the 23 and 24-step SHA-512 attack are respectively $2^{16.5}$ and $2^{32.5}$ calls. Using a look-up table having $2^{32}$ (resp. $2^{64}$) entries the computational effort for finding 24-step SHA-256 (resp. SHA-512) collisions can be reduced to $2^{15.5}$ (resp. $2^{22.5}$) calls. We exhibit colliding message pairs for 22, 23 and 24-step SHA-256 and SHA-512. This is the \emph{first} time that a colliding message pair for 24-step SHA-512 is provided. The previous work on 23 and 24-step SHA-2 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikolić and Biryukov NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ for 23 and 24-step SHA-256 respectively and $2^{43.9}$ and $2^{53}$ for 23 and 24-step SHA-512. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-2 family. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. This is the extended version of a paper which will appear in Indocrypt 2008.
Keywords
CryptanalysisSHA-2 hash familyreduced round attacks.
Contact author(s)
somitra_r @ isical ac in
History
2008-09-22: revised
2008-06-18: received
See all versions
Short URL
https://ia.cr/2008/270
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/270,
      author = {Somitra Kumar Sanadhya and Palash Sarkar},
      title = {New Collision attacks Against Up To 24-step {SHA}-2},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/270},
      year = {2008},
      url = {https://eprint.iacr.org/2008/270}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.