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 majord...@metzdowd.com