3 ms·
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 d
by 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...
- oh_sigh 3y agoHell, even picking seeds like "the text of the NYT headline from [future date]", since the FBI or some other shadowy governmental organization could lean on the NYT editor to construct the headline in a manner that is useful to them
- capitainenemo 3y agoThat seems solvable by picking things about the future that are a lot harder to influence, like the hashes of future bitcoin blocks, or the exact value of all stocks on the NYSE at a given moment in time. ... ok. stock one is probably easier to influence by suborning the exchange :) - all world exchanges?
- rainsford 3y agoIt's an interesting thought experiment, but it feels a little like trying to come up with the best defense against alien invaders. We're already talking about attackers able to craft cryptographic weaknesses decades of peer review can't discover or explain. Trying to figure out how to usefully constrain their algorithm design choices does not seem like a winning strategy. The bitcoin block hash thing is interesting, but if you're talking about an attacker with that kind of unknown but sophisticated capability, how do you know it actually thwarts their plans? Maybe all they need is any large number with high entropy or maybe the leading zeros characteristic of bitcoin block hashes is actually key to their attack? Once you imbue your adversary with unknown powers, it's by definition difficult to know what helps or hurts them.
- capitainenemo 3y agoheh. well, could drop the leading zeros :) But, yeah, magic powers, sure, anything goes. I was just thinking there must be something more reliable than NYT headlines.
- nextaccountic 3y agoIt's way harder to fake physical measurements (like weather, solar activity, etc) published by international bodies, You could maybeeee influence the least significant digit but even this would be hard without cooking up experimental data. Maybe get physical measurements, stock exchange data, newspaper headlines, and bitcoin blocks, all in 6 months in the future, and XOR all of them.
- nmadden 3y ago> 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). If I remember correctly, part of the reason for the cofactor in 25519 is because Montgomery curves have to have a cofactor and only those curves have the nice x-only Montgomery Ladder, which basically rules out invalid curve attacks (so long as the curve is twist-secure — not all the NIST curves are IIRC). Do the complete addition formulas for short Weierstrass curves also fix this? Invalid curve attacks are a major danger for NIST curves. I know you can use compressed point representation to get the same benefit, but that seems very rare in NIST curve implementations (because old now-expired patents). The landscape of NIST prime-order curve implementations is not great. If all those libraries were going to actually switch to complete addition formulas and compressed public keys then I might feel better about them enjoying a renaissance.
- tptacek 3y agoI agree with you, and am reassured by cryptosystems that use 25519 and put on edge by those that use the P-curves (not because of backdoor conspiracy theories, which are silly, but because the P-curves are easy to mess up). But cryptography engineers increasingly disagree with me.
- tptacek 3y ago(oh, also: yes, that's my understanding too, that you're still stuck validating incoming curve points in ECDH, but I think the anti-cofactor people have a corresponding argument for signature schemes.)
- karelpeeters 3y agoCould you share the paper(s) about "backdoors" in physical constants? That doesn't make much sense at first sight.
- UncleMeat 3y agohttps://bada55.cr.yp.to/bada55-20150927.pdf https://bada55.cr.yp.to/bada55-20150927.pdf
- bmulcahy 3y ago>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 Might such discoveries by academics be forcibly suppressed by government agencies?