Cryptology ePrint Archive: Report 2012/440

New Preimage Attacks Against Reduced SHA-1

Simon Knellwolf and Dmitry Khovratovich

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 2159.3 evaluations of the compression function. For the same variant our attacks find a one-block preimage at 2150.6 and a correctly padded two-block preimage at 2151.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.

Category / Keywords: secret-key cryptography / cryptanalysis, hash functions, SHA-1, preimage attack, meet-in-the-middle

Publication Info: A short version of this paper appears at Crypto 2012.

Date: received 2 Aug 2012

Contact author: simon knellwolf at fhnw ch

Available format(s): PDF | BibTeX Citation

Version: 20120805:175630 (All versions of this report)

Short URL: ia.cr/2012/440

Discussion forum: Show discussion | Start new discussion