ejohansson.se

Found an interesting article today: Attacking Hash Functions by Poisoned Messages.

The authors have created two postscript files that, when viewed in a postscript viewer seem to differ, but when passed through a MD5 function produces the same hash. This have the consequent that when a non-suspecting individual electronically signs the “good” document A (by signing the MD5 hash of the document), his signature is also valid for the “evil” document B.

To accomplish this they are using the fact that postscript is really a full blown programming language and that, if MD5(X1) is equal to MD5(X2), then MD5(X1 || X) is equal to MD5(X2 || X). (|| means concatenation.) [1]

This is how they’ve done it…

The first document, document A, looks like this.

%!PS-Adobe-1.0
%%BoundingBox: 0 0 612 792
(S)(S)eq{
[postscript for document A]
}{
[postscript for document B]
}ifelse
showpage

And the second, document B, like this.

%!PS-Adobe-1.0
%%BoundingBox: 0 0 612 792
(T)(S)eq{
[postscript for document A]
}{
[postscript for document B]
}ifelse
showpage

Both S and T are binary blobs of 128 bytes. Expressed in pseudo C, the two documents can be written like this.

if (X == S)
	display(A);
else
	display(B);

X equals S in document A, and T in document B. So each document contains postscript for both documents, and it’s the first 192 bytes that decides which text to show in respective document.

Then, what they have done is finding S and T so that the MD5 hash for

%!PS-Adobe-1.0
%%BoundingBox: 0 0 612 792
(S

equals the MD5 hash for

%!PS-Adobe-1.0
%%BoundingBox: 0 0 612 792
(T

Which apparently took only a couple of hours on a stock PC.

Then they are able to create two, seemingly different documents with the same MD5 hash.

If you’re eager to try this yourself, T and S can be extracted from the order.ps file.

# head --bytes=192 order.ps | tail --bytes=128 > T
# head --bytes=322 order.ps | tail --bytes=128 > S

Hopefully this will make you think twice before signing any postscript document. Or any binary files for that matter. If you follow that advice, the impact of this shouldn’t be that big. But, just too be safe, stop using MD5 as your “hash function of choice”.

[1] – Hash Functions and the Blind Passenger Attack
[2] – Observe that the line endings in the example postscript files are CRLF, not LF.