International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Some Observations on Strengthening the SHA-2 Family

Somitra Kumar Sanadhya
Palash Sarkar
Search ePrint
Search Google
Abstract: In this work, we study several properties of the SHA-2 design which have been utilized in recent collision attacks against reduced SHA-2. We suggest small modifications to the SHA-2 design to thwart these attacks. The cost of SHA-2 evaluations does not change significantly due to our modifications but the new design provides resistance to the recent collision attacks. Further, we describe an easy method of exhibiting non-randomness of the compression functions of the entire SHA family, that is SHA-0, SHA-1 and all the hash functions in SHA-2. Specifically, we show that given any $\IV_1$ and any pair of messages $M_1$ and $M_2$, an $\IV_2$ can be easily and deterministically constructed such that the relation $H(\IV_1,M_1)-\IV_1 = H(\IV_2,M_2)-\IV_2$ holds. For a truly random hash function $H$ outputting a $k$-bit digest, such a relation should hold with probability $2^{-k}$. We introduce the general idea of ``multiple feed-forward" in the context of construction of cryptographic hash functions. When used in SHA designs, this technique removes the non-randomness mentioned earlier. Perhaps more importantly, it provides increased resistance to the Chabaud-Joux type ``perturbation-correction'' collision attacks. The idea of feed-forward is taken further by introducing the idea of feed-forward across message blocks. This provides quantifiably better resistance to Joux type generic multi-collision attacks. For example, with our modification of SHA-256, finding $2^r$ messages which map to the same value will require $r\times 2^{384}$ invocations of the compression function.
  title={Some Observations on Strengthening the SHA-2 Family},
  booktitle={IACR Eprint archive},
  keywords={SHA-2 hash family,  non-randomness, hash function design.},
  note={Communicated. May 9, 2008. 14042 received 12 Jun 2008},
  author={Somitra Kumar Sanadhya and Palash Sarkar},