Hash Me If You Can

Task description

Upload two image files A and B such that neither is byte-identical to the other, the OCR’d text in A reads f(MD5(B)), the OCR’d text in B reads f(MD5(A)), where f(h) maps each hex character of h to another hex character by using it as an index back into h itself.

The circular trap

Image A’s required content depends on B’s hash; image B’s required content depends on A’s hash. Changing either image’s visible content changes its bytes, which changes its hash, which changes what the other image is supposed to display, an apparent chicken-and-egg loop with no obvious starting point.

Breaking the circle with a collision

If MD5(A) = MD5(B), both required texts, f(MD5(A)) and f(MD5(B)), become identical, since they’re f() applied to the same hash either way. The two cross-referencing conditions collapse into one: both images just need to display the same fixed text, computed from a hash value both already share.

That still leaves the problem of knowing the hash in advance. The actual trick removes even that requirement: have each file compute its own MD5 at render time, rather than needing it baked in beforehand.

A file that hashes itself

The challenge’s rendering pipeline accepts PostScript, PDF and EPS files through ImageMagick, which in turn runs them through Ghostscript, a real PostScript interpreter. PostScript has a built-in MD5Encode filter, and a short program can seek back to the start of its own file, read its own raw bytes, and hash them:

%!PS-Adobe-3.0
/hexchars (0123456789abcdef) def
/hashout 16 string def
/hexstr 32 string def
/result 32 string def
{
  currentfile 0 setfileposition            % seek back to the start of this file
  currentfile bytesavailable /flen exch def
  /allbytes flen string def
  currentfile allbytes readstring pop pop   % read every byte of this file
  /md5f hashout /MD5Encode filter def
  md5f allbytes writestring
  md5f closefile                            % hashout now holds this file's own MD5
  0 1 15 {                                  % expand the 16 raw bytes to 32 hex characters
    /i exch def
    /b hashout i get def
    hexstr i 2 mul hexchars b -4 bitshift 15 and get put
    hexstr i 2 mul 1 add hexchars b 15 and get put
  } for
  0 1 31 {                                  % apply f(h): index each hex char back into h itself
    /i exch def
    /c hexstr i get def
    c 48 ge c 57 le and { /idx c 48 sub def } { /idx c 87 sub def } ifelse
    result i hexstr idx get put
  } for
  /Courier-Bold findfont 24 scalefont setfont
  36 400 moveto result show
  showpage
  quit
} exec

Since the file reads and hashes its entire contents, including anything appended after the quit that stops PostScript execution, whatever bytes come after quit are part of the hash but never interpreted as code.

Appending a collision

That’s exactly where an MD5 identical-prefix collision comes in: padding the PostScript source to a 64-byte boundary (a requirement of collision tools like fastcoll) and using it as a shared prefix, two different 128-byte collision blocks are appended, one to each file. The two resulting files:

• differ in their bytes (the collision blocks themselves),
• hash to the exact same MD5,
• both execute identically as PostScript, since the collision blocks sit after quit and are read as data for the hash, never as code.

Uploading

# pad the PostScript source to a 64-byte boundary, as fastcoll requires for its prefix
python3 -c "
data = open('self_hash.ps', 'rb').read()
pad = (-len(data)) % 64
open('prefix.ps', 'wb').write(data + b' ' * pad)
"

# produce two files sharing that prefix but colliding on MD5
./fastcoll -p prefix.ps -o file_a.ps file_b.ps

curl -F "file=@file_a.ps" http://chal.live.hackultet.hr:PORT/upload -F "slot=A"
curl -F "file=@file_b.ps" http://chal.live.hackultet.hr:PORT/upload -F "slot=B"

Both files, each computing and rendering f() of its own MD5 (which is the same value in both cases, by construction), are uploaded as .ps files. The server’s ImageMagick/Ghostscript pipeline renders them, an OCR step (Tesseract) reads the rendered text back out, and the cross-check passes, since MD5(A) = MD5(B) makes the two required conditions identical and already satisfied.

What this depended on

Three separate pieces had to line up: recognising that a hash collision collapses the circular requirement into a single shared one, knowing that PostScript (via Ghostscript) can compute and act on its own file’s hash without any external tooling, and having an MD5 identical-prefix collision tool (fastcoll) available to actually produce two colliding files sharing the required prefix.