New Collision Attacks against Up to 24-Step SHA-2

In this work, we provide new and improved attacks against 22, 23 and 24-step SHA-2 family using a local collision given by Sanadhya and Sarkar (SS) at ACISP ’08. The success probability of our 22-step attack is 1 for both SHA-256 and SHA-512. The computational efforts for the 23-step and 24-step SHA-256 attacks are respectively 2

11.5

and 2

28.5

calls to the corresponding step reduced SHA-256. The corresponding values for the 23 and 24-step SHA-512 attack are respectively 2

16.5

and 2

32.5

calls. Using a look-up table having 2

32

(resp. 2

64

) entries the computational effort for finding 24-step SHA-256 (resp. SHA-512) collisions can be reduced to 2

15.5

(resp. 2

22.5

) calls. We exhibit colliding message pairs for 22, 23 and 24-step SHA-256 and SHA-512. This is the

first

time that a colliding message pair for 24-step SHA-512 is provided. The previous work on 23 and 24-step SHA-2 attacks is due to Indesteege et al. and utilizes the local collision presented by Nikolić and Biryukov (NB) at FSE ’08. The reported computational efforts are 2

18

and 2

28.5

for 23 and 24-step SHA-256 respectively and 2

43.9

and 2

53

for 23 and 24-step SHA-512. The previous 23 and 24-step attacks first constructed a pseudo-collision and later converted it into a collision for the reduced round SHA-2 family. We show that this two step procedure is unnecessary. Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.