Interesting . . . A Few Thoughts on Cryptographic Engineering: How does the NSA break SSL? Monday, December 2, 2013 (source)A few weeks ago I wrote a long post about theNSA'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. Alotofthings, 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, theNSA BULLRUN briefing sheetmentions 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 thatit 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. Hence our focus here will be primarily on passive eavesdropping. For the same reason, we're not going to worry about man-in-the-middle (MITM) attacks. While we know thatNSA runs these, they're a very targeted sort of attack. Not only are these attacks detectable if you do them at large scale, they don't comport with what we know abouthow NSA does large-scale interception -- mostly via beam splitters and taps. The rules above aren't absolute, of course. For example, we will consider limited targeted attacks on servers, provided they later permit mass decryption of large amounts of traffic; e.g., decryption of traffic to major websites. We will also consider arbitrary modifications to software and hardware -- somethingwe 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 builtnext to BWI. We'll start with the 'practical' attacks. 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 decryptevery 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 knowthat GCHQ and NSA areperfectly 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 knowNSA/GCHQ have been collaborating with hardware manufacturersto '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 thathere.) 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' --whichinclude 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 conditions in which the attackercan get close. The most obvious exampleinvolves virtualized TLS serversin the cloud setting, where a clever attacker may share physical resources with the target device. A second class of attackuses remote timing informationto slowly recover an RSA key. These attacks can be disabled via countermeasures such asRSA blinding, though amusingly, some 'secure' hardware co-processors may actuallyturn these countermeasuresoff 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: 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.* On the clientor 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. 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 maintainersmade this point beautifullyback 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 inSpecial 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 thegenerator 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 mentionedIntel's plans to replace the Linux kernel RNGwith its own hardware RNG. Esoteric Weaknesses in PFS systems.Many web servers, includingGoogleand 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 beshared 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 ispure 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 itdoesn'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 ispocket changefor 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 wesimply 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 inWEP) 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 trulynew 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 asRSA 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 likesquaring a blinding factorbetween 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 reallycook the NIST P-curvesto 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 agiant supercomputer named TRANSLTRthat 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 'extremelyfragile'. 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. I sure hope so. 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. Posted byMatthew Greenat8:55 PM
You're only safe until they start looking for you. Privacy is only permitted those unimportant enough to fall below their threshold for "communications of interest."
This is why most of my posts are unintelligible ramblings, on relatively insignificant topics. I'm protecting my privacy.
That BULLRUN briefing sheet is probably the most highly classified/controlled document that I have ever seen hit the public domain. Those particular classification caveats are designed to restrict the access to that document to a very small (relatively) group of people. There were a lot of groans to be heard at the Agency when that document hit the newspapers.
