4 ms·

I don't have much experience in cryptography, so this may be a stupid question, but I've always wondered about whether Elliptic Curve cryptography opens up some

by pryce 7y ago

I don't have much experience in cryptography, so this may be a stupid question, but I've always wondered about whether Elliptic Curve cryptography opens up some possibilities for partially decentralizing encryption standards. My understanding is that end-users of ECC have to decide which curves to use, and constructing a curve de-novo isn't a choice laymen or crypto end-users should ever make, so a set of standardized curves are issued by standards bodies, such as NIST. Cryptographers endorse the math of ECC as not known to be decipherable, provided that the chosen curve (defined eg by 4 points) isn't specifically constructed to be easily compromised; and the problem becomes whether the curve-issuing standards bodies, such as NIST, are acting in the interests of state security agencies (for argument's sake, lets say NSA) who have vested interests in crypto users adopting curves that NSA can break. Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure?

Klathmon 7y ago
While I don't know enough about this stuff to answer your main question, I will point out that there are some popular curves which aren't tied to any one nation or agency. Ed25519 specifically has major contributions from 5 different people from multiple nationalities. It's not quite the decentralized ideal you talk about, but it's somewhat close! https://ed25519.cr.yp.to/ https://ed25519.cr.yp.to/
- chmike 7y ago
  ed25519 is the signature system based on curve25519
cipherboy 7y ago
> Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure? The process would be a little more complicated than simply choosing 4 points, but yes you could do something close enough to this in theory. In actual practice there's really only two sets of curves most people [0] implement, and just about everyone agrees to use: - The NIST p curves - Curve25519/Curve448 by Bernstein &c. Which you use tends to fall on what side of the crypto divide you fall on: - NIST p curves if you care about governmental compliance such as FIPS - Bernstein &c's curves if you care about security and distrust NIST created curves. I personally fall on the latter side but spend most of my time doing software for the former. :) A promised later revision to FIPS will standardize Bernstein &c's curves. Almost nobody implements negotiating arbitrary curves. That's really unsafe. So, as 'tptacek would say... just use Curve25519. [0]: I'm talking about major software such as TLS, VPNs, SSH, Kerberos... etc.
- Aeolun 7y ago
  I don’t follow. How can the curve itself be insecure? Isn’t the security generated by the random points on the curve?
  - mlindner 7y ago
    https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG That's the case I know of. Basically you mathematically design a curve that makes it look like it's random numbers but the numbers aren't actually random.
  - cyphar 7y ago
    There are all sorts of pitfalls and potential attacks even if the curves are truly random[1]. Some curves also require you to verify whether public keys are valid points on the curve (and their security breaks if you don't do so). So they're harder to implement safely. Others are hard to implement in a way that avoids timing attacks. This is one of the reasons more paranoid people have generally preferred Curve25519 over the NIST curves -- the NIST curves have very arbitrary base point values which (in theory) could have been backdoored. NIST later published a proof that if you hashed some other arbitrary values, you get the base points -- but then the follow up question is where did the other arbitrary values come from. [1]: https://safecurves.cr.yp.to/ https://safecurves.cr.yp.to/
    - nullc 7y ago
      It's misleading to claim that 25519 pubkeys don't require validation: In some applications validation isn't required, in other applications validation is simpler but still required. Marketing bullet points aren't a replacement for careful cryptographic review.
hannob 7y ago
There have been attempts in this direction, it's absolutely doable to use a shared seed where many people contribute a random value. However ultimately a different approach was chosen that solves the same problem: You don't choose an arbitrary curve, instead you define a set of properties that you want your curve to have, based on security, speed and ease of implementation. Then you end up picking the very first curve that fulfils that property. That's how Curve25519 was created. There's very little wiggle room in there. Also it should be said that the hypothesies of choosing a "bad" curve that noone can spot are very hypothetical. We know these NIST curves have an unexplained random seed, but noone has an idea how this could've been used for a backdoor.

by pryce 7y ago

Klathmon 7y ago

While I don't know enough about this stuff to answer your main question, I will point out that there are some popular curves which aren't tied to any one nation or agency. Ed25519 specifically has major contributions from 5 different people from multiple nationalities. It's not quite the decentralized ideal you talk about, but it's somewhat close! https://ed25519.cr.yp.to/ https://ed25519.cr.yp.to/

chmike 7y ago
ed25519 is the signature system based on curve25519

cipherboy 7y ago

> Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure? The process would be a little more complicated than simply choosing 4 points, but yes you could do something close enough to this in theory. In actual practice there's really only two sets of curves most people [0] implement, and just about everyone agrees to use: - The NIST p curves - Curve25519/Curve448 by Bernstein &c. Which you use tends to fall on what side of the crypto divide you fall on: - NIST p curves if you care about governmental compliance such as FIPS - Bernstein &c's curves if you care about security and distrust NIST created curves. I personally fall on the latter side but spend most of my time doing software for the former. :) A promised later revision to FIPS will standardize Bernstein &c's curves. Almost nobody implements negotiating arbitrary curves. That's really unsafe. So, as 'tptacek would say... just use Curve25519. [0]: I'm talking about major software such as TLS, VPNs, SSH, Kerberos... etc.

Aeolun 7y ago
I don’t follow. How can the curve itself be insecure? Isn’t the security generated by the random points on the curve?
- mlindner 7y ago
  https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG That's the case I know of. Basically you mathematically design a curve that makes it look like it's random numbers but the numbers aren't actually random.
- cyphar 7y ago
  There are all sorts of pitfalls and potential attacks even if the curves are truly random[1]. Some curves also require you to verify whether public keys are valid points on the curve (and their security breaks if you don't do so). So they're harder to implement safely. Others are hard to implement in a way that avoids timing attacks. This is one of the reasons more paranoid people have generally preferred Curve25519 over the NIST curves -- the NIST curves have very arbitrary base point values which (in theory) could have been backdoored. NIST later published a proof that if you hashed some other arbitrary values, you get the base points -- but then the follow up question is where did the other arbitrary values come from. [1]: https://safecurves.cr.yp.to/ https://safecurves.cr.yp.to/
  - nullc 7y ago
    It's misleading to claim that 25519 pubkeys don't require validation: In some applications validation isn't required, in other applications validation is simpler but still required. Marketing bullet points aren't a replacement for careful cryptographic review.

hannob 7y ago

There have been attempts in this direction, it's absolutely doable to use a shared seed where many people contribute a random value. However ultimately a different approach was chosen that solves the same problem: You don't choose an arbitrary curve, instead you define a set of properties that you want your curve to have, based on security, speed and ease of implementation. Then you end up picking the very first curve that fulfils that property. That's how Curve25519 was created. There's very little wiggle room in there. Also it should be said that the hypothesies of choosing a "bad" curve that noone can spot are very hypothetical. We know these NIST curves have an unexplained random seed, but noone has an idea how this could've been used for a backdoor.