John Kelsey wrote: > 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. >

Hmm, wouldn't you expect a lot of partial collisions among all those 2^96 collision pairs? That is, after 2^80 runs of the algorithm you would obtain your first partial collision in collision pairs, don't you? For 2^96 that's roughly 2^32 such pairs of pairs. Those might help you to speed up your search. Am I missing something here? Ulrich --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]