Bogus digital signatures, Re: OT: utility account transfer frauds

[Matthew Astley]

On Fri, Oct 11, 2002 at 07:54:22AM +0100, lists@notatla.demon.co.uk wrote:
> From: Matthew Astley <lists-ukcrypto@fruitcake.demon.co.uk>

> > Anyway, it would appear that distributed.net is big enough[1] to
> > attack the 128-bit MD5, because the birthday paradox reduces it to
> > an approximately 64-bit problem.

  http://www.certainkey.com/dnet/

It's dated 2002-09-28, so my apologies if the real cryptographers 9-)
here have seen it already.

This attack appears to be aimed at breaking MD5 fairly severely.  I
believe this would render all PGP 2.6.x signatures worthless,
including the ones currently generated by the time stamper at
http://www.itconsult.co.uk/stamper.htm .


Steve pointed me at the right place in the d.net mail archive,

  http://lists.distributed.net/hypermail/rc5.Sep2002/subject.html#37

For some reason their "sort by thread" index omits the entire of the
relevant thread.


> There's the additional matter of not having all their memory in the
> same place (this can be dealt with).  But 24*(2^64) bytes sounds a
> lot to me and I doubt there is that much to be recruited.

They reckon on needing 2^32 * ( 96 + 40 ) bits ~= 70 gig of disk space
(ie. peanuts), and about the same amount of CPU and network traffic as
the RC5-64 challenge.

Whether it's wise for world+dog to donate sole control of such a
powerful database to d.net is another question.

> Plus you have to keep the original documents around until you finish so
> you can say what the collision was.

The project itself is aimed at finding any old collision, but once you
get one then many more follow.  The fact that you can pre-calculate
all except the last part of MD5 makes exploiting this easier.

http://www.certainkey.com/dnet/dnet_md5_contract.php

This page leaves me feeling that I've failed to grok the power of the
birthday attack...

AIUI this attack wouldn't break MD5-HMAC unless you know the secret.
Comments?

The impact on David Madore's free speech method might be interesting
too.


If the victim of a forgery disputes the signature in court, will it be
a "birthday suit"?


Matthew  #8-)