Adam Bozanich Did Not Uncover An NSA IPsec Conspiracy: Diffie Hellman Parameter Validation Explained

Thomas Ptacek | September 25th, 2007 | Filed Under: Defenses, New Findings, Uncategorized

introduction

Alice and Bob want to arrange a tryst. Bob’s wife Eve is sniffing their Instant Messenger traffic.

No problem! Alice and Bob will encrypt their messages with AES-256-CBC. Eve won’t be able to decode the traffic before the heat death of the universe.

One small problem: what AES key to use? Actually: not a small problem. No matter what key Alice comes up with, she can’t send it to Bob without exposing it. She can’t encrypt the key; chicken and egg.

number theory f.t.w.

There’s a solution to this problem. Alice and Bob will run the Diffie-Hellman protocol (DH) to securely exchange a key.

Alice and Bob agree on a prime number p, and a smaller number g with a special relationship with p ([1]). These are parameters to Diffie Hellman. “23” and “7” are valid p and g parameters. So are “37” and “5”. They aren’t secret. Think of them like a “version” of DH that Alice and Bob agree to use.

For the sake of argument, Alice and Bob agree on “37, 5” DH.

Bust out your calculator. I’ll be Bob.

Generate a random number a, modulo 37 (divide your number by 37 and a is the remainder).

I’ll do the same thing to generate a different b.

Now take your a and make A. Raise 5 to the a‘th power, modulo 37 (in Ruby, do “(5 ** a) % 37”. I’ll do the same with b to make B.

A is your public key. a is your private key. Send me A. I’ll send you B. It’s 29.

Take 29 and raise it to the a‘th power mod 37 (I don’t know what a is; it’s your private key, so I can’t tell you what you’ll get.) That’s “(B ** a) % 37” in Ruby. I’ll do the same with B.

We just arrived at the same number. Was your private key 7? We came up with 8. Was your private key 26? We came up with 27. 27 is our session key.

Funny thing about our session key: you know it, and I know it, but Eve can’t know it. Even though we did this computation out in the open. This is the deep magic, yo.

quick aside:

Well OK, Eve totally knows what number we came up with, because we used a ridiculously small p. Instead of 37, 5, try this:

FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF

Just use 2 as g. Remember now that your private key a is a random number modulo this huge p. It will also be huge.

Raising a number to a power modulo another number is modular exponentiation (modexp). A modexp is straightforward to compute.

The opposite of exponentiation is a logarithm. Taking a log mod another number is a discrete logarithm. Discrete logs are extremely hard to solve. With large enough numbers, “racing heat death of the universe” hard; “every atom in the Solar System is a computer trying to solve it, still unsolvable” hard.

So you have two closely related operations, exponentiation and logarithm mod p, one of which is easy to compute and one of which is hard. This is a cryptographic building block and the foundation of DH.

back to alice and bob

We got 26 for our session key. Let’s say we MD5 the text value of “26”, to get “4e732ced3463d06de0ca9a15b6153677”. Tack a “0x” at the front of that value, and we now have a 128 bit number we can use as an AES key. Eve can’t know we came up with 26, and so can’t know what the MD5 of the session key is, and so doesn’t know what our AES key is.

Problem solved! Cue arbitrary foreshadowing device. We’ll come back to this.

what adam bozanich found

Adam works for Mu Security. Mu is writing an IKE fuzzer. IKE is a key exchange protocol for IPSec. IKE is probably one of the worst protocols ever to come out of the IETF, and I’m not going to explain it.

What you need to know is that IKE generates the keys that secure dynamically-keyed IPSec tunnels (layer-3 VPNs), and that IKE uses DH to do that.

Adam remembers a DH gotcha. When Alice and Bob run DH, they have to be careful not to allow any of the parameters —- p, g, A, or B —- be zero or one mod p.

Why’s that? Bust out your 37, 5 DH math again. Alice’s session key computation is “(B ** a) % 37”. Bob sends B. If B is 1, the session key is… wait for it… 1. If B is 0, it’s 0. No matter what Alice’s private key is.

If Eve sees a public key that works out to 0 or 1 mod p, Eve knows what the session key was; it’s zero or one. Remember that there are infinitely many values that work out to 0 or 1 mod p. 0 is 0 mod 37. So is 37. So is 74. And so on. Bob could have sent any one of those bad public key values.

Alice and Bob are supposed to check for this. Adam looked at a bunch of IKE implementations. None of them did.

context

This is a well-known problem. It’s in Eric Rescorla’s DH RFC. It’s in an ANSI standard. You can’t use p - 1 mod p either. You also have to be careful with g; broken values will generate subgroups, not the entire group. And real DH implementations have optimizations that can be attacked mathematically if you’re not careful.

Just because it’s well known doesn’t mean people won’t make the mistake. That’s why Nate and I pointed the problem out last year (almost to the day!).

The general class of problems we’re talking about is parameter validation. You attack them by looking at the messages a protocol exchanges, and sending malicious bad values that will break the computation.

Are you a security researcher? Go look for some of these bugs. They rock. More in a sec.

but back to adam

So it’s interesting that IKE implementations don’t validate parameters, but it’s not particularly meaningful.

IKE Bob can send IKE Alice a bad public key. This key will cause Eve to know the session key Bob and Alice use. But why would Bob do this? He’s negating his own security!

Eve can try to inject a bad public key into the session. But so what? If Bob and Alice don’t agree on A and B, the public keys, they can’t run DH. Maybe a different attacker, Mallory, can get between Alice and Bob and proxy the messages. She’ll be a “man in the middle”.

In this case, Mallory wins. No matter what parameters you use and what bugs your code has, Mallory beats DH. This is a basic challenge with DH. The solution involves more crypto.

DH is a useful building block, but protocols that use DH usually depend on some other operation to ensure security. For instance, DH SSL uses RSA certificates to beat Mallory. DH is useful to SSL; it gives you perfect forward secrecy by not tying your SSL session key to a fixed RSA key that can be compromised. But DH SSL depends on RSA for security.

So it’s not a good sign that IKE implementations aren’t smart enough to do parameter validation. But it doesn’t make much of a difference. The “vulnerability” allows an IKE participant to elect an insecure session.

accident? or… murder!

Adam wants to take this somewhere. So he writes a blog post suggesting that the uniform weakness of IKE implementations could be evidence of a conspiracy.

I don’t think he’s being entirely serious, but here’s his argument: the NSA —- no wait, it’s 2007, let’s make it the RIAA —- demands the ability to snoop on everyone’s IPSec sessions. They get all the IKE vendors to ship backdoored IKE agents. On some secret signal, the IKE agent will send public keys that work out to 0 mod p, and the RIAA can break these sessions with the sniffers they’ve installed at every exchange point on the Internet.

There’s a reason this is silly besides the fact that it involves backdooring one of the least important security mechanisms on the Internet: it’s a dumb attack.

Mallory knows p and g. So does Seth, the secops guy. Mallory can watch for A and B values that are 0 mod p. So can Seth. Why would the RIAA install a secret backdoor you could write an IDS signature for?

There are much more subtle things you can do to backdoor DH. Start with, IKE implementations can just be backdoored with a known private key value, or a root backdoor private key and an algorithm for generating variants of it. Move on from there.

This isn’t a conspiracy. This is just ignorance.

and I know that because…?

Because this vulnerability happens all over the place.

Take SRP for example. SRP is a derivative of DH. Alice is a client, Bob is a server. Alice and Bob know Alice’s password. Alice generates a public key that is related to the SHA-1 hash of the password. Alice and Bob do a DH exchange to prove Alice knows the password, and if the exchange works, Alice wins.

Mallory sends Bob a public key of 0 mod p. Mallory wins. She can log in as Alice without knowing Alice’s password.

This vulnerability is well known. It’s in the RFC for SRP. But I’ve tested SRP implementations written by smart security people, and they’ve had this vulnerability. (Due credit: I got this trick from Trevor Perrin, via Nate Lawson).

Compare the SRP vulnerability to the DH vulnerability. The SRP parameter validation problem is really, really bad. It’s auth bypass. The DH vulnerability is just a dumb way to backdoor an IKE agent.

well played, adam

IKE is a mess of a protocol. Crypto parameter validation attacks are totally underappreciated. Adam’s blog post is cool. It was smart of him to check for this, and interesting that he found it.

and what have we learned?

Not much about IKE. It’s as secure as you thought it was before you heard about Adam’s finding.

Hopefully a lot about crypto, though. Like I said, we wrote a post last year talking about parameter validation tricks for DH, SRP, Elliptic Curve, and RSA.

Forget about algorithmic attacks and advances in factorization and quantum computers. Parameter validation attacks are a systems flaw; systems depend on code, and code is riddled with bugs. All bugs are vulnerabilities. Most… any? cryptosystems will be beaten by stupid bugs like this.

Go look for them!

---

[1]: g is a primitive root modulo p. For values of x from 0 to p - 1, raise g to x modulo p. If g is a primitive root modulo p, you’ll end up with every number between 1 and p - 1, in some order. For instance, the following Ruby snippet asks if 3 is a primitive root mod 37.

lst = [] ; 0.upto(36) {|d| lst << ((3 ** d) % 37)} ; lst.sort

elicits the following output:

[1, 1, 1, 3, 3, 4, 4, 7, 7, 9, 9, 10, 10, 11, 11, 
 12, 12, 16, 16, 21, 21, 25, 25, 26, 26, 27, 27, 28, 
 28, 30, 30, 33, 33, 34, 34, 36, 36]

2’s missing. So’s 5 and 6, etc. 3 is not a primitive root mod 37. Now try 5:

lst = [] ; 0.upto(36) {|d| lst << ((3 ** d) % 37)} ; lst.sort

[1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 
 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 
 29, 30, 31, 32, 33, 34, 35, 36]

All the numbers between 1 and 36 are there. 5 is primitive root mod 37.

Why is this important? Because if you’re working with a 1024 bit prime, you want session key values to possibly be any one of those 1024 bit values. Another word for “primitive root” is generator. Generators generate the entire group of values mod p. Bad values of g generate subgroups, with fewer than 1024 bits of possible values. The worst g values generate only two possible values!