MD5 considered harmful today

Len Sassaman len.sassaman at esat.kuleuven.be
Fri Jan 2 13:22:39 EST 2009


On Tue, 30 Dec 2008, Hal Finney wrote:
>
>  - The attack relies on cryptographic advances in the state of the art for
>    finding MD5 collisions from inputs with different prefixes. These advances
>    are not yet being published but will presumably appear in 2009.

To insert a malicious "basicConstraints CA = TRUE" these advances appear
necessary; I do not believe that they are necessary for the other very
similar attack (where the malicious cert is a wildcard (*) certificate). I
could be wrong about this, but I also don't think that the advances in
cryptography to get from chosen prefix attacks to here are anywhere near
as great as were needed to get the original chosen prefix work. We can
evaluate the correctness of that statement when the work is published, of
course.

>  - The collision was found using Arjen Lenstra's PlayStation Lab and used
>    200 PS3s with collectively 30 GB of memory. The attack is in two parts,
>    a new preliminary "birthdaying" step which is highly parallelizable and
>    required 18 hours on the PS3s, and a second stage which constructs the
>    actual collision using 3 MD5 blocks and runs on a single quad core PC,
>    taking 3 to 10 hours.

Prof. Lenstra's PlayStation Lab is definitely impressive, but there are
many ways to get the computation time needed to perform this attack,
including Amazon's EC2, botnets, and other high powered computing systems.
It's not *that* much computation time.

> My take on this is that because the method required advances in
> cryptography and sophisticated hardware, it is unlikely that it could
> be exploited by attackers before the publication of the method, or
> the publication of equivalent improvements by other cryptographers. If
> these CAs stop issuing MD5 certs before this time, we will be OK. Once
> a CA stops issuing MD5 certs, it cannot be used for the attack. Its old
> MD5 certs are safe and there is no danger of future successful attacks
> along these lines.  As the paper notes, changing to using random serial
> numbers may be an easier short-term fix.

I am worried that this may be too optimistic of an outlook. This attack
was known and discussed by at least two research teams for at least a year
(Dan Kaminsky, Meredith L. Patterson, and I worked out the attack at the
last CCC).

To be fully confident in the CA infrastructure, all certificates that have
delegated signing authority granted to them by a higher CA (using MD5 on
the certificate in question) should be audited to ensure they are not
malicious. This of course includes private certificate infrastructures,
too.

I would be extremely surprised if this attack had been performed prior to
the original chosen prefix work being published -- but since that time,
there has been plenty of opportunity for a malicious party to quietly
perform this attack in the wild.



--Len.



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



More information about the cryptography mailing list