Recent MD5 Collision

[Tacvek]

Lucks' and Daum's new attack on MD5 is very scary.
Cryptographically it is a no-op in that it abuses the user. The postscript
file that is signed contains both messages.

A similar exploit would be to have a program that prints one document on
Caesar's computer (printer), but a different one on all other computers
(printers).

Exploit is due to user's thinking of postscript programs as documents, and
signatures on them being equivalent to signatures on the output. The rest of
this message ignores this fact, just as most users will.


The attack works due to the fact that:
If md5(M)==md5(M') then md5(M||A)==md5(M'||A), where || stands for
concatenate. Import to note that A||M||B and A||M'||B also work.

The attack is then simple, find ANY M and M' such that md5(M)==md5(M') [In
reality certain characters or sequences may need to be avoided, but in
postscript it seems to generally not be too big a problem.]

Then construct A and B. Here is a possible A and B for a basic-like
programming language. This example assumes that M can be differentiated from
M' because the first character of M is #, but the first character of M' is
something different.

---- BEGIN A ----
temp$="
---- END A----
---- BEGIN B ----
"\nIf left$(temp$,1)="#" then\nprint "Message A"\nelse\nprint "Message
B"\nEnd If
---- END B----
Obviously A and B could be changed arbitrarily.

That is what has already been done. What is really scary is that if somebody
finds *ANY* SHA-1 collision the above could be used in exactly the same way.
this actually applies to
all Merkle-Damgård hash functions.