In this paper we study the security of summing the outputs of two independent hash functions, in an eort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combinerH1(M) H2(M) is one of the two most classical combiners, together with the concatenation combiner H1(M)kH2(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 oer no security), H1 H2 is indierentiable 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 ard 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 ~
['Gaëtan Leurent', 'Lei Wang']
The Sum Can Be Weaker Than Each Part