In a recent article, Bruce Schneier suggested that he prefers classic discrete log crypto over ECC because "I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry."

Can someone elaborate on a case study what the above phrase would mean in the real world? Could a backdoored ECC allow the passive sniffing of HTTPS traffic that uses ECC for the ephemeral key? Can someone explain the logic behind this fear?

  • $\begingroup$ It'd break TLS with ECDHE suites, probably passively. In particular gmail. But since nobody in the public knows a way to weaken the curve by choosing a bad $b$ constant, it's unclear what the impact of such a hypothetical attack would be. $\endgroup$ – CodesInChaos Sep 12 '13 at 11:43
  • $\begingroup$ Wired.com | Hale's AMS Paper | Shumow-Ferguson Paper $\endgroup$ – earthmeLon Feb 7 '14 at 19:40

If the NSA has chosen the elliptic curve parameters (the "constants") in a way that makes the elliptic curve cryptographically weak, then cryptography using that curve might be, well, insecure and breakable by the NSA. For instance, it is known that there exist various classes of elliptic curves where the discrete log problem is easy (or not very hard). If the NSA knows of an additional class of weak curves, and if they were able to influence the choice of parameters, it is plausible they could have chosen the parameters to make the curve weak. Given that the NSA apparently spends $250 million per year on research, it is not implausible that they might know of classes of weak curves that are not known to the public community.

No one currently knows of a concrete, fully-worked-out way they could have done that with the NIST curves (for instance), but at the same time, no one knows of any proof or argument why this would be impossible.

In this scenario, if the curve is sufficiently weak, then it would let them mount passive attacks: by eavesdropping on traffic that is protected with ECC using those curves, they could break the ECC crypto and decrypt the traffic. Hypothetically. Yes, in this scenario, it could let them passively sniff HTTPS traffic that is using an ECC-based ciphersuite. This is all terribly speculative, but you asked how it could happen, at least in principle.

| improve this answer | |
  • 1
    $\begingroup$ +1. Of course, if you are willing to hypothesize unknown NSA capabilities, then nothing is secure from them, "at least in principle" :-). I keep going back and forth on whether they know something relevant about the NIST curves, or if this is all just the Dual_EC_DRBG backdoor getting exaggerated in the retelling. No doubt Schneier is spooked, though; his new GPG key is not ECC based. $\endgroup$ – Nemo Sep 16 '13 at 1:20
  • $\begingroup$ The standard also "suggests" points $P$ and $Q$ (and implementers tend to use and did use those choices) whose origin is not explained. No need to break the elliptic curve discrete log problem, see rump2007.cr.yp.to/15-shumow.pdf $\endgroup$ – j.p. Sep 16 '13 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.