----- 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]

Reply via email to