MD5 Collision with CRC32 Preimage | Hacker News Reader

MD5 Collision with CRC32 Preimage

gist.github.com

34 pointsRetr0id12 comments

Note that hashquines, i.e., programs that print their own hash when executed do not depend on the hash function being broken. In fact, they are a fun little exercise.

    #!/bin/sh
    md5sum $0

I have no idea where to even begin if the digest does not leak something about the data

The same way as a normal quine:

  $ cat >a.py
  #! /bin/python
  import hashlib
  s='#! /bin/python\nimport hashlib\ns=%r\nprint hashlib.sha512(s%%s).hexdigest()\n'
  print hashlib.sha512(s%s).hexdigest()
  $ python a.py
  cf1daf466a7a95b245eab685b808fb861dab9af26078250a8041c4c08a8ff384 (edit: wrap)
  7f7d1853f9d62d6b40cc53d0c5be3efd80eb09f57b71250910c0d6157b73fcd3
  $ sha512sum a.py
  cf1daf466a7a95b245eab685b808fb861dab9af26078250a8041c4c08a8ff384 (edit: wrap)
  7f7d1853f9d62d6b40cc53d0c5be3efd80eb09f57b71250910c0d6157b73fcd3  a.py

Oh duh. That's a clever trick which is rather obvious in hindsight.

Any cryptographic digest is not supposed to leak anything about the data that went in. That’s a core property.

In this case the hash doesn’t depend on the data at all. Do you see how that helps?

  #!/bin/sh
  HASH=6ce1c11751e405291eac368af96de90f
  # Increment until hash of this file equals $HASH: 1
  echo $HASH

MD5 is broken so badly that this hash starts and ends with 1337. Next step is to generate that type of quine when image has two pieces of string data: one is hash of image with no quine and another is exactly same image with two hashes.

1 out of every 4 billion random files will have an md5 that matches your description. Same for sha1, sha256, sha512, and any other proper hash function...

Any proper hash function guarantees that any given bit of the output has an equal chance of being a 1 or a 0 for a random input. So for a specific pattern in 32 specific bits, there is a 1/2^32 chance in any hash func

0x1337 is only two bytes. 2^32, for four bytes, is not a particularly large number.

What are you talking about?? The hash does not start 1337... The hash of the example files is f54e7363d9c72ebf81605e2b38fa2be5. The crc32 is deadbeef.

They're describing the PNG hashquine, which is referenced near the start of the article.

Reply on news.ycombinator.com