[Cryptography] "NSA could put undetectable “trapdoors” in millions of crypto keys"

Jerry Leichter leichter at lrw.com
Tue Oct 11 21:26:08 EDT 2016


> Yes, It seems prudent to behave as if there has been a breakthrough.
> But that begs the question of what specific actions are prudent.
> 
> First, It seems prudent to replace the tools that generate these fragile primes.
> 
> Perhaps it is the tests of primality in the tools that is allowing a predictable
> set of  keys.  Or perhaps allowing some composite numbers that look prime to be used.
No, that's not it at all.  The primes are really prime.  The weakness is much more subtle.  Number field algorithms are in a sense statistical:  You generate a large number of "probes" each of which gives you a tiny bit of information, and when you have enough information you can combine it to factor (or do a DLOG, as the case may be).  The hidden information essentially lets you generate the "probes" much more efficiently - you can get by with about a factor of 800 fewer "probes" against a 1024-bit prime than someone who doesn't know the hidden information.

>  "The researchers were able to break one of these weakened 1,024-bit primes in slightly 
>    more than two months using an academic computing cluster of 2,000 to 3,000 CPUs."
So with the same equipment, it would have taken someone without access to the hidden information about 70 years.  (If you add in further scaling based on having more CPU's, you can see the origin of the push to get off of 1024-bit primes entirely:  We're at the point where certain organizations can probably mount attacks without any help at all, and soon such attacks will be within the reach of many much smaller organizations.  It is worth pointing out, though, that all number field algorithms have a large extremely parallizable component - the "probes" - followed by a stage for which parallelism doesn't seem to help and extremely large memories are needed.  This has for years been the real bottleneck - but, again, machines are now large enough that 1024-bit primes are vulnerable.)

> The apparent issue that I smell is there is a more bounded set of generated primes
> being generated than expected and that bounded set of generated primes allows a lookup table 
> to operate in a parallel attack.
No.

The issue is that non-randomly-generated primes *may* contain trap doors, and it's impractical to check.  This would be just as true for 2048 bit primes - or *any* primes - though with near-future hardware, even a prime with a trap door is safe (and larger primes are safe for that much longer).

Still ... the real take-away here is:  Don't trust primes generated in non-transparent ways.  You don't know what might be hidden in them.  Almost all the widely used D-H primes were *allegedly* generated using random techniques - but with no details published.  The primes ... just sort of dropped from the sky into the standards.
                                                        -- Jerry


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161011/4d9fbcf0/attachment.html>


More information about the cryptography mailing list