The Sum Can Be Weaker Than Each Part

Abstract : In this paper we study the security of summing the outputs of two independent hash functions, in an effort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combiner H1(M)⊕H2(M) is one of the two most classical combiners, together with the concatenation combiner H1(M) H2(M). While the security of the concatenation of two hash functions is well understood since Joux's seminal work on multicollisions, the security of the sum of two hash functions has been much less studied. The XOR combiner is well known as a good PRF and MAC combiner, and is used in practice in TLS versions 1.0 and 1.1. In a hash function setting, Hoch and Shamir have shown that if the compression functions are modeled as random oracles, or even weak random oracles (i.e. they can easily be inverted – in particular H1 and H2 offer no security), H1 ⊕ H2 is indifferentiable from a random oracle up to the birthday bound. In this work, we focus on the preimage resistance of the sum of two narrow-pipe n-bit hash functions, following the Merkle-Damgård or HAIFA structure (the internal state size and the output size are both n bits). We show a rather surprising result: the sum of two such hash functions, e.g. SHA-512 ⊕ Whirlpool, can never provide n-bit security for preimage resistance. More precisely, we present a generic preimage attack with a complexity of O(2 5n/6). While it is already known that the XOR combiner is not preserving for preimage resistance (i.e. there might be some instantiations where the hash functions are secure but the sum is not), our result is much stronger: for any narrow-pipe functions, the sum is not preimage resistant. Besides, we also provide concrete preimage attacks on the XOR combiner (and the concatenation combiner) when one or both of the compression functions are weak; this complements Hoch and Shamir's proof by showing its tightness for preimage resistance. Of independent interests, one of our main technical contributions is a novel structure to control simultaneously the behavior of independent hash computations which share the same input message. We hope that breaking the pairwise relationship between their internal states will have applications in related settings.
Type de document :
Communication dans un congrès
Elisabeth Oswald; Marc Fischlin. Advances in Cryptology - Eurocrypt 2015 (Part I) - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2015, Sofia, Bulgaria. Springer, 9056, pp.345-367, 2015, Lecture Notes in Computer Science. 〈https://www.cosic.esat.kuleuven.be/eurocrypt_2015/〉. 〈10.1007/978-3-662-46800-5_14〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01105129
Contributeur : Gaëtan Leurent <>
Soumis le : lundi 14 décembre 2015 - 17:16:02
Dernière modification le : mardi 17 avril 2018 - 11:24:00
Document(s) archivé(s) le : samedi 29 avril 2017 - 13:14:46

Fichier

070.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gaëtan Leurent, Lei Wang. The Sum Can Be Weaker Than Each Part. Elisabeth Oswald; Marc Fischlin. Advances in Cryptology - Eurocrypt 2015 (Part I) - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2015, Sofia, Bulgaria. Springer, 9056, pp.345-367, 2015, Lecture Notes in Computer Science. 〈https://www.cosic.esat.kuleuven.be/eurocrypt_2015/〉. 〈10.1007/978-3-662-46800-5_14〉. 〈hal-01105129〉

Partager

Métriques

Consultations de la notice

299

Téléchargements de fichiers

60