Bug 2330 - Moduli Generation - Generator 3 not possible at all!
Summary: Moduli Generation - Generator 3 not possible at all!
Status: CLOSED FIXED
Alias: None
Product: Portable OpenSSH
Classification: Unclassified
Component: ssh-keygen (show other bugs)
Version: 6.7p1
Hardware: Other Other
: P5 enhancement
Assignee: Assigned to nobody
URL:
Keywords:
Depends on:
Blocks: V_8_0
  Show dependency treegraph
 
Reported: 2014-12-29 00:52 AEDT by Christian Wittenhorst
Modified: 2021-04-23 15:01 AEST (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Christian Wittenhorst 2014-12-29 00:52:08 AEDT
The cause lies in lines 713+ in moduli.c

/*
 * guess unknown generator
 */
 if (generator_known == 0) {
  if (BN_mod_word(p, 24) == 11)
   generator_known = 2;
  else if (BN_mod_word(p, 12) == 5)
   generator_known = 3;
  else {
   u_int32_t r = BN_mod_word(p, 10);
   if (r == 3 || r == 7)
    generator_known = 5;
  }
 }

As p is Sophie-Germain prime: p=2q+1, where q is a prime as well.

  p   = 5 (mod 12)
  2q+1= 5 (mod 12) 
  2q  = 4 (mod 12)
   q  = 2 (mod 12)

so q would be divisible by 2, but as q is a prime, this is impossible. 

RFC 4419 only mentions generators of 2 or 5.

6.1.  Choice of Generator

   One useful technique is to select the generator, and then limit the
   modulus selection sieve to primes with that generator:

      2   when p (mod 24) = 11.
      5   when p (mod 10) = 3 or 7.


Proposed fixed:

/*
 * guess unknown generator
 */
 if (generator_known == 0) {
  if (BN_mod_word(p, 24) == 11)
   generator_known = 2;
  else {
   u_int32_t r = BN_mod_word(p, 10);
   if (r == 3 || r == 7)
    generator_known = 5;
  }
 }
Comment 1 Darren Tucker 2019-01-23 20:49:27 AEDT
This has been applied and will be in the 8.0 release.

Thanks.
Comment 2 Damien Miller 2021-04-23 15:01:30 AEST
closing resolved bugs as of 8.6p1 release