International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Collision attacks against 22-step SHA-512

Somitra Kumar Sanadhya
Palash Sarkar
Search ePrint
Search Google
Abstract: In this work, we present two attacks against 22-step SHA-512. Our first attack succeeds with probability about $2^{-8}$ whereas the second attack is deterministic. To construct the attack, we use a single local collision and handle conditions on the colliding pair of messages. All but one condition can be satisfied deterministically in our first attack while in the second attack all conditions can be satisfied deterministically. There are four free words in our second attack and hence we get exactly $2^{256}$ collisions for 22-step SHA-512. Recently, attacks against up to 24-step SHA-256 have been reported in the literature which use a local collision given earlier by Nikoli\'{c} and Biryukov at FSE'08. We provide evidence which shows that using this local collision is unlikely to produce collisions for step reduced SHA-512. Consequently, our attacks are currently the best against reduced round SHA-512. The same attacks also work against SHA-256. Since our second attack is a deterministic construction, it is also the best attack against 22-step SHA-256.
  title={Collision attacks against 22-step SHA-512},
  booktitle={IACR Eprint archive},
  keywords={Cryptanalysis, SHA-2 hash family, reduced round attacks},
  note={Communicated. April 3, 2008. 14042 received 12 Jun 2008},
  author={Somitra Kumar Sanadhya and Palash Sarkar},