[IP] SHA-1 cracked?

[Hal Finney]

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 majordomo at metzdowd.com