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