[Cryptography] "NSA could put undetectable “trapdoors” in millions of crypto keys"

[Georgi Guninski]

On Tue, Oct 11, 2016 at 11:56:47AM -0400, Jerry Leichter wrote:
> Ars Technicha at http://arstechnica.com/security/2016/10/how-the-nsa-could-put-undetectable-trapdoors-in-millions-of-crypto-keys/
> 
> "Researchers have devised a way to place undetectable backdoors in the cryptographic keys that protect websites, virtual private networks, and Internet servers. The feat allows hackers to passively decrypt hundreds of millions of encrypted communications as well as cryptographically impersonate key owners."
> 
> Basically the researchers describe a way to generate primes for which number sieve is much easier if you know the secret - and there's no way to detect this by looking at the prime.  In the case of 1024 bit D-H primes, the result would be to move cracking into a fairly easy range.  And in the case of most of the widely-used 1024-bit D-H primes, nothing is known about how they were generated.
> 
> Original paper at https://eprint.iacr.org/2016/961.pdf.  The paper points out that all the basic work was done by Gordon back in 1992, but his technique wasn't able to hide the "spike" successfully, partly because doing so at the time seemed to require an impractical amount of computation.  The authors were able to expand the attack and use more modern hardware to make the attack go through.
>

Haven't read the paper yet.

Isn't this disturbing sign for elliptic curve crypto, where the
"mainstream" curves are given by the "authority"?

Curves are of relatively small order, so even exponential algorithm with complexity
O(n/k) for nice $k$ will break them, not counting subexponential stuff.