sorting with expensive compares?

[Paul Rubin]

Thomas Wouters <thomas at xs4all.nl> writes:
> But the odds of such a message having the same MD5 as an existing
> song on his disk is quite a lot higher than 2**64, unless he has a really,
> really large music collection ;) In the case you propose, two files don't
> just need to have the same MD5, but they also need to have a whole lot of
> other characterstics; both need to be (somewhat) valid MP3's, one needs to
> be a piece of music (or other sound) that is somewhat to the target's
> liking, and the other needs to be something playable with a subliminal
> message the target is likely to respond to.

The way the known collision attack works, the saboteur has to
construct both files.  However, the attacker does have a fair amount
of control over the content.  So he can start an innocent file
circulating, then replace it with a sabotaged file on some network.
A user might possibly somehow end up with both versions.

See: http://www.cits.rub.de/MD5Collisions/ for how that kind of attack
can work.