in attacks, TLS/SSL 2,168 Words

Attack of the week: FREAK (or ‘factoring the NSA for fun and profit’)

This is the story of how a handful of cryptographers ‘hacked’ the NSA. It’s also a story of encryption backdoors, and why they never quite work out the way you want them to.

But I think I’m getting ahead of myself a bit here.

Today’s Washington Post has the story of a nasty bug in some TLS/SSL servers and clients, one that has the potential to downgrade the security of your TLS connections to something that isn’t really secure at all. In this post I’m going to talk about the technical aspects of the attack, why it matters, and how bad it is.
If you don’t want to read a long blog post, let me give you a TL;DR:

A group of cryptographers at INRIA, Microsoft Research and IMDEA have discovered some serious vulnerabilities in OpenSSL (e.g., Android) clients and Apple TLS/SSL clients (e.g., Safari) that allow a ‘man in the middle attacker’ to downgrade connections from ‘strong’ RSA to ‘export-grade’ RSA. These attacks are real and exploitable against a shocking number of websites — including government websites. Patch soon and be careful. 

You can find a detailed description of the work by the researchers — Beurdouche, Bhargavan, Delignat-Lavaud, Fournet, Kohlweiss, Pironti, Strub, Zinzindohoue, Zanella-Béguelin — at their site SmackTLS.com. You should go visit that site and read about the exploits directly. The proof of concept implementation also involved contributions from Nadia Heninger at U. Penn.

I’m going to explain the rest of it in the ‘fun’ question and answer format I save for this kind of attack.

What is SSL/TLS and what are ‘EXPORT cipher suites’ anyway?

In case you’re not familiar with SSL and its successor TLS, what you should know is that they’re the most important security protocols on the Internet. In a world full of untrusted networks, SSL and TLS are what makes modern communication possible.

Or rather, that’s the theory. In practice, SSL and TLS have been a more like a work in progress. In part this is because they were developed during an era when modern cryptographic best practices weren’t nailed down yet. But more to the point: it’s because even when the crypto is right, many software implementations still get things wrong.

With all that in mind, there’s a third aspect of SSL/TLS that doesn’t get nearly as much attention. That is: the SSL protocol itself was deliberately designed to be broken.

Let me explain what I mean by that.

Back in the early 1990s when SSL was first invented at Netscape Corporation, the United States maintained a rigorous regime of export controls for encryption systems. In order to distribute crypto outside of the U.S., companies were required to deliberately ‘weaken’ the strength of encryption keys. For RSA encryption, this implied a maximum allowed key length of 512 bits.*

The 512-bit export grade encryption was a compromise between dumb and dumber. In theory it was designed to ensure that the NSA would have the ability to ‘access’ communications, while allegedly providing crypto that was still ‘good enough’ for commercial use. Or if you prefer modern terms, think of it as the original “golden master key“.

The need to support export-grade ciphers led to some technical challenges. Since U.S. servers needed to support both strong and weak crypto, the SSL designers used a ‘cipher suite’ negotiation mechanism to identify the best cipher both parties could support. In theory this would allow ‘strong’ clients to negotiate ‘strong’ ciphersuites with servers that supported them, while still providing compatibility to the broken foreign clients.

This story has a happy ending, after a fashion. The U.S eventually lifted the most onerous of its export policies. Unfortunately, the EXPORT ciphersuites didn’t go away. Today they live on like zombies — just waiting to eat our flesh.

If EXPORT ciphers are known to be broken, what’s the news here?

We don’t usually worry about export-grade cipher suites very much, because supposedly they aren’t very relevant to the modern Internet. There are three general reasons we don’t think they matter anymore:

  1. Most ‘modern’ clients (e.g., web browsers) won’t offer export grade ciphersuites as part of the negotiation process. In theory this means that even if the server supports export-grade crypto, your session will use strong crypto.
  2. Almost no servers, it was believed, even offer export-grade ciphersuites anymore.
  3. Even if you do accidentally negotiate an export-grade RSA ciphersuite, a meaningful attack still requires the attacker to factor a 512-bit RSA key (or break a 40-bit symmetric cipher). This is doable, but it’s generally considered too onerous if you have to do it for every single connection.
This was the theory anyway. It turns out that theory is almost always different than practice. Which brings us to the recent work by Beurdouche et al. from INRIA, Microsoft Research and IMDEA.

What these researchers did was develop a fairly beautiful piece of formal analysis tooling that allows them to ‘fuzz’ the state machines of most modern SSL/TLS implementations. They found a bunch of wonderful things in the course of doing this — some of them quite nasty. I’m not going to cover all of them in this post, but the one we care about here is quite simple.

You see, it turns out that some modern TLS clients — including Apple’s SecureTransport and OpenSSL — have a bug in them. This bug causes them to accept RSA export-grade keys even when the client didn’t ask for export-grade RSA. The impact of this bug can be quite nasty: it admits a ‘man in the middle’ attack whereby an active attacker can force down the quality of a connection, provided that the client is vulnerable and the server supports export RSA.

The MITM attack works as follows:
  1. In the client’s Hello message, it asks for a standard ‘RSA’ ciphersuite.
  2. The MITM attacker changes this message to ask for ‘export RSA’.
  3. The server responds with a 512-bit export RSA key, signed with its long-term key.
  4. The client accepts this weak key due to the OpenSSL/SecureTransport bug.
  5. The attacker factors the RSA modulus to recover the corresponding RSA decryption key.
  6. When the client encrypts the ‘pre-master secret’ to the server, the attacker can now decrypt it to recover the TLS ‘master secret’.
  7. From here on out, the attacker sees plaintext and can inject anything it wants.
So that’s bad news and it definitely breaks our assumption in point (1) above. But at least in theory we should still be safe based on points (2) and (3).
Right?

How common are export-enabled TLS servers?

No matter how bad you think the Internet is, it can always surprise you. The surprise in this case is that export-grade RSA is by no means as extinct as we thought it was.

Based on some recent scans by Alex Halderman, Zakir Durumeric and David Adrian at University of Michigan, it seems that export-RSA is supported by as many as 5.2% 36.7% (!!!!) of the 14 million sites serving browser-trusted certs. The vast majority of these sites appear to be content distribution networks (CDN) like Akamai. Those CDNs are now in the process of removing export grade suites.
While the numbers are impressive, the identity of those sites is a bit more worrying. They include U.S. government sites like www.nsa.gov (Oy vey), http://www.whitehouse.gov and http://www.irs.gov. It turns out that the FBI tip reporting site (tips.fbi.gov) was also vulnerable.

(Facebook have updated their configuration as a result of this work.)

Factoring an RSA key seems pretty expensive for breaking one session.

This brings us to the most awful part of this attack. You don’t have to be that fast.

 You see, it turns out that generating fresh RSA keys is a bit costly. So modern web servers don’t do it for every single connection. In fact, Apache mod_ssl by default will generate a single export-grade RSA key when the server starts up, and will simply re-use that key for the lifetime of that server.
What this means is that you can obtain that RSA key once, factor it, and break every session you can get your ‘man in the middle’ mitts on until the server goes down. And that’s the ballgame.

PoC or GTFO.

Fortunately, a proof of concept for this attack requires only a few ingredients. First, you need some tooling to actually run the MITM attack. Then you need the ability to (quickly) factor 512-bit RSA keys. From there it’s just a question of finding a vulnerable client and server.

This is what happens to EC2 spot pricing
when Nadia runs 75 ‘large’ instances
to factor a 512-bit key.

Just because someone says an implementation is vulnerable doesn’t mean it actually is. You should ask for proof.

The guts of the PoC were put together by Karthik Bhargavan and Antoine Delignat-Lavaud at INRIA. They assembled an MITM proxy that can intercept connections and re-write them to use export-RSA against a willing website.

To factor the 512-bit export keys, the project enlisted the help of Nadia Heninger at U. Penn, who has been working on “Factoring as a Service” for exactly this purpose. Her platform uses cado-nfs on a cluster of EC2 virtual servers, and (with Nadia doing quite a bit of handholding to deal with crashes) was able to factor a bunch of 512-bit keys — each in about 7.5 hours for $104 in EC2 time.

From there all you need is a vulnerable website.

Since the NSA was the organization that demanded export-grade crypto, it’s only fitting that they should be the first site affected by this vulnerability. There’s great video on the SmackTLS site. After a few hours of factoring, one can take the original site (which looked like this):

 

And change it into this:

Attack images courtesy Karthik, Antoine INRIA.

Very dramatic.

Some will point out that an MITM attack on the NSA is not really an ‘MITM attack on the NSA’ because NSA outsources its web presence to the Akamai CDN (see obligatory XKCD at right). These people may be right, but they also lack poetry in their souls.

Is it patched?

The most recent of OpenSSL does have a patch. This was announced (though not very loudly) in January of this year.

Apple is working on a patch.

Akamai and other CDNs are also rolling out a patch to solve these problems. Over the next two weeks we will hopefully see export ciphersuites extinguished from the Internet. In the mean time, try to be safe.

What does it all mean?

You might think this is all a bit absurd and doesn’t affect you very much. In a strictly technical sense you’re probably right. The client bugs will soon be patched (update your devices! unless you have Android in which case you’re screwed). With good luck, servers supporting export-grade RSA cipher suites will soon be rare curiosity.

Still, to take this as the main lesson of the work would, I think, be missing the forest for the trees. There’s a much more important moral to this story.

The export-grade RSA ciphers are the remains of a 1980s-vintage effort to weaken cryptography so that intelligence agencies would be able to monitor foreign traffic. This was done badly. So badly, that while the policies were ultimately scrapped, they’re still hurting us today.

This might be an academic point if it was only a history lesson. However, for the past several months, U.S. and European politicians have been publicly mooting the notion of a new set of cryptographic backdoors in systems we use today. While the proposals aren’t explicit, they would presumably involve deliberately weakening encryption tech so that governments can intercept and read our conversations. While officials carefully avoid the term “back door” — or any suggestion of weakening our encryption systems against real attackers — this is wishful thinking. These systems are already so complex that even normal issues stress them to the breaking point. There’s just no room for new backdoors.

To be blunt about it, the moral is pretty simple:

Encryption backdoors will always turn around and bite you in the ass. They are never worth it.

Acknowledgements

Special thanks to Karthik and Antoine for sharing this with me, Nadia for factoring, Ivan Ristic for interrupting his vacation to get us data, and the CADO-NFS team for the software that made this possible.

Notes:

* Export controls might have made some sense in the days when ‘encryption’ meant big clunky pieces of hardware, but it was nonsensical in a world of software. Non-U.S. users could easily skirt the paltry IP-address checks to download strong versions of browsers such as Netscape, and — when that was too much trouble — they could easily re-implement the crypto themselves or use foreign open source libraries. (The requirements became so absurd that mainstream U.S. companies like RSA Security wound up hiring foreign developers to build their encryption libraries, since it was easier to import strong encryption than to export it.)

62 thoughts on “Attack of the week: FREAK (or ‘factoring the NSA for fun and profit’)”

  3. Not to be all super-sensitive, but that ?Walking Dead? (I think?) screencap is really, really disturbing if you're not someone who watches the show. If you don't know it's a show, it's basically 4chan gore material. It took me a minute to notice the people in the background and then make out the character whose sexy costume analogues were everywhere last Halloween.

    Anyway. Just wanted to mention that perspective.

  6. I agree with this sentiment, halloween/gore material does not befit the subject very well – it serious and well written article and might as well have pics to back that up with

  8. To go over some of the technical details, attacker can't just generate a 512-bit RSA key as the key in the ServerKeyExchange message is signed by the server, and the Finished message don't prevent the attack as all the hash depends on is the master secret that can be obtained after the 512-bit RSA key is factored. As a side note, this make me wonder if a similar attack is possible with 512-bit DHE. A server still using it is https://www.ssllabs.com/ssltest/analyze.html?d=mobilelinkgen.com

  9. Yes, that is *incredibly* sensitive. There's no gore at all in that screen capture, even if you zoom in on it. There's far worse on the news every night, even pre-watershed.

    (Unless it has been changed since your comment, in which case, sorry)

  10. Yes, that is *incredibly* sensitive. There's no gore at all in that screen capture, even if you zoom in on it. There's far worse on the news every night, even pre-watershed.

    (Unless it has been changed since your comment, in which case, sorry)

  13. To the people complaining about zombies – grow a backbone. Stop getting so offended over everything little thing on the internet.

  14. OpenSSL is the descendent of SSLeay (eay = Eric A Young) who with a few others wrote the library – the Crypto, ASN.1, bignum, etc. in Australia outside of the export controls, so everyone could use it. Those in the USA could import it.
    So the only servers that used weak crypto were the ones in the USA.

  15. I'm not finding the details on this, leading me to speculate that the MITM is choosing an EXPORT40 in it's server-hello selection that wasn't originally offered in the the client-hello, and that the client is accepting that EXPORT40. (is this the bug?). If so, then I'm also under the impression that this would only be vulnerable to SSLv2, not SSLv3+, as I believe handshake is protected in the MAC, i.e. protected in SSLv3+. The attack on an SSLv3+ would fail MAC check by both real client and server. If this is the attack, than it's scope is really quite limited, to a combined client&server that allow SSLv2. Further FREAK then sounds like a long well known attack, with a new easy to remember name that's catchy among various media outlets.

  17. As forssl and TLS taking a longtime to secure?Steve point out there is no reason for the delay .even HE is almost ready to release his secure ID suite called S.Q.R.L ,as some know before mostly in assembler.nha most likely some don't want web 100% secure and have to ask a jjudge to peer at Obama bedroom webcam

  20. ALL: in regards to Matthew's “what does it all mean?” section, see also: “Surveillance or Security?”, Susan Landau, MIT Press, 2011 –

  22. I can vouch for the export control silliness. In 93/94 I implemented PEM while in England and in about 3 weeks was able to exchange PEM encrypted email with the TISPEM reference implementation. At the time the UK government was also using the same export control policy and we decided it was not possible to export the PEM product.

  23. From what I understood, this attack is only feasible against Apache mod_ssl -based applications or websites, because Apache mod_ssl by default generates a single export-grade RSA key when the server starts up (or against any other Apple SecureTransport or OpenSSL -based application that has the same behavior), so you can factor the RSA modulus to recover the corresponding RSA decryption key offline and reuse it in future sessions (during the lifetime of this key). Otherwise, it seems unfeasible that a handshake would last for 7.5 hours, right?

  26. Cool 🙂 Yet another race to patch this just begun, it departments are probably 'excited' 🙂 Although it's better to have a bug fixed rather than lurking somewhere.

  28. From what I can see in ssl_engine_kernel.c on line 1313, current version of Apache uses the same algorithm for generating DH and EXPORT keys. I can assume EXPORT keys don't usually live long and unique for every client, just as DH. So you're right.

  30. The EXPORT keys (do you mean RSA_EXPORT keys — used to encrypt — or DH(E)_RSA_EXPORT where RSA is used to sign (*)) might be generated using the same function than DH values. However, it doesn't imply that the generation is done every SSL/TLS session.

    (*) RSA_EXPORT: RSA used for encryption, size <= 512 bits
    DH(E)_RSA_EXPORT: RSA used for signature, size >= 512 bits

  31. Handbag clutching people who take themselves too seriously really grind my gears.

  34. Temporary RSA 512 Bit Keylife for FREAK attack

    So I’ve patched OpenSSL’s s_client a bit to print temporary RSA 512 public key used for EXPORT cipher

    --- 1/apps/s_cb.c 2015-03-04 17:17:28.349494504 +0300
+++ 2/apps/s_cb.c 2015-03-04 17:17:30.452827799 +0300
@@ -507,6 +507,7 @@
     switch (EVP_PKEY_id(key)) {
     case EVP_PKEY_RSA:
         BIO_printf(out, "RSA, %d bits\n", EVP_PKEY_bits(key));
+        PEM_write_bio_PUBKEY(out, key);
         break;
 
     case EVP_PKEY_DH:

    Then grabbed domain list from freakattack.com, got first IP addresses from domain with

    parallel -u -j8 -a domainlist.txt 'dig +short a {} | egrep "[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}" | head -n1' > ips.txt

    and ran parallel -u -a ips.txt -j20 './run.sh {}' twice to collect temporary RSA 512 bit keys, where run.sh is as follows:

    openssl s_client -connect $1:443 -showcerts -cipher EXP-RC4-MD5 < /dev/null | grep -A3 'BEGIN PUBLIC KEY' >> output/$1.txt

    then count all domains with more than 4 unique RSA key lines:

    parallel -u -a ../ips.txt -j1 'if [ "$(sort -u {}.txt | wc -l)" -gt 4 ]; then echo {}; fi' > ../random.txt

    Total hosts in list: 415
    Hosts with enabled EXPORT: 368
    Hosts with random keys for every connection: 137
    Hosts with static keys for every connection: 231

    view raw

    freak-rsa-keylife.md

    hosted with ❤ by GitHub

  35. I share your concern about the government's request to allow all Internet communication to be able to be read by them, so please don't take this comment as me being an apologist for backdoors in cryptology. However, there are alternative ways to allowing the internet traffic to be read without weakening the cryptology. For example, the communications could be signed with the government's public key at the same time it is signed by your own public key. The cryptology would remain strong until the government's private key is accidentally leaked.

  36. May you elaborate on the comment that Android users are “screwed?” Would it be because a patch to Android's OpenSSL would have to go through the customary path Google-Manufacturer-Cell carrier-User?

  38. you could use a sniffer to record the traffic and go back and decyrypt it once you've factored the key, couldn't you? then you wouldn't worry how long the key was actively used…

  42. I'm not sure if you can do downgrade attack without the key. I suppose key negotiation is signed with this exact key, but I'm not sure.

  43. Where on earth is it possible to get the OpenSSL patches or the changed source code lines for each OpenSSL files?

  48. This vulnerability was the result of an audit by a team that wrote special tools to do it. So what you want is already happening, and them publishing their results is what is triggering you to ask for someone to do something like they just did.

  49. The authors state ” In other words, the JSSE implementation of TLS has been providing virtually no security guarantee (no authentication, no integrity, no confidentiality) for the past several years. ” in the 8th paragraph of their web site: https://www.smacktls.com/.

    So yes, it affects the client-side of the Java TLS/SSL stack.

  50. Why is the current stable Chrome 40.0.2214.109 for Android vulnerable while Chrome Beta for Android is not? Both support the exact same cipher suites. Many thanks!

  51. Don't forget how the “key escrow” backdoor in Lotus Notes used 768-bit RSA, and remember that the key has to be factored only once!

  52. Probably a reference to the fact that over half of devices in use are not supported anymore and are running years-old OS versions.

  53. A horror story, not far from it, because my question is simply, how much else we do not know or somebody does not want us to know.
    Is there anyone who is aware of entire technology and possibilities of attacks?
    I am asking because we created all these protocols, and if we left these gaps here that we know of now, then nothing will ever be secure, since obviously there is a general humongous problem in the entire industry: the software industry is NOT trust worthy even at the lowest possible level.
    If this attack has been exploited for 35 years (35 years!) and nobody said a word about it, then there is a dominant extreme culture of silencing among technical staff everywhere in this world and this is very very very very very bad news. I am not surprised that we have only one person talking at the moment openly.
    A horror story to the highest possible degree.

  55. Matthew, thanks for the explanation of this.

    While I agree that it's important to be aware of these things and get them fixed ASAP, and I agree that enryption backdoors in general are a really bad idea, I disagree with your conclusion in this particular case that this is all because of an “encryption backdoor”. Because from what I can see, this is mostly down to a client implementation flaw which allows the client to do something it is not supposed to do (allowing the cipher to be downgraded when they never offered it in the first place), combined with a server implementation flaw which it should not be allowed to do. (The long-term key usage thing)

    Yes, if servers offer lower-grade encryption then that makes this scenario more likely to occur. But the reason servers sometimes offer that lower-grade encryption is because some clients (still a bunch out there!) have a choice between that, or no encryption at all. And it's not particularly ironic that these sometimes happen to be government-run websites – those same websites are mandated to be usable by the widest possible spectrum of citizens and UA's possible, even if they are vision-impaired, and/or using an old computer with a small screen and an old OS that does not support modern encryption protocols, can't render pages with complex AJAX scripting and so on. Unlike profit-driven websites, the government has a mandate to serve *everyone*.

    So, it's a tradeoff. There are still a lot of people with analog TV sets and 40-year-old radios which can still tune in radio stations. I think the real guilty parties in this particular case are the people who released that buggy client and server code.

  56. I think the author is trying to draw a parallel between the fiction and hype portrayed in the movie and his own article.

  57. The January 2015 critical update for Java 1.5, 1.6, 1.7 and 1.8 prevents the attack.

  60. Does nginx also createand re-use a single RSA key when it starts? I am confused on the relationship between export cipher suites with max 512-bit RSA keys and modern server certificates that are 2048-bits or greater.

  61. Something is really not clear for me. Please let me explain my doubts: I know that once the certificate arrived to the client, and after that the client check that it's ok, it take the public key contained into this certificate (that is usually at 2048 bits, but however not less then 1024) and encrypt the pre-master key for the symmetrick cryttography. How can this attack reduce this key to 512 bits if it is 2048 bits? Other question, in the article is written that the RSA key are the same until the server go down, but how is possible since the key is written in the certificate? If it change the signature of the certification authority is not valid…please, someone help me to understand ;(

Comments are closed.