[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

[Mark D. Baushke]

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