So by now, everyone has probably heard that the NSA has supposedly compromised SSL security. It’s a bold claim, and a worrying one. But what exactly did they pull off, because the information floating around about the project is quite limited.
First off, it’s important to realize how SSL actually works. SSL itself is not an encryption algorithm, it’s a communication security protocol that uses encryption under the hood. Not even just one encryption algorithm, but a suite of algorithms the server and client mutually select from. On any given SSL connection to a website, several things happen:
In other words, RSA is used to establish a symmetric encryption key, and the remainder of the communication is encrypted using the symmetric encryption algorithm like RC4 or AES.
The information about what the NSA has achieved suggests that the primary attack on SSL is a brute force attack. This means they are trying to guess one of the keys being used. Either the RSA private key, or the negotiated session key. They must effectively try most of the possible keys before coming up with the correct one. Testing a key takes time, so the more you have to test, the longer it’s going to take. The security of these algorithms is based on the fact that you would need to try so many keys that it would take far too long to be practical (decades or more). As technology gets better however, the speed at which these tests can be performed is reduced, and larger key spaces can be tested in reasonable amounts of time.
So first let’s look at RC4 and AES. These are the encryption algorithms generally used once RSA is used to negotiate their keys (usually RC4). These algorithms in the context of SSL generally end up using a 128 bit encryption key (especially over the last few years when the data was actually collected by the NSA). There are no significant attacks on RC4 or AES which allow faster brute force attacks than the full key size (with a few minor exceptions that aren’t extremely applicable in the context of reading mass numbers of SSL encrypted communications). This means that in order to brute force the symmetric encryption key, they would need to test 3.4028236692093846346337460743177e+38 possible keys (in reality a bit less, but still an enormous number). If they could realistically test 1 billion keys every second, it would take 10790283070806014188971 years to complete. Obviously that still isn’t practical. So realistically, they are not likely to have cracked the symmetric portion either mathematically or through brute force.
That leaves RSA as the potential target for the NSA. And it makes sense too, because if you can compromise the RSA private key of a single site, you can read all of the communications for every user who visits that same domain. Effectively, you crack one key, and you get a lot more bang for your buck. While the current recommendation for RSA key size is 2048 (which is plenty secure for the foreseeable future), many sites have 1024 bit certificates or weaker, especially over the course of the last two years.
So there are really two different ways the NSA could have approached the attack on RSA. The first and most likely, at least to some degree, is that they literally asked for the private keys of major websites. I would like to believe that companies would be unwilling to leak their own keys, and that CAs wouldn’t be so untrustworthy to have leaked them, but in reality, who knows. Clearly the telecom industry has no problem furnishing that type of access. Alternately, they could compromise some of the RSA keys simply by using keys that have been leaked in the past. Since they don’t care if the key was revoked, they can decrypt all traffic that was encrypted with a key that was later leaked to the public.
What I believe they are likely doing when they can’t get the key from the source, is to brute force the RSA keys. In order to do that, they would need to be able to factor an extremely large number into the two prime numbers that make it up. It is understood that this is an exceptionally difficult mathematical problem and cannot be solved in a reasonable amount of time. However in the last couple years, people have made serious advances in the ability to perform this task for smaller numbers. How small is the question.
It seems that while it has become relatively trivial to factor for RSA keys up to about 768 bits, 1024 (the most common size used in the past) is still out of reach. Or at least it was, until the Weizmann Institute released a paper on a theoretical hardware implementation named TWIRL capable of dramatically speeding up the process for 1024 bit RSA keys. Of course it would take millions of dollars to construct the system, but given that the NSA has spent nearly a quarter billion dollars on the project, I think we may have our answer.
So my best educated guess on what the NSA is doing, is that they have constructed a TWIRL like system for rapidly recovering the private keys of SSL communications (in under 1 year per domain, probably even under a week given the scale of their investment). They are also likely utilizing leaked RSA private keys, and contacts with companies willing to hand over their private keys. They are then using the private keys to decrypt mass amounts of traffic for anyone who visited those domains while the key was in effect.
What does this mean for the average consumer? It’s unfortunately too late in regards to the data the NSA has already collected. That information is likely encrypted with 1024 or less, and that can’t be fixed retroactively. In other words, yes, the NSA can probably see all your SSL traffic for the last two years, or at least they will be able to in a couple years when they crack the rest of the most popular RSA certificates.
What does this mean going forward? Companies need to begin upgrading their SSL certificates to a size of 2048. That one measure will prevent all future traffic from being cracked in the foreseeable future. However anything is possible, so let’s assume the NSA figures out how to break 2048 in a few years. In order to ensure that even if that were to happen, the NSA would still not be able to view the plaintext traffic, SSL forward security should be leveraged. SSL forward security uses RSA and a secondary cipher like always, but instead of simply encrypting the symmetric key with the public RSA key, it does a real cryptographic key exchange. This means that the symmetric key is never actually transmitted between the two parties (not even in an encrypted format). So even if the RSA key is compromised, the NSA wouldn’t be able to recover the symmetric keys, and therefore wouldn’t be able to read the traffic.
In conclusion, I would just like to wrap up by saying that SSL has NOT been cracked. The SSL protocol itself, and the optimal encryption schemes it can use, are plenty secure. The entire reason the NSA was able to do this, is because they have historical data covering a period of time where the encryption used was not optimal. That hasn’t changed yet, but I would hope this is a wakeup call to everyone responsible for building SSL enabled software to start supporting, or even better, mandating the selection of optimal algorithms and key sizes. I seriously hope that CAs will stop selling 1024 and lower RSA certificates, and that browsers will not by default, disable the stronger cipher suites they are capable of using (yes, even though your browser can do better, its off by default… Wonder who pushed for those settings?).
Discussing a wide range of topics impacting enterprises and
data center security.