Higher-Order Differential Meet-in-the-middle Preimage Attacks on SHA-1 and BLAKE

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.
Type de document :
Communication dans un congrès
Rosario Gennaro; Matthew Robshaw. 35th International Cryptology Conference - CRYPTO 2015, Aug 2015, Santa Barbara, United States. Springer, pp.683-701, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference. 〈https://www.iacr.org/conferences/crypto2015/〉. 〈10.1007/978-3-662-47989-6_33〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01183070
Contributeur : Pierre Karpman <>
Soumis le : jeudi 6 août 2015 - 10:44:16
Dernière modification le : mercredi 16 mai 2018 - 11:24:10

Lien texte intégral

Identifiants

Citation

Thomas Espitau, Pierre-Alain Fouque, Pierre Karpman. Higher-Order Differential Meet-in-the-middle Preimage Attacks on SHA-1 and BLAKE. Rosario Gennaro; Matthew Robshaw. 35th International Cryptology Conference - CRYPTO 2015, Aug 2015, Santa Barbara, United States. Springer, pp.683-701, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference. 〈https://www.iacr.org/conferences/crypto2015/〉. 〈10.1007/978-3-662-47989-6_33〉. 〈hal-01183070〉

Partager

Métriques

Consultations de la notice

585