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.