Paper 2015/515

Higher-Order Differential Meet-in-The-Middle Preimage Attacks on SHA-1 and BLAKE

Thomas Espitau, Pierre-Alain Fouque, and Pierre Karpman

Abstract

At CRYPTO 2012, Knellwolf and Khovratovich presented a differential formulation of advanced meet-in-the-middle techniques for preimage attacks on hash functions. They demonstrated the usefulness of their approach by significantly improving the previously best known attacks on SHA-1 from CRYPTO~2009, increasing the number of attacked rounds from a 48-round one-block pseudo-preimage without padding and a 48-round two-block preimage without padding to a 57-round one-block preimage without padding and a 57-round two-block preimage with padding, out of 80 rounds for the full function. In this work, we exploit further the differential view of meet-in-the-middle techniques and generalize it to higher-order differentials. Despite being an important technique dating from the mid-90's, this is the first time higher-order differentials have been applied to meet-in-the-middle preimages. We show that doing so may lead to significant improvements to preimage attacks on hash functions with a simple linear message expansion. We extend the number of attacked rounds on SHA-1 to give a 62-round one-block preimage without padding, a 56-round one-block preimage with padding, and a 62-round two-block preimage with padding. We also apply our framework to the more recent SHA-3 finalist BLAKE and its newer variant BLAKE2, and give an attack for a 2.75-round preimage with padding, and a 7.5-round pseudo-preimage on the compression function.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2015
Keywords
Hash functionpreimage attackSHA-1BLAKEBLAKE2
Contact author(s)
thomas espitau @ ens-cachan fr
History
2015-06-03: revised
2015-05-29: received
See all versions
Short URL
https://ia.cr/2015/515
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/515,
      author = {Thomas Espitau and Pierre-Alain Fouque and Pierre Karpman},
      title = {Higher-Order Differential Meet-in-The-Middle Preimage Attacks on SHA-1 and BLAKE},
      howpublished = {Cryptology ePrint Archive, Paper 2015/515},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/515}},
      url = {https://eprint.iacr.org/2015/515}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.