Weak DH primes and openssh

[Daniel Kahn Gillmor]

On Wed 2015-05-27 05:23:41 -0400, Hubert Kario wrote:
> On Tuesday 26 May 2015 15:10:01 Daniel Kahn Gillmor wrote:
>> On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote:
>> > 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
>
> I'm quite sure that this means that gmpy doesn't use pure M-R with randomly 
> selected witnesses.

https://gmplib.org/manual/Prime-Testing-Algorithm.html#Prime-Testing-Algorithm

suggests is chooses a random base, but it also runs some non-M-R tests
before executing M-R:

 http://sources.debian.net/src/gmp/2:6.0.0%2Bdfsg-6/mpz/pprime_p.c/

GMP's M-R tests are using randomly selected witnesses, though:

 http://sources.debian.net/src/gmp/2:6.0.0%2Bdfsg-6/mpz/millerrabin.c/#L92

> Hmm, I have a distinct recollection of reading of a possibility of a
> small subgroup attacks on primes (as in very few primes have this
> property, so randomly selected one are almost certainly not
> problematic, but if you can pick any prime, you can find them)
>
> Maybe what they mean is that this may does not apply to Sophie Germain
> primes, but to "DSA style" primes, I haven't dug too deep into
> this. Creating it pseudo-randomly from nothing up my sleeve numbers
> fixes this issue anyway.

I think you mean "safe primes" where you say "Sophie Germain primes" --
if q = (p-1)/2, and p and q are primes, then p is a "safe prime" and q
is a "Sophie Germain prime".

Small subgroup attacks are not possible for safe primes as long as you
test your peer's public share and the generator to ensure that they are
in the range (exclusive) 1 < x < p-1.

This is because totient(p) = p-1 (because p is prime), and p-1 has only
two factors: 2 and q.  So there exists one small subgroup, but it's of
order 2, and its generator is p-1 (the subgroup cycles between p-1 and
1).  All other elements are generators of order either q or p-1.  There
are no other subgroups, iiuc.

If this is the only attack you're trying to address, and you've already
limited yourself to safe primes, then NUMS properties don't really add
anything.  The NUMS approach is there are to try to avoid the
possibility of other, unknown cryptanalytic attacks against some
infrequent type of group, so that the entity who defines the group can't
force you into this secret corner case if they have special knowledge.

   --dkg