> From: Valdis.Kletnieks_at_vt.edu [mailto:Valdis.Kletnieks_at_vt.edu]
> Sent: Tuesday, October 15, 2002 12:28 PM
> Forcing a collision to *a specific known hash* is a lot harder - and at
> that point you'll probably still have an essentially random file.
> And unlike beating a CRC-32, there's probably no efficient way to take
> a *given* file, and find a way to *modify* that file and still maintain
> the SAME md5sum.
I agree with this assessment, and your entire post on the subject, but some
vuln-dev readers may be interested in the following:
Gideon Yuval describes a Birthday Paradox attack on a hash function that has
a useful result. Alice and Bob are going to sign a contract. Alice
prepares two versions of the contract, one with the correct terms and one
with terms of her choosing. She picks N/2 points in each contract that can
be varied in binary fashion without changing the sense of the text - a
variant spelling ("grey" vs "gray"), for example. (N is the bit length of
the digest.) Then she hashes both documents, iterating through the 2**(N/2)
versions of each until she gets a collision. She has Bob sign the proper
contract in its colliding version, and then she uses the colliding version
of the improper contract to "prove" Bob signed it instead.
Obviously this is still impractical with current technology etc etc, and as
described there's an easy fix in at least this situation (Bob makes a
cosmetic change to the contract before he signs it). All this is from
Schneier, AC2, 18.1.
It doesn't cover the precise situation you describe, either, since the
attacker can't vary both the "good" and "evil" preimages, just the evil one.
(If the attacker can make changes to, say, sendmail.tar.gz before its MD5
hash gets posted, we have bigger problems, eh?)
But this is an example of a protocol that uses a birthday attack to
accomplish something, anyway.
Michael Wojcik
Principal Software Systems Developer, Micro Focus
Received on Oct 15 2002
Intro
