Certainty

[Hal Finney]

Paul Hoffman wrote:
> Getting a straight answer on whether or not the recent preimage work
> is actually related to the earlier collision work would be useful.

I am not clueful enough about this work to give an authoritative answer.
My impression is that they use some of the same general techniques and
weaknesses, for example the ability to make modifications to message
words and compensate them with modifications to other message words
that cancel. However I think there are differences as well, the preimage
work often uses meet in the middle techniques which I don't think apply
to collisions.

There was an amusing demo at the rump session though of a different
kind of preimage technique which does depend directly on collisions. It
uses the Merkle-Damgard structure of MD5 and creates lots of blocks that
collide (possibly with different prefixes, I didn't look at it closely).
Then they were able to show a second preimage attack on a chosen message.

That is, they could create a message and have a signer sign it using MD5.
Then they could create more messages at will that had the same MD5 hash.
In this demo, the messages started with text that said, "Dear so-and-so"
and then had more readable text, followed by binary data. They were able
to change the person's name in the first line to that of a volunteer
from the audience, then modify the binary data and create a new version
of the message with the same MD5 hash, in just a second or two! Very
amusing demo.

Google for "trojan message attack" to find details, or read:
www.di.ens.fr/~bouillaguet/pub/SAC2009.pdf
slides (not too informative):
http://rump2009.cr.yp.to/ccbe0b9600bfd9f7f5f62ae1d5e915c8.pdf

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com