So how did the NSA backdoored the Internet or did they???

New ground-breaking paper shows that DSA and DH mod P keys with 1024 bits are vulnerable to practical backdoors which can be exploited to break our secure communications.

Few highlights:

• For such trapdoored primes the DL problem can be solved in 2 months by an academic cluster.
• The work is quite technical and improves on Crypto’92 paper by Gordon.
• New result is a lot stronger than recent work by Wong and Dorey-Chang-Fong-Essex where the number was not prime, which are also very common problems on the Internet.
• There is no known detection method for such trapdoor primes, or not yet.
  • So if this sort of backdoor exists today, it is likely to remain hidden for yet some time.
• • However researchers have also found a handful of primes used on the Internet and which are backdoored in a trivial and detectable way.
• There is a strong suspicion that many of currently used primes on the Internet are of dubious origin. We have lots of “opaque standardized” prime numbers used in many security standards.
  • For example 37% of the Alexa top 1M web sites use primes which are hardcoded in Apache and nobody knows if they are not trapdoored.
  • Similarly in May 2015, 56% of HTTPS handshakes have used a restricted set of primes which are controversial and many could be bugged.
• The only plausible defense at this moment is provably random nothing-up-my-sleeve primes such as defined in TLS 1.3. and some other security standards.
• It is also important to see that these problems concern primarily users and systems which do not apply latest NSA/NIST and other security recommendations (unhappily most people don’t).

Discussion

This is a SPECTACULAR reversal for the recommendation given by Bruce Schneier in Sep 2013 after being given the privilege of examining the bulk of unpublished Snowden files:

• “Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can”, see here.

The impact is also MUCH LARGER than with ECCs: a much larger part of the Internet communications is encrypted using “conventional discrete-log-based systems” than with ECCs (their share is about 10%).