Public key crypto, and what "NSA foils encryption" might mean

On September 5th, the Guardian, the New York Times and ProPublica published the latest Snowden documents. The headline was “N.S.A. Able to Foil Basic Safeguards of Privacy on Web”. The program is called Bullrun, and the documents describe a multi-year effort, with a budget in the hundreds of millions of dollars, to defeat the encryption that protects most internet traffic.

A lot of people read that headline as “the NSA has broken the math”. I don’t think that’s what the documents say, and to see why, it helps to know what the math actually is. So here’s public key crypto with small numbers, and then the places where the attacks probably are.

Talking privately in public

Two people want to talk privately over a channel that anyone can listen to. With ordinary symmetric encryption, like AES, they need a shared secret key first. But how do you agree on a secret key when everyone can hear you? For most of history the answer was “meet in person”. In 1976, Whitfield Diffie and Martin Hellman published a better one.

Diffie-Hellman: agreeing on a secret in public

The usual illustration uses paint. Mixing paint is easy, and un-mixing it is practically impossible.

With numbers, “mixing” is modular exponentiation. Alice and Bob publicly agree on a prime p = 23 and a base g = 5.

1. Alice picks a secret a = 6 and sends 5⁶ mod 23 = 8.
2. Bob picks a secret b = 15 and sends 5¹⁵ mod 23 = 19.
3. Alice computes 19⁶ mod 23 = 2.
4. Bob computes 8¹⁵ mod 23 = 2.

They both get 2, because (gᵇ)ᵃ = (gᵃ)ᵇ. An eavesdropper has seen 23, 5, 8 and 19. To get the secret, they’d need to recover 6 from 8, which is the discrete logarithm problem. With a 23, you can just try every value. With a 2048-bit prime, nobody knows a way to do it in any reasonable time.

RSA: a lock anyone can close

RSA, from 1977, solves a slightly different problem. It gives you a public key that anyone can use to encrypt a message, and a private key that only you can use to decrypt it. The textbook small example:

• Pick two primes: p = 61, q = 53. Multiply them: n = 3233.
• Compute (p−1)(q−1) = 3120, and pick a public exponent e = 17 that shares no factors with it.
• Find the private exponent d = 2753, where 17 × 2753 = 46801 = 15 × 3120 + 1.
• Public key: (3233, 17). Private key: 2753.

To encrypt the message 65: 65¹⁷ mod 3233 = 2790. To decrypt: 2790²⁷⁵³ mod 3233 = 65.

Anyone can encrypt with the public key. To compute d, you need (p−1)(q−1), which means you need to know p and q, which means you need to factor n. Factoring 3233 is trivial. Factoring a 2048-bit n is, as far as anyone publicly knows, out of reach for decades.

How TLS uses both

When your browser connects to an HTTPS site, it doesn’t use RSA or Diffie-Hellman to encrypt your traffic. They’re far too slow. They’re used to agree on a symmetric key, and then AES or RC4 does the bulk encryption. The server’s certificate, signed with RSA, is what proves you’re talking to the right server and not someone in the middle.

So where would you attack?

If the math is sound, a well-funded attacker goes around it. Bruce Schneier, who has seen some of the documents, wrote in the Guardian: “Trust the math. Encryption is your friend.” And, in the same piece, “The math is good, but math has no agency. Code has agency, and the code has been subverted.” Here are the places I’d look, roughly in order of how cheap they are:

1. Get the keys. Ask nicely, with a court order, or hack the server and take the private key. There’s no math involved. And without forward secrecy, which I wrote about in June, one stolen RSA key decrypts every recorded session from the past.
2. Weaken the random numbers. Every key above started with a random choice: a, b, p, q. If the random number generator is predictable, the keys are predictable, and the rest of the math doesn’t matter. This is where the most specific allegation in the reporting points. The Times reported that the NSA influenced a NIST standard so that it contains a weakness the agency can exploit. That fits Dual_EC_DRBG, a random number generator that Dan Shumow and Niels Ferguson showed back in 2007 could contain a backdoor: if someone knew the relationship between two of its constants, they could predict its output. NIST has now reopened the standard for public comment and told people not to use it.
3. Exploit implementations. Padding oracles, timing side channels, bugs in OpenSSL, weak defaults. Most real-world crypto breaks have been here. Every CTF crypto challenge I’ve done has been some version of this too. In last year’s Stripe CTF, one level had an API that signed requests with SHA1(secret + message). SHA-1 is fine, the secret was fine, and you could still forge requests with a length extension attack, because of how the two were glued together. Nobody broke any math, the construction was just wrong.
4. Choose weak parameters. A lot of servers still use 1024-bit RSA and Diffie-Hellman keys. These are believed to be within reach of a nation-state budget, if not yet anyone else’s.
5. Insert backdoors in products. The documents also describe working with companies to “insert vulnerabilities into commercial encryption systems”. If that’s true, the question is which ones, and we don’t know.

What I’d actually do

• Use well-reviewed open-source implementations, and keep them patched.
• Turn on forward secrecy. Recorded traffic is the big prize, and forward secrecy takes it away.
• Retire 1024-bit keys. Use 2048-bit RSA or elliptic curves.
• Don’t use Dual_EC_DRBG. It was always slow and suspicious. Check whether any library you depend on defaults to it.
• Be a bit more skeptical of standards that arrived without a public explanation of their constants.