[73643] in North American Network Operators' Group
Re: Senator Diane Feinstein Wants to know about the Benefits of
daemon@ATHENA.MIT.EDU (Scott A Crosby)
Mon Aug 30 18:51:13 2004
To: Gregory Hicks <ghicks@cadence.com>
Cc: goemon@anime.net, mike@sentex.net, nanog@merit.edu
From: Scott A Crosby <scrosby@cs.rice.edu>
Date: Mon, 30 Aug 2004 17:41:23 -0500
In-Reply-To: <200408302133.i7ULXLG19124@metis.cadence.com> (Gregory Hicks's
message of "Mon, 30 Aug 2004 14:33:21 -0700 (PDT)")
Errors-To: owner-nanog-outgoing@merit.edu
On Mon, 30 Aug 2004 14:33:21 -0700 (PDT), Gregory Hicks <ghicks@cadence.com> writes:
>> I recall even seeing posts about people claiming this meant original data
>> being reconstructed from the checksum! That would be truly amazing since I
>> could reconstruct a 680MB ISO from just 61d38fad42b4037970338636b5e72e5a. Wow!
Assuming that MD5 is a PRF, about 2^{-128} files will have such a hash
value. For a file 680MB in size, About 2^{680*1024*1024*8-128} in
total. If I had a list of all of those files, it would be impossible
for me to identify which of them was the 'right' image.
First-preimage resistance means that it should be computationally
infeasible for anyone to create *any* file with that particular
hash. It was also believed to be computationally infeasible to find
*any* two files that had the same MD5 hash. The attack on MD5 showed
that it in fact is computationally feasible to find two files with the
same MD5 --- someone did it. This attack showed that MD5 no longer
meets some of its design requirements.
> The "collision" problem discovered means that there might be
> MULTIPLE 680MB files that give the same checksum.
Scott
