International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Attacking Step Reduced SHA-2 Family in a Unified Framework

Somitra Kumar Sanadhya
Palash Sarkar
Search ePrint
Search Google
Abstract: In this work, we make a detailed analysis of local collisions and their applicability to obtain collisions for step reduced SHA-2 hash family. Our analysis explains previously reported collisions for up to 22-step SHA-2 hash functions with probability one. We provide new and improved attacks against 23 and 24-step SHA-256 using a local collision given by Sanadhya and Sarkar (SS) at ACISP '08. The computational efforts for the 23-step and 24-step attacks are respectively $2^{12.5}$ and $2^{28.5}$ calls to the corresponding step reduced SHA-256. Using a look-up table having $2^{32}$ entries the computational effort for finding 24-step collisions can be reduced to $2^{14.5}$ calls. We exhibit colliding message pairs for both the 23 and 24-step attacks. The previous work on 23 and 24-step SHA-256 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikoli\'{c} and Biryukov (NB) at FSE '08. The reported computational efforts are $2^{18}$ and $2^{28.5}$ respectively. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-256. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-256 attacks, they do not threaten the security of the full SHA-2 family.
  title={Attacking Step Reduced SHA-2 Family in a Unified Framework},
  booktitle={IACR Eprint archive},
  keywords={Cryptanalysis, SHA-2 hash family, reduced round attacks},
  note={Communicated. May 15, 2008. 14049 received 12 Jun 2008, last revised 19 Jun 2008},
  author={Somitra Kumar Sanadhya and Palash Sarkar},