Monday, December 2, 2013

How does the NSA break SSL?

(source)
A few weeks ago I wrote a long post about the NSA's 'BULLRUN' project to subvert modern encryption standards. I had intended to come back to this at some point, since I didn't have time to discuss the issues in detail. But then things got in the way. A lot of things, actually. Some of which I hope to write about in the near future.

But before I get there, and at the risk of boring you all to tears, I wanted to come back to this subject at least one more time, if only to pontificate a bit about a question that's been bugging me.

You see, the NSA BULLRUN briefing sheet mentions that NSA has been breaking quite a few encryption technologies, some of which are more interesting than others. One of those technologies is particularly surprising to me, since I just can't figure how NSA might be doing it. In this extremely long post I'm going to try to dig a bit deeper into the most important question facing the Internet today.

Specifically: how the hell is NSA breaking SSL?
Section of the BULLRUN briefing sheet. Source: New York Times.
To keep things on target I'm going to make a few basic ground rules.

First, I'm well aware that NSA can install malware on your computer and pwn any cryptography you choose. That doesn't interest me at all, for the simple reason that it doesn't scale well. NSA can do this to you, but they can't do it for an entire population. And that's really what concerns me about the recent leaks: the possibility that NSA is breaking encryption for the purposes of mass surveillance.

For the same reason, we're not going to worry about man-in-the-middle (MITM) attacks. While we know that NSA does run these, they're also a very targeted attack. Not only are MITMs detectable if you do them at large scale, they don't comport with what we know about how NSA does large-scale interception -- mostly via beam splitters and taps. In other words: we're really concerned about passive surveillance.

The rules above aren't absolute, of course. We will consider limited targeted attacks on servers, provided they later permit passive decryption of large amounts of traffic; e.g., decryption of traffic to major websites. We will also consider arbitrary modifications to software and hardware -- something we know NSA is already doing.

One last point: to keep things from going off the rails, I've helpfully divided this post into two sections. The first will cover attacks that use only known techniques. Everything in this section can be implemented by a TAO employee with enough gumption and access to software. The second section, which I've titled the 'Tinfoil Hat Spectrum' covers the fun and speculative stuff -- ranging from new side channel attacks all the way to that huge quantum computer the NSA keeps next to BWI.

We'll start with the 'practical'.

Attacks that use Known Techniques

Theft of RSA keys. The most obvious way to 'crack' SSL doesn't really involve cracking anything. Why waste time and money on cryptanalysis when you can just steal the keys? This issue is of particular concern in servers configured for the TLS RSA handshake, where a single 128-byte server key is all you need to decrypt every past and future connection made from the device.

In fact, this technique is so obvious that it's hard to imagine NSA spending a lot of resources on sophisticated cryptanalytic attacks. We know that GCHQ and NSA are perfectly comfortable suborning even US providers overseas. And inside our borders, they've demonstrated a willingness to obtain TLS/SSL keys using subpoena powers and gag orders. If you're using an RSA connection to a major website, it may be sensible to assume the key is already known.

Of course, even where NSA doesn't resort to direct measures, there's always the possibility of obtaining keys via a remote software exploit. The beauty is that these attacks don't even require remote code execution. Given the right vulnerability, it may simply require a handful of malformed SSL requests to map the full contents of the OpenSSL/SChannel heap.


Source: New York Times
Suborning hardware encryption chips. A significant fraction of SSL traffic on the Internet is produced by hardware devices such as SSL terminators and VPN-enabled routers. Fortunately we don't have to
speculate about the security of these devices -- we already know NSA/GCHQ have been collaborating with hardware manufacturers to 'enable' decryption on several major VPN encryption chips.

The NSA documents aren't clear on how this capability works, or if it even involves SSL. If it does, the obvious guess is that each chip encrypts and exflitrates bits of the session key via 'random' fields such as IVs and handshake nonces. Indeed, this is relatively easy to implement on an opaque hardware device. The interesting question is how one ensures these backdoors can only be exploited by NSA -- and not by rival intelligence agencies. (Some thoughts on that here.)

Side channel attacks. Traditionally when we analyze cryptographic algorithms we concern ourselves with the expected inputs and outputs of the system. But real systems leak all kinds of extra information. These 'side channels' -- which include operation time, resource consumption, cache timing, and RF emissions -- can often be used to extract secret key material.

The good news is that most of these channels are only exploitable when the attacker is in physical proximity to a TLS server. The bad news is that there are conditions in which the attacker can get close. The most obvious example involves virtualized TLS servers in the cloud setting, where a clever attacker may share physical resources with the target device.

A second class of attack uses remote timing information to slowly recover an RSA key. These attacks can be disabled via countermeasures such as RSA blinding, though amusingly, some 'secure' hardware co-processors may actually turn these countermeasures off by default! At very least, this makes the hardware vulnerable to attacks by a local user, and could even facilitate remote recovery of RSA keys.

Weak random number generators. Even if you're using strong Perfect Forward Secrecy ciphersuites, the security of TLS depends fundamentally on the availability of unpredictable random numbers. Not coincidentally, tampering with random number generator standards appears to have been a particular focus of NSA's efforts.

Random numbers are critical to a number of elements in TLS, but they're particularly important in three places:
  1. On the client side, during the RSA handshake. The RNG is used to generate the RSA pre-master secret and encryption padding. If the attacker can predict the output of this generator, she can subsequently decrypt the entire session. Ironically, a failure of the server RNG is much less devastating to the RSA handshake.*
  2. On the client or server side, during the Diffie-Hellman handshake(s). Since Diffie-Hellman requires a contribution from each side of the connection, a predictable RNG on either side renders the session completely transparent.
  3. During long-term key generation, particularly of RSA keys. If this happens, you're screwed.
And you just don't need to be that sophisticated to weaken a random number generator. These generators are already surprisingly fragile, and it's awfully difficult to detect when one is broken. Debian's maintainers made this point beautifully back in 2008 when an errant code cleanup reduced the effective entropy of OpenSSL to just 16 bits. In fact, RNGs are so vulnerable that the challenge here is not weakening the RNG -- any idiot with a keyboard can do that -- it's doing so without making the implementation trivially vulnerable to everyone else. 

The good news is that it's relatively easy to tamper with an SSL implementation to make it encrypt and exfiltrate the current RNG seed. This still requires someone to physically alter the library, or install a persistent exploit, but it can be done cleverly without even adding much new code to the existing OpenSSL code. (OpenSSL's love of function pointers makes it particularly easy to tamper with this stuff.)

If tampering isn't your style, why not put the backdoor in plain sight? That's the approach NSA took with the Dual_EC RNG, standardized by NIST in Special Publication 800-90. There's compelling evidence that NSA deliberately engineered this generator with a backdoor -- one that allows them to break any TLS/SSL connection made using it. Since the generator is (was) the default in RSA's BSAFE library, you should expect every TLS connection made using that software to be potentially compromised.

And I haven't even mentioned Intel's plans to replace the Linux kernel RNG with its own hardware RNG.

Esoteric Weaknesses in PFS systems. Many web servers, including Google and Facebook, now use Perfect Forward Secrecy ciphersuites like ephemeral Diffie-Hellman (DHE and ECDHE). In theory these ciphersuites provide the best of all possible worlds: keys persist for one session and then disappear once the connection is over. While this doesn't save you from RNG issues, it does make key theft a whole lot more difficult.

PFS ciphersuites are a good thing, but a variety of subtle issues can cramp their style. For one thing, the session resumption mechanism can be finicky: session keys must either be stored locally, or encrypted and given out to users in the form of session tickets. Unfortunately, the use of session tickets somewhat diminishes the 'perfectness' of PFS systems, since the keys used for encrypting the tickets now represent a major weakness in the system. Moreover, you can't even keep them internal to one server, since they have to be shared among all of a site's front-end servers! In short, they seem like kind of a nightmare.

A final area of concern is the validation of Diffie-Hellman parameters. The current SSL design assumes that DH groups are always honestly generated by the server. But a malicious implementation can violate this assumption and use bad parameters, which enable third party eavesdropping. This seems like a pretty unlikely avenue for enabling surveillance, but it goes to show how delicate these systems are.

The Tinfoil Hat Spectrum

I'm going to refer to the next batch of attacks as 'tinfoil hat' vulnerabilities. Where the previous issues all leverage well known techniques, each of the following proposals require totally new cryptanalytic techniques. All of which is a way of saying that the following section is pure speculation. It's fun to speculate, of course. But it requires us to assume facts not in evidence. Moreover, we have to be a bit careful about where we stop.

So from here on out we are essentially conducting a thought-experiment. Let's imagine the NSA has a passive SSL-breaking capability; and furthermore, that it doesn't rely on the tricks of the previous section. What's left?

The following list begins with the most 'likely' theories and works towards the truly insane.

Breaking RSA keys. There's a persistent rumor in our field that NSA is cracking 1024-bit RSA keys. It's doubtful this rumor stems from any real knowledge of NSA operations. More likely it's driven by the fact that cracking 1024-bit keys is highly feasible for an organization with NSA's resources.

How feasible? Several credible researchers have attempted to answer this question, and it turns out that the cost is lower than you think. Way back in 2003, Shamir and Tromer estimated $10 million for a purpose-built machine that could factor one 1024-bit key per year. In 2013, Tromer reduced those numbers to about $1 million, factoring in hardware advances. And it could be significantly lower. This is pocket change for NSA.

Along similar lines, Bernstein, Heninger and Lange examined at the feasibility of cracking RSA using distributed networks of standard PCs. Their results are pretty disturbing: in principal, a cluster about the size of the real-life Conficker botnet could do serious violence to 1024-bit keys.

Given all this, you might ask why this possibility is even in the 'tinfoil hat' category. The simple answer is: because nobody's actually done it. That means it's at least conceivable that the estimates above are dramatically too high -- or even too low. Moreover, RSA-1024 keys are being rapidly being phased out. Cracking 2048 bit keys would require significant mathematical advances, taking us much deeper into the tinfoil hat.**

Cracking RC4. On paper, TLS supports a variety of strong encryption algorithms. In practice, about half of all TLS traffic is secured with the creaky old RC4 cipher. And this should worry you -- because RC4 is starting to show its age. In fact, as used in TLS it's already vulnerable to (borderline) practical attacks. Thus it seems like a nice candidate for a true cryptanalytic advance on NSA's part.

Unfortunately the problem with this theory is that we simply don't know of any attack that would allow the NSA to usefully crack RC4! The known techniques require an attacker to collect thousands or millions of ciphertexts that are either (a) encrypted with related keys (as in WEP) or (b) contain the same plaintext. The best known attack against TLS takes the latter form -- it requires the victim to establish billions of sessions, and even then it only recovers fixed plaintext elements like cookies or passwords.

The counterargument is that the public research community hasn't been thinking very hard about RC4 for the past decade -- in part because we thought it was so broken people had stopped using it (oops!) If we'd been focusing all our attention on it (or better, the NSA's attention), who knows what we'd have today.

If you told me the NSA had one truly new cryptanalytic capability, I'd agree with Jake and point the finger at RC4. Mostly because the alternatives are far scarier.

New side-channel attacks. For the most part, remote timing attacks appear to have been killed off by the implementation of countermeasures such as RSA blinding, which confound timing by multiplying a random blinding factor into each ciphertext prior to decryption. In theory this should make timing information essentially worthless. In practice, many TLS implementations implement compromises in the blinding code that might resurrect these attacks, things like squaring a blinding factor between decryption operations, rather than generating a new one each time. It's quite unlikely there are attacks here, but who knows.

Goofy stuff. Maybe NSA does have something truly amazing up its sleeve. The problem with opening this Pandora's box is that it's really hard to get it closed again. Did Jerry Solinas really cook the NIST P-curves to support some amazing new attack (which NSA knew about way back in the late 1990s, but we have not yet discovered)? Does the NSA have a giant supercomputer named TRANSLTR that can brute-force any cryptosystem? Is there a giant quantum computer at the BWI Friendship annex? For answers to these questions you may as well just shake the Magic 8-Ball, cause I don't have a clue.

Conclusion

We don't know and can't know the answer to these things, and honestly it'll make you crazy if you start thinking about it. All we can really do is take NSA/GCHQ at their word when they tell us that these capabilities are 'extremely fragile'. That should at least give us hope.

The question now is if we can guess well enough to turn that fragility from a warning into a promise.

Notes:

* A failure of the server RNG could result in some predictable values like the ServerRandom and session IDs. An attacker who can predict these values may be able to run active attacks against the protocol, but -- in the RSA ciphersuite, at least -- they don't admit passive compromise.

** Even though 1024-bit RSA keys are being eliminated, many servers still use 1024-bit for Diffie-Hellman (mostly for efficiency reasons). The attacks on these keys are similar to the ones used against RSA -- however, the major difference is that fresh Diffie-Hellman 'ephemeral' keys are generated for each new connection. Breaking large amounts of traffic seems quite costly.

24 comments:

  1. What do you think about the possibility of kleptographic attacks, e.g., some of the client or server's random seed being exfiltrated in the client_random or server_ranom values in the Hello messages?

    ReplyDelete
    Replies
    1. exactly my thoughts. this is a well-known weak point in ssl and certainly the most effective way to get the message clear.

      Delete
  2. My bet on hardware subornation is one of the popular options being "tamper with the RNG" strategy discussed here, since the alternative of in-channel leaking of key material does produce layout changes which are potentially detectable if the chip is reverse engineered, either by the manufacturer or by a third party.

    This is especially true as, unless the channel-leaked material is protected by a public-key operation, any adversary who does this reversing will now also be able to exploit, not just have knowledge that the backdoor exists.

    E.g. there was a really good paper showing how you could hardware tamper with the Intel tRNG design, reducing it to 32 bits of entropy, without ANY layout changes, only doping changes, so the tampering could be only be detected if you took the chip apart and examined individual transistor doping.

    Or getting various chips to use Dual_EC_DRBG through economic pressure, after all, its FIPS compliant...

    The latter is particularly attractive, because of the asymmetric nature of the backdoor: unless the Chinese (or French, or Russians...) manage to get the magic numbers it remains secure. So even if the opposition knows about the sabotage, they can't use it.

    ReplyDelete
    Replies
    1. Yes, it seems to me you have three choices: either use asymmetric backdoors (like Dual_EC), use a unique backdoor key per device (increases manufacturing cost, doesn't work for software), or just make the system weak.

      On the other hand, when it comes to chips there may be enough entropy left by the manufacturing process that a chip can generate its own unique key symmetric key. But you still need to read it out.

      Delete
  3. For what it's worth, I got a government... person, drunk at a security conference... a decade ago and he told me they were breaking "128bit", "on the fly". How and with what, I don't know. But when you look at the TRILLIONS missing from the Pentagon, I've always thought computing power beyond anything imaginable.

    ReplyDelete
  4. Great post, re: squaring the previous blinding factor rather than calculating a new one, FWIW and to be fair to OpenSSL this was what Kocher recommended doing in order to *avoid* letting the timing attack back in (ref section 10 of his CRYPTO '96 paper) http://www.cryptography.com/public/pdf/TimingAttacks.pdf

    ReplyDelete
    Replies
    1. I don't see how this can be attacked, but it's at least a little less confidence-inspiring than proper blinding would be.

      Delete
  5. WRT Rc4 (and others) - if the NSA is already sniffing global internet traffic, they already have the ability to compare "known decrypted" strings with encrypted ones. How many truly unique google searches and responses are there for example? We have to stop thinking that the NSA is akin to a single hacker. They have the ability to see nearly ALL of the traffic that's flowing through the internet. If they can see plain text data for the top internet sites (and they can, they just put it into their browser), then are able to compare what they see as encrypted traffic for that same stream of data, and can then compare that to all other datastreams on the 'net.. How hard would it be to detect the patterns in rc4, or broken random generators?

    ReplyDelete
    Replies
    1. Properly encrypted (with random keys) the data streams should be different from each other even if that is the same plaintext. And when they have a weakness in RC4 or a RNG, I don't suppose they need to compare existing known plaintext + ciphertext, they can just generate them themselves if needed.

      Delete
  6. > And you just don't need to be that sophisticated to weaken a random number generator. These generators are already surprisingly fragile

    So what you're saying is the NSA folks aren't that smart, and this stuff could be done by just about any organization with a $100 Billion budget, is that right?

    ReplyDelete
  7. I never thought one can break SSL..this is socking for me and i am trying to learning more in this regards.

    Please keep sharing your thoughts in this regards

    ReplyDelete
  8. Do you have any thoughts on how they're breaking SSH?

    ReplyDelete
    Replies
    1. That concerned me too. Thinking about it, I wonder if the list of things mentioned in the brief (along with the nebulous "not limited to") indicates a weakness _necessarily_ common to each of those? In that case, I think PRNG weaknesses seem "most likely".

      Delete
  9. I don't understand how stealing the RSA keys equals decrypting all past and future SSL sessions. You need the (all) symmetric session (or sessions) keys for that. Can you explain how you derive the session keys from the RSA keys? Thank you.

    ReplyDelete
    Replies
    1. If you're not using a ciphersuite which provides forward secrecy, then the client generates the pre-master secret (which is used to derive the session key), encrypts it with the server's RSA key, and sends it to the server. So if you steal the RSA private key, you can simply decrypt the pre-master secret that's sent to the server and then derive the session key. None of this is an issue if you're using a ciphersuite with forward secrecy of course.

      Delete
    2. Thanks, but still, even without FS the derivation involves RNG no? The pre-master is not the same as the session key.

      Delete
    3. In the RSA handshake the session key is computed by combining the PMS and some random values that are visible in the handshake. Everything besides the PMS is visible from sniffing the handshake. The PMS is the only encrypted piece.

      Delete
    4. Thanks Matthew. So how can the NSA decrypt the PMS without access to the server private key?

      Delete
  10. I feel a bit stupid asking this question with all you computer buffs out there - but here goes. I am starting a job which demands total security on my computer. They have suggested I use TrueCrypt and they sent me details on how to download it. I followed these details to the letter, but now I find I cannot print anything - the printer is fine with my unencrypted laptop but it cuts out when I try to print an encrypted document. Am I right in thinking that anything I write in Word from now on is encrypted and therefore non-printable? Also I was instructed to make a disc back-up but there was too much info for one disc - so I tried to continue with disc 2 - but nothing happened. Do I need a special disc or something with masses of space? I am just a simple old granny who is trying to get to grips with things here! (Think I've managed darn well so far for my advancing years). Thanks for any feedback. BTW... my company see me as totally self-employed and they are not available to help with any problems with my computer or software. I am using a Windows 7 Professional comp.

    ReplyDelete
    Replies
    1. No you are at the right place, thanks for your question, I'm sure someone will be right with you.

      Delete
  11. It's my understanding that they aren't necessarily BREAKING SSL as they are bypassing it. Check this out: http://www.bauer-power.net/2013/09/how-nsa-bypasses-online-encryption.html

    ReplyDelete
  12. Wrt "...NSA can install malware on your computer and pwn any cryptography you choose. That doesn't interest me at all, for the simple reason that it doesn't scale well. NSA can do this to you, but they can't do it for an entire population..."

    I can't help but think this is cast aside too easily.
    Why, with the auto-update features (for 'our' security!) of modern systems is this not trivial?

    Cannot a majority of the population be blessed with "fixes" that introduce purpose build zero-days for just this purpose ?

    If I were attacking your system, had bags of cash and other leverage (a govt. has LOTS), not to mention experience coercing hardware manufatures already (your ref to the vpn etc endpoint article), this would be top of my list. Why would I not jump at the chance to deliver hard to find, ephemeral back doors, via update systems ?

    Ephemeral you ask? Becuase I can have said back doors fixed and replaced with a new one on the next update. Does this not make them harder to find, especially in closed-source systems anyway ?

    ReplyDelete
  13. My guess is the NSA uses all the above and more. With the super computers they own,
    (remember no budget) something as simple as brute force can be done in minutes vs. 2000 years on an average high end consumser PC. Another factor, the are filling the pockets of every major ISP and E/commerce site out there. I predicted Walmart as a data mine for them about five years ago and just recently heard that they are on that "coveted" list of the NSA. So that means they have had their sniffers sniffing Walmart for at least a decade. Most of what they "steal" is just paid for under the table. Its the most cost effective way. How about that Jet, Yacht, vacation, summer home, new fleet of cars, 24 hour armed security and more. Mere peanuts to just pay up instead of play down???

    ReplyDelete
  14. Here is how they do it:

    http://www.politaia.org/wp-content/uploads/2013/12/Full-Disclosure-NSA-GCHQ-Hacks.pdf

    You thought it was some sophisticated attack. It was script kiddy level shit with rootkits, in collusion with your ISP. That's it.

    ReplyDelete