FREAK (Factoring RSA Export Keys) is a vulnerability in several
implementations of SSL that was discovered at the end of 2014/beginning of
2015 by a team from INRIA, IMDEA and
Microsoft Research. Much of this post was guided by their excellent website and Matthew Green’s very
accessible write-up
of the attack. I have tried to add a little flavour and detail on some
concepts directly and tangentially related to the attack as well (the fix to
OpenSSL, Perfect Forward Secrecy, Replay Attacks).
After watching “The Imitation Game”, the post-World War II US government
realised that cryptography was a big military deal. They immediately and
ham-fistedly regulated
the export of cryptographic technology on grounds of national security.
SSL, the encryption protocol that protects all HTTPS connections everywhere on
the internet, was developed in the 1990s at Netscape. Regulation still required
that RSA keys used to encrypt traffic travelling out of the US be limited to 512
bits, the intent of which was to ensure that the government could still
tractably spy on foreign communication at will. SSL was designed in such a way
that it could support multiple different ways of generating and authenticating a
“shared secret” (more on this later), one of which was the deliberately
hamstrung, 512-bit “Export RSA”.
Time went on, t-shirts became
designated munitions, and the government started gradually relaxing this
inadvisable regulation. However, for backwards-compatability, Export RSA lives
on in the SSL spec as a (theoretically) rarely-used way to create unusably
weakly encrypted connections. Until recently, this was believed to be peaceful.
As part of the connection negotiation process, the client specifies which
ciphersuites (eg. RSA, Diffie-Hellman) they are prepared to use to exchange a
shared secret with the server. The server chooses the most secure of these that
they support (if any), and the connection is negotiated and the shared secret
exchanged using this suite. Very few clients were believed to be prepared to
accept Export RSA, and almost no servers were believed to offer it as an option.
It was a dormant, inaccessible relic.
In reality, at the time of FREAK’s reporting, 36.7%
of sites using SSL certificates trusted by major browsers were shown to offer
Export RSA. This is alarming. But still, whilst all complete SSL
implementations had to include support for Export RSA in order to comply with
the SSL spec, very few credible browsers would ever actually ask to use it. So
it should still have been very unlikely that an SSL connection would ever use
Export RSA.
However, there was a bug. Several SSL implementations, including OpenSSL,
allowed a Man-In-The-Middle to trick clients and servers into using a flimsy,
straightforward-to-brute-force
512-bit key, even when the client had explicitly stated that it had no interest
in such nonsense. Weak encryption is about as good as no encryption, and any
connection tricked in this way would essentially be plaintext to the attacker.
A client wants to open an SSL connection with a server. Little do they know that
there is a Man lurking In The Middle.
1. ClientHello
The client sends the ClientHello. This contains no sensitive data, and is (by
design) a plaintext message with information including the set of cipher suites
the client is prepared to use.
2. MITM Part I
The MITM intercepts the plaintext message, and changes it to request an Export
RSA (and only Export RSA) ciphersuite.
3. ServerHello
A server that does not offer Export RSA will see that it is not going to be able
to agree on a ciphersuite with this cavalier client, and will fail the handshake
here. However, one of the 36.7% servers that was inadvisably configured to be OK
with it will happily respond with the ServerHello, supplying information
including its SSL certificate.
4. Sending the ServerKeyExchange
For normal RSA, after receiving the ServeHello the client would already have all
the information it needs. It would generate the Pre-Master Secret (more on this
later), and encrypt it using the server’s (minimum 1024-bit
or greater) public key from its SSL certificate.
But for Export RSA, a weaker RSA key-pair than the one on the Server’s SSL
certificate is required. The server therefore generates or retrieves a 512-bit
RSA key-pair (more on this later too). It signs the new public key with its SSL
certificate’s private key to authenticate it to the client, and then sends the
512-bit key and signature in an optional ServerKeyExchange message. Of course,
our MITM is watching this exchange…
5. Receiving the ServerKeyExchange
The client receives the ServerKeyExchange, essentially a message from the Server
saying “hey, here’s that crappy Export RSA key you asked for!” In an ideal
world, the client should say “woah, I didn’t ask for this” and error out,
shutting down the attack there and then.
However, the bug in OpenSSL (amongst other implementations) meant that this did
not happen, and the client would accept and use this weak key for the rest of
the handshake.
6. Encrypting the Pre-Master Secret
In both normal and Export RSA, the Master Secret, used for symmetric encryption
of all messages in the rest of the connection, is generated using:
The Pre-Master Secret
The ClientRandom (a nonce sent in plaintext in the ClientHello)
The ServerRandom (another nonce sent in plaintext in the ServerHello)
(more on the details of the Pre-Master Secret and the purpose of the nonces
later).
The Pre-Master Secret is a random string, generated by the client. The client
encrypts it using either the Server’s SSL certificate public key (in normal RSA)
or the 512-bit public key from the ServerKeyExchange (in Export RSA). It then
sends it to the Server, allowing them to both generate the same Master Secret.
It is the only one of the inputs that an eavesdropper does not (or should not)
know. If a MITM could recover the Pre-Master Secret then they would also be able
to generate the Master Secret, and trivially read/modify the entirety of the
connection.
The only thing standing between them and breaking the connection wide open is
the fact that the client encrypted the Pre-Master Secret using a public key, and
they do not know they corresponding private key. In normal RSA, private key
calculation is currently computational infeasible, and so everything is fine.
But in 512-bit Export RSA, factorising
the public key to obtain the private key is not a particularly difficult
task, and can be done using about $100
of AWS computing time.
The MITM therefore takes the public key from the ServerKeyExchange, forks over
their $100, and a few hours later they have the private key, Pre-Master Secret,
and Master Secret. They can decrypt and read all of the messages passed between
client and server, including passwords, credit cards details and Steve
Steveington’s salacious Tinder messages. In fact, things are even worse than
this (see later).
The OpenSSL fix
The vulnerability was fixed by this
rather short commit. My C is somewhere between bad and very bad, but it is
actually fairly straightforward to see how it works.
In ssl/s3_clnt.c, a file dealing with the client-side half of the SSL
handshake, we see the addition of a new if-clause:
#ifndef OPENSSL_NO_RSA
if(alg_k&SSL_kRSA){/* Temporary RSA keys only allowed in export ciphersuites */if(!SSL_C_IS_EXPORT(s->s3->tmp.new_cipher)){al=SSL_AD_UNEXPECTED_MESSAGE;SSLerr(SSL_F_SSL3_GET_SERVER_CERTIFICATE,SSL_R_UNEXPECTED_MESSAGE);gotof_err;}
This block is called as part of ssl3_get_key_exchange(view),
and whilst I have not traced this all the way to the top of the call-stack, my
assumption is that this function (or at the very least the quoted block) is only
called if the Client receives a ServerKeyExchange message.
alg_k is set to s->s3->tmp.new_cipher->algorithm_mkey(view),
a long denoting the key exchange algorithm in use. SSL_kRSA is another
constant long that represents RSA key exchange, and thus if(alg_k & SSL_kRSA) is a bitwise-and operation that is here functionally similar to
if(alg_k == SSL_kRSA), or simply “if we are using RSA key-exchange”.
The if-clause added by the commit reads if (!SSL_C_IS_EXPORT(s->s3->tmp.new_cipher)), or simply “if we are not using
Export crypto”. And if we are indeed not using Export crypto, we wisely error
out.
Since we believe that this code will only be called if the client receives a
ServerKeyExchange message, the overall effect is simply:
“If the Client receives a ServerKeyExchange message for a handshake that it
believes is using non-Export RSA, abandon handshake.”
We are safe again. Until the next vulnerability.
Further very interesting details
Congratulations, you now understand the basic mechanics and fix behind FREAK!
Read on to learn about the significance of the Pre-Master Secret, what we mean
by Perfect Forward Secrecy, and why Export RSA does not give us it even when you
think it might.
Pre-Master Secret and Master Secret
Recall that the Master Secret is the key used to symmetrically encrypt every
message between client and server in the rest of the post-handshake connection.
Securely generating a Master Secret that is shared between a client and an
authenticated server is essentially the entire point of the SSL handshake. It is
Very Important.
We want to make sure that the Master Secret is generated from:
Secret information known only to the Client and Server (the Pre-Master Secret)
Information generated by the Client (the client_random nonce)
Information generated by the Server (the server_random nonce)
The need for the secret information is obvious - the Master Secret must be
generate-able only by the Client and Server. On the other hand, the nonces are required to prevent
a “Replay Attack”.
Suppose that we removed the nonces from the Master Secret generation, and
generated it from the Pre-Master Secret only. Now consider a MITM attacker
observing the handshake and all subsequent messages sent over the connection.
The MITM could later send exactly the same ClientHello, and get back essentially
the same ServerHello as in the previous, legitimate connection. For an RSA
handshake, she could respond with exactly the same ClientKeyExchange, containing
exactly the same encrypted Pre-Master Secret. Since the Master Secret is
generated using only the Pre-Master Secret as input, the Master Secret for the
MITM’s connection will be exactly the same as it was for the legitimate
connection! The MITM can therefore re-send the same encrypted messages that were
sent over the legitimate connection, and the Server will decrypt them and
believe that it is receiving real messages from the legitimate Client. The
Server may therefore charge the Client’s credit card twice, send messages twice,
or otherwise mistakenly repeat actions.
Note that the MITM has no idea what the messages she is replaying actually say,
and still has no way to actually decrypt and read them. However, she knows that
they mean something to the Server, and this is more than enough to do some
dastardly damage. Interestingly, because the Client is responsible for
generating the Pre-Master Secret, the mirror-image attack, where the MITM
replays the Server’s messages to the Client, could never work.
The nonces make sure that each Master Secret is different. Now when the MITM
sends the same ClientHello, even with the same client_random, the server will
reply with a different server_random to the handshake being replayed. Whilst
the MITM is welcome to send the same encrypted Pre-Master Secret, the new
server_random means that the Master Secret will be different, and so any
messages encrypted with the old Master Secret become unintelligible nonsense.
The Replay Attack is thwarted.
Perfect Forward Secrecy
Consider normal RSA. Every message over a connection negotiated using the same
server SSL cert relies on the secrecy of the certificate’s private key. If that
key ever becomes known, even many years after the connection is dropped, every
message that was ever encrypted by the certificate becomes trivially
decryptable. Nobody can know what the future holds or who is storing your
communication, and this is potentially a very scary proposition.
However, protocols possessing “Perfect Forward Secrecy”
are robust to the compromise of any long-term keys (like an SSL cert private
key) used in the derivation of their session keys. Consider Export RSA. In
potentia (NOT in practice) every Export RSA connection negotiated by the same
server could be protected by a different 512-bit key pair. The function of the
SSL cert is simply to sign the 512-bit public key and prove to the Client that
it was generated by the Server. The private key could be thrown away at the end
of each connection, and no one could ever directly discover the private key that
protected it. Unfortunately, as we know, in the case of Export RSA this is no
comfort at all.
Perfect Forward Secrecy can be achieved in a useful and tractable way using
Diffie-Hellman key exchange to generate the Pre-Master Secret, instead of RSA.
The high-level process is conceptually
fairly simple, and allows the client and server to secretly agree on a
Pre-Master Secret via a process that cannot be directly reconstructed once
various internal data that does not travel over the wire between them is erased
from their internal memory. Once again, the Server’s SSL cert is only used to sign
the Server’s contribution to the process, to prove to the Client that the shared
secret it has just generated is indeed shared with the Server, and not some
other entity. If the private key were one day compromised, it would not help an
attacker decrypt any past connections that they had observed
We start to see an interesting pattern emerge - we can either:
Use the server’s SSL cert directly as the session keys that actually encrypt
the data on the wire. In this case, the Client knows that the Server is the only
one with the private key corresponding to the public key it used to do the
encryption.
Generate the session keys some other way, and use the server’s SSL cert
for signature only (rather than for any encryption) to verify to the client that
it has negotiated with the right person.
In practice, RSA is almost never used in this second “ephemeral” way. Generating new RSA
keys is computationally expensive, and so most servers do not generate new
512-bit keys for each new Export RSA connection. By default, Apache mod_ssl will
generate a single 512-bit key at startup, and reuse that key for each Export RSA
connection until it is restarted.
Note that not only does this mean that the Forward Secrecy of Export RSA is much
less than Perfect (the session keys used in each connection are not immediately
thrown away, and live for a substantial amount of time after the end of the
connection), but it also means that once a MITM has factorised one 512-bit
Export RSA key used in one connection by a server, they now probably know the
key used for all connections to that server for a long time to come. This
enables them to read all the connections to a server whilst expending almost no additional computational
power, and enables them to read AND modify messages in either
direction in realtime, making widespread and destructive exploitation much easier.
Conclusion
It is just incredible that an eavesdropper can watch every single message that
ever passes between a client and a server and still have no idea what they are
saying. It’s as though you could invite your mortal enemy to a conference about
how much of a dick he is, spend the first lecture agreeing on the codes that you
and the other delegates will use whilst he watches, and then all proceed to vigorously deride his
personal hygiene him without him having any idea what you are saying.
But the margin for error is slim, and any slight imprecision can blow the whole
scheme wide open. Heartbleed, BEAST, CRIME, BREACH and now FREAK are all stark
reminders that no protocol in practical use is ever likely to be bulletproof,
and that the best we can do is try and find the holes before the bad guys.
