International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 10 February 2015

Gaëtan Leurent, Lei Wang
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.