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.