Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. A short version of this paper appears at Crypto 2012.
Keywords
cryptanalysishash functionsSHA-1preimage attackmeet-in-the-middle
Contact author(s)
simon knellwolf @ fhnw ch
History
2012-08-05: received
Short URL
https://ia.cr/2012/440
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/440,
      author = {Simon Knellwolf and Dmitry Khovratovich},
      title = {New Preimage Attacks Against Reduced SHA-1},
      howpublished = {Cryptology ePrint Archive, Paper 2012/440},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/440}},
      url = {https://eprint.iacr.org/2012/440}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.