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 25516 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

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

Popular posts from this blog

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://safecurves.cr.yp.to…

Slack SAML authentication bypass

tl;dr  I found a severe issue in the Slack's SAML implementation that allowed me to bypass the authentication. This has now been solved by Slack.
Introduction IMHO the rule #1 of any bug hunter (note I do not consider myself one of them since I do this really sporadically) is to have a good RSS feed list.  In the course of the last years I built a pretty decent one and I try to follow other security experts trying to "steal" some useful tricks. There are many experts in different fields of the security panorama and too many to quote them here (maybe another post). But one of the leading expert (that I follow) on SAML is by far Ioannis Kakavas. Indeed he was able in the last years to find serious vulnerability in the SAML implementation of Microsoft and Github. Usually I am more an "OAuth guy" but since both, SAML and OAuth, are nothing else that grandchildren of Kerberos learning SAML has been in my todo list for long time. The Github incident gave me the final…

CSRF in Facebook/Dropbox - "Mallory added a file using Dropbox"

tl;dr  Facebook Groups offers the option to upload files directly from the Dropbox account. This integration is done using the OAuth 2.0 protocol and suffered from a variant of the classic OAuth CSRF (defined by Egor Homakov as the the Most Common OAuth2 Vulnerability),  see video below:



Introduction  Facebook Groups offers the option to upload files directly from the Dropbox account:


This will allow to surf via browser the Dropbox account 


and post a specific file to the group.  This integration is done using a variant of the OAuth 2.0 protocol seen in this blog many many times. But once more, OAuth is an access delegation protocol standardized under the IETF umbrella. A typical OAuth flow would look like:
Usually the client initiates the OAuth flow in the following way:

then after that the resource owner has authorized the client the authorization server redirects the resource owner back to the client with an authorization code:
Then the OAuth dance continues....
Facebook/Dropbox i…