“We could prove our innocence by disclosing the details, if only we could remember them”, Jerry Solinas, NSA, page 18.
[deleted]
Safe curves for Elliptic Curve Cryptography [pdf]
61–70 of 76 posts
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#62The 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…
It's always a problem when scientific guidance becomes dogmatic.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#63Earlier quoted context omitted.
SSH by default isn't, but admins can set up their own list of allowed ciphers in their config file. Github, for example, has banned ssh_dss - I think they still support ECDSA, but they only mention Curve25519 and RSA (with caveats) on their SSH keys page.
> SSH by default isn't Yes, and that's fine. But if SSH mandated a certain thing and disallowed even admins to change it it would be the equivalent problem. It's Ubuntu preventing the use of anything but "SafeCurves" that's the problem. If Ubuntu/Canonical want to use them—fine. (Maybe.†) But don't disable the functionality for admins. † Some regulated industries need to use certain Approved Algorithms, which may or…
So, I'm mostly with you here, but I'd say disallowing e.g. MD5 (horribly broken) or anything involving Dual_EC (horribly suspicious) by force would be reasonable. ECDSA/secp* curves, that's more controversial.
The TLS 1.2 -> 1.3 upgrade also disallowed a lot of previously used things, and this was generally considered to be a great improvement (though of course TLS endpoints can be backwards-compatible).
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#64The 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…
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…
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.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#65Earlier quoted context omitted.
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 cur…
I wasn't aware of this interpretation. Thanks.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#66Earlier quoted context omitted.
imo this article dramatically understates the likelihood that the NSA has unpublished factoring algorithms. it also shows the CPU performance plateau, but GPUs have mostly followed exponential performance scaling
The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here. The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimization equivalent to making the GNFS as good as the SNFS, or a bigger breakthrough of say, L(1/4, 2.5), 4096 bit keys could easily be necessary. For reference, this amount of improvement is about the same as the difference between the Quadratic sieve and GNFS.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#67Earlier quoted context omitted.
The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here. The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimizat…
Why yes, if there was an algorithm known good enough to make 4096 bit keys necessary then 4096 bit keys would be necessary. But there isn't and there has been little progress for a long time now.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#68The 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…
It's always a problem when scientific guidance becomes dogmatic.
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.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#69Earlier quoted context omitted.
that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimizat…
Why yes, if there was an algorithm known good enough to make 4096 bit keys necessary then 4096 bit keys would be necessary. But there isn't and there has been little progress for a long time now.
> But there isn't and there has been little progress for a long time now.
publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.
Re: Safe curves for Elliptic Curve Cryptography [pdf]
#70The 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…
> 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.