Non-determinism

[David Bolen]

Martin Pool [mbp at samba.org] writes:

> To put it in simple language, the probability of an file transmission
> error being undetected by MD4 message digest is believed to be
> approximately one in one thousand million million million million
> million million.  

I think that's one duodecillion :-)

As a cryptographic message-digest hash, MD4 (and MD5) is intended as
having 2^128 operations necessary to crack a specific digest (find the
original source), but probably only on the order of 2^64 operations to 
find two messages that have the same digest.  But even that isn't a 
direct translation to the probability that two random input strings 
might hash to the same value.

There's an interesting thread from sci.crypt from late last year that
had some addressing of this question:

http://groups.google.com/groups?threadm=u21i5llf2bpt03%40corp.supernews.com

which for one of the examples where the computation was followed through
(the odds of a collision when keeping all 128 bits of the hash and
running it against about 67 million files), the probability of a
collision was about 2^-77.  So I suppose you'd sort of have to figure
out what you wanted to declare your universe of files to be since more
files would increase the odds and less files decrease them.

It's about at this point that I sit back and just say, that's one tiny
probability!

It is interesting that MD4 has been a "cracked" algorithm for a while
now, so if someone was explicitly trying to forge a file that would
fool it, it's very doable.  But I doubt that changes the odds on two
random files colliding.  MD5 has not yet had any duplication found
(and plenty of protocols currently assume there aren't any), but it's
far more computationally intensive to compute, so I think MD4 is more
than sufficient for rsync.

-- David

/-----------------------------------------------------------------------\
 \               David Bolen            \   E-mail: db3l at fitlinxx.com  /
  |             FitLinxx, Inc.            \  Phone: (203) 708-5192    |
 /  860 Canal Street, Stamford, CT  06902   \  Fax: (203) 316-5150     \
\-----------------------------------------------------------------------/