Guys, I have what seems like a new and interesting result, which I haven't seen before, but which may or may not be new.
The high order bit is that you can't generally guarantee that truncating your hash (chopping off some bits) won't weaken it. That is, if you chop SHA256 off to 160 bits as a replacement for SHA1 (something I'm working on with Niels Ferguson for X9 right now), it's possible that there's no attack on SHA256, but there is an attack on SHA160. 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? If it does, then we can make a reduction proof that says that the truncated hash is strong if the original hash is strong. Unfortunately, we can't make this argument, because this postulated collision algorithm can't be used to find a collision in the whole SHA256 more efficiently than brute force. 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, each found at a cost of 2^{64}. The resulting work is 2^{64} * 2^{96} = 2^{160}, more than a straight brute-force collision search on SHA256. What does this mean? It means that just because you have a good 256-bit hash, you can't necessarily make a good 160 bit hash from it. You might be able to--it seems like you usually will be able to--but there's no guarantee. Comments? Is this some well-known result that I'm rediscovering? --John --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]