Paper 2008/131

Collisions and other Non-Random Properties for Step-Reduced SHA-256

Sebastiaan Indesteege, Florian Mendel, Bart Preneel, and Christian Rechberger

Abstract

We study the security of step-reduced but otherwise unmodified SHA-256. We show the first collision attacks on SHA-256 reduced to 23 and 24 steps with complexities $2^{18}$ and $2^{28.5}$, respectively. We give example colliding message pairs for 23-step and 24-step SHA-256. The best previous, recently obtained result was a collision attack for up to 22 steps. We extend our attacks to 23 and 24-step reduced SHA-512 with respective complexities of $2^{44.9}$ and $2^{53.0}$. Additionally, we show non-random behaviour of the SHA-256 compression function in the form of free-start near-collisions for up to 31 steps, which is 6 more steps than the recently obtained non-random behaviour in the form of a free-start near-collision. Even though this represents a step forwards in terms of cryptanalytic techniques, the results do not threaten the security of applications using SHA-256.

Note: This version of the paper also extends the results to SHA-512.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Accepted at SAC 2008
Keywords
SHA-256hash functionscollisionssemi-free start collisionsfree start collisionspseudo-near-collisions
Contact author(s)
sebastiaan indesteege @ esat kuleuven be
History
2008-07-15: last of 6 revisions
2008-03-25: received
See all versions
Short URL
https://ia.cr/2008/131
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/131,
      author = {Sebastiaan Indesteege and Florian Mendel and Bart Preneel and Christian Rechberger},
      title = {Collisions and other Non-Random Properties for Step-Reduced SHA-256},
      howpublished = {Cryptology ePrint Archive, Paper 2008/131},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/131}},
      url = {https://eprint.iacr.org/2008/131}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.