The Debian OpenSSL PRNG bug and DHE

| Comments (1) | COMSEC
Some colleagues (Hovav Shacham, Brendan Enright, Scott Yikel, Stefan Savage) and I have been tracking the aftermath of the Debian OpenSSL PRNG bug (see Hovav's Work-In-Progress presentation at USENIX WIP here). One of the questions that comes up is what you can do with this Here's what's obvious (I'm talking about SSL only below):
  • If the server key was generated with the weak PRNG, you can guess the server key and:
    • Impersonate the server.
    • Passively decode traffic encrypted with static RSA (which a lot of traffic is). This doesn't help with ephemeral Diffie-Hellman (DHE).
  • If the server key is strong but the server has a weak PRNG:
    • If the server has a DSA private key, you can recover it. This isn't much of an issue for SSL but SSH does use DSA reasonably often.
    • This doesn't directly allow you to recover traffic in static RSA mode. The reason for this is that in static RSA mode, the client generates the only secret data (the PreMaster Secret).
  • If the client stack is insecure, then you could in principle guess the client's random values. However, none of the major browsers use OpenSSL, so this is probably limited to non-browser clients.

But this raises the interesting question: can you passively attack DHE mode? In this mode, the server generates a fresh DH key for each transaction. Knowing the server's long-term private key doesn't help here— that just lets you impersonate the server. So, the implementation used to generate the long-term key doesn't matter. However, unlike RSA DHE requires the server to generate secret random values, so if the server is running a broken version, this may give us a way in.

We're not the only ones to think along these lines: along these lines: Luciano Bello describes a partial attack and has posted a patch to Wireshark to attack DHE connections:

If an eavesdropper can explore the complete private key space (the all possible numbers for Xc or Xs), he/she will be able to get access to the shared secret. With it all the communication can be deciphered. That's what this patch can do.

A Wireshark with this patch and a list of possible private keys will try to brute force the share secret. If one of the parties is using the vulnerable OpenSSL package the communication is totally insecure and will be decrypted.

Bello demonstrates attacking a connection between a broken client and a decent server. However, the attack as described doesn't work with secure clients (which, as I said, is pretty much any browser) and broken non-toy Web servers (the situation is different for non-Web servers (e.g., IMAP and POP servers which run out of inetd): even if the server's PRNG is broken, there isn't a fixed-size list of keys it generates.

To understand why, you need to understand the vulnerability better. Effectively, the vulnerability stopped any invocations of RAND_seed() from mixing data into the PRNG. The only time new seed data gets mixed in is when you get new randomness values via RAND_bytes(). Each time you call RAND_bytes() the current process ID gets mixed into the PRNG. So, for a given PID and a given sequence of invocations of RAND_bytes(), you always get the same string of random values. These values are (statistically) unique, but predictable: you can say "the nth value will always be one of the following 2^15 values depending on the PID". However, it should be clear that even for a given PID, you can generate an arbitrary (well, almost) number of distinct values. So, if you had a process which generated a million DH keys in sequence, they'd all be different. Unfortunately for Bello's attack, this is exactly how many real Web servers work. For instance, Apache w/ Mod_SSL forks off a bunch of long-lived server processes which each handle many requests. Bello's attack would potentially work on the first connection, but the second connection would not be on the key list. You need another 2^15 values to handle the second connection. We've confirmed this by setting up a server, connecting to it, and pulling out more than 2^15 distinct public keys. So, you need to do something more complicated.

What follows is our initial analysis of Apache with Mod_SSL, which we're currently working on confirming. The details may not be quite right, but I suspect the general contours are.

With Apache and Mod_SSL it turns out that RAND_bytes() gets called in the parent process before it forks off the subprocesses, so each subprocess has both the parent process and the subprocess PIDs mixed in. So, you have 2^30 distinct PID combinations and therefore random value streams to deal with. In general, however, since the parent process forks off an initial set of children immediately and children aren't killed or started that often, the entropy is probably a lot less than 2^30, and even 2^30 is still searchable if you've got even modest computer power.

So, if you get to observe the server from the time of startup, you're in fine shape. As soon as you observe a connection, you check your table of known keys (basically a bigger version of Bello's table that takes into account both parent and child PIDs). [Actually, you can save some compute time by building a table of ServerRandom values, which saves you doing the modular exponentiation to compute the public key for a given private key.] That tells you what the PID pair of the server process you're observing is, and of course it's current state. You've got the private key so you can decrypt the connection. To handle the next connection to that server process, you roll the PRNG forward to compute the next expected key. When the next connection comes in, you repeat this process, so at any given time you know the next value for each active PID pair.

If you're not lucky enough to see the server from the time of startup, then life gets more complicated, since you don't know where in its random number stream each server process is. So, you would need to try candidate numbers of connections. Unfortunately, there's another complicating factor: TLS handshakes with Diffie-Hellman and RSA key exchanges involve different patterns of random values: the DH exchange involves an extra 128-byte random value for the Xs (the DH private key) No problem you say, we'll just compute reasonably sized sections of the random value stream and look for matches within the probable zone. Unfortunately, this doesn't look like it's going to work. As I said earlier, each time you invoke RAND_bytes() the PID gets mixed into the PRNG. In other words: RAND_bytes(128); RAND_bytes(32); does not produce the same 160 bytes as RAND_bytes(32); RAND_bytes(128);. This means that every connection introduces one bit of entropy: whether DHE or RSA was used. If you're not observing these connections, this entropy quickly adds up and it becomes impractical to search the space. It's possible that there's some analytic attack on the PRNG that would let you reduce this search space, but nothing popped out at us on casual inspection. This suggests that if you have a server which only does DHE, you can attack individual connections, but if it does both DHE and RSA, you need to observe all the connections from the server to make sure you know the DHE/RSA pattern.

I should mention one more issue: OpenSSL uses a random blinding value to stop remote timing attacks on static RSA. If you can predict the blinding value, then it may be possible to mount a timing attack on the static RSA key, even if it was generated with a strong PRNG. We're still looking into this as well.

As I said at the beginning all this is preliminary and only partly confirmed. We're hoping to have definitive results sometime in the next few weeks and be publishing soon after that.

UPDATE: Fixed Luciano's name to be "Luciano" from "Lucian". Also, I should add that the Wireshark work was done by Paolo Abeni and Maximiliano Bertacchini as well as Luciano Bello.


You may want to add to your preso that the exponent selection (3 or 4, the '-f' flag) also matters; doubling the space; and that there are three distinct random state keeping options with $HOME/.rnd - not writable (common for users like 'www'; there, but empty and not mutable or fully RW. This increases the size of your keyspace again somewhat.

Leave a comment