determinism

[Martin Pool]

On 17 Apr 2002, David Bolen <db3l at fitlinxx.com> wrote:
> 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.

I suppose what we're trying to calculate is the probability that for
a given file, a set of random errors produce a file with the same
digest.  I *think* that means the birthday paradox in fact does
not apply, and so the answer is closer to 2^128, not 2^64.  

The birthday paradox probably does apply when searching for matching
blocks.

--
Martin