openssh unix dev - May 2015 - [Bug 2302] with DH-GEX, ssh (and sshd) should not fall back to unconfigured DH groups or at least document this behaviour and use a stronger group

Hi Folks,

The generator value of 5 does not lead to a q-ordered subgroup which is
needed to pass tests in

http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-2007.pdf

  1. Verify that 2 <= y <= p-2

  2. Verify that y^q = 1 (mod p)

It appears that choosing a generator values of 2, 3, 7, 11, or 13
would all work as generator values.

I do understand that RFC 4419 wants you to chose a g = 2 value only when
p (mod 24) == 11, but that is not always a good selection.

With the p value given, and q created with (p-1)/2, running

BN_is_prime_fasttest(p, 0, NULL, ctx, NULL, 0) shows p is prime
q = BN_dup(dhg.p)
BN_sub_word(q, 1)
BN_rshift1(q, q)
BN_is_prime_fasttest(q, 0, NULL, ctx, NULL, 0) shows q is prime
BN_mod_word(p, 24) == 23
BN_mod_word(p, 10) == 3		# RFC 4419 says g == 5 when p (mod 10) = 3
BN_mod_word(p, 12) == 11

If I use the values below, then NIST SP 800-56A Revision 1 of March 2007
tests work on all values of y that I tested. If I use a generator g = 5,
then I was getting failures.

static char *gen = "2";
static char *p 	    "DDE41D70" "21F9DF82"
"40D0BD8E" "14CE1E37" "4A4FFDD0"
	    "73767E84" "C8C347B6" "F8327312"
"77F9D333" "B8BC7CD9"
	    "6ED164DF" "5C6F26E4" "6E4BAF0A"
"A7C87B26" "CE3E1104"
	    "2C1BDDF7" "6095E50D" "7772E5DC"
"0C48EBA0" "E41EC92E"
	    "AFA655DA" "1B6C614E" "1F0F9AD8"
"15BD7505" "AA9B8A26"
	    "5D13956B" "5A26141E" "E812404D"
"E13B821C" "9B7BCA99"
	    "82B8CF7D" "862F8E8A" "373FEFEE"
"4AE46EC2" "122519A2"
	    "AD896ED1" "8CAECEF3" "14D1B98C"
"83358B6E" "9D2F3BC5"
	    "8C1688F1" "62E3CF1F" "F58E57E7"
"B9E14BB3" "7C9C9E96"
	    "92E57C42" "937141C2" "26E84C35"
"B42DED90" "55A7F366"
	    "A61C3CB4" "899B4992" "78ED4C72"
"9CC1DE54" "827E8822"
	    "90F9FC13" "F7F1488F" "897698EA"
"62A99468" "D6F3ED05"
	    "61816C39" "B8279154" "FC7A8E45"
"3CCC4EB1" "ABC777A3"
	    "97B694E1" "B9866C24" "95489F94"
"721A3351" "B252D05F"
	    "E6C78579" "29B34C19" "A8EB42AB"
"ED88FA37" "0DABCA83"
	    "A245DC35" "CFB39982" "4D127507"
"AD540054" "C647F61C"
	    "6BD11CAF" "C3FE5277" "A1014DF6"
"B538BC8B" "FE009315"
	    "BCD60E02" "0DAB840B" "8A4219EB"
"A4E34968" "0BC7CA3A"
	    "9BC36164" "A3D36E32" "5C530B17"
"8747814F" "57589912"
	    "6B307EB6" "3F910DDE" "0F09E505"
"6B2F9F7E" "230A42C1"
	    "1DDD34A9" "B23A6409" "0C2FF9C7"
"F3DD696E" "6828613E"
	    "74A64CFC" "4046ECFA" "997BE849"
"81430D8A" "7F8AEC63"
	    "001E50AF" "9F556567" "A0065A9A"
"013A66A2" "737CEEE4"
	    "68D6A150" "02358AC6" "48D862B0"
"618E6DD6" "A98BBBE9"
	    "E68174D9" "C9FE4568" "BB2D1208"
"3CF6892B" "6B8D5830"
	    "7944955A" "987F3791" "775049BF";

There is probaby a better way to calculate the generator g value using
FCC math, but I am pretty sure that the values you are putting into
https://bugzilla.mindrot.org/attachment.cgi?id=2630 are not going to
be useful if anyone needs to pass NIT SP 800-56A with those values.

Thanks for your time!

	-- Mark

On Wed, May 27, 2015 at 05:08:25PM -0400, Daniel Kahn Gillmor
wrote:
> On Tue 2015-05-26 15:39:49 -0400, Mark D. Baushke wrote:
> > Hi Folks,
> >
> > The generator value of 5 does not lead to a q-ordered subgroup which
> > is needed to pass tests in
> >
> >
http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-2007.pdf
> 
> I pulled revision 2 of this document from here:
> 
> https://dx.doi.org/10.6028/nist.sp.800-56ar2
> 
> The "FFC Domain Parameter Generation" section does say:
> 
>     g is a generator of the cyclic subgroup of GF(p)* of order q,
> 
> But i don't see a recommendation of why this matters.  Surely we
don't
> want the subgroup of order 2, but what is wrong with using a subgroup
> of order 2q = p-1?
> 
> There's clearly no strong security advantage to the 2q subgroup --
> it's just one bit larger -- but is there an attack that works against
> the 2q subgroup that doesn't work against the q subgroup?  If this is
> a known concern, i'd be happy with just a pointer to a paper or web
> page explaining the risks of the larger group.
> 
> otoh, if the goal is just to ensure we have word-for-word compliance
> with SP800-56A, then it's clear that choosing a different generator is
> the way to go (and without much of a security cost).  but i'd like to
> know if there's a reason other than blind-spec-compliance.  Pointers?
> 
> Regards,
> 
>         --dkg
One reason the generator of the full (Z/pZ)* is avoided is because
knowledge of g^a and g^b (both known to Mallory) leaks information about
the shared secret g^(ab) via their legendre symbols.  This is
particularly troublesome in the context of El Gamal.  

I don't have a reference to recommend off-hand but you might want to
google for "decisional diffie hellman assumption".

--mancha
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150527/eab16e75/attachment.bin>