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

[Mike Hamburg]

> On Oct 11, 2016, at 12:24 PM, Ray Dillinger <bear at sonic.net> wrote:
> 
> 
> 
> On 10/11/2016 08:56 AM, Jerry Leichter wrote:
> 
>> 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.
> 
> So there is now a potentially very large undetectable class of
> weak keys.
> 
> I suppose the prudent thing to do would be to behave as if there
> has been a breakthrough in factoring such that primes now require
> about twice as many bits length to achieve the same level of
> security against factoring.  For primes whose origins we don't
> know anyway - but that pretty much includes all 'ephemeral' DH
> primes, as well as the primes used to construct RSA keys created
> by others.
> 
> Am I right in thinking that this affects pretty much all pubkey
> crypto operations performed on a modular field -- RSA, DH, ECC,
> etc?
> 
> 				Bear

The paper only talks about prime-field discrete log, meaning classic DH and DSA (not ECDH or ECDSA).  This was suggested in 1992, but the new paper appears to be able to hide the backdoor better — perhaps so well that nobody can find it.

For RSA, the person who generated the primes is the one who’s supposed to read your message anyway.  If they want Eve to be able to read the message, they can just give her the key.  It’s also not difficult to exfiltrate an encrypted seed of the key in the key itself.

For ECC, this sort of back door has been suggested many times, but nobody (publicly) knows if it’s possible to build it.

— Mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3693 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161011/4c575dac/attachment.bin>