[cryptography] fyi: diffie-hellman weakness

Paul Wouters paul at cypherpunks.ca
Fri Oct 14 12:34:06 EDT 2016

On Fri, 14 Oct 2016, Givonne wrote:

> http://thehackernews.com/2016/10/nsa-crack-encryption.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+TheHackersNews+%28The+Hackers+News+-+Security+Blog%29&_m=3n.009a.1343.bx0ao08q8s.scz

The article is not entirely correct:

 	the researchers explained that the Diffie-Hellman algorithm
 	does not contain any backdoor itself, but it has been intentionally
 	weakened in an undetectable way by hiding the fact how various
 	applications generate prime numbers.

The paper actually states "we cannot proof common DH values have not
been backdoored". Also, these "applications" referred to should really be
"RFC standards listed DH values for protocols". So they are not
"intentially weaked", we just cannot prove they have not been
intentially weakened. Which in itself is damning, but quite a different

 	So, advanced hackers or well-resourced agencies who are aware of
 	the fact how prime numbers are being generated for trapdoor function and
 	looking to decrypt 1024-bit secured communications can unscramble the
 	discrete logarithm in order to decrypt hundreds of millions of
 	Diffie-Hellman-protected communications.

The researchers never claimed with enough CPU power to be able to
find the trapdoor. Just that with enough CPU power they could create a
trapdoor'ed set of DH values that no one known (including themselves)
could detect without the knowledge of how they were created.

 	The concept of backdooring primes used in the Diffie-Hellman key
 	exchange algorithm is almost similar to the one discovered in the Dual
 	Elliptic Curve Deterministic Random Bit Generator, better known as
 	Dual_EC_DRBG, which is also believed to have been introduced by the NSA.

Note the "also believed [..] by the NSA", which now blames the NSA for
backdooring every RFC standard. I believe the only DH values that are suspect
are the RFC-5114 ones. And people started to distrust these for these
exact reason a few years ago. The new thing now is that the researchers
proved this could have been done.

And it seems no ons is explaining the "use well known/researched primes"
versus the "accept/generate primes without these having been researched
or even proven to be prime" dilemma.


More information about the cryptography mailing list