Skip to main content

Historical courses and resorts in Elliptic Curves Cryptography - Is Curve25519 dead?

tl;dr This short blog post serves to me to recollect some of the thing I have been learning (climbing) about Elliptic Curves Cryptography (ECC from now on) during the last months/years, so please take it with a grain of salt since it might contains some erroneous beliefs.

'80 - Introduction

Giambattista Vico  was an Italian political philosopher and rhetorician, historian and jurist, of the Age of Enlightenment famous (also) for the concept of historical courses and resorts. This can be resumed with: "some events are repeated in the same way even after a long time; and this is not by chance". Well it seems that this might also applies to ECC so he maybe he was right :)
Elliptic Curve made its first appearance in cryptography with Lenstra in 1984 (eventually published in 1987). Curiously enough he introduced them not while trying to come up with a new crypto system but he employed EC in order to factor integers (a side note, there is a really beautiful survey about the number factorization problem by the great Carl Pomerance). Then it did not take long for Neal Koblitz and independently (as often happens in science) Victor S. Miller to connects the dots and coming with a brand new crypto system that translated the Diffie Hellman technique from finite field to EC.  Clearly the main advantage claimed back then (and it looks that this still stands 30 years later) is that EC are immune to index-calculus attacks.
Great starting points to learn ECC are :

'90 - ECC NIST Standard

Fast forward to the '90s when NIST standardized some EC.  The EC in the standard were in the form

y^2 = ax^3 + ax + b

that are so called Weierstrass curves. This is a really classic shape of elliptic curve.
Weierstrass curve
The formulas used for this curves are derived from the work done by the Chudnovsky brothers and as we will see shortly might not be the most efficient. The complete formulas are somehow complicated and on top is not easy to implement constant time algorithm for those curves (unless replace all that code with curve specific, constant-time code). This paper from Brown,Hankerson, Lopez, Menezes shows several optimizations that can be done for NIST's elliptic curves.
One important thing to remember for the sake of this blog post is that this kind of curves have a minimum cofactor of 1, hence the might have a prime order (like all the NIST curves). 
One thing to take care when implementing EC is to employ point validation, in order to avoid invalid curve attacks (see the recent Critical vulnerability in JSON Web Encryption for an example ).
So far so good. For many years did not gain too much popularity among the practitioners, probably due patent related worryings.

'00 - DJB curves

In 2006 djb published the famous Curve25519 paper. In this work he leverages some work done by Montgomery, the so called (unsurprisingly) Montgomery curve. A Montgomery curve comes in the form:

by^2 = x^3 + ax^2 + x

A Montgomery curve is different from the usual Weierstrass form:

Montgomery curve

but it turns out that constitute ≈25% of all elliptic curves.  The main advantages of using such curve shapes are:

  • Speed: a single scalar multiplication is very simple and fast (it can leverage the so called Montgomery Ladder)
  • Side-channel resistance: the Montgomery Ladder is not only fast but is also side-channel resistant,
  • Security: one peculiarity of Montgomery Ladder is that the output is guaranteed to be either on the curve or on its twist. So if a curve is chosen to be twist secure there is no risk to fall into the invalid curve trap seen above.
In his paper djb introduced a new Montgomery Curve (Curve 25519) that contained all the goodies listed above (see also djb and Tanja talk at 31c3 or visit to visit https://safecurves.cr.yp.to for details).

But as this wasn't still enough goodies, as djb explains in the The first 10 years of Curve25519 talk, while him and Tanja moved in the Netherlands they discovered Edwards (and twisted Edwards) curves.

Edward curve


And they immediately got the idea to employ those new object for signing starting from Schnorr signature (this became eventually the Ed25519 signature system). Now it turns out that every Montgomery Curve is bi-rationally equivalent to a twisted Edward curve (in particular: Curve25519).
Beautiful, right? Yes indeed but but but ... there is a little caveat: Montgomery Curves have a  minimum cofactor of 4 (Curve 25519 has cofactor 8). We will see shortly how this is relevant...

'10 - Historical courses and resorts

Gradually ECC was better understood (also some patents expired) and ECC grew up popularity together (also) within mobile devices (EC arithmetic is way faster since it uses way less bits). Also the majority of TLS connections are now served using ECDHE (we probably need to thank Snowden for this). Together with EC also djb curves gain more and more popularity mainly due to two reasons:
  • Curve 25519 has all the goodies listed above
  • People have more confidence on djb than NIST
But in the last months/days we started to see some cracks on djb's castle. The first signal of something happening was JP's blog post about Curve25519's validation that caused some debate on the curve mailing list (all is beautifully summarized in  this post).
Second we started to see some catastrophic failures (about 1.000.000 $!!!!!) related to curve having cofactor > 1 (is also true that CryptoNote employed a rather exotic flow without a proper understanding of the underlying primitive, but still).
It appears clearly that what it seems to be a settled (by djb et al) problem is actually not (at all).
Lately the curve mailing list is full of discussion about:
and as Isis says in another curve mailing list thread"... To say that cofactors are annoying would be putting it mildly! ..".
Now I am not saying this is the end of  Curve25519 and/or Montgomery Curve BUT lately the great Prof. Barreto proposed a new curve that is prime order and a Weierstrass curve.
This made me thinking, is  Prof. Barreto right? Should we go back to Weierstrass curves? Aka ending as we started with Vico

Historical courses and resorts in Elliptic Curves Cryptography 

 

That's all folks. For more crypto goodies, follow me on Twitter. 

Comments

Unknown said…
Clickbait in the title. SAD!
ll said…
really ? Why do you think so? I hope I did argumented my point of view enough...

Popular posts from this blog

OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701)

Usual Mandatory Disclaimer: IANAC (I am not a cryptographer) so I might likely end up writing a bunch of mistakes in this blog post... tl;dr The OpenSSL 1.0.2 releases suffer from a Key Recovery Attack on DH small subgroups . This issue got assigned CVE-2016-0701 with a severity of High and OpenSSL 1.0.2 users should upgrade to 1.0.2f. If an application is using DH configured with parameters based on primes that are not "safe" or not Lim-Lee (as the one in RFC 5114 ) and either Static DH ciphersuites are used or DHE ciphersuites with the default OpenSSL configuration (in particular SSL_OP_SINGLE_DH_USE is not set) then is vulnerable to this attack.  It is believed that many popular applications (e.g. Apache mod_ssl) do set the  SSL_OP_SINGLE_DH_USE option and would therefore not be at risk (for DHE ciphersuites), they still might be for Static DH ciphersuites. Introduction So if you are still here it means you wanna know more. And here is the thing. In my last bl

Critical vulnerability in JSON Web Encryption (JWE) - RFC 7516

tl;dr if you are using go-jose , node-jose , jose2go , Nimbus JOSE+JWT or jose4j with ECDH-ES please update to the latest version. RFC 7516 aka JSON Web Encryption (JWE) hence many software libraries implementing this specification used to suffer from a classic Invalid Curve Attack . This would allow an attacker to completely recover the secret key of a party using JWE with Key Agreement with Elliptic Curve Diffie-Hellman Ephemeral Static (ECDH-ES) , where the sender could extract receiver’s private key. Premise In this blog post I assume you are already knowledgeable about elliptic curves and their use in cryptography. If not Nick Sullivan 's A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography or Andrea Corbellini's series Elliptic Curve Cryptography: finite fields and discrete logarithms are great starting points. Then if you further want to climb the elliptic learning curve including the related attacks you might also want to visit https://s

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 r emoving 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 pape r where we examine the issue with some more rigors.