A few weeks ago, just before New Year, news arrived that a group of security researchers had managed to create a fake intermediate CA certificate that was accepted by all browsers, because it was, to all appearances, signed by a Root
Certificate Authority (CA) trusted by those browsers.
The fake intermediate CA certificate was, however, not signed by the Root CA. What the Root CA
had signed was another certificate based on a completely valid request from the researchers, but the researchers had managed to craft that request -- and a second certificate -- in a way that the digital signature for the certificate signed by the Root CA could also be used by the second certificate.
The Root CA had two problems with their issuing procedure, and the researchers would have failed in their attack had only one of the problems been present.
The first problem was that they signed new
certificates using the
MD5 algorithm to generate the signature of the certificate. MD5 has been showing signs of stress for many years, although it has not been broken yet. MD5 has, therefore, been on the short list for replacement for many years.
The second problem was that the Root CA was issuing certificates with a predictable serial number, not one that appears to be random (it might still be predictable, but only to the issuer), and almost all the other information in the relevant part of the certificate was either easy to predict (such as expiration date), or controlled by the researchers. In combination with the use of MD5 this meant that the researchers could create two certificates that would have the same signature.
Digital signatures have two components, a relatively short checksum (a
hash/digest) calculated over the document that is to be signed -- MD5 is one such digest algorithm,
SHA-1 and
SHA-256 are others -- and that checksum is then encrypted using the signer's private key, usually an
RSA key, and the resulting signature is stored with the document. During verification, the checksum is calculated over the received document and compared against the signed checksum decrypted with the signer's public key (which is known to all).
Digest functions are called one-way functions because they are easy to calculate one way (calculate the checksum of a document), but it is
very difficult to reverse the calculation (calculate the document that produced the checksum). These functions also have a second required attribute: changing a single bit in the document must produce a wildly different checksum; that is why these function are called hash-functions, because they slice, dice and generally make a hash of the bits in the document.
One way to attack a digest function is to find easy ways to calculate two documents that produce the same checksum. The very nature of digests, that the checksum is of finite length, means that there will always be an infinite number of documents that have the exact same checksum, known as collision.
It is "relatively" easy to find such collisions by using a method called the "Birthday attack", after the fact that there is a 50% chance that in a room of 23 people you will find
two people having their birthday on the same day of the year. The problem with the "Birthday attack" has always been creating messages that have meaning, such as a certificate, that will be accepted by a reader (human or machine).
In recent years, such collision attacks on MD5 have become better, and in the recent incident mentioned above, the researchers were able to make the necessary breakthroughs that allowed them to calculate two documents (certificates) that would be accepted by browsers verifying certificates, using "just" 3 days of calculation (bit tweaking, really) on 200 Playstation 3s. Essentially, they calculated two documents "ABC" and "XYC", by changing B and Y, so that the signature for "ABC" would also verify "XYC".
The researchers got an ordinary certificate from the Root CA, and were in possession of a second certificate, for which the same signature was valid. This second certificate was something we call an intermediate CA certificate, meaning it has the authority to sign yet new certificates. The intermediate CA certificate was then used to create a Web site certificate, and that certificate was accepted by the browsers, because the signatures verified all the way to the Root CA's certificate. However, neither the intermediate CA certificate, nor the Web site certificate had ever been authorized by the Root CA. The intermediate CA certificate, controlled by the researchers, was now in a position to create fake certificates for any Web site on the net.
Fortunately, the intermediate CA certificate they created was intentionally configured so that it expired several years ago, so you will always get a certificate warning when accessing a site using a certificate issued by this "CA".
The first consequence of this is that MD5 should not be used when issuing
new certificates. Existing certificates, including Roots that are signed with MD5, are still secure and cannot be faked because the attacker needs to control the data of the certificate, and portions of the data sent to the issuer have to contain random data that are chosen as part of the calculation process; otherwise the attack becomes much harder.
The CA in question have already stopped issuing certificates using MD5, and have AFAIK implemented other countermeasures, such as random serial numbers, so the attack is no longer possible. There are currently no indications that what the researchers did had been duplicated by anyone before they published their results, and considering the (as yet unpublished) new theory they had to develop, it is unlikely that anyone has.
Given the steps that have been taken, this proof of concept is unlikely to affect the security of users.
The second consequence is that use of MD5 (and the weaker MD2 function) in protocols, including certificates, should be phased out as quickly as possible. "Attacks always get better, they never get worse", to quote
Bruce Schneier and the NSA, so it is only a question of time before attacks that are currently unfeasible will become feasible.
That is a much larger task, one that cannot be done overnight.
Certificates: A large fraction (30% according to the researchers, 14% according to
Netcraft) of
certificates used by Web sites are still signed using MD5, and then we are probably not counting the certificates that chain to a MD5 or
MD2 signed root. Disabling MD5 and MD2 in certificate verification today would, almost quite literally, break the Internet. Most certificates today are signed using the more secure
SHA-1 function, but steps are being taken to start using the even more secure SHA-256 function for signatures. Opera 9.0 and later are able to handle certificates signed using SHA-256, as are a number of other modern browsers, but there are quite a few browser users out there with browsers that cannot handle
SHA-256, and the problem of how to migrate to SHA-256 without breaking the Internet has not yet been solved.
Please note that
Extended Validation (EV) certificates are not affected by this. EV site certificates and intermediate CA certificates cannot be signed using MD5, and no Root using 1024 bit keys are accepts for EV in Opera.
SSL v3: SSL version 3, the oldest version of the SSL/TLS protocol that Opera supports, uses MD5 directly as part of several functions, including key calculation; however, due to the design of the protocol, for most purposes, MD5 is combined with another more secure method, SHA-1, even a complete break of MD5 should not compromise the security of SSL v3. Considering that SHA-1 is also showing signs of stress, though considered to be secure for several more years, Web sites should move away from using servers that only support SSL v3 (such servers are also, usually, more than 8 years old). While it is currently not practical to disable support for SSL v3, it may become necessary in a few years.
TLS v1.0 and v1.1: These two versions of TLS both use MD5 in combination with SHA-1, like SSL v3, but use these functions indirectly in a multistep "keyed" operation called
HMAC, where the input data is combined with other data, and the result is then recalculated a second time -- a procedure that foils several types of attacks on these functions. Unless there are problems with the HMAC construction, TLS v1.0 and v1.1 are likely to remain secure for quite some time, but Web sites are encouraged to adopt TLS v1.2 as soon as it becomes available in servers.
TLS v1.2: This is the newest version of TLS, and one first available in Opera 10.0 alpha (Opera Presto 2.2). This version of TLS no longer use MD5 or SHA-1 as part of the protocol, but has changed to using the more secure SHA-256 function for the operations for which MD5 and SHA-1 have been used in SSL v3, TLS v1.0 and TLS 1.1. The only functionality for which MD5 and SHA-1 (together with HMAC) are still used is in the checksums for each encrypted record, but these are still considered reasonably secure. TLS v1.2 also has encryption specifications that use SHA-256, and those are the preferred ones.
While the SSL/TLS protocols versions should be secure for several more years, server vendors should add support for TLS 1.2 and SHA-256 as soon as possible. Web site administrators should start using TLS v1.2 servers as soon as they become available, and in the meantime migrate to servers using TLS v1.1. This will provide their customers with the best available security.
Web surfers should of course at any time use the most up to date version of their browser.
What steps are Opera planning?
We have considered blacklisting the fake intermediate CA certificate, but currently we are leaning towards not doing so. In the new
online certificate repository, we can tell all 9.50+ installations not to trust specific certificates, and we will do so if it is necessary, particularly if a Root is compromised. However, in this case we are dealing with a single demonstration Web site and an expired fake intermediate CA certificate created by a group of researchers that have stated that they will keep the private key for that certificate safe. Marking the certificate untrusted in all installations will, under the circumstances, be a bit of an overkill.
We are, however, planning some changes to the blacklist functionality to make it scale better and be more targeted. Primarily we would like the blacklist to be updated only when the user actually encounters a potentially blacklisted certificate.
In the long term we are very likely going to require all Web site certificates chained to a Root (that is, except self-signed site certificates) to be validated using online validity checks, based on
OCSP and
CRLs, and refuse to connect if some of the non-Root certificates in the chain cannot be checked against either of those validation systems. One of the things the fake CA in this case did not provide was a URL to a CRL that could be used to validate it. Such a step is unlikely to cause disruption for Web sites using a certificate issued from one of the CAs in the Rootstore, but it might cause problems for certificates created by system administrators that roll their own Root certificates. It might also cause problems at Wi-Fi hotspots and ISP networks that restrict external access before payment have been accepted. The benefit of such a policy would be that all certificates would be checked frequently.
We are not going to disable MD5 in certificates for some time. We have asked some CAs to provide information about their phase out plans, but I would be surprised if we can do that within a year. However, all of the affected Roots are using 1024 bit
RSA keys, which means that they are no longer recommended for use past 2010. Therefore, the CAs are already in the process of migrating customers away from those Roots over to Roots with stronger keys.
Another possibility that we are considering regarding MD5 is to add a remote updatable preference to Opera that allows us to turn off MD5 in certificates in all installations at some time. This would mean that, when MD5 is no longer considered secure, or necessary, users would not have to install a new version to disable MD5.
We are also considering, just to be on the safe side, whether or not to disable the single remaining SSL/TLS cipher suite using MD5, the 128 bit
ARC4(RC4) with RSA key exchange and MD5 for integrity checking (128 bit ARC4-RSA/MD5). Before we decide on that, we need to check how many servers that support only that method (there is a SHA-1 variant that is preferred by Opera). My guess is that all servers support at least the 128 bit ARC4-RSA/SHA-1 variant, meaning that there will be no significant disruption if we do this.
The process we are seeing, of ever better attacks on MD5, is part of life for encryption algorithms. All encryption algorithms have a use-by date, although it may not be easy to find, which is why most protocols allow the algorithms to be changed or can be updated to use new ones. Changing from one method to another, more secure method is a process that usually takes several years, particularly in the case of the Internet, due to the number of installed servers and clients that have to continue to work without disruption. This concern is often the reason why disabling of unsecure protocols and methods take longer than one could wish.
More information about the MD5 certificate problem can be found here:
WIDGETIZE