SafeCurves: Choosing Safe Curves for Elliptic Curve Cryptography

Daniel J. Bernstein (djb) and Tanja Lange

SchmooCon 2014

video 1: https://www.youtube.com/watch?v=dFUJmzcj0iw&list=PLgO7JBj821uGZTXEXBLckChu70kl7Celh&index=15

video 2 (same?): https://www.youtube.com/watch?v=maBOorEfOOk&list=PLgO7JBj821uGZTXEXBLckChu70kl7Celh&index=91

Video intro text

There are several different standards covering selection of curves for use in elliptic-curve cryptography (ECC). Each of these standards tries to ensure that the elliptic-curve discrete-logarithm problem (ECDLP) is difficult. ECDLP is the problem of finding an ECC user's secret key, given the user's public key.

Unfortunately, there is a gap between ECDLP difficulty and ECC security. None of these standards do a good job of ensuring ECC security. There are many attacks that break real-world ECC without solving ECDLP. The core problem is that if you implement the standard curves, chances are you're doing it wrong:

  • Your implementation produces incorrect results for some rare curve points.
  • Your implementation leaks secret data when the input isn't a curve point.
  • Your implementation leaks secret data through branch timing.
  • Your implementation leaks secret data through cache timing.

These problems are exploitable by real attackers, taking advantage of the gaps between ECDLP and real-world ECC. Secure implementations of the standard curves are theoretically possible but very hard.

Most of these attacks would have been ruled out by better choices of curves that allow simple implementations to be secure implementations. This is the primary motivation for SafeCurves https://safecurves.cr.yp.to/ ... The SafeCurves criteria are designed to ensure ECC security, not just ECDLP security.

... their new mechanism for choosing safe elliptic curve cryptographic curves. Thank you very much.

Introduction

A few quick words. Am I audible? Where do elliptic curves fit in this? Where do elliptic curves fit in there? This is part of public key cryptography, something you use when you sign something. Say the government is issuing you a passport, or you're a certificate authority, or if you're a programmer and you're doing code signing. If you do that, then you're using public key cryptography, and elliptic curves, and RSA, and diffie-hellman. Also, public key encryption so when you're using a connection to a website, the first thing you do is a handshake. Well, assuming you're using HTTPS, the first thing you do is a cryptographic handshake, and you have to make the ... so you're building up a shared secret based on public key cryptography. RSA is also an encryption system, that elliptic curve diffie-hellman and normal diffie-hellman finds fields of different examples. This is in big contrast to symmetric cryptography, which you use for file decryption. If you don't want to do public key encryption because it's much slower, so you use AES which is an example of symmetric encryption. A system where you and the website you're sharing a key with know the same secret and can transmit encrypted data very very quickly.

Elliptic curve cryptography

Alright, I'll give this one a try. Within public key crypto, why do people move from RSA to elliptic curve crypto? The main reason is an attack strategy called index calculus. This is a complicated attack. It's something that keeps getting more sophisticated over the years. It actually started in the 1930s before crypto was really understood. In the 1930s, people were thinking about how do we factor big numbers? And they started with the beginnings of index calculus. After that, in the 70s, people were still thinking about factorization, there was the CFRAC algorithm in 1975. And then in the late 1970s, around 1977, there was the original Diffie-Hellman system and RSA. That attracted a lot of attention to how fast can we factor numbers and compute discrete logs. So people became very focused on index calculus. A lot of the buzzwords are listed here, like linear sieve, quadratic sieve, number-field sieve, function-field sieve (FFS)... I should mention that some of these recent, the last few lines in this history list, like function-field sieve does not help for factoring, but it helps for discrete logs, but it's still in this index calculus method. If you are trying to figure out how big your RSA keys have to be, you have to get into these complicated series of algorithms from index calculus, and you have to worry if there's going to be more improvements.

Index calculus attacks

To give you a numerical eample, if you fix your key size with say RSA-1024 bits or RSA-2048 bits, then, in the initial design of the index calculus, CFRAC was well understood and linear sieve was just coming out. So these systems would have a security property where it would take an attacker 120 operations to break it. For a smaller system. And 270 for the bigger system. When RSA was designed, the linear sieve had just come out. So this reduced security to like 2110 bits. At that time, it looked like 2110 operations, independent of the computer architecture, it's just mathematical operations. If you go for computer instructions, it's a multiple of that. As I mentioned, it brought security down to 2100 or 280 depending on RSA key size. Even before the number-field sieve came out, there was a proposal from Miller in 1986 "Use of elliptic curves in cryptography" where it was said "It is etremely unlikely that an 'index calculus' attack on the elliptic curve method will ever be able to work". He proposed using elliptic curves, and that was his argument, that mathematically it doesn't look like there could be anything like these index calculus attacks. The closest analogy would be Diffie-Hellman and finite fields, and there's extensive use of making a finite field look like the integers. It's called lifting. And Victor shows that lifting wouldn't exist for elliptic curves.

Unit circle and clock cryptography introduction

Alright, so, to get an idea of what elliptic curve crypto looks like, we have to get more familiar with these curves. With these kinds of curves, you could imagine well, you could maybe think about straight lines. But if you don't have a straight line, the simplest curve is a clock, or a clock, a mathematical circle, that's x2 + y2 = 1. Take all the points (x, y) in the plane that satisfies the equation x2 + y2 = 1. That's the unit circle. Now, I have to give you a warning here, which is that circles are examples of ellipses, which are stretched circles. You might think that elliptic curves are another name for ellipses, but that's not the case. Ellipses and circles are not elliptic curves. Elliptic curves are a little bit more complicated than circles. If I had stretched this circle, it would have been an ellipse. Any advantages that elliptic curves have, ellipses and circles do not have that advantage.

Just in case some of you have forgotten what these things look like, it's kind of quaint you know. Some exmaples of points on the clock. When you look at this pocket watch, you find 12 clock points out there. So in mathematical coordinates, we have 0 in the x direction and 1 in the y direction. That's the top point up here. This one is at 1, and this one is also at 1. There's the 6 o'clock point at (0, -1), there's a 3 o'clock and 9 o'clock point. And then there's the question like where is the 2 o'clock point, it's somewhat over and somewhat up, the over is quite a bit and the up is just a little bit. So the up is by 1/2 and the over is by square root of 3/4. And coming up with more numbers, you can mirror that point and flip the (x, y) and then you can do 1/2 in the x direction and minus square root 3/4 in the other direction. So that's how you find the other points. And there are lots of other points that make nice times. There are other points. If you are finding just the (x, y) to satisfy the equation, then this other point (3/5, 4/5) is valid. You can approximate this as a time, but it's not a regular time on your clock. Getting a plus and minus sign, it's just (x, y) but you also have (-x, y) and you can also flip x and y and you can find many more points.

So what happens when you add times? For instance, if you look here, p1 on this picture is something like 1 o'clock. And p2 might be more than 2 o'clock or something. Maybe p1 is 1:15 and p2 is 2:30. If you add those, you get something past 4 o'clock. There wont be a whole lot of trig. There will be a little bit of trigonometry. Once upon a time, everyone learned how to do addition of angles on a circle. Long time ago. In math courses for some reason, instead of doing it on the clock, starting at 0 and 12, for some reason they put 0 on the side, so the sine and cosine are flipped from what you might remember from the trig courses. So if is a sine of an angle and y is a cosine of an angle, there are formulas for adding these together. x2 + y2 = 1 parameterized by x = sin(a) and y = cos(a). Recall that (sin(a1 + a2), cos(a1 + a2)) = (sin(a1)*cos(a2) + cos(a1)*sin(a2), cos(a1)*cos(a2) - sin(a1)*sin(a2)). Now, we would like to simplify this for you, thinks about sine and cosine, just think about points x and y on the curve without thinking about angles. To simplify this picture a bit, to do clock addition, it's the same addition operation, working with x and y instead. If the sines are X and the cosines are Y, and so on. So you have some formulas for doing some additions and multiplications. The sum of two points (x1, y1) and (x2, y2), ... you get (x1 * y2 + y1 * x2, y1 * y2 - x1 * x2).

Okay, to give some numerical examples, we already know some points on the clock. We know the 2pm point and the 5pm point. If someone asked you, what's the ... then you answer 7 o'clock. Similarly, our addition should take the 2pm point and 5pm point, so in numbers it's -1/2 and negative square root of 3/4. Anyway, you sum and you can indeed get 7pm. At some point, you are going to wrap around the clock. If you have 9pm and 5pm, .. in mathematical formula, we get put in the 5pm point and 9pm point, the 9pm point is nice because it has a zero there, anything multiplied by y just disappears. And then there's some weird points in 3/5 and 4/5.... we can compute 3 times a point, 4 times a point, and so on. There's also the 9pm point, it's special the 12 o'clock point. If I had asked you what's the time after 1:30pm after 12 hours later, it's 1:30pm. Adding 0 to a 1 to anything, shouldn't change anything. So you should get the exact same (x,y) that you put in. You can verify this with the formulas. You plug in the x2 being 0, this one is x2 * 1, and here you have y1 * ... 0... so nothing changes. Similarly if you want to add a point on this side of the clock, to a point that is on the same height of the clock on the other side, so same y coordinate but the x coordinate has flipped the sign. Then that is like 2pm plus 10pm. So you get the 12 o'clock point. And that works, again, with the math formulas.

In crypto, instead of working with real numbers like the square root of 3/4, we want a finite thing that we can represent with bits in computers. So we use instead, integers mod some prime. Or as mathematicians like to call it, finite fields. The clock had something like 80 points on that picture. In this picture, this is integers mod ... when you add numbers, and you get more than 7, ... and when you multiply numbers, like 2 * 5 is bigger than 7, so subtract some and you get 3. So minus 1 and 6 are the same thing. So we have at least 7 different numbers to work with, 0 through 6. You can multiply and divide, except by 0. Here we are working with mod 7, which has the advantage that you can divide by anything except for the 0. The 0 is in the middle of the picture, then it goes 1 2 3 on the right, and to the left it's -1 -2 -3. If you look at the top right of the picture, that's 2 over and 2 up. So that (2, 2) is a point on the circle. If you plot all the points on the circle, well it's there. So that's a clock, in mod 7.

If you take a larger for a million 3, you have to find a point once, and then you can happily start doubling it. One of the things you notice is that the numbers still stay small. The reduction modulo this very large number doesn't kick in. We do some squaring of this coordinate and that coordinate, and the numbers don't reach a prime there. Eventually you will hit the number, you will hit the "12 o'clock" as it were. So 17 times a point is this result, it's 951405, and whatever y coordinate it maps to. So this we call "scalar multiplication". You take a scalar, 17 in this example, and you take a point like (1000, 2) and they compute 17 times this point. And the easiest way is we double then add some more times. So scalar multiplication is where you take n and p, and you compute n times p.

The example you just saw is the binary method of figuring out n times a point, even if n is huge, it could be 100s or 1000s or millions of bits. You can still do n times a point. If it is an even number, we start computing 8 times a point, double that and add it, so we get to 16, and then you can quickly get to big powers of 2. Most of the time you will be doubling; if you do some number of additions, lots of doublings, you get quickly up to n times p. If you are given an integer n, and you want to compute n times p, you can do that very fast. If you're given an (x, y) point but it's (n, p). And someone tells you the points, would you have guessed that it is 17 times the original point? Another example is that I give you a 6 digit number n, could you figure out a number so that it gets to that exact point 947472 or whatever? You could do it, but it's much much slower than the addition operations we had to do.

Why clock cryptography is interesting

So here is why you should care about this. Namely, clock cryptography which you probably haven't seen yet, but let's stick to this example for now. If Alice and Bob know how to compute on the clock, we can design a scheme where we can find a shared secret just by doing public computations and some computation stays on your computer in secret. Alice chooses something on... smaller than the prime that you wrap around with, but pretty much that size. Bob also picks something, but they don't share this integer. Both of them on a computer, preferably offline in a safe; Alice does a computation with the base point, and Bob does b times this base point. Each of them does the computation using the method we just eplained. Check if it's even, double, or add if it's odd, which Dan explained a moment ago. We don't know the value eactly, it's hard to find mod a p. And now we can send the resulting points over the internet. Let me give you a picture for that. Alice computes a times the point, Bob computes b times the point. Now they exchange those messages. Alice sends one to Bob, and Bob sends his points to the others. So this is scalar multiplication... Bob takes his scalar b and multiplies against Alice's point. Now we have computed a point plus plus p times, and now that whole thing, a times to itself. So Bob has a times b times a point. And Alice has a times b times a point. So even though they have both changed the order of the computation, they have got the same point. So this would be the shared secret between them, and then they can run it through a hash function and use AES between each other. If you are going to implement this, don/'t pick just any prime. Also, clocks are not elliptic. So whatever sizes you use for elliptic curves, they do not apply for clocks. To get security for a clock, say RSA 3000 bits, then you have to choose a pime that has half as many bits. If you are aiming for RSA-3072 then you should have a prime with 1536 bits.

Side channel attacks

See also https://en.wikipedia.org/wiki/Side-channel_attack

Something else to watch out for is that even if you have chosen a good prime, and we'll tell you about how to get around the second problem which is choosing a big enough prime, and we'll tell you a little later about elliptic stuff and how you can make things much smaller and faster and not vulnerable to index calculus. But still, there's timing attacks. Remember the rules for if you want to compute n times a point, it depends on whether n is even or odd. You get different results, you get some doubling operation ; it changes the patterns of operations. The time you take is going to depend on the secret number's value. So there's some numbers of additions involved, like 30 additions in the last example. Well, however big n is, maybe it's 270 bits or something. Someone watching your network and looking for how long you were computing, they might be able to get some information. It might not sound threatening, until you realize the same kind of side channels where people can see the total time, they can see more information about how much time you spend on each operation. Your CPU is doing memory lookup; it has some operations that are using a certain amount of power, that capacitor is whining a little bit. When your computer is doing arithmetic, like multiplications from before, it's consuming different amounts of power. There was a paper a few months ago about acoustic attacks, where someone has a parabolic microphone and a target laptop about that distance away, and then with this parabolic microphone in about an hour they were able to retrieve a gnupg secret key out of a laptop just from the acoustics of the capacitor that was feeding the power to the CPU. The amount of noise it was generating was giving them side channel information. In order to avoid this problem, you have to use something where instead of you're doing branches based on bits of n and so on and other variable time operations, you must make sure that every operation you're doing is in constant time. You must not have any data flow from your secret integers to the operations that you're doing. Always the same operations, you can do arithmetic like additions based on secrets, but not anything like an "if" or anything based on secrets.

Elliptic curves and point addition

Ready for elliptic curves? Okay. So here's one method of getting an elliptic curve. You take your circle, you take your clock; you squish in the corners. So instead of having x2 + y2 = 1, you take a little bit away from it. So you have x2 + y2 = 1 - 30 x2 y2. Well to make addition happy, let's take some number times x2 y2. This thing, is an elliptic curve. Now, we've seen how to add points on an elliptic curve, but elliptic curve is just one of the possibilities. In this case, it's a little bit different. You can't take the exact same points. There's an addition formula, it's similar to the addition formula from the unit circle. And then there are some bits in the denominator, it has changed a little bit. So for comparison, the clock just has x1 y2 and x2 y2. And then there's the same value here, and then you divide by 1 - 30x(....). So it's almost the same except for the sign flip, instead of minus 30, it's plus 30. If you're comfortable with addition on the clock, then it looks almost similar on the elliptic curve. If you look at the angle here, plus this angle, it doesn't really add up to the angle at the red line. But other features are preserved. If you add the 12 o'clock point to anything, it doesn't change anything, the same as in the unit circle, this is what mathematicians call a neutral element. It's actually a good thing, because addition of the angles would be too simple of an operation, it fits like the case of index calculus attacks. And also we're happy that the clock is similar and we can use it for explanations.

Avoid square roots and zero divisors

Okay, the 30 is not something special. There's lots of elliptic curves out there. You can change the 30 to some other number, or the minus 30 to some other number. I'll put in one warning note here. You want that number, the minus 30, to be something that is not a square. Say you take a big prime p, and then you pick some integer d on p which is not a square mod p. That's something you can figure out, you can figure out if d is a square using fast computation. And then, the elliptic curves that we're working with here, these are called Edwards curves, or more specifically, complete Edwards curves, which are any curve x2 + y2 + dx2 * y2. And then the additions looks a little similar to the clock addition; and the minus 30 changes to the minus d.

What if the denominators are zero? The universe exploding is bad. Don't do that. Fortunately you can prove that these denominators never end up being zero. No matter the x1, y2, there will never be a divisible by zero thing here. Because p is a prime, you can always divide by any non-zero number. So we refer to this addition as being "complete"; it's kind of the normal situation, but you'll hear more about exceptions in a bit. It's critical that the d, the denominator, is chosen to be a non-square. It must never be a zero. It's critical. If we instead choose square d, the curve is still elliptic, and addition seems to work, but there are failure cases, often exploitable by attackers. Safe code is more complicated. And actually, the same formulas seem to work when you have chosen do to be a square... it's elliptic curve crypto, but sometimes there will be divisions by zero, you will never find them if you are just randomly testing, and an attacker can find those. If you actually want elliptic curve crypto to work correctly when d is a square, then you have to write more of a code and your test framework is more of a mess.

Curve examples

So here are some examples of nice curves. This is a safe example of a very nice curve. If you want to use something for cryptography, this is something that we recommend. The prime is 255 - 19, that's p. Choose d = 121665 / 121666. This is non-square in field Fp. If you compute the function, it gets pretty big, but if you keep it as a fraction of two values, it's not too big. And the curve is x2 + y2 = 1 + d x2 y2 is a safe curve for ECC (elliptic curve cryptography). Everything we know says this is good.

There are more nice curves. You can keep the same p and d. Instead of having + x2, you can have a minus x2. And at the d term, you could put a minus instead of a plus. Putting a minus in front of the x2 can give you extra speed.

Another safe curve is, well if you take your x and y and you multiply any point on the first curve, you take the x coordinate and you multiply by square root of -1, then the x2 gets a -1 and the plus dx2y2 also gets a -1. So each point gets translated to a point on the second curve. So whatever you do on the first curve you can do on the second curve. In this case, the second one is a little faster on the second form. If anyone had an attack on one of those two representations, like any way to get Alice's secret on the first curve, that second curve... just takes that.. and it's on the first curve.

Even more elliptic curves

Okay, some more examples of elliptic curves. If you want to read the different standards out there for elliptic curve cryptography, then you have to memorize all of these shapes. There will be a test after this talk.

Edwards curves: x2 + y2 = 1 + d x2 y2 see also https://en.wikipedia.org/wiki/EdDSA

Twisted Edwards curves: ax2 + y2 = 1 + d x2 y2

Weierstrass curves: u2 = u3 + au + b

Montgomery curves: bv2 = u3 + au2 + u

Many relationships, e.g. substitute x = u/v, y = (u - 1)/(u + 1) in Edwards to obtain Montgomery.

Twisted edwards curves gives you something in front of hte x2 that doesn't have to be -1. Um, there's all sorts of ways to view these curves as being other curves in disguise, like the example of -1 and square root of -1. You can transform some of these curves. You can look at every Edwards curve as a Montgomery curve. There are other relationships where this is not true. There are restrictions and you have to look at all sorts of details to see how these curves relate to each other.

Weierstrass curves

In Weierstrass curves, we will talk about when they were young and old people saying you have no idea how good you have it; when I walked to school, I walked to school uphills both ways, and Weierstrass curves looked like this. This was additio with lots of cases; you want to add two points. Think of points on the clock. This is what you have to do for point addition on Weierstrass curves. So you have to check if the new coordinate and old coordinate are the same; and if not, then you are in this branch, it's still a bunch of operations, you compute some lambda here which is the difference of the v coordinates divided by the difference of the u coords; then you have to... compute the v coord.. and finally you're done. However, should it happen that the v coordinate was non-zero, or if the u coordinates were the same and you were only adding points to their negative... then there's another case... and then there's another case for infinity. It's in your favorite crypto libraries, so you should hope their implementation is right.

Montgomery-curve ECDH using the "Montgommery ladder"

Something much nicer is the Montgomery shape. This is actually what we recommend for doing Diffie-Hellman. A lot of people in the keynote talk yesterday, heard about talking about a quick diffie-hellman to give yourself forward secrecy. If you want to do diffie-hellman, then we recommend using Montgomery curves, or an Edwards curve viewed as a Montgomery curve which always works; take the Montgomery curve and use something called the Montgomery ladder. What's interesting about the Montgomery ladder is that you you only have to work with one coordinate instead of two, you can have only the u coordinate of a point, which is easy to send through the network; then your arithmetic can be very small. There's a very simple procedure where n plus a point and n times a point, starting from the point, given the u coordinate, where the n+1 and so on is computed with half of n; you can figure out half of n plus 1 times p, and apply certain formulas, recursively, to get n + 1 times P and n times P. And the fact that this always works is really nice.

One last comment on the Montgommery slide is that those of you have heard about the prime 25519 in other contexts, ... Curve25519 (see also wikipedia on Curve25519) is a Montgommery curve in exactly the shape, and it's the same curve we showed you before, and another way of moving between those coordinates. It's the same mathematical object but there's different ways of representing it. Curve25519 is still the same curve. It's not that we said you should use this because we said so, it's still the same curve.

Standards

There are other people recommending curves. There's a whole long list of standards starting in 1991. So remember, Victor Miller and also Koblitz in 1985 suggested using elliptic curves. We credit Miller because he had the index calculus result. We credit both of them though. ANSI caught up later and they proposed elliptic curves. And then there's the Certicom group. ... explaining how to choose curves, and NIST is proposing curves, and then there's a Brainpool group, and then there's NSA Suite B after that, and then there's also 2011 ANSI, it's not a typo, you always have to type something special so they threw in an extra s here.

There's a wonderful xkcd about okay there's 15 standards out there. We should redo something to merge them. Well crap, now we have 16 standards. We also have a suggestion of how one should use secure curves. To highlight what we mean by this, we have a webpage called Safecurves where we evaluate the security of curves there. We also give rationale and some background.

What do the standards say

So what do all the standards say and what do we say about choosing curves? Actually there's a lot of agreement, there's complete consensus on a lot of criteria. The research is saying what's safe, except for, well you'll hear the exceptions later. First of all, all these standards will say we're looking at elliptic curves, don't use the clock. They all say the number of curve points have to have a big prime divisor in it. This is not hard to do the computation for. You can figure out the number of curve points, and you can figure out that there is a big prime in it. But if the prime for the field was around 2255, and the L for that one is something like 2252 or something... in general I would say 2200. The attacks we have take square root of L symbol operations. So if L was 2200 or bigger, that means it's at least 2100 operations to break. That's a pretty serious number of operations. We recommend 2255 or 2256, and then it's 2128 operations and that's a massive number of operations. If you can afford it, take L even higher. The last criteria is that L must not have some weird relationship to the prime p that you're doing arithmetic mod p. So L is not allowed to divide p, or (p2 - 1) or square root of p, or up to p20 - 1. If you made a curve that actually had this weird feature, like L being p + 1, which you could do, that would actually be something like a circle in describe, where you could transfer your curve to a circle, which is scary because we know that circles are vulnerable to index calculus. So don't have L being one of thse special values. And also, there's no point in stopping at 20, you could go up to 1000, but 20 is where all standards agree.

There's something that not all standards agree on, but it's a cautious thing to do to avoid unnecessary structure. Let's say I give you arithmetic speedup that you need on a tiny 8-bit microcontroller, you can only do exact computation, okay fine you only get what you paid for. But if you're on a big computer, and you're .. over a fraction of a microsecond, you should avoid unnecessary structure. Yes, we're throwing away a large fraction of all curves, but what you need in the end is one good curve in order for the Internet to communicate. So you can be selective. You don't need to... the largest possible curve you can imagine, you just want to narrow it down to things that are not scary. So, some things are a little bit scary if the curves have a certain structure, which is called the C-M field, then if you take a random curve out of the pot, even if it as a random curve out of the pot with a large prime factor, then the discriminant is going to be pretty big. Also it shouldn't have any, yeah, any special divisible properties. As I mentioned already, using 20, or 1000, or something up to to something related to the security level, if your L is 200 bits, why not just require that there is no such curve? Most of the curves in our Safecurves webpage is saying, don't choose any suspicious curves. Choose something that fits everywhere. NIST curves sometimes say use a prime... but prime fields, like a comfortable solved thing to do.

Rigidity and curve generation and curve selection and choosing curves

So if you're worried about all these things where maybe there's an attack that uses the structure, so let's just stay away from the structure just in case. Well you should also think what if there is an attack out there that is based on the structure, and what if the attacker has manipulated our choice of curves to be vulnerable to that kind of attack? It's kind of an obscure situation. But maybe, maybe, there's some attack we don't know, like the attacks that maybe exist that exploit this structure - not that anyone has been able to figure this out - but maybe there's an attack that effects some curves maybe one in a million or one in a billion curves- and we haven't figured it out- but maybe the bad guys have figured out, the bad guys of course being the Chinese advanced persistent threat unit somewhere in Shanghai, and maybe the bad guys have figured it out and maybe they have managed to manipulate the standardizAtion of the curve to find a curve and they will tell everyone else yeah this is good but they secretly know the attack that nobody else has figured out. It's a very obscure corner case, but maybe it happens.

The NIST curves are saying that their parameters, they go from ... y2 = x3 - 3x + b. It's explained that - 3x is because of efficiency. And then they say b is generated in a verifiably random way. They publish a seed, such that if you run it through SHA-1 hash function, and do some arithmetic will give you the b value in the standard. Now, is the seed actually random? Where does this thing come from? We don't know. We know how to generate the curves, but we don't know what they tried. If someone in China, if there is somebody who is willing to run a billion hash computations and a billion curve counts, if this person knows a very rare property of elliptic curves, such as one in a billion or one in a trillion, then he has to try that many times to get different hashes and try at the end to publish the one hash that works. This is the same that NIST does. Often NIST tries many different seeds, but for different reasons. Prime order ... for generating the seed. It's not verifiable where this seed number comes from.

The French comes up in 2011 and they say use our curve it's random, and they don't even give you the seed. Well, then a response from the Germans. So the Brainpool project goes through something called Rigidity, which means the people- whatever process that some people carried out to generate a curve, if it's rigid, if the process is rigid, it means it could only have generated a small number of curves, then it means that if they are trying to generate a one in a trillion curve that satisfies some secret property that we don't know, that they know, then they just don't have the flexibility to generate that curve. So a rigid curve generation process protects us against this corner case possibility, because it means the people who generated the curve couldn't have generated many different curves that might be vulnerable. What Brainpool does is, and it's somewhat rigid, is they take the digits of pi, digits of e, and some pattern, feed it through some sort of hash function, and that is what generates the number b. Now, they don't completely explain the hash that they are using. They don't explain why they are using pi and e, instead of square root of 2 like some crypto standards do. It's basically a nothing-up-my-sleeves number, but there's a little bit of weirdness to it. You can actually look at the Brainpool numbers and you see some very weird patterns where they said, oh yeah we shouldn't have chosen that hash; but it had some little bit of flexibility in what they were doing, but not much. It was something like e2pi square root of 13 over 15 minus.. times something and you get this long expression with pi... e and pi, okay. I was around back when doing the Brainpool curves, and e and pi seemed innocent. Well, square root of 2 also seems innocent. Safecurves allows what Brainpool is doing in their rating of different curves. What they are doing is okay. We recommend to take the smallest numbers that satisfies all of their criteria. Instead of taking some random number, you take the smallest number, and that gives you very little flexibility as a curve generator, all you could possibly do is play with the criteria, but that's something where basically people have converged on "here's what the criteria are".

https://www.youtube.com/watch?v=maBOorEfOOk&t=46m50s

Attacking implementations by feeding fake points

So far we have talked about ECC security. Uh, sorry, ECDLP security. Somebody gives you a standard problem, here is the base point, here is where alpha is computed. You don't have access to the computation. And then as mentioned there are timing attacks. That's one example of how real... if you see L is broken... elliptic curve case again.. it's not because someone had found an algorithm better than square root of L, it's because the implementation is leaking information. Someone could feed you a point not on the curve, and depending on how your program is written, you might directly compute with that fake point that you were given. And your output the result. And this might give the attacker about your value a that you otherwise wouldn't have given him. Or the timing information or some weird failure that says oh divide by zero, this point was not legitimate and of course there's something that doesn't happen normally, well the attacker can handcraft an example that maes a failure occur because they operate in the worst case model and not the average case.

So if you change what your curves are, with d being square or not square, that changes whether there are failure cases that are hard to test for. If you choose your curves carefully, you end up with simple implementations that are correct and secure. This is good. It makes ECC much less likely to fail. That's the motivation for Safecurves. That's the difference between the previous standards and the Safecurves site. Here's some extra criteria that makes sure that simple implementations are going to be much less fragile when implementing ECC.

Twist security

Twist security... if we have NIST 224 .. is not a secure curve. And if you have a curve that is not secure; and everything before Safecurves all the standards allow for something like P224, then there's something called twist attacks that will break .. implementations... unless the programmer went to some extra work. The random tests will say yes this implementation is fine. You do your regression tests, everything seems fine, but then you didn't test getting a u coordinate that is not a point on the curve, rather it's a point on something called the twist, and nobody actually checked anything about that. So unless the implementer went to some extra work, which is not obvious, which doesn't seem to have anything to do with functionality, these twist attacks really do break ECC. So we could just tell the implementers hey it's your fault do ECC better and you should test for this, we told you to test for this, why didn't you read page 472 of the spec? Or... you choose a better curve. That's one of the Safecurves requirements, that the curve is twist secure, and then if the implementer doesn't check, then that's fine. If you're interested in more information, here's... the whole thing. This is just an excerpt from the Safecurves website. The green lines are from us and some other research groups.

https://safecurves.cr.yp.to/

Thanks for your attention.

Questions and answers

https://www.youtube.com/watch?v=maBOorEfOOk&t=50m33s

Q: ... non... you get.. my question is.. would that.. the result..

A: The question was whether there was a proof that index calculus attacks wouldn't work on elliptic curves. There is a something called the high function, aand there was a paper about high function elliptic curve, they give arguments for why if you take a curve and lift, and take points, you can't take enough points and you get degradations. What it is exlcuding is attacks lifting an elliptic curve over the field to an elliptic curve over the rationals. If someone comes up with a different index calculus technique, sure, that might work. Also, if you have a ... it's a paper about prime field curves, if you have a binary curve then this does not apply. Are there more questions? I mean, we're still around for a bit. Also someone is walking around with a microphone.

Q: ... url again...?

A: https://safecurves.cr.yp.to/

Q: If you were building an internal CA today, and you had the curve implementations in most browsers today, or RSA, which would you choose between? The broken curves in most browsers, or would you still rely on RSA?

A: Which is way worse, between the following bad options? Look, it's not like the NIST curves are completely broken. It's theoretically possible to do a safe implementation of the NIST curves. Yeah there might be index calculus attacks for RSA, but if you pump up the key sizes sure that might work. Moving forward, we're trying to create a better environment so that it's a lot easier to make seucre implementations. If you're stuck with what's in your browser, it's pretty much using p256, and it's working hard to make sure it's implemented correctly. I would say there's a different kind of risk for p256 and RSA. Both of the implementations are hard to get right. For NIST p256, how worthy is the seed chosen? These are all kind of small risks, but you have to watch out for them. The biggest risk is not having a constant time implementation, which is a problem for both RSA implementations and NIST p256. Pragmatically, I would push to get leliptic curves in there, and then once browsers are comfortable with that, I would get rid of them.

Q: How do attacks relate to ECDSA and signing? Are they same kinds of attacks?

A: If you can do discrete logs, then you can also break ECDSA. So for the signature standard, there is a public key, sam way shown here, we just stuck with Diffie-Hellman because it was somewhat easier to conceptually explain. Also in the signatures you also get to see many more examples for discrete logs; for every signature you see the nonce times a point, and if you break that then you can get the secret keys. There are attacks on ECDSA that do not break the discrete log, that work by oops someone used an obscure random number generator or in the playstation disaster they did not use any randomness at all. We had a proposal called Ed25519 which was using the signature scheme curve we presented earlier, and it also, not just has a better curve, but also has a better data flow for the encryption, so that things like skewed randomness or no randomness at all, they don't involve. So you have pseudorandomness, which is good, you don't need fresh randomness per signature.

Q: Are you spent any time looking at the ECDSA .. in more recent openssh and do you have any comments on their choice of curves or their implementation on susceptibility to constant time and so on?

A: I haven't personally looked at the openssh code. I believe they have vetted support for our recommended curve. I don't know if their implementation is using one of our recommended constant time implementations. Variable time is a huge mess. Side channel attacks are a huge problem for cryptography. Making it easier to do constant time implementations is one of the huge motivations for this work. It's easy to get it right, that's why the curve shape, Montgomery arithmetic, easiest way is to use the ladder, you can still screw up the data flow, but as an advertisement, we have good implementations on the internet, like the NaCl library, which includes a constant-time implementation of Ed25519 for diffie-hellman, and also we will be including a constant-time RSA implementation. We have optimized implementations and we have reference implementations. They all are constant time, they all avoid branches. For example, iphones and tor and so on, these are typically using the software that we have produced.

Q: A lot of people have had trouble getting NaCl to compile on anything other than djb's personal machine. Any comment on libsodium or more portable salt projects to get it to work with ruby and stuff?

A: Yeah so they took the reference implementations we provided, and repackaged those with another build script, and added some optimized assembly implementations, it's a reasonable structure, we're not tied to any particular build system. There's also a new project called TweetNaCl, where we have tweeted in 100 messages a complete implementation of a high-security cryptographic library, ... you see 100 tweets, which is, function for function compatible with salt and provides all the same functions, high-security implementations of ECC and all the necessary secret key cryptography, and 100 tweets is not that much code, you can drop the dot c into .. of course.. with constant time code system. I think libsodium has added some things that we haven't seen, and we can't vouch for that, but to the extent that they have repackaged what we have done, yeah that's fine. For constant time we make sure we're avoiding as much as we can with gcc or C language messing us up. So we have tried to do reviewed assembly implementations, to try to avoid having the compiler included in our trusted toolchain. If you have someone taking similar reference C code, yeah that's fine.

Q: Which of the safe curves would be fastest to implement at 192 bit and other security?

A: Could you repeat the security level?

Q: 128, 192, 256 bit security.

A: Okay. So. Um. Here and upwards... the top ones a little smaller. There are two proposals. Ed25519... both of those are fine. This one was constructed because we wanted one for.. p314... I think more people have looked into Ed25519. I would stick with that one. For the security level of 192 bits, well, .. shameless self-promotion.. Silent Circle gave us a request that asked for a 414-bit prime, it's overkill. It's 414-bit prime, it's more than 2200 security level, but it's as fast as sp384. If you are interested in 192-bit security level, I suppo... for the higher security level, the side is truncated on that slide, but 3 groups have agreed on E5321. It's 25321. If you could afford a curve with that level, sure go for it. I don't think anyone has implemented that yet, but it should be easy to implement in a secure way. It should have performance very similar to other curves of that security level, if you an afford that, then definitely go for E5321.

We'll be sticking around for a bit if there are other questions, and otherwise thanks for you're attention.