Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Safe curves for Elliptic Curve Cryptography [pdf]

eprint.iacr.org

Post reply on HN
Print view View original

41–50 of 76 posts

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#41

Post by tptacek »

red_admiral wrote: post #32
tialaramex wrote: post #28

Earlier quoted context omitted.

Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron. My favourite also reasonable explanation for the mysteri…

As far as I'm aware, the other problem with Dual EC is there's two kinds of componets you can use to build a DRBG: "chaotic" (think hash functions, or components thereof) and "algebraic" (highly structured but guaranteed to have certain properties such as minimum period size). Cryptographic common sense is that if you use an "algebraic" generator, you feed the output through a "chaotic" one at the end. This can't pos…

This is really overthinking it. Dual EC is an asymmetric RNG; it "encrypts" its state to a public key, with an undisclosed private key. To believe it wasn't backdoored (as some people, me included, did --- long story!) you have to take on faith that nobody in the world actually has that private key. We're now fairly sure someone does. That's the whole story.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#42

Post by tptacek »

ivlad wrote: post #12
bvrmn wrote: post #9

Earlier quoted context omitted.

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

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 quan…

This is deeply silly.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#43

Post by tptacek »

fguerraz wrote: post #3

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

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.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#44

Post by tptacek »

mike_hearn wrote: post #33
api wrote: post #23

Earlier quoted context omitted.

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 techn…

The argument for a back door goes like this: 1. The NSA is one of the world's only institutions that has any use for the otherwise irrelevant specialism of designing asymmetrically backdoored cryptography algorithms. They also have (or had) lots of maths PhDs writing internal papers. It's reasonable to assume they know things about kleptography that others don't, as it's not a well funded sub-field of cryptography ou…

From memory, so I'm probably wrong, but: I thought the bona fides for Curve25519's design was that it demonstrated clear engineering reasons for all its choices, and Bernstein's issue with other curves was that NUMS constants (like pi, e, etc) were manipulable in the sense that you could take permutations of them --- the (silly) B4D455 paper.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#46

Post by marcosdumay »

mike_hearn wrote: post #7

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…

[flagged]

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#47

Post by marcosdumay »

fguerraz wrote: post #3

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

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.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#48

Post by zahllos »

schoen wrote: post #24
api wrote: post #23

Earlier quoted context omitted.

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 techn…

NSA did make a mysterious announcement a few years ago that people should not use ECC and should go back to older public-key methods. Of course, due to their fundamental conflict of interest and reluctance to share their rationale, very few organizations that didn't have to follow that guidance apparently did so.

This is a bit misinformed.

NSA required the use of "Suite B Cryptography" for commercial vendors of government systems, which in its latest revision meant ECC. However, vendors were (and are) slow to adopt ECC from the previously used RSA. If you want public evidence of how slow such transitions can be, check any other commercial crypto like certificate authorities and see which trust chains are entirely elliptic curve. Mostly people are stuck on RSA, even though elliptic curves broadly offer better speed and smaller keys/signatures for the same or better levels of security. There's also still plenty of deployed DES and SHA-1, even though the former is inadvisable and the latter inexcusable. In fact, from what I read in the response to the NSA proposing to drop SHA-3 in favour of SHA-2 in the new PQ standards, vendors were a bit frustrated at the change because of the short timescale involved in the migration. I interpret the demanding schedule for adoption of PQC as a deliberate choice by NSA - a somewhat passive aggressive response to vendors to tell them to get their acts together, based on their experience of trying to roll out ECC.

What NSA said is "if you haven't migrated to elliptic curve cryptography, you should now wait for post quantum and then start on that". You can read that message here: https://web.archive.org/web/20151123081120/https://www.nsa.g... and here is the exact quote:

> For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.

I don't think there's much mystery here - basically it amounts to a bunch of procurement rules and guidelines.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#49

Post by red_admiral »

tptacek wrote: post #41
red_admiral wrote: post #32

Earlier quoted context omitted.

As far as I'm aware, the other problem with Dual EC is there's two kinds of componets you can use to build a DRBG: "chaotic" (think hash functions, or components thereof) and "algebraic" (highly structured but guaranteed to have certain properties such as minimum period size). Cryptographic common sense is that if you use an "algebraic" generator, you feed the output through a "chaotic" one at the end. This can't pos…

This is really overthinking it. Dual EC is an asymmetric RNG; it "encrypts" its state to a public key, with an undisclosed private key. To believe it wasn't backdoored (as some people, me included, did --- long story!) you have to take on faith that nobody in the world actually has that private key. We're now fairly sure someone does. That's the whole story.

You're probably right, I'm just saying that if you want to design a RNG that doesn't look extremely suspicious, you do it in such as way that there is no way to have a private key to start with. For example with a hash function somewhere in the loop, since these are (presumably) one-way.

Re: Safe curves for Elliptic Curve Cryptography [pdf]

#50

Post by red_admiral »

less_less wrote: post #39
tialaramex wrote: post #28

Earlier quoted context omitted.

Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron. My favourite also reasonable explanation for the mysteri…

> Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron. Hard disagree. Dual_EC_DRBG more-or-less encrypts the…

Bernstein's argument is that, even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open, such as non-constant-time implementations or sloppy handling of invalid data such as points that do not lie on the curve, or in a small-order subgroup (all of which has been seen in practice).
Post reply on HN