4 ms·

The author never addresses the issue of trusting standard parameters. I agree with them on the rest, but standard parameters need evidence that they were not sp

The author never addresses the issue of trusting standard parameters. I agree with them on the rest, but standard parameters need evidence that they were not specially selected for reasons unknown to everyone else.

FiloSottile 3y ago
Footnote [1] is about different strategies to select trustworthy standard parameters. I believe they are all good enough to make it so that if someone can still "backdoor" the result, they are so far ahead of the outside world that they might as well have broken the whole scheme, without influencing the parameters. [1] https://words.filippo.io/dispatches/parameters/#fn1 https://words.filippo.io/dispatches/parameters/#fn1 (Yes, I hide too much stuff in the footnotes.)
- comex 3y ago
  Out of curiosity, have people considered rigidly defining requirements, but rather than picking the simplest/lowest value that satisfies the requirements, instead having a public “parameter choice ceremony” using a multiparty random number generation protocol to pick a random value that satisfies the requirements? That seems like it would make it much harder to manipulate the value by changing the requirements.
  - woodruffw 3y ago
    This probably leads to regress (why trust the multiparty scheme?), and would only be convincing to a tiny fraction of skeptics (asymptotically, the ones who are least likely to be cranks and therefore the least noisy ones). Meanwhile, a big part of current cryptographic design is recognizing that many of our current primitives have far larger margins than we really need, and that we can squeeze performance out of our schemes by taking a more evidence-based approach to parameter selection/round counts/etc.[1]. [1]: https://eprint.iacr.org/2019/1492 https://eprint.iacr.org/2019/1492
tptacek 3y ago
You're never going to get a satisfactory answer. The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That author's subtext, as I understood it, was that curves should be selected by functional optimization; pick the curve parameters that best solve the engineering problems. It was a useful argument given their preferred curve, 25519, which does indeed have a lot of attractive engineering features! But it's not hard to see that engineering excellence is a selection principle with even more degrees of freedom than mathematical constants; moreover, you're only ever considering optimality at a fixed point in time, but the optimums change over time --- cofactors might be less important when we lack complete additional formulae for a Weierstrass curves, which makes them hard to implement in constant time, but much more important once we do (as is the case now). There's really no way around just doing the computer science and cryptological work of working out curve attacks. That's the Menezes and Koblitz argument from the "Enigma" paper: that the reason to trust the NIST P-curves is that we'd know by now if they were weak (not because NSA doesn't have secret attacks, but because the mechanism by which they were generated would result in whole large classes of broken curves that academic cryptography and mathematics would have caught by now). If you don't find Alfred Menezes and Neil Koblitz persuasive surveyors of elliptic curve security, that's fine, but my response would be that you can't really trust any parameters at all at that point. Certainly, investing trust in the cryptographers best known to the generalist programmer audience seems like a bad alternative strategy.
- phkahler 3y ago
  >> The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That sounds like an argument against standard parameters. Even if we trust an algorithm, we can't trust others to choose parameters for them? The solution seems obvious - find a better way to choose (non-standard) parameters.
- throw0101c 3y ago
  > That's the Menezes and Koblitz argument from the "Enigma" paper […] PDF: > In August 2015 the U.S. National Security Agency (NSA) released a major policy statement on the need for post-quantum cryp- tography (PQC). This announcement will be a great stimulus to the development, standardization, and commercialization of new quantum- safe algorithms. However, certain peculiarities in the wording and tim- ing of the statement have puzzled many people and given rise to much speculation concerning the NSA, elliptic curve cryptography (ECC), and quantum-safe cryptography. Our purpose is to attempt to evaluate some of the theories that have been proposed. * https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf Then-coverage: * https://blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/ https://blog.cryptographyengineering.com/2015/10/22/a-riddle...
EGreg 3y ago
That's why the Bitcoin and Ethereum crowd trust the Koblitz curves like secp256k1 instead of secp256r1 which is the only curve that is in widespread use in browsers, operating systems, secure enclaves etc. The k1 curve has parameters like 15, whereas the "standard" one has curves with parameters chosen as an "arbitrary" number in the billions for some reason. People believe the NSA may have iterated through the previous ones until they found a vulnerable curve, and NIST recommended that. Take a look: https://cointelegraph.com/news/this-researcher-says-bitcoins-elliptic-curve-could-have-a-secret-backdoor https://cointelegraph.com/news/this-researcher-says-bitcoins... “(1) The Koblitz curve is specially designed for faster scalar multiplications. Hence the (signing, verifying and key generation) operations on Secp256k1 are faster than those on Secp256r1. (2) Although the Secp256r1 curve was announced to be randomly selected, there could still exist some suspicion that some backdoor might be secretly set up in the curve parameters. In contrast, the Koblitz curve parameters are mathematically determined, and there is little possibility for setting such a backdoor.” However, given the prevalence of the r1 curve, Ethereum devs might want to add a precompiled contract so that people can sign into the blockchain without trusting web sites and wallet software: https://ethereum-magicians.org/t/eip-7212-precompiled-for-secp256r1-curve-support/14789 https://ethereum-magicians.org/t/eip-7212-precompiled-for-se... https://security.stackexchange.com/questions/256088/is-the-elliptic-curve-secp256r1-without-a-backdoor https://security.stackexchange.com/questions/256088/is-the-e...
uxp8u61q 3y ago
Whereas parameters generated on the fly don't?
teekert 3y ago
Sounds like one has to prove "a negative" https://youtu.be/n-kXok4tznU?t=26 https://youtu.be/n-kXok4tznU?t=26

FiloSottile 3y ago

Footnote [1] is about different strategies to select trustworthy standard parameters. I believe they are all good enough to make it so that if someone can still "backdoor" the result, they are so far ahead of the outside world that they might as well have broken the whole scheme, without influencing the parameters. [1] https://words.filippo.io/dispatches/parameters/#fn1 https://words.filippo.io/dispatches/parameters/#fn1 (Yes, I hide too much stuff in the footnotes.)

comex 3y ago
Out of curiosity, have people considered rigidly defining requirements, but rather than picking the simplest/lowest value that satisfies the requirements, instead having a public “parameter choice ceremony” using a multiparty random number generation protocol to pick a random value that satisfies the requirements? That seems like it would make it much harder to manipulate the value by changing the requirements.
- woodruffw 3y ago
  This probably leads to regress (why trust the multiparty scheme?), and would only be convincing to a tiny fraction of skeptics (asymptotically, the ones who are least likely to be cranks and therefore the least noisy ones). Meanwhile, a big part of current cryptographic design is recognizing that many of our current primitives have far larger margins than we really need, and that we can squeeze performance out of our schemes by taking a more evidence-based approach to parameter selection/round counts/etc.[1]. [1]: https://eprint.iacr.org/2019/1492 https://eprint.iacr.org/2019/1492

tptacek 3y ago

You're never going to get a satisfactory answer. The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That author's subtext, as I understood it, was that curves should be selected by functional optimization; pick the curve parameters that best solve the engineering problems. It was a useful argument given their preferred curve, 25519, which does indeed have a lot of attractive engineering features! But it's not hard to see that engineering excellence is a selection principle with even more degrees of freedom than mathematical constants; moreover, you're only ever considering optimality at a fixed point in time, but the optimums change over time --- cofactors might be less important when we lack complete additional formulae for a Weierstrass curves, which makes them hard to implement in constant time, but much more important once we do (as is the case now). There's really no way around just doing the computer science and cryptological work of working out curve attacks. That's the Menezes and Koblitz argument from the "Enigma" paper: that the reason to trust the NIST P-curves is that we'd know by now if they were weak (not because NSA doesn't have secret attacks, but because the mechanism by which they were generated would result in whole large classes of broken curves that academic cryptography and mathematics would have caught by now). If you don't find Alfred Menezes and Neil Koblitz persuasive surveyors of elliptic curve security, that's fine, but my response would be that you can't really trust any parameters at all at that point. Certainly, investing trust in the cryptographers best known to the generalist programmer audience seems like a bad alternative strategy.

phkahler 3y ago
>> The world's foremost proponent of not trusting standardized parameters wrote and repeatedly submitted a paper demonstrating a model attack that targeted curves built from mathematical constants; when you've "backdoored pi", there's really no place to go from there. That sounds like an argument against standard parameters. Even if we trust an algorithm, we can't trust others to choose parameters for them? The solution seems obvious - find a better way to choose (non-standard) parameters.
throw0101c 3y ago
> That's the Menezes and Koblitz argument from the "Enigma" paper […] PDF: > In August 2015 the U.S. National Security Agency (NSA) released a major policy statement on the need for post-quantum cryp- tography (PQC). This announcement will be a great stimulus to the development, standardization, and commercialization of new quantum- safe algorithms. However, certain peculiarities in the wording and tim- ing of the statement have puzzled many people and given rise to much speculation concerning the NSA, elliptic curve cryptography (ECC), and quantum-safe cryptography. Our purpose is to attempt to evaluate some of the theories that have been proposed. * https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf Then-coverage: * https://blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/ https://blog.cryptographyengineering.com/2015/10/22/a-riddle...

EGreg 3y ago

That's why the Bitcoin and Ethereum crowd trust the Koblitz curves like secp256k1 instead of secp256r1 which is the only curve that is in widespread use in browsers, operating systems, secure enclaves etc. The k1 curve has parameters like 15, whereas the "standard" one has curves with parameters chosen as an "arbitrary" number in the billions for some reason. People believe the NSA may have iterated through the previous ones until they found a vulnerable curve, and NIST recommended that. Take a look: https://cointelegraph.com/news/this-researcher-says-bitcoins-elliptic-curve-could-have-a-secret-backdoor https://cointelegraph.com/news/this-researcher-says-bitcoins... “(1) The Koblitz curve is specially designed for faster scalar multiplications. Hence the (signing, verifying and key generation) operations on Secp256k1 are faster than those on Secp256r1. (2) Although the Secp256r1 curve was announced to be randomly selected, there could still exist some suspicion that some backdoor might be secretly set up in the curve parameters. In contrast, the Koblitz curve parameters are mathematically determined, and there is little possibility for setting such a backdoor.” However, given the prevalence of the r1 curve, Ethereum devs might want to add a precompiled contract so that people can sign into the blockchain without trusting web sites and wallet software: https://ethereum-magicians.org/t/eip-7212-precompiled-for-secp256r1-curve-support/14789 https://ethereum-magicians.org/t/eip-7212-precompiled-for-se... https://security.stackexchange.com/questions/256088/is-the-elliptic-curve-secp256r1-without-a-backdoor https://security.stackexchange.com/questions/256088/is-the-e...

uxp8u61q 3y ago

Whereas parameters generated on the fly don't?

teekert 3y ago

Sounds like one has to prove "a negative" https://youtu.be/n-kXok4tznU?t=26 https://youtu.be/n-kXok4tznU?t=26