Collision for 64-step SHA-1

Graz, May 2006: Researchers of the Krypto group of the IAIK succeeded in constructing a collision for a simplified variant of the standard hash function SHA-1. The simplified variant differs from the standard only in the number of iterations of the step functions that is used: 64 instead of 80. The previously best result was a collision for a variant with 58 iterations, first shown by Wang et al. in 2005.

In order to achieve this result, the methods developed by Prof. Wang et al. were analyzed, extended and automated. The computational effort to produce the collision was equivalent to 2³⁵ applications of the hash function variant.

This research project is sponsored in part by the Austrian Science Fund (FWF) under project number P18138, and in part by the Secure Information Technology Center - Austria (A-SIT).

A technical article describing the used technique is being prepared. The research is continued in order to be able to produce collisions for the full 80-step standard.

Details of a collision for SHA-1 reduced to 64 steps: The 1024-bit messages (M1,M2) and (M1*,M2*) both produce the value H for the chaining variable. Adding the padding and/or further common blocks changes the hash output, but not the fact that there is a collision.

    M1       M1*   
63DAEFDD 63DAEFDE
30A0D167 70A0D135
52EDCDA4 12EDCDE4
90012F5F 70012F0D
0DB4DFB5 ADB4DFB5
E5A3F9AB 65A3F9EB
AE66EE56 8E66EE57
12A5663F 32A5665F
D0320F85 50320F84
8505C67C C505C63E
756336DA B5633699
DFFF4DB9 9FFF4D9B
596D6A95 596D6A96
0855F129 4855F16B
429A41B3 829A41F0
ED5AE1CD 2D5AE1EF

    M2       M2*     
3B2AB4E1 3B2AB4E2
AAD112EF EAD112BD
669C9BAE 269C9BEE
5DEA4D14 BDEA4D46
1DBE220E BDBE220E
AB46A5E0 2B46A5A0
96E2D937 B6E2D936
F3E58B63 D3E58B03
BE594F1C 3E594F1D
BD63F044 FD63F006
50C42AA5 90C42AE6
8B793546 CB793564
A9B24128 A9B2412B
816FD53A C16FD578
D1B663DC 11B6639F
B615DD01 7615DD23

    H   
A750337B
55FFFDBB
C08DB36C
0C6CFD97
A12EFFE0