We show that preimages of SHA-1 can be computed at the cost of 2159.3 compression function computations. For variants with a reduced number of steps we obtain significantly faster attacks than previously known. The best previous attack was on 48 (of 80) steps with a complexity of 2159.3. Our attack on this variant has complexity 2152.1. The new results heavily rely on the linear message expansion and the low diffusion of the step transformation. The techniques in this paper apply to any hash function with linear message expansion.
In the talk we will provide a general introduction to meet-in-the-middle preimage attacks on hash functions.
©2011 Microsoft Corporation. All rights reserved.
Date recorded7 September 2011