Steve Bellovin writes: > Note that finding a hash function collision by brute force is > inherently harder, because it requires some communication: two > widely-separated machines may have produced matching outputs, but > they need to know about the other one.
That's not necessarily true, although we don't know the details yet about the new attacks so we can't say for sure. (The new cert collision paper suggests that the details will be presented at Eurocrypt.) Some of the work in this area finds the collisions in a different way than might be expected. They start with a linear or nearly linear approximation to the hash function. On this basis they find an XOR or additive difference that will produce a collision. Then they look for an input for which this pre-chosen difference will produce a collision in the actual hash. That amounts to finding a text for which the nonlinearities cancel out in the proper way, so that the chosen difference works to produce a collision. In the case of MD5, the differential was only 6 (carefuly chosen!) bits. The hard part was to find a plaintext where the nonlinearities associated with those bits did not prevent the collision from occuring. http://eprint.iacr.org/2004/264.pdf presents some "musings" on the Wang attack and estimates that they could find a suitable text for this differential in 2^42.2 work, which is a couple of orders of magnitude more than what Wang apparently needs, indicating that she has more tricks up her sleeve. This method does not require comparing hashes from different plaintexts. Rather, each independent search engine is given the pre-chosen differential and tries to find a plaintext which satisfies the conditions that will allow a collision to occur. A machine to do this would be highly parallelizable and would not require any special communication capabilities. Hal Finney --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]