Cryptology ePrint Archive: Report 2015/515

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

Thomas Espitau and 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.

Category / Keywords: secret-key cryptography / Hash function, preimage attack, higher-order differential meet-in-the-middle, SHA-1, BLAKE, BLAKE2

Original Publication (with minor differences): IACR-CRYPTO-2015

Date: received 28 May 2015, last revised 3 Jun 2015

Contact author: thomas espitau at ens-cachan fr

Available format(s): PDF | BibTeX Citation

Version: 20150603:164643 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]