[curves] Kleptographic prime number generation

Ray Dillinger bear at sonic.net
Tue Oct 11 10:34:59 PDT 2016

Forwarded without comment.


-------- Forwarded Message --------
Subject: [Cryptography] "NSA could put undetectable “trapdoors” in
millions of crypto keys"
Date: Tue, 11 Oct 2016 11:56:47 -0400
From: Jerry Leichter <leichter at lrw.com>
To: Cryptography <cryptography at metzdowd.com>

Ars Technicha at

"Researchers have devised a way to place undetectable backdoors in the
cryptographic keys that protect websites, virtual private networks, and
Internet servers. The feat allows hackers to passively decrypt hundreds
of millions of encrypted communications as well as cryptographically
impersonate key owners."

Basically the researchers describe a way to generate primes for which
number sieve is much easier if you know the secret - and there's no way
to detect this by looking at the prime.  In the case of 1024 bit D-H
primes, the result would be to move cracking into a fairly easy range.
And in the case of most of the widely-used 1024-bit D-H primes, nothing
is known about how they were generated.

Original paper at https://eprint.iacr.org/2016/961.pdf.  The paper
points out that all the basic work was done by Gordon back in 1992, but
his technique wasn't able to hide the "spike" successfully, partly
because doing so at the time seemed to require an impractical amount of
computation.  The authors were able to expand the attack and use more
modern hardware to make the attack go through.

                                                        -- Jerry

The cryptography mailing list
cryptography at metzdowd.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161011/5bb4636c/attachment.sig>

More information about the Curves mailing list