[cryptography] fyi: diffie-hellman weakness
paul at cypherpunks.ca
Fri Oct 14 12:34:06 EDT 2016
On Fri, 14 Oct 2016, Givonne wrote:
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
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