NEW: Also subscribe to my new series, Programming Feedback for Advanced Beginners.
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).
For a brief refresher on SSL and HTTPS, see “How does HTTPS actually work?”.
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.
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.
The MITM intercepts the plaintext message, and changes it to request an Export RSA (and only Export RSA) ciphersuite.
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.
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…
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.
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:
(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 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.
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:
This block is called as part of
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
long denoting the key exchange algorithm in use.
SSL_kRSA is another
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
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.
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.
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:
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.
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.
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.
NEW: Also subscribe to my new series, Programming Feedback for Advanced Beginners.