Re: MD5 [was: [NSPipe pipe] returning nil (running out of filehandles?)]

FROM : Jens Alfke
DATE : Wed Apr 02 22:52:50 2008

On 2 Apr '08, at 9:12 AM, John Stiles wrote:

> And AFAIK nobody is even remotely close to finding a technique which 
> would let you write arbitrary data and then tack on a few bytes to 
> get the signature you want,


From the Wikipedia article:
Because MD5 makes only one pass over the data, if two prefixes with 
the same hash can be constructed, a common suffix can be added to both 
to make the collision more reasonable.
Because the current collision-finding techniques allow the preceding 
hash state to be specified arbitrarily, a collision can be found for 
any desired prefix; that is, for any given string of characters X, two 
colliding files can be determined which both begin with X.
All that is required to generate two colliding files is a template 
file, with a 128-byte block of data aligned on a 64-byte boundary, 
that can be changed freely by the collision-finding algorithm.
Recently, a number of projects have created MD5 "rainbow tables" which 
are easily accessible online, and can be used to reverse many MD5 
hashes into strings that collide with the original input, usually for 
the purposes of password cracking. However, if passwords are combined 
with asalt before the MD5 digest is generated, rainbow tables become 
much less useful.

> and that's what I'd call "fully broken," at least that's what you'd 
> need to find in order to make an exploit.


That depends on what the digest is being used for — different 
cryptographic protocols rely on different features of the underlying 
algorithms. In some circumstances simply finding any hash collision 
could be enough to break security. (Schneier's "Advanced Cryptography" 
has several examples where a seemingly irrelevant weakness in an 
underlying algorithm led to an attack on a higher level protocol that 
used it. I believe the sad case of WEP was one.)

—Jens