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