Safe curves for Elliptic Curve Cryptography [pdf]

https://eprint.iacr.org/2024/1265.pdf

by sebgan • 2 years ago

84 68 2 years ago

eprint.iacr.org

zdw• 2 years ago

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

fguerraz• 2 years 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• 2 years 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.

upofadown5• 2 years ago

RSA must use very long keys, ...

But probably no longer than 2048 bits:

https://articles.59.ca/doku.php?id=em:20482030

ramchip• 2 years ago

"Seriously, stop using RSA"

https://news.ycombinator.com/item?id=30879442

bvrmn• 2 years ago

It's hilarious foil-hat level shit here: https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...

upofadown5• 2 years ago

My comments on that article:

https://articles.59.ca/doku.php?id=pgpfan:rsabad

red_admiral11• 2 years 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• 2 years 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.

tptacek6• 2 years 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_less7• 2 years 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.

marcosdumay• 2 years 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_hearn3• 2 years 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_admiral11• 2 years 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• 2 years ago

GPG is using ed25519 keys as default since 2.3

https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/0004...

mike_hearn3• 2 years ago

Yes, but SSH isn't e.g. forbidding you from connecting to servers that use RSA or secp256r1, whereas they want to make apt refuse to access repositories that aren't using djb's curves.

Y_Y• 2 years ago

unless you think the NSA have an unknown backdoor that nobody was able to find

Your post names sense to me, but I don't think it's too crazy to allow for the possibility that e.g. the NSA has backdoored some of the "recommended" crypto constants in current use.

red_admiral11• 2 years ago

Snowden said that they were doing this, I think?

api3• 2 years ago

There’s a strong argument against back doors of this type in ECC.

To back door the NIST curves would require that the NSA knows a secret attack against ECC and used brute force search to find seed hashes to generate the curves to be vulnerable. It would have to be a secret attack since nobody else has found it.

Thing is… if this is true it means there is a secret attack against some elliptic curves.

Using 1990s technology they couldn’t have brute forced all that many curves, meaning some non-trivial percentage of curves must be vulnerable.

How do we know curve25519 isn’t vulnerable to this secret attack? We don’t.

The ultimate conclusion is that if NIST curves are backdoored using secret math we shouldn’t use ECC at all, at least unless NSA discloses the math. But they couldn’t do that without blowing up the Internet since so much uses the NIST curves. It would be an argument to phase out all ECC.

api3• 2 years ago

Infosec suffers from a huge cargo cult and mindless sticky meme problem because so few people actually understand it.

There are still admins who block all ICMP because of the “ping of death,” a Windows bug from either the late 1990s or 2000s. They don’t know this though. They just heard that ICMP is “dangerous.”

People also don’t use IPv6 because they think NAT is a security feature.

I guess it’s similar to baseless health fears and happens whenever people don’t really understand a domain. You get a proliferation of lore that is just repeated.

upofadown5• 2 years ago

In either the case of infosec or health, the idea at work is that you can ensure that something is good simply by identifying and removing all that is bad. ... and everyone feels free to determine for themselves what is bad with no deep understanding of the involved systems.

leeter• 2 years ago

People also don’t use IPv6 because they think NAT is a security feature.

Literally had a sales engineer parrot this at me awhile back. I had to point out that the service they were offering was on the open internet. It only got worse from there. Le sigh...

esdf• 2 years ago

Windows had an ICMP CVE last year and also just released a patch for an IPv6 CVE. OpenSSH on Linux had a CVE recently too. Security in depth is reasonable and not baseless.

glitchc• 2 years ago

It's always a problem when scientific guidance becomes dogmatic.

wahern• 2 years ago

Bernstein is savvy enough that I suspect he anticipated how the term "safe" would be interpreted by different groups. That is, he expected and perhaps even intended the subsequent cargo culting.

TacticalCoder• 2 years ago

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

It's "only" a CSPRNG (Cryptographically INsecure PRNG in this case) but the NIST recommending a backdoored curve in the past is an undisputable fact.

So I don't think it's that non-sensical to go for something simple like 2 exp 255 - 19.

https://en.wikipedia.org/wiki/Dual_EC_DRBG

tptacek6• 2 years ago

I don't think you should be using words like "undisputable fact" in this thread, because Dual EC isn't a curve; it's a construction that uses curves.

madduci• 2 years 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

less_less7• 2 years ago

There's a bunch of validation software at https://safecurves.cr.yp.to/verify.html

nemoniac• 2 years ago

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

throw0101a2• 2 years 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

Safe curves for Elliptic Curve Cryptography [pdf]

Related Stories