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

Billion Laugh Attack in https://sites.google.com

tl;dr https://sites.google.com suffered from a Billion Laugh Attack vulnerability that made the containerized environment to crash with a single invocation.
Introduction Few months ago I applied for a talk at a security conference titled Soyouwanna be a Bug Bounty Hunter but it was rejected :(. The reason behind it is that I have been on/off in the bug bounty business for a while as you can see here:
Funny. Found in a forgotten drawer from the time I was a bug hunter :p #facebook#bug#bountypic.twitter.com/Tt4saGZVLI — Antonio Sanso (@asanso) November 30, 2018 and I would have liked to share some of the things I have learned during these years (not necessary technical advises only). You can find a couple of these advises here:


Rule #1 of any bug hunter is to have a good RSS feed list
and here


The rule #2 of any bug hunter is to DO NOT be to fussy with 'food' specifically with "left over"
Today's rule is: The rule #3 of any bug hunter is DO LOOK at the old stuff

and…

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 blog post I was …

Top 10 OAuth 2 Implementation Vulnerabilities

Some time ago I posted a blogpost abut  Top 5 OAuth 2 Implementation Vulnerabilities.
This week I have extended the list while presenting Top X OAuth 2 Hacks at OWASP Switzerland.

This blog post (like the presentation) is just a collection of interesting attack OAuth related.

#10 The Postman Always Rings Twice  I have introduced this 'attack' in last year post . This is for provider implementer, it is not extremely severe but, hey, is better to follow the spec. Specifically

The client MUST NOT use the authorization code  more than once.  If an authorization code is used more than once, the authorization server MUST deny the request and SHOULD revoke (when possible) all tokens previously issued based on that authorization code.

It turned out that even Facebook and Googledid it wrong... :)

#9 Match Point To all OAuth Providers be sure to follow section 4.1.3 of the spec in particular

...if the "redirect_uri" parameter was included in the initial authorization requ…