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