----- Original Message -----
From: "John Kelsey" <[EMAIL PROTECTED]>
Subject: Possibly new result on truncating hashes
How could this work? Suppose we have an algorithm like the
Wang attacks on MD5, SHA0, or SHA1 for finding a single
collision pair. The algorithm returns a single collision
pair on the first 160 bits of SHA256 for (say) 2^{64} work.
(Remember that this is just an example--I don't have any
such algorithm!) Each time the algorithm is run, it gives a
new, unrelated collision pair, and the remaining 96 bits are
completely randomized by the collision pair.
Now, this is an attack on SHA256 truncated to 160 bits.
Does it lead to an attack on SHA256 as a whole?
Actually it does. Such an attack would reduce the difficulty of producing a
collision in SHA-256 to 2^(64+(96/2)) or 2^112. The math for this is fairly
easy, the remaining 96 bits will collide in on average 2^(96/2) tries, since
it takes 2^64 work for each of these tries, we get 2^112 work, hence an
attack on the original hash has been found.
Let's do the counting argument: Each time we call the
160-bit collision algorithm, we get a new pair which has the
same first 160 bits of SHA256 output, and random unrelated
last 96 bits of SHA256 output. Each pair has a probability
of 2^{-96} of colliding in the remaining bits. So, to get a
collision on the whole SHA256 using this 160-bit collision
algorithm, we expect to have to try about 2^{96} collision
pairs
There's the mistake. To find a collision in the remaining bits requires
2^(96/2) work, not 2^96 work. For a chosen initial value you will of course
have the 2^96 work, but there you'll only have 2^(64+96) work instead of
2^256, the attack still works.
Joe
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
