Weak DH primes and openssh

[Daniel Kahn Gillmor]

On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote:
> On Tuesday 26 May 2015 13:43:13 Daniel Kahn Gillmor wrote:
>> On Tue 2015-05-26 12:57:05 -0400, Hubert Kario wrote:
>> > creating composites that will pass even 100000 rounds of Miller-Rabin is
>> > relatively simple....
>> > (assuming the values for M-R tests are picked randomly)
>> 
>> Can you point me to the algorithms for doing that?
>
> OEIS A014233

Hm, this is a sequence, but not an algorithm.  It looks to me like it is
not exhaustive, just a list of those integers which are known to have
the stated property ("Smallest odd number for which Miller-Rabin
primality test on bases <= n-th prime does not reveal compositeness").

Taking the final integer in that sequence (a(11)) fails even the default
25-round M-R test in gmp:

>>> k = gmpy2.mpz(3825123056546413051)
>>> gmpy2.is_prime(k)
False
>>>

Indeed, the arxiv suggests that in 2012 people were still writing proofs
about a(11) for this sequence:

  http://arxiv.org/abs/1207.0063

but i see no evidence that an algorithm for generating a(n) where n is
arbitrarily large exists.   Does such a thing exist?

> yes, using ECPP and distributing proof with the prime (or just placing it on 
> the project website) is a reasonable minimum, that still leaves out the 
> possibility of a backdoor if the initial seed value is random

it sounds like we're heading into the same territory as the ECDH curve
selection discussion -- the theory you're suggesting is that some
safe-prime moduli could themselves have a backdoor that we don't know
about.  Am i understanding you correctly?

I've been talking with several cryptographers for the last year about
finite-field DH (FFDH) and i haven't heard any suggestion that any of
them think there is likely to be such a class of backdoored moduli.

> yes, it would basically exclude the chance that the primes are backdoored, 
> there's still the chance for the values to be composites
>
> for values to be used on this many machines, I'd say we should have primality 
> proofs, not just M-R "guess"

Does anyone have a pointer to any decent free software for generating
and verifying primality proofs?

          --dkg
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 948 bytes
Desc: not available
URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150526/467bdc1f/attachment.bin>