Mark D. Baushke
2015-May-26 19:39 UTC
[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
mancha
2015-May-27 22:02 UTC
[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
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, > > --dkgOne 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>
Seemingly Similar Threads
- [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
- [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
- [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
- [Bug 2303] New: ssh (and perhaps even sshd) should allow to specify the minimum DH group sizes for DH GEX
- [Bug 2302] New: ssh (and sshd) should not fall back to deselected KEX algos