[Dshield] Digital sigs cracked (was: Re: Self-signed certificates)

Brian Dessent brian at dessent.net
Fri Jun 17 04:03:01 GMT 2005

Don Jackson wrote:

> This regards newly discovered "collisions" (where two messages
> result in the same hash code) in the SHA-1 algorithm.   MD5 was
> "cracked" some time ago using the same methods.

Actually no, this attack was on MD5 only.

> The odds that these messages could be construed as
> meaningful -- that is, that they are low-entropy, structured
> using a format or syntax for communication that makes
> sense to any person or system -- is infinitesimal!

That's precisely what they did.  However, it is dependent on the fact
that postscript is a programmatic language.  You could not use this on a
plain text file.

Basically what they did was first generate two strings of random binary
nonsense that both have the same MD5 hash.  Then they generated code in
postscript to display one of two messages.  The final postscript file
for both cases looks like the following:

file A:
<random binary string 1><postscript code: if the proceeding string is
H1, then print "message 1" else print "message 2">

file B:
<random binary string 2><postscript code: if the proceeding string is
H1, then print "message 1" else print "message 2">

So as you can see, file A will print "message 1" while file B will print
"message 2", both of which can be arbitrary strings.  The key here is
that the only part of the file that actually differs is the first block
of random binary junk, which allows for a hash collision to be found
rather easily since the junk needn't make any sense.  It also takes
advantage of the fact that if md5(A) == md5(B) then appending the same
text to both A and B will still result in the same hash of both.

So, what this really tells us is:

1. Don't use MD5 - but we knew that already for quite some time.
2. Don't use pass sensitive documents in a format that is based on a
fully featured programmatic language like PS.

You could probably extend this to PDF as well, since those allow
JavaScript to be embedded.  Microsoft .doc files would probably qualify
as well, since you can embed VB macros in them.


More information about the list mailing list