New Preimage
Attacks Against Reduced SHA-1
Simon Knellwolf (ETH
Dmitry Khovratovich (Microsoft Research
Abstract:
This paper shows preimage attacks against reduced
SHA-1 up to 57 steps. The best previous attack has been presented at CRYPTO
2009 and was for 48 steps finding a two-block preimage
with incorrect padding at the cost of $2^{159.3}$ evaluations of the
compression function. For the same variant our attacks find a one-block preimage at $2^{150.6}$ and a
correctly padded two-block preimage at $2^{151.1}$
evaluations of the compression function. The improved results come out of a
differential view on the meet-in-the-middle technique originally developed by
Aoki and Sasaki. The new framework closely relates meet-in-the-middle attacks
to differential cryptanalysis which turns out to be particularly useful for
hash functions with linear message expansion and weak diffusion properties.