[Bug 2330] New: Moduli Generation - Generator 3 not possible at all!

[bugzilla-daemon at mindrot.org]

https://bugzilla.mindrot.org/show_bug.cgi?id=2330

            Bug ID: 2330
           Summary: Moduli Generation - Generator 3 not possible at all!
           Product: Portable OpenSSH
           Version: 6.7p1
          Hardware: Other
                OS: Other
            Status: NEW
          Severity: enhancement
          Priority: P5
         Component: ssh-keygen
          Assignee: unassigned-bugs at mindrot.org
          Reporter: wiwi at progon.net

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;
  }
 }

-- 
You are receiving this mail because:
You are watching the assignee of the bug.