Possibly new result on truncating hashes

[Joseph Ashwood]

----- Original Message ----- 
From: "John Kelsey" <kelsey.j at ix.netcom.com>
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 majordomo at metzdowd.com