You can add arbitrary bytes to the end of a gzipped file and it will still uncompress to the same thing. This is how the first illegal prime was discovered.
Comment on Re^2: On showing the weakness in the MD5 digest function and getting bitten by scalar context