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.
- 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).
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%).