Implementer's notes

The most important security pillar in SSL/TLS is the strength of the method used when agreeing on the encryption keys. If the method used for this is inherently weak, then it doesn't really matter how secure the rest of the encryption we are using really is.

The primary method used for this is the Public Key encryption methods, the most famous of which is RSA. These methods work by breaking the encryption key into two parts; one secret/private key and one public which is known by all (certificates are used to confirm who the public key belongs to). The relationship between these is that a message encrypted by one key can only be decrypted by the other. This means that anything encrypted with the private key can be read by everyone, but one will know that only the secret key could have created the message, and this property is used in digital signatures. Similarly a message encrypted with the public key can only be read using the private key to decrypt, and this is used in SSL/TLS to agree on the encryption keys used for the connection.

The security of this step depends on how difficult it is to break the encryption used to protect the encryption keys. For these methods breaking the private key means you can break all messages protected by it, and that when you have broken the key you can impersonate the owner. The difficulty of breaking an RSA key is generally determined by how long the key is. Given present technology, I estimate that the work doubles for every 25-30 bits that are added to the key length (as opposed to work doubling for every additional bit when attacking keys for a symmetric method, like AES). At present, 640 bit RSA keys have been broken in 5 months using less than 100 workstations, but even the commonly used 1024 bit keys are threatened now and are not recommended for messages that need to be secure past 2010. As a result, Opera will warn (and is the only browser that does) when these keys are shorter than 900 bits.

A way to make exposure of past messages more difficult is to change the key used to protect the messages very often. This means that there are more keys to break if you want access to all messages. With sufficiently strong private keys, massive attack becomes infeasible and even attacking a single key becomes impracticable.

In SSL/TLS these kind of rapidly changing keys are implemented using the Public Key method, also known as the Diffie-Hellman (DH) key agreement. The system most commonly works by having the server send a temporary (ephemeral) DH key (or DHE key) to the client, which then confirms the authenticity of the key by digitally signing it with its RSA key. The client then uses this DHE key to agree with the server on the encryption keys. Given that these keys are changed every few minutes there will be hundreds of keys used by a server every day, making the task of breaking the keys infeasible if the tasks take even a short time. But best of all, even if the RSA key of the site is broken, the attacker won't get the secret parts of the DHE keys. To be able to do this, they would have to break each key.

Given that the RSA and Diffie-Hellman algorithms are based on the same math, they are equally strong for a given key-size. This means that to provide the same level of security for a given connection as the RSA key, the DHE key has to be as long as the RSA keys. This is where an increasing number of secure servers fall short.

Both RSA and DHE secret key operations are very time consuming and therefore reduce the number of connections a server can handle. While most sites are using RSA keys that are sufficiently long, the fact that there are lots of DHE keys have led some vendors to mistakenly think that they can reduce the length of the DH keys so that more transactions can be performed. Most of these reduced keys are either 512 bits or 768 bits long (which Opera warns about), but I have actually seen servers sending 256(!) bit DHE keys (Hint: I estimate that these can be broken in minutes or hours).

What these vendors seem to forget is that not all attackers are interested in every transaction performed at a site. An attacker might just be interested in one individual visiting the site, and in such cases the size of the DHE key becomes significant. If the key is too short it may become economically feasible for the attacker to break the DHE key. This is why Opera also warns about weak DHE keys, which are shorter than 900 bits.

As reports about weak DHE keys seem to increase, I found it necessary to take a few steps to counter this problem.

The first step was to ask the TLS Work Group to specify clearer how these keys are created. In addition, specify what steps a client should take to ensure the DHE keys are adequately secure. This is currently being worked on for TLS 1.2.

The second step was to evaluate the size of the DHE key when we receive it. If the key is shorter than 1024 bits, we close down the connection after sending an Insufficient Security (71) fatal error to the server, and automatically try to establish a new connection where the DHE methods are listed as less preferred than they normally are. By doing this we will most likely be able to establish a sufficiently secure connection using the RSA-only methods instead. If the server still selects a DHE method, then a warning may be displayed if necessary. This extra round trip will usually not take extra time because it will be handled as part of our usual TLS feature testing of the server (watch this space for news about that). A known issue we are working to fix is that for mail servers where this dialog have been shown previously, this will not take effect until the second time you check email, and that the first attempt will fail.

The end result is that (normally) you will no longer see the weak public key warning, except if the site is using a weak key in the certificate. We can't do anything about the certificate keys because the size of that key is selected directly by the Webmaster. If you get any of those warnings, please notify the webmaster!

Further reading about crypto on Wikipedia:

Public Key Cryptography
RSA
Diffie-Hellman (DH)
SSL and TLS
About Keysizes

Earlier this week news arrived about the successful factoring of a 1020 bit (307 digit) number using just 11 months and about 100 computers to perform the necessary calculations.

The number that was factored is a specially structured number, meaning that it was much easier to factor than a general number of the same size. The largest general factorings accomplished so far are 640 and 663 bits. Both were announced last year.

This is important because the difficulty of factoring a large number determines the security of the RSA encryption method, one of the primary supporting pillars of SSL/TLS, as well as PGP and S/MIME, as they are used today. If the RSA key used by a site is broken, an attacker can not just read all communcation with the site protected by that key, he can also impersonate the site from then on, and he would be able to read all communication with the site that was ever protected by that key, assuming he had archived them.

At present there is no immediate danger that an attacker can break a 1024 bit key, the keylength used by most website certificates (and also CAs) at present. However, like what has been happening to SHA-1 which is another cornerstone of SSL/TLS, this is a warning shot across the bow of the world's 1024 bit RSA keys. Within a few years (it could be 3-4 years, or it could be 10 or more) it is quite likely that the methods used will dramatically reduce the security of 1024 bit RSA keys.

There is currently no indication that RSA itself is broken, but as computation power increases and factorization methods improve this will change the properties of which RSA keys can be considered secure. 10 years ago 768 bits were considered reasonably secure, that limit was later raised to 1024 bits, now it is time to raise the limit even further.

Effects for Opera

I have already taken steps to increase the default length of client certificate keys generated by Opera to 1536 bits.

We are also considering changing the default value of opera:config#SecurityPrefs|MinimumSecurityLevel from "0" to "1". This would raise the lower limit of what is Level 3 (L3) security for RSA from 1000 bits to at least 1020 bits (For settings "0"-"3" Level 1 security is everything below 900 bits).

The consequence of such a change is that sites using certificates issued by at least one root (that was issued with a 1000 bit key) would lose the padlock, as they would be classified as having Level 2 security. We haven't made a decision on this yet, because we first need to find out how problematic the change would be.

Within a few years, probably between 2009 and 2012 (depending on what happens on the factorization front), it is likely that this preference will be raised to "2" (L3 = 1100 bits) or "3" (L3 = 1200 bits).

And before somebody asks: Yes, I am investigating Elliptic Curve Cryptography (ECC). But before it can be implemented and released in a public version, there are still several legal requirements that have to be met.

Last week I also suggested to the W3C's Web Security Context (WSC) group that browsers should not consider a connection secure (and show a padlock) unless the encryption keys used to protect the communication was 2³² (4 billion) times more difficult to break than what can reasonably be broken in one year using currently known methods and technology. The other members of WSC has not yet considered my suggestions.

Such a rule will ensure that, short of revolutionary leaps in technology and/or methods (such as a complete solution of the factoring problem), not even enormous amounts of money can compromise the keys by brute-force computation (if somebody is that interested in some piece of informaiton there are other, less expensive, ways to get hold of the key, such as "buying" it, although that would reveal the interest).

Given the current state of the art, this proposed rule puts 1024 bit RSA in the unsafe zone.

General effects

My recommendation to the world's RSA users would be to use longer keys, at least 1536 bits ( only if performance is an issue), but preferably 2048 bits, and get their certificates issued from Certificate Authorities (CAs) using keys that are at least 2048 bit long (ask the CA if you are not sure).

Thanks to Bruce Schneier for the first post. Bruce also says: "I hope[d] RSA applications would have moved away from 1024-bit security years ago, but for those who haven't yet: wake up."

Thanks also to Eric Rescorla.

See also http://en.wikipedia.org/wiki/RSA_Factoring_Challenge for more on factoring big numbers