Re: Added hashes.

Tino Schwarze <tino.schwarze.0401@tisc.de> wrote:
>Kristian Gjøsteen <kristiag+news@item.ntnu.no> wrote:
>
>> >I'd not xor the result but keep both results (e.g. append hash 1 to hash
>> >2). So if somebody is able to produce a plaintext for hash 1 (say MD5),
>> >chances should be very low that it also matches hash 2 (say SHA1). But I
>> >would only consider this for long-time archiving.
>> >
>> >This should[1] also significantly lower the probability of a hash
>> >collision.
>> >
>> >[1] read "sounds logical to me but I'm not a cryptologist."
>>
>> This piece of folklore was proven false by "Multicollisions in
>> Iterated Hash Functions. Application to Cascaded Constructions" by
>> Antoine Joux.
>>
>> The paper is very easy to understand and a nice read.
>
>And hard to get... :-( Could someone please summarize the main points?

Here's my take. (I haven't read the paper carefully, so I may have
missed some subtle points. Someone is sure to correct me. Also, I'm
ignoring a lot of details like padding and block sizes etc.)

First of all, this applies to iterated hash functions, where the
message is split into blocks and then the iteration rule is x =
f(x,m[i]), where x is the hash state. The hash state has a specified
initial value.

Denote by h(m;x) the hash value when you start with state x.

Suppose you have a collision finder for a hash function that works
for (at least a significant fraction of) all initial values. First
you use the collision finder to find a collision h(m1) = h(m1') =
x1, starting with the specified initial value.

Then you find a collision h(m2;x1) = h(m2';x1) = x2.

Now, because of the iterated nature of the hash function, you have
found four collisions in the hash function, namely:

        h(m1||m2) = h(m1'||m2) = h(m1||m2') = h(m1'||m2') .

You proceed like this, finding t collisions, and this gives you a
total of 2^t messages that all collide to the same hash value. For
any other hash function with output length 2t, it is by the birthday
paradox likely that there will be a collision among the 2^t messages.

Therefore any concatenation of hash functions will at best only
have the strength of the longest hash output.

Unless I missed something, you cannot combine collision finders.
But even so, the MD5-SHA-1 concatenation will have a strength of
approximately 2^70 (based on putting the SHA-1 collision finder
first, and then multiplying by 128).

-- 
Kristian Gjøsteen