I wrote
>> the Bi are the input blocks:
>> (IV) -> B1 -> B2 -> B3 -> ... Bk -> H1
>> (IV) -> B2 -> B3 -> ... Bk -> B1 -> H2
>>then we combine H1 and H2 nonlinearly.
(Note that I have since proposed a couple of improvements,
but I don't think they are relevant to the present remarks.)
David Wagner wrote:
This does not add any strength against Joux's attack. One can find
collisions for this in 80*2^80 time with Joux's attack.
First, generate 2^80 collisions for the top line. Find B1,B1* that
produce a collision, i.e., C(IV,B1)=C(IV,B1*)=V2. Then, find B2,B2*
that produce a collision, i.e., C(V2,B2)=C(V2,B2*)=V3. Continue to
find B3,B3*, ..., Bk,Bk*. Note that we can combine this in any way
we like (e.g., B1, B2*, B3*, B4, .., Bk) to get 2^80 different messages
that all produce the same output in the top line (same H1).
OK so far. I think this assumes a sufficiently long input string,
but I'm willing to make that assumption.
Next, look at the bottom line. For each of the 2^80 ways to combine
the above blocks, compute what output you get in the bottom line.
OK so far.
By the birthday paradox,
Whoa, lost me there.
I thought H1 was fixed, namely the ordinarly has of the original
message. Two questions:
1) If H1 is fixed, I don't understand how birthday arguments apply.
Why will trying the bottom line 2^80 times find me H@ equal to a
particular fixed H1? There are a whooooole lot more that 2^80
possibilities.
2) If H1 is not fixed, then this seems to be an unnecessarily
difficult way of saying that a 160-bit hash can be broken using
2^80 work. But we knew that already. We didn't need Joux or
anybody else to tell us that.
A proposal that uses 80*2^80 work is particularly confusing, if
H1 is not fixed.
you will find some pair that produce a
collision in the bottom line (same H2). But that pair also produces
a collision in the top line (since all pairs collide in the top line),
so you have a collision for the whole hash (same H1,H2).
Still lost, for the same reasons. Please explain. Also if possible
please address the improved version, with different IVs and long-range
permutation of a partial block.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
