Weak DH primes and openssh

[Hubert Kario]

On Tuesday 26 May 2015 15:10:01 Daniel Kahn Gillmor wrote:
> 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

I'm quite sure that this means that gmpy doesn't use pure M-R with randomly 
selected witnesses.
 
> 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?

As far as I know, the most computationally efficient algorithm is basically 
going over every non trivially composite number and checking all witnesses

point is that this is a proof that such numbers exists, it also shows that the 
resistance to witnesses is not probabilistically independent.

> > 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?

yes, it's so that they are "rigid" in ECC nomenclature

> 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.

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.
-- 
Regards,
Hubert Kario
Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150527/1f6a3a76/attachment.bin>