Skip navigation.

Security @ Opera

MD5 in certificates: What is happening?

, , , , , ,

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. :yikes:

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:


Introducing the Security @ Opera home page9.64

Comments

Chas4 31. January 2009, 03:57

Very well done,and very informative

JanGen 31. January 2009, 12:05

Thx Yngve for sharing this solid and informative insight. There is so much fuzz around the web, and Dutch papers were shouting that internetbanking wasn't secure anymore. They don't know what they're, talking about but you do! And I understand now a little.

Aux 31. January 2009, 12:23

I'm not so good at understanding all the work around certificates, so my question may be dumb, but anyways.

Why we need certificates for web? What is their role in SSL? Only as a key/salt for encyption algorithm? Then why do I as a developer should pay someone just to free my users from browser warnings? What security they offer?

For example I have a legit music download service and payments work through SSL with valid cert from CA. Cert is assigned to my domain. I place under it a special hidden page for fraudulent actions and use it for sophisticated cross-domain hacks. So everyone is happy: users see green SSL icon, I stole their money.

What am I missing? Currently I really don't see any role for certificates except for salt/key for encryption, but then why should I get certs from CA?

yngve 31. January 2009, 15:00

Aux: Certificates form the foundation of all three pillars (authentication, integrity, privacy) holding up SSL/TLS encryption, and are used for two purposes: Identification of the website, and source of the public key used to agree with the server on the secret used to calculate the encryption keys. It is possible to achieve this through other means, but those usually mean that you must meet the other party, or a trusted representative, physically to agree on the encryption keys.

Identification: Without identitification you do not know who you are talking to, so the information is checked by a trusted thirdparty who signed the information (browsers are able to connect this signature to the trusted copies of the issuer certificate stored in the browser). The information includes at least the name of the server, but may also include the organization name. In EV certificates the identification data have been through more thorough checking than in normal certificates, many of which may only have checked control of the domain (domain validated).

Public Key: This key is stored in the certificate (and the issuer have confirmed that the certificate holder has access to the associated private key). Public Key crypto works in the fashion that data encrypted with the public key can only be decrypted using the private key (vice versa, data encrypted with the private key can be decrypted with the publiuc key, and prove who did it, which is how signatures work); that means that we can encrypt data and send key agreement information to the web server and know that only the server can read the information. That information is then used to calculate the encryption keys used to secure your creditcard information.

Browsers check the information in the certificate, such as verification of all signatures on the certificate, and compares the hostname identified in the certificate against the hostname of the server it is connecting to. If the certificate is issued for www.example.com, but the hostname from the URL is www.yourbank.com every correctly implemented browser will say "Hold on a second! There's something fishy going on here". Usually this will result in a warning dialog to the users, although I am more in favor of completely refusing to access the site (Firefox 3 is halfway there; their warning is currently nastier than ours, which have some people at slashdot up in arms.) In your theoretical example you would either have to use your own domain, or DNS hacks and social engineering to trick users into bypassing the certificate warning dialog (and the missing padlock) to fraudulently separate them from their money.

Only after all the checks (inlcuding such things as checking the revocation status) is completed, do we start to send key agreement information to the server.

Certificates can be said to make Internet commerce possible. Without certificates it would be much more difficult to connect securely to a merchant, or bank, that you have never met (whether you trust them, or not; that is another question, and one that cannot be solved using certificates: certificates is just one of the stepping stones on that path)

Generally speaking: If you encounter a certificate warning (or other security warnings) when going to a site you think is legit, don't continue. Close the window and do your business somewhere else. You should also try to inform the legitimate site about the problem. Legitimate sites do not trigger security warnings.

BTW: There is a mode in SSL/TLS that does not use certificate, called the anonymous mode, disabled by deafult, but since you do not know who you are talking to, anyone who is listening when you start the connection can insert their own negotiation key and not just listen in on everything you send back and forth to the server, but modify it, as well.

Aux 1. February 2009, 10:48

Ok, I understood technical details, but lets take an example. I currently working in online casino division and, of course, our clients make payments through SSL with valid certificate. Yet to track user activity we use Google Analytics which is installed as a JavaScript from HTTPS. So our users see that out casinos are good and can be trusted, no warnings etc. Yet Google gathers a lot of information including mouse moves and stores on their server. Yes, we trust Google, but someone at Google may easily record a few credit cards without anyone knowing.

So where is security? I really don't see...

yngve 1. February 2009, 11:13

Aux: That is something that cannot be solved by SSL (SSL/TLS ensures the security of the communcation between client and server, it cannot secure the endpoints, or the content), in fact it have to be solved by the page author, who is responsible for the overall security of the site.

The solution is however quite simple: Don't include external content in payment pages or other sensitive content, particularly external Javascript (which gets complete access to content). If external content is to be included, don't put any session information in the URL, and if Javascript is used to create the content, it must be inserted from the origin server and not via external reference from another server, and the site author must verify that the script actually does what it is supposed to, and nothing else. You don't allow unverifable content into sensitive pages, but that is not something browsers can enforce (except by full block, a.k.a. breaking the Internet).

As for insiders at the thirdparty being a danger, while a possibility, it is well known that the most serious threat is the insider at the first party. Both can be countered only by implementing good security policies.

ArbiterClass 2. February 2009, 06:05

Nice article. It looks like Opera is doing what it should do.

But I wonder how it is possible that MD5 is still used so much. SHA has been around for a long time and it was clear that MD5 would become problematic for years. Yet, there are/were still CA's using MD5 for new certificates.

Next will be SHA-1, then SHA-256, then SHA-512, then SHA-3, and the cycle will be the same. The industry will change only after there is public proof that it is insecure. And at that point it is painful because the insecure algorithm is widely used.

---

"As for insiders at the thirdparty being a danger, while a possibility, it is well known that the most serious threat is the insider at the first party. Both can be countered only by implementing good security policies."

So, does Opera Software have good security policies? Can we rest assured that there will be no tampering with the root certificates or the online certificate repository or with the Opera executable itself? Does Opera Software police its own employees?


Aux 2. February 2009, 10:17

yngve, big thanks for explanations!

KeMiSa 2. February 2009, 13:06

Great explanation of the security issues there.

However, could anyone explain to me who Asa Dotzler is, and why he seems to be so antagonistic towards Opera?

I recently subscribed to the Planet Opera feed and I have seen some of his posts. The language used seems disparaging of Opera. Even the one that lead me to this post, was from one of his, entitled "Perhaps".

Is he a disgruntled ex-employee of Opera ASA?

Any explanation would help me have a better understanding of his motives.

Thank you.

And keep up the good work Opera.

Aux 2. February 2009, 15:37

@KeMiSa: Asa is a troll currently working in Mozilla Inc PR. See? Troll + PR! In one of interviews some other Mozilla employee sad that they do not really like Asa's tongue, but he does the job.

alsokoloff 4. February 2009, 17:50

Interesting reading, thanks for article.

KeMiSa 5. February 2009, 19:09

@Aux

Thanks.

Write a comment

You must be logged in to write a comment. If you're not a registered member, please sign up.