Weak DH primes and openssh

[Hubert Kario]

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

>  This would suggest
> that we really do want primality proofs (and a good way to verify them).

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

> Do those algorithms hold for creating composites that pass M-R tests for
> both p and (p-1)/2 ?

that I don't know, I'd assume it's much harder, that being said, the A014233 
is suspiciously short...

> > I'd be against shipping any primes that are not generated from known,
> > expected values, like hash of "OpenSSH 1024 bit DH prime, try #1"
> 
> This is trying to put some sort of NUMS-y ("Nothing Up My Sleeve")
> constraint on prime generation 

yes

> -- presumably you'd count up from the
> hash value until you find something that passes M-R for both p and
> (p-1)/2, right? 

yes, use it as the base for the PRNG to get candidates

> I observe that the values in ./moduli all seem quite
> similar in that respect (i.e. the values for any given length share most
> of the same prefix, and differ only in the trailing bits).
> 
> Wouldn't primality proofs make this NUMS-y approach less relevant?

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"

-- 
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/20150526/427c2768/attachment.bin>