openssh unix dev - May 2015 - Weak DH primes and openssh

On Thu, 28 May 2015, Hubert Kario wrote:
> > 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.
>
> that being said, how using NUMS seeds to generate safe prime would
> hurt?
If you're concerned about precomputation, then it effectively gives the
attackers a list of what you're going to use in the future.
> also, doesn't that require us to provide primality certificates for q
> rather than p?
IMO you'd want both to prove a safe prime

-d

On Friday 29 May 2015 09:23:59 Damien Miller wrote:
> On Thu, 28 May 2015, Hubert Kario wrote:
> > > 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.
> > 
> > that being said, how using NUMS seeds to generate safe prime would
> > hurt?
> 
> If you're concerned about precomputation,
I'm afraid for precomputation only in 1024 bit case, 
/which we should strive not to use anyway/
> then it effectively gives the
> attackers a list of what you're going to use in the future.
Not really, no.

We can use this time an initial seed of "OpenSSH 1024 bit prime, attempt
#1".
Next time we generate the primes we can use the initial seed of "2017
OpenSSH
1024 bit prime, attempt #1", but we can use just as well a "2nd
generation
OpenSSH 1024 bit DH parameters, try number 1". Then we can also change the 
algorithm to use this seed for M-R witnesses, or not. Then we can use SHA-512 
instead of SHA-256, or some SHA-3 variant.

The space for possible selected values is rather large...
 
> > also, doesn't that require us to provide primality certificates
for q
> > rather than p?
> 
> IMO you'd want both to prove a safe prime
The process to prove primality of p when you know that q is prime[1] is rather 
simple, just use Pocklington Theorem to do that.

So the primality of q is basically a primality certificate for p.

 1 - continuing the nomenclature of q = (p-1)/2, where p and q are prime
-- 
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/20150529/22443115/attachment.bin>

On Fri, 29 May 2015, Hubert Kario wrote:
> Not really, no.
> 
> We can use this time an initial seed of "OpenSSH 1024 bit prime,
attempt #1".
> Next time we generate the primes we can use the initial seed of "2017
OpenSSH
> 1024 bit prime, attempt #1", but we can use just as well a "2nd
generation
> OpenSSH 1024 bit DH parameters, try number 1". Then we can also change
the
> algorithm to use this seed for M-R witnesses, or not. Then we can use
SHA-512
> instead of SHA-256, or some SHA-3 variant.
If you're constantly changing the parameters, then this is the opposite of
NUMS. Anyway, I don't think a NUMS-like approach is necessary. It certainly
isn't with users independently generating primality certificates.

-d