Kleptographic prime number generation
(too old to reply)
Ray Dillinger
2016-10-11 17:34:59 UTC
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 <***@lrw.com>
To: Cryptography <***@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