International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Sebastiaan Indesteege
Florian Mendel
Bart Preneel
Christian Rechberger
Download:
URL: http://eprint.iacr.org/2008/131
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17808,
  title={Collisions and other Non-Random Properties for Step-Reduced SHA-256},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / SHA-256, hash functions, collisions, semi-free start collisions, free start collisions, pseudo-near-collisions},
  url={http://eprint.iacr.org/2008/131},
  note={Accepted at SAC 2008 sebastiaan.indesteege@esat.kuleuven.be 14075 received 23 Mar 2008, last revised 15 Jul 2008},
  author={Sebastiaan Indesteege and Florian Mendel and Bart Preneel and Christian Rechberger},
  year=2008
}