Re: Senator Diane Feinstein Wants to know about the Benefits of P2P

[Scott A Crosby <scrosby () cs rice 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