determinism

[tim.conway at philips.com]

Oh.  Now i feel like an *enlightened* idiot.  I 've always thought of a 
checksum, crc, or whatever as giving 1/2^^length certainty, and I have a 
sense that that knowing the file length adds another amount of certainty, 
though I can't quantify that.  I just know that if the size doesn't match, 
the checksum doesn't matter.

I'd never considered the implications of the presumption that the file is 
the same file hit by random mutations.  The math just blew a circuit 
breaker in my brain.  I've got to go get a beer to reset it.

Tim Conway
tim.conway at philips.com
303.682.4917
Philips Semiconductor - Longmont TC
1880 Industrial Circle, Suite D
Longmont, CO 80501
Available via SameTime Connect within Philips, n9hmg on AIM
perl -e 'print pack(nnnnnnnnnnnn, 
19061,29556,8289,28271,29800,25970,8304,25970,27680,26721,25451,25970), 
".\n" '
"There are some who call me.... Tim?"




Martin Pool <mbp at samba.org>
Sent by: rsync-admin at lists.samba.org
04/17/2002 10:59 PM

 
        To:     rsync at lists.samba.org
        cc:     (bcc: Tim Conway/LMT/SC/PHILIPS)
        Subject:        determinism
        Classification: 



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

-- 
To unsubscribe or change options: 
http://lists.samba.org/mailman/listinfo/rsync
Before posting, read: http://www.tuxedo.org/~esr/faqs/smart-questions.html