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

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.

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

Darren Tucker <dtucker at dtucker.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dtucker at dtucker.net
             Blocks|                            |2915
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #1 from Darren Tucker <dtucker at dtucker.net> ---
This has been applied and will be in the 8.0 release.

Thanks.


Referenced Bugs:

https://bugzilla.mindrot.org/show_bug.cgi?id=2915
[Bug 2915] Tracking bug for 8.0 release
-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

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

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |CLOSED

--- Comment #2 from Damien Miller <djm at mindrot.org> ---
closing resolved bugs as of 8.6p1 release

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.