Chasing X25519

Usage of insecure curves still common

This article continues my research from 2015 which you should read to get an impression of some nasty "the-NSA-backdoored-our-crypto" things.

Findings from 2015 in a nutshell

In 2015 I checked some browsers and recommendations for webserver configuration and the support of "trustworthy" cryptography when using forward secrecy with elliptic curves.

It turned out that all major browsers, Chrome, Firefox, Edge, Internet Explorer, and Opera only supported questionable (i.e. "defined-by-NIST-probably-backdoored-by-NSA") cryptographic parameters (secp256r1, secp384r1, secp521r1) whenever forward secrecy using elliptic curves (i.e. ECDHE) had to be in place. At the same time many institutions (e.g. Qualys, Mozilla, IETF, and Acunetix) recommended you to activate forward secrecy using elliptic curves.

The finding was, that most confidential communication on the Internet used suspicious cryptographic parameters. Trustworthy alternatives (e.g. using Curve25519) for elliptic cryptography were not available at all. Neither in the browser, nor on the webserver side.

What has changed in the past two years?

 

Some time after my last blog post I found that browser vendors wanted to implement support for X25519 to provide an alternative to the fishy NIST curves. Some more time has passed now and so I wanted to check the progress, and if X25519 is indeed used in our daily business by default.

In this article I would like to show you my findings.

Browser support for X25519? Yes!

 

Most browser vendors have added support for Curve25519. That's good news! Chrome, Firefox, Opera and Edge support it, IE11 does not. Where supported X25519 is even on top of the browser's preference list. That's also good news, but keep reading ...

So far so good. At least things changed in the browser world.

(I will leave IE11 out for the rest of this article - no news for this one anyway)

 

Server support for X25519? Meeeeh...!

It needs two for this game. The best browser cannot speak freely when the bad server doesn't want them to...

 

How about ... PayPal?

I usually choose PayPal to dump traffic. PayPal, because they usually do things right and serve as a good reference. Not in this case, however:

O PayPal, Where Art Thou?

Hmmm... so PayPal does not support X25519 and chooses the old and busted secp256r1.

Though the browser supports X25519 but the server does not and so secp256r1 is chosen for key agreement 😒

That is not too promising at all. I wonder how other servers handle those requests for X25519. Let's check that!

How about ... Google?

Good ol' Goo'!

Google - X25519 - good!

How about ... Alexa Top 100?

Of course, I wrote a scanner to check Alexa Top X sites for their curve usage. I checked three things

1. Does the site support x25519?
2. Does the site prefer x25519?
3. Does the site honor the client's curve preference for x25519?

(1) is checked by sending ECDHE as the only supported cipher suites and X25519 as the only supported curve.

(2) is checked by sending ECDHE as the only supported cipher suites and "P-256:X25519" as the only supported curves, in that order. "Good" servers should choose X25519 even if it is only the client's second preference.

(This point is a bit tricky, because you can also say that "good" servers should honor the client's preference. I acknowledge that argument but in terms of security the trustworthy curves should always win if the client supports them.)

(3) is checked by sending ECDHE as the only supported cipher suites and "X25519:P-256" as the only supported curves, in that order. "Good" servers should choose X25519, i.e. the client's preference, even though they have the choice to use P-256.

Now servers can either not support X25519 at all, or have one of the following combinations:

Prefers X25519: Yes, Honors client's prefs: Yes
("x25519 preferred") These servers choose X25519, no matter what the client says. They use their own preferences and X25519 is on top. Good.

Prefers X25519: Yes, Honors client's prefs: No
These servers choose X25519 unless the client prefers X25519 in which case they choose P-256. That's weird - and is an indication that there is some load balancing going on where the servers are configured differently, some good, some bad.

Prefers X25519: No, Honors client's prefs: Yes
("Client's choice") These servers select the curve that the client prefers. Even if X25519 is supported, the server chooses P-256 when the client prefers that. This is arguably bad behavior, at least from a security perspective. These servers should be changed to use X25519 when the client supports it.

Prefers X25519: No, Honors client's prefs: No
("P-256 preferred") That's a bad combination, and a big NO-NO-NO-NO-NO! Although these servers support X25519 they virtually never use it. Again you may find this combination due to load balancing issues, but it is usually an indication that a server has been configured to use their own curve preferences and P-256 is on top of it. The bad thing is that this guy looks friendly - it supports X25519 - but has a bad-ass behavior - it never uses X25519 in real life. (e.g. www.microsoft.com ^^)
However, the solution is easy, change the curve preferences to have X25519 on top and everything is fine :-)

This is how the Alexa Top 100 sites look in terms of X25519:

Alexa Top 100 - X25519 Support

And here are the Alexa Top 10k results:

Alexa Top 10.000 - X25519 Support

You can download the

• Alexa Top 10k results here and 
• the whole Alexa Top 1 million results here.

Conclusion

 

From the Top 100 websites only 38 provide sensible configuration. When I started this article I expected to see X25519 being in use virtually everywhere. It may take some more time to fix things, but the missing Top 62 sites should definitely hurry up, especially the 57 which do not support X25519 at all!


Given the Top 10k websites things look even worse. About 70% do not even support X25519 and only ~8.7% come with a sensible configuration, while 5.2% would not use X25519 even if the client requested its use.

Also ...

If you looked carefully at the screenshots above, you may have noticed that even though "good" servers use X25519 for key agreement, they still stick to secp256r1 for signatures. A standard for signing with Curve25519 left the draft status only in January 2018.

You may also have noticed "GREASE" in the screenshots above. These are random values used for testing TLS implementations for compatibility problems on-the-fly. This mechanism has been invented by a google engineer to test servers if they ignore unknown values as they should.

Conclusion in a nutshell

Tips & Tricks

If you want to scan a few servers, you can use the OpenSSL (> v1.1.0) command line client:

$ openssl version
OpenSSL 1.1.0g  2 Nov 2017

$ # Check 1: X25519 support
$ echo|openssl s_client -connect www.microsoft.com:443 -cipher ECDHE -curves "X25519" 2>&1 | grep "Server Temp Key"
Server Temp Key: X25519, 253 bits

$ # Check 2: X25519 preferrence
$ echo|openssl s_client -connect www.microsoft.com:443 -cipher ECDHE -curves "P-256:X25519" 2>&1 | grep "Server Temp Key"
Server Temp Key: ECDH, P-256, 256 bits

$ # Check 3: use client's preference
$ echo|openssl s_client -connect www.microsoft.com:443 -cipher ECDHE -curves "X25519:P-256" 2>&1 | grep "Server Temp Key"
Server Temp Key: ECDH, P-256, 256 bits 

A+ Fail

... why an A+ at Qualys can fail nevertheless

So you're using encryption every day, right?

And you feel comfortable with it, because your browser shows a green icon next to the address bar and Qualys SSL Labs shows only A+ for your server?

You think the NSA can't sniff your connection, because you followed some of the best-practice guidelines and recommendations (1, 2, 3, 4) around there?

You're probably wrong. But let's start at the beginning...

Perfect Forward Secrecy

In 2013 Perfect Forward Secrecy (PFS) was a big topic. Everybody started using it, verifying that others are using it and demanding its usage from almost every website operator. Since then, not using PFS is frowned upon.

Today the situation has not changed much and most websites prefer using ciphers that provide PFS. Those are, for example, Diffie-Hellman Exchange (DHE) and Elliptic Curve Diffie-Hellman Exchange (ECDHE).

The efforts towards PFS may originate in the finding that the NSA stores internet traffic for later decryption.

Attacks on DHE Implementation

The documents released by Ed Snowden revealed indications for the NSA being able to decrypt most of the internet traffic nowadays. Security and cryptography specialists were curious about how the NSA actually manages to do that. Then some clever guys gave us an idea of how that can be done and they actually did it. The attack they used basically relies on specific DH keys that are commonly used all over the internet. When someone manages to break them, they can effectively break encryptions by forcing connections to use these weak keys (read the paper!).

What these people discovered is an attack on the implementation rather than on the mathematical problems behind the crypto system.

But the NSA can do more...

Mathematical Backdoors - The Case Dual_EC_DRBG (Confirmed)!

The NSA puts an enormous amount of effort into attempts to covertly introduce weaknesses into the encryption standards followed by hardware and software developers around the world.


On of the best studied examples may be the random number generator Dual_EC_DRBG. It is an algorithm for generating random numbers based on Elliptic Curve (EC) cryptography which got published by the National Institute of Standards and Technology (NIST) in 2007.

Soon after the draft was released in 2004 to the public there were indications of possible weaknesses in the algorithm. Despite these problems the algorithm was standardized by the NIST (not only by the NIST) as Dual_EC_DRBG in NIST SP 800-90A. In a nutshell:

1998 ANSI RNG standardization started as X9.82

2000 The NSA drives to include Dual_EC_DRBG in the emerging standard

2007 Standard released by NIST

2007 Dan Shumow and Niels Ferguson write about the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng

2007 Bruce Schneier asks Did NSA Put a Secret Backdoor in New Encryption Standard?

2013 Ed Snowden's leaks proof that the suspicions were justified and that the NSA indeed introduced a backdoor in this standard

Mathematical Backdoors - The Case secp256r1 (Suspicious)!

You may already know what I'm about to say. The secp256r1 curve is not trustworthy. Any indication to corroborate that statement? Well, kind of ...

The curve was defined in 1999 as Curve P-256 by the NIST. In the linked document the generation of suitable elliptic curve was defined as well as how to verify certain properties of the generation procedure. For generating pseudo-random curves (that's what the "r" in secp256r1 stands for) you have to take a random initial value, say c49d3608 86e70493 6a6678e1 139d26b7 819f7e90, put it through SHA-1 and use the resulting value to calculate the curve. The whole process is defined in the same document.

Curve P-256 alias secp256r1 - suspicious!

So where's the problem?

The way it should be

A trustworthy way of defining the curve would be to take an obviously unbiased number as the initial value. For example 1234567890 or the first numbers of Pi, or whatever you consider unbiased that more that 80 of 100 people would agree on. This would be a nothing up my sleeve number, which is a principle known at least since the mid nineties. You generate the SHA-1 hash of it and use it.

The way it is

• Your good friend the NSA chose a random number (so they say) for you, namely c49d360886e704936a6678e1139d26b7819f7e90 and fixed it as the initial value.
• We know what the NSA is capable of, and that they employ some of the best mathematicians in the world. 
• This initial value is the foundation for (most?) encrypted connections in the whole world.
• The NSA is interested in (and capable of) decrypting lots of stuff.

Just one way to rule them all

Assume, just for a moment, that the NSA is aware of a method to break one in a billion curves and they want one of those to be standardized. It's easy for them to just

• try a billion random initial values and hash them with SHA-1
• check if the result is breakable
• give the breakable initial value to the NIST for standardization

Enough to be skeptical

Please get me right, I don't claim that this is what happened. I am just suspicious because if I can think of ways to undermine the security of that curve, than what might the NSA be able to realize? They employ some of the best mathematicians in the world and their influence on and weakening of standards is proven.

The bad news

If you are just a little susceptible to conspiracy theories or if you just want the most possible privacy for yourself, you might not want to use secp256r1 anymore. The bad news is

You use secp256r1 every day. Why?

For two reasons.

Webserver configuration

Most web servers today are configured according to the latest recommendations and best-practice guidelines. They usually recommend to activate PFS and they are not very picky when it comes to Elliptic Curves. Just an excerpt from some of the otherwise good recommendations:

[Qualys]:

"Put ECDHE and DHE suites to the top of your list."

[Mozilla]:

"ECDHE+AESGCM ciphers are selected first"

[IETF]:

"(...) following cipher suites is RECOMMENDED:
o TLS_DHE_RSA_WITH_AES_128_GCM_SHA256
o TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
o TLS_DHE_RSA_WITH_AES_256_GCM_SHA384
o TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384"

[Acunetix]

"#1 Elliptic Curve Diffie–Hellman (ECDH)"

Browser configuration

So what does your browser say? Unfortunately all major browsers only support the NIST curves, namely secp256r1, secp384r1, secp521r1. And please, don't assume that the secp384r1 and secp521r1 are any more trustworthy. They're defined in exactly the same way as secp256r1.

I chose PayPal to dump some traffic. PayPal because they usually do things right and hence they serve as a good reference. So here are the results

And in case you wonder if the server really established a connection with the elliptic curves...

So yes, they did. Only in one case the PayPal server decided to chose another cipher suite. I wonder if that was on purpose... ^^

Conclusion

You may not have noticed that already, but you are probably using on of the most controversial crypto algorithms today, everyday.

I cannot prove that the NSA somehow backdoored these NIST curves, but they smell fishy!

And unfortunately these curves are the ones that are most widely used nowadays.

We are discussing the problem since 2013 without any advance.

Suspicions about the curves themselves reaches back to 1999.

So ... what next?

Please, dearest browser vendors, give us alternatives. There are many curves out there that are worth being supported by your products. Ed25519, Koblitz or Brainpool curves.

Google, Microsoft, Mozilla, Opera, What are you waiting for?