5 ms·

Safe curves for Elliptic Curve Cryptography [pdf]

84 points by sebgan 2y ago

zdw 2y ago
Seems to be overloaded, see also the earlier site on this topic from the authors: https://safecurves.cr.yp.to https://safecurves.cr.yp.to
fguerraz 2y ago
It begs the question: what's wrong with RSA??? I've always heard it's because implementation is hard and ECC magically solves most of these problems, but clearly that's not the case...
- adrian_b 2y ago
  Even if many older RSA implementations had serious security bugs, that is not the reason why it is not preferred any more. For equivalent security with ECC (or with AES) at their typical parameters (i.e. 256 to 512 bit elliptic curves or 128-bit to 256-bit AES keys), RSA must use very long keys, even longer than any RSA keys that are used in practice (which are normally no longer than 4096 bits), which makes the RSA operations slow and adds a large overhead to the communication protocols that must send and receive such long keys.
  - upofadown 2y ago
    >RSA must use very long keys, ... But probably no longer than 2048 bits: https://articles.59.ca/doku.php?id=em:20482030 https://articles.59.ca/doku.php?id=em:20482030
    - adgjlsfhk1 2y ago
      imo this article dramatically understates the likelihood that the NSA has unpublished factoring algorithms. it also shows the CPU performance plateau, but GPUs have mostly followed exponential performance scaling
      - upofadown 2y ago
        The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here. The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
        adgjlsfhk1 2y ago
        that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimization equivalent to making the GNFS as good as the SNFS, or a bigger breakthrough of say, L(1/4, 2.5), 4096 bit keys could easily be necessary. For reference, this amount of improvement is about the same as the difference between the Quadratic sieve and GNFS.
        upofadown 2y ago
        Why yes, if there was an algorithm known good enough to make 4096 bit keys necessary then 4096 bit keys would be necessary. But there isn't and there has been little progress for a long time now.
        adgjlsfhk1 2y ago
        > But there isn't and there has been little progress for a long time now. publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.
- ramchip 2y ago
  "Seriously, stop using RSA" https://news.ycombinator.com/item?id=30879442 https://news.ycombinator.com/item?id=30879442
  - bvrmn 2y ago
    It's hilarious foil-hat level shit here: https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91809 https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...
    - ivlad 2y ago
      He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
      - genewitch 2y ago
        This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key. I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
        red_admiral 2y ago
        I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.
        ivlad 2y ago
- red_admiral 2y ago
  According to the 2020 NIST recommendations, if I'm reading correctly, to get the equivalent of 256 bits of symmetric security, ECC needs 512 bit keys (the factor 2 seems unavoidable for any public key system, because math), but for both RSA and finite-field crypto, you need 15k bit keys to get the same security level. This is due to the multiplication group modulo a prime (or a pair of primes in RSA) being vulnerable to "index calculus", a faster-than-brute-force way of attacking things. As the paper says, the main point of ECC is being impervious to index calculus by design, based on an argument by Victor Miller in 1986 about the structure of "point heights" on elliptic curves. RSA implementations have also led to vulnerabilities in the past, and one of the big claims of djb (as the paper's first author is called in the crypto scene) is that Curve25519 and friends are designed specifically to select, among many secure choices, one that is particularly easy to implement without falling into any of the usual traps.
- ogogmad 2y ago
  Tl;dr reason: RSA requires larger key sizes, which makes it slower. ECC makes cryptanalysis more complicated, so the keys can be made smaller, which makes it faster.
- tptacek 2y ago
  Everyone else is talking about key lengths here, but the better reason to avoid RSA is that it's full of footguns that ECC hides from you. ECC constructions don't generally expose a direct encrypt-to-the-public-key operation, which is almost never what you want (unless you're doing RSA-KEM, which nobody does) but frequently what you get. The de facto standard RSA padding --- by the way, another parameter ECC doesn't demand you fix for your system --- is PKCS1v15, which is admits a padding oracle attack that TLS has spent 2 decades going through contortions avoiding. Even the process of randomly generating keys --- for Curve25519 this is practically a simple as "fill a buffer with random bytes" --- has been fraught with problems. The reason not to use RSA is that you're not going to get it right, because it's hard to get right. In cryptography, that makes it intrinsically bad on the merits.
  - less_less 2y ago
    I mostly agree with this, but you could still have advice of like "use only xxx flavor of RSA-KEM for key establishment and yyy flavor of RSA-FDH-SHAKE for sigs" and things would be fine. Those still aren't exactly easy to implement, but they aren't really any harder than ECC. But they do have bigger keys and are slower, especially for keygen.
    - dadrian 2y ago
      They are harder to implement than ECC.
      - less_less 2y ago
        Really? My experience is that RSA in general is harder because it has so many knobs, but if you just lock it to the easiest-to-implement-securely choices then it's not so bad. However, for DJB's point there is a major advantage for X25519/X448 specifically: it's hard to get a huge speedup by implementing them insecurely, and the same is not true of RSA.
- marcosdumay 2y ago
  It's so full of foot-guns that the implementation you are using almost certainly missed a few; It has been partially broken so many times that it's expected it will be partially broken again; (That's how foot-guns are born.) It is slow and expensive, even more because every time it's broken people have to increase their key size, making it slower and more expensive; It's very flexible, so that people keep using it wrong again and again. Arguably that could be a benefit, but it's hard enough to make people use it right, making them get an innovative usage right is almost impossible.
mike_hearn 2y ago
The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that nobody was able to find. But that isn't their stated justification. Instead they cite djb's website. It's apparently not clear enough that the "SafeCurves" are safe in the sense of being easier for cryptographers to implement without bugs, not in the sense that if you have two correct implementations of a "safe" and "unsafe" curve both are equally cryptographically strong. Therefore if people want to migrate to the "safe" curves over time, that's fine, but it's more like migrating stuff from C++ to Rust. It doesn't automatically imply the prior codebase was buggy, and if you do know of a specific bug then you need to fix it anyway so such migrations are always about reducing the risk of future problems through better engineering practices. That doesn't justify creating a lot of disruption across a distributed ecosystem.
- red_admiral 2y ago
  People migrating to djb's curves, or at least allowing them as a first-class citizen, include - SSH (which includes git over SSH - github suggests djb's Curve 25519 as default: https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent) - TLS (recommended in n1.3) - NIST (allows Curve25519, but isn't the default choice) - various cryptocurrency crap The people not on djb's curves yet are PGP/GPG/OpenPGP (available as an "advanced" option but not by default, for backwards compatibility) and as a consequence, debian's package signing (that mostly uses GPG with RSA, afaik). So ubuntu is in good company, even if it makes their job of working with "upstream" harder. [EDIT: apparently changed now - GPG has joined the ranks of djb-by-default] It's only like migrating from C to rust for the person implementing the crypto package and singature verifier. For the average package maintainer, they just have to generate a new key and pass a new command line flag to their sign command.
  - normaler 2y ago
    GPG is using ed25519 keys as default since 2.3 https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/000458.html https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/0004...
madduci 2y ago
I would like to see if the authors of this paper have released some kind of benchmark/validation script/tool implementing the maths and checks behind their paper
- deleted 2y ago
  [deleted]
- less_less 2y ago
  There's a bunch of validation software at https://safecurves.cr.yp.to/verify.html https://safecurves.cr.yp.to/verify.html
nemoniac 2y ago
“We could prove our innocence by disclosing the details, if only we could remember them”, Jerry Solinas, NSA, page 18.
- throw0101a 2y ago
  Apparent backstory: > Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise". > At the time, the "pass a string through SHA1" thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn't have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000's, and this explanation wasn't nearly enough to quell conspiracy theories. > But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he'd forgotten the string he used! * https://news.ycombinator.com/item?id=37784499#unv_37784770 https://news.ycombinator.com/item?id=37784499#unv_37784770
- deleted 2y ago
  [deleted]

84 points by sebgan 2y ago

zdw 2y ago

Seems to be overloaded, see also the earlier site on this topic from the authors: https://safecurves.cr.yp.to https://safecurves.cr.yp.to

fguerraz 2y ago

It begs the question: what's wrong with RSA??? I've always heard it's because implementation is hard and ECC magically solves most of these problems, but clearly that's not the case...

adrian_b 2y ago
Even if many older RSA implementations had serious security bugs, that is not the reason why it is not preferred any more. For equivalent security with ECC (or with AES) at their typical parameters (i.e. 256 to 512 bit elliptic curves or 128-bit to 256-bit AES keys), RSA must use very long keys, even longer than any RSA keys that are used in practice (which are normally no longer than 4096 bits), which makes the RSA operations slow and adds a large overhead to the communication protocols that must send and receive such long keys.
- upofadown 2y ago
  >RSA must use very long keys, ... But probably no longer than 2048 bits: https://articles.59.ca/doku.php?id=em:20482030 https://articles.59.ca/doku.php?id=em:20482030
  - adgjlsfhk1 2y ago
    imo this article dramatically understates the likelihood that the NSA has unpublished factoring algorithms. it also shows the CPU performance plateau, but GPUs have mostly followed exponential performance scaling
    - upofadown 2y ago
      The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here. The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
      - adgjlsfhk1 2y ago
        that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimization equivalent to making the GNFS as good as the SNFS, or a bigger breakthrough of say, L(1/4, 2.5), 4096 bit keys could easily be necessary. For reference, this amount of improvement is about the same as the difference between the Quadratic sieve and GNFS.
        upofadown 2y ago
        Why yes, if there was an algorithm known good enough to make 4096 bit keys necessary then 4096 bit keys would be necessary. But there isn't and there has been little progress for a long time now.
        adgjlsfhk1 2y ago
        > But there isn't and there has been little progress for a long time now. publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.
ramchip 2y ago
"Seriously, stop using RSA" https://news.ycombinator.com/item?id=30879442 https://news.ycombinator.com/item?id=30879442
- bvrmn 2y ago
  It's hilarious foil-hat level shit here: https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91809 https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...
  - ivlad 2y ago
    He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.” Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
    - genewitch 2y ago
      This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key. I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
      - red_admiral 2y ago
        I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.
      - ivlad 2y ago
red_admiral 2y ago
According to the 2020 NIST recommendations, if I'm reading correctly, to get the equivalent of 256 bits of symmetric security, ECC needs 512 bit keys (the factor 2 seems unavoidable for any public key system, because math), but for both RSA and finite-field crypto, you need 15k bit keys to get the same security level. This is due to the multiplication group modulo a prime (or a pair of primes in RSA) being vulnerable to "index calculus", a faster-than-brute-force way of attacking things. As the paper says, the main point of ECC is being impervious to index calculus by design, based on an argument by Victor Miller in 1986 about the structure of "point heights" on elliptic curves. RSA implementations have also led to vulnerabilities in the past, and one of the big claims of djb (as the paper's first author is called in the crypto scene) is that Curve25519 and friends are designed specifically to select, among many secure choices, one that is particularly easy to implement without falling into any of the usual traps.
ogogmad 2y ago
Tl;dr reason: RSA requires larger key sizes, which makes it slower. ECC makes cryptanalysis more complicated, so the keys can be made smaller, which makes it faster.
tptacek 2y ago
Everyone else is talking about key lengths here, but the better reason to avoid RSA is that it's full of footguns that ECC hides from you. ECC constructions don't generally expose a direct encrypt-to-the-public-key operation, which is almost never what you want (unless you're doing RSA-KEM, which nobody does) but frequently what you get. The de facto standard RSA padding --- by the way, another parameter ECC doesn't demand you fix for your system --- is PKCS1v15, which is admits a padding oracle attack that TLS has spent 2 decades going through contortions avoiding. Even the process of randomly generating keys --- for Curve25519 this is practically a simple as "fill a buffer with random bytes" --- has been fraught with problems. The reason not to use RSA is that you're not going to get it right, because it's hard to get right. In cryptography, that makes it intrinsically bad on the merits.
- less_less 2y ago
  I mostly agree with this, but you could still have advice of like "use only xxx flavor of RSA-KEM for key establishment and yyy flavor of RSA-FDH-SHAKE for sigs" and things would be fine. Those still aren't exactly easy to implement, but they aren't really any harder than ECC. But they do have bigger keys and are slower, especially for keygen.
  - dadrian 2y ago
    They are harder to implement than ECC.
    - less_less 2y ago
      Really? My experience is that RSA in general is harder because it has so many knobs, but if you just lock it to the easiest-to-implement-securely choices then it's not so bad. However, for DJB's point there is a major advantage for X25519/X448 specifically: it's hard to get a huge speedup by implementing them insecurely, and the same is not true of RSA.
marcosdumay 2y ago
It's so full of foot-guns that the implementation you are using almost certainly missed a few; It has been partially broken so many times that it's expected it will be partially broken again; (That's how foot-guns are born.) It is slow and expensive, even more because every time it's broken people have to increase their key size, making it slower and more expensive; It's very flexible, so that people keep using it wrong again and again. Arguably that could be a benefit, but it's hard enough to make people use it right, making them get an innovative usage right is almost impossible.

mike_hearn 2y ago

The naming is unfortunate. Some people (Ubuntu...) have concluded that because some curves are branded "safe" that must mean all the other curves are therefore "unsafe" and must be aggressively phased out as if they were MD5. They're changing apt to refuse to download from repositories signed using NIST curves, for instance. This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that nobody was able to find. But that isn't their stated justification. Instead they cite djb's website. It's apparently not clear enough that the "SafeCurves" are safe in the sense of being easier for cryptographers to implement without bugs, not in the sense that if you have two correct implementations of a "safe" and "unsafe" curve both are equally cryptographically strong. Therefore if people want to migrate to the "safe" curves over time, that's fine, but it's more like migrating stuff from C++ to Rust. It doesn't automatically imply the prior codebase was buggy, and if you do know of a specific bug then you need to fix it anyway so such migrations are always about reducing the risk of future problems through better engineering practices. That doesn't justify creating a lot of disruption across a distributed ecosystem.

red_admiral 2y ago
People migrating to djb's curves, or at least allowing them as a first-class citizen, include - SSH (which includes git over SSH - github suggests djb's Curve 25519 as default: https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent) - TLS (recommended in n1.3) - NIST (allows Curve25519, but isn't the default choice) - various cryptocurrency crap The people not on djb's curves yet are PGP/GPG/OpenPGP (available as an "advanced" option but not by default, for backwards compatibility) and as a consequence, debian's package signing (that mostly uses GPG with RSA, afaik). So ubuntu is in good company, even if it makes their job of working with "upstream" harder. [EDIT: apparently changed now - GPG has joined the ranks of djb-by-default] It's only like migrating from C to rust for the person implementing the crypto package and singature verifier. For the average package maintainer, they just have to generate a new key and pass a new command line flag to their sign command.
- normaler 2y ago
  GPG is using ed25519 keys as default since 2.3 https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/000458.html https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/0004...

madduci 2y ago

I would like to see if the authors of this paper have released some kind of benchmark/validation script/tool implementing the maths and checks behind their paper

deleted 2y ago
[deleted]
less_less 2y ago
There's a bunch of validation software at https://safecurves.cr.yp.to/verify.html https://safecurves.cr.yp.to/verify.html

nemoniac 2y ago

“We could prove our innocence by disclosing the details, if only we could remember them”, Jerry Solinas, NSA, page 18.

throw0101a 2y ago
Apparent backstory: > Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise". > At the time, the "pass a string through SHA1" thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn't have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000's, and this explanation wasn't nearly enough to quell conspiracy theories. > But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he'd forgotten the string he used! * https://news.ycombinator.com/item?id=37784499#unv_37784770 https://news.ycombinator.com/item?id=37784499#unv_37784770
deleted 2y ago
[deleted]