by Marc Stevens
When weaknesses are found in cryptographic protocols or algorithms on which the everyday security of the Internet relies, it is important that they are replaced by more secure alternatives. This is clearly emphasized by the recent case of MD5, an algorithm commonly used to create digital signatures in which severe weaknesses were found in 2004. The continued use of MD5 by several leading Certification Authorities (CAs) on the Internet enabled our team to become a rogue CA itself, triggering quick and adequate responses from the affected CAs and major Internet browsers.
When you visit a Web site whose URL starts with 'https', a small padlock symbol appears in the browser window. This indicates that the Web sites digital identity is verified using a digital certificate issued by one of a few trusted CAs. To ensure that the digital certificate is legitimate, the browser verifies its signature using standard cryptographic algorithms. It is one of these algorithms, known as MD5, which can be misused. MD5 is vulnerable to an attack called 'chosen-prefix collisions', which essentially allows one to manipulate any two files so that they would receive the same MD5-based signature. In principle this allows fraud by copying a signature between two such 'colliding' files, for instance by copying a CA's signature from an issued certificate to a rogue certificate. Such an attack becomes a real threat when the rogue certificate is in fact a CA certificate instead of a regular end-user certificate.
MD5 is an algorithm that splits a file or certificate into small fixed-size blocks that are iteratively processed to update the small internal state that MD5 maintains. A chosen-prefix collision attack manipulates a few sequential blocks in both files to remove all differences between the two internal states in an iterative process. The two internal states will thereafter be equal and remain equal when the remaining blocks are also equal for both files and in the end lead to the same digital signature. The number of blocks available for these manipulations is severely limited in the case of certificates as issued by real CAs, greatly increasing the computational cost normally required for a chosen-prefix collision attack.
Our new mathematical improvements allow more differences per message block to be removed in a very flexible manner and allow new trade-offs between the computational and memory costs of various parts of the attack. These improvements can greatly reduce the computational costs for short chosen-prefix collisions depending on the available memory. Combined with the use of a cluster of 215 PlayStation3s, performing like 8600 PC cores, this enhanced attack can now be performed on certificates in only a single day whereas previously it would take this cluster two months. When making use of terabytes of hard-drive space, this enhanced attack is even possible in a single day on twenty PS3s or on the publicly available Amazon EC2 computing service at an estimated cost of $2,000.
For the attack to succeed, the validity period and serial number of the issued certificate had to be predicted correctly, as both will be generated by the signing CA. We found one particular CA for which this could easily be done and after a few attempts we succeeded. The correctly predicted issued certificate thereby contains a signature that is also valid for the colliding rogue CA certificate, promoting it into a CA certificate trusted by all major Internet browsers.
With the example rogue CA we managed to demonstrate that a critical part of the Internets infrastructure was not safe. In combination with known weaknesses in the DNS (Domain Name System) protocol, this could have opened the door for virtually undetectable phishing attacks. For example, without being aware of it, users could be redirected to malicious sites that appear exactly the same as the trusted banking or e-commerce websites they believe they are visiting. The Web browser could then receive a forged certificate that will be erroneously trusted, and users passwords and other private data can fall into the wrong hands.
To prevent any damage from occurring, the certificate we created had a validity of only one month August 2004 which expired more than four years ago. The only objective of our research was to stimulate better Internet security with adequate protocols that provide the necessary security. All affected CAs responded quickly and migrated to more secure alternatives to MD5 only hours after our presentation of the rogue CA at the 25C3 security conference in Berlin on December 30, 2008. The leading CAs together with the major Internet browsers are pushing stronger security measures for all CAs, since this CA infrastructure is only as strong as its weakest link.
More research is needed into alternatives to MD5 on possible weaknesses and the real security they provide. The National Institute of Standards and Technology (NIST) is holding an open competition to select a new standard SHA-3 to replace MD5 and its current alternatives.
The team consisted of Marc Stevens (Cryptology Group, CWI), Alexander Sotirov, Jacob Appelbaum (Noisebridge, The Tor Project), Arjen Lenstra (EPFL), David Molnar (UC Berkeley), Dag Arne Osvik (EPFL) and Benne de Weger (TU/e).
Links:
http://www.cwi.nl/en/node/839
http://www.win.tue.nl/hashclash/rogue-ca/
Please contact:
Marc Stevens, Cryptology Group, CWI, The Netherlands
Tel: +31 20 592 4103
E-mail: Marc.Stevens
cwi.nl
