Weak DH primes and openssh

Hubert Kario hkario at redhat.com
Fri May 29 00:54:21 AEST 2015

On Wednesday 27 May 2015 13:11:43 Daniel Kahn Gillmor wrote:
> On Wed 2015-05-27 05:23:41 -0400, Hubert Kario wrote:
> > 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".

yes, I used it as a synonym for "safe 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.

yes, this does sound right
> 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?

also, doesn't that require us to provide primality certificates for q rather 
than p?
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/20150528/7fbcffd2/attachment-0001.bin>

More information about the openssh-unix-dev mailing list