On: The Curious Case of MD5

[a1369209993]

> a PDF file that can be also run in a NES emulator, and will display its own MD5 hash. The MD5 hash is also shown in the pdf document itself.

By that logic, SHA 256 is also broken:

  $ cat >sha256.py
  from hashlib import sha256
  s = 'from hashlib import sha256\ns = %r\nprint sha256(s%%s).hexdigest()\n'
  print sha256(s%s).hexdigest()
  $ sha256sum sha256.py
  14cc85c420ced317fdb73e9403ac3f6e1d96d19c70ae0dce8da9b8d96fa0b4d3  sha256.py
  $ python sha256.py
  14cc85c420ced317fdb73e9403ac3f6e1d96d19c70ae0dce8da9b8d96fa0b4d3

(Yes, PDF is turing complete. Yes, that's terrible. No, it doesn't have anything to do with hash function deficiencies; it's turing complete on (malicious) purpose, just like webpages with javascript.)

[Dwedit → a1369209993]

Don't be silly here, the MD5 is clearly in the plaintext here, and the NES ROM is only the first 40k of the file. It is not able to scan itself and print out a hash that way.

[a1369209993 → Dwedit]

> the MD5 is clearly in the plaintext here

Alright, I'll bite: at what byte offset in the binary file contents does a trivial encoding[0] of the MD5 hash occur?

> the NES ROM is only the first 40k of the file. It is not able to scan itself and print out a hash that way.

It is possible to encode the effects of multiple blocks of arbitrary[1] data on a hash function internal state (independently of what state you start in) in much less space than that data actually takes up, although I'll grant that actually doing so is somewhat impressive in it's own right, so I don't have a trivial translation to SHA 256 immediately ready to post.

Edit: tracked down my saved version:

  $ md5sum pocorgtfo14.pdf
  5eaf00d25c14232555a51a50b126746c  pocorgtfo14.pdf
  $ grep -aoi 5eaf00d pocorgtfo14.pdf || echo not found
  not found
  $ # using ...b126746c because 5eaf00... has a nul
  $ grep -aoF $(printf '\xb1\x26\x74\x6c') pocorgtfo14.pdf || echo not found
  not found

The MD5 is definitely not clearly in the plaintext here, though it could be only mildly unclear.

0: Eg, I'd accept 31 34 63 63 38 35 63 34 ... as an encoding of 14cc85c4... from above.

1: Including random/incompressible data.

[Dwedit → a1369209993]

I stand corrected here, ran it in a debugger, and the NES ROM appears to be doing significant computation between each HEX digit being displayed. Haven't actually read the trace log yet to confirm if it is performing MD5.

NES ROM still doesn't have any access to the rest of the file though.

[bawolff → a1369209993]

I dont know about that specific file, but pdf usually gzips its component parts so i wouldn't expect naive grepping to work.

[planede → a1369209993]

PDF being Turing complete doesn't mean that the program embedded within can access the bytes of the document.