Subject: [saag] are RFC 3526 primes "safe"? (Re: [Ietf-krb-wg] RFC 4556 DH parameter oddities)

From: Tom Yu <[email-masked]>
Date: Tue, 13 Mar 2012 22:09:19 -0400

Anyone here able to answer the following?  Or should I ask CFRG?  Thanks.

To: [email-masked]
From: Tom Yu <[email-masked]>
Date: Fri, 09 Mar 2012 14:53:23 -0500
Subject: Re: [Ietf-krb-wg] RFC 4556 DH parameter oddities

Also, could someone with better number theory and/or cryptography
experience than me please confirm whether the RFC 3526 primes are
indeed safe primes?

---

From: Jon Callas <[email-masked]>
Date: Tue, 13 Mar 2012 20:04:53 -0700

> experience than me please confirm whether the RFC 3526 primes are

What would make them non-safe primes?

I'm not being dismissive, I want to know what the concern is.

Is this related to the weak RSA key brou-ha-ha? Or is it just a matter of making sure that they've been properly vetted not to have number-theoretic issues?

In other words, what's the *real* question?

	Jon

---

From: Nico Williams <[email-masked]>
Date: Tue, 13 Mar 2012 22:16:27 -0500

> Is this related to the weak RSA key brou-ha-ha? Or is it just a matter of making sure that they've been properly vetted not to have number-theoretic issues?

These are DH groups though, so this is not about the RSA common primes problem.

DH MODP groups generally need to have safe primes, or so I understand.  E.g.,

http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

which says

"The order of G should be prime or have a large prime factor to
prevent use of the Pohlig–Hellman algorithm to obtain a or b. For this
reason, a Sophie Germain prime q is sometimes used to calculate
p=2q+1, called a safe prime, since the order of G is then only
divisible by 2 and q. g is then sometimes chosen to generate the order
q subgroup of G, rather than G, so that the Legendre symbol of ga
never reveals the low order bit of a."

I believe Tom is asking whether the primes in RFC3526 are safe in this sense:

http://en.wikipedia.org/wiki/Safe_prime

I suppose the answer is: subtract 1, div 2, confirm that the result is
Sophie Germain prime.

I thought of checking the form of the primes myself, but I don't know
what " { [2^1406 pi] + 741804 }" means in this (from RFC3526):

"
   The prime is: 2^1536 - 2^1472 - 1 + 2^64 * { [2^1406 pi] + 741804 }
"

Nico
-- 

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Tue, 13 Mar 2012 22:30:15 -0500

>   The prime is: 2^1536 - 2^1472 - 1 + 2^64 * { [2^1406 pi] + 741804 }

Converting the hex given in the RFC to decimal (with $EDITOR and
dc(1)), and then doing mod 6 produces 5.  Mod 4 it's 3.  Mod 12 it's
11.  And that number minus 1, then div 2, is prime.

So I think it's fair to say that the 1536-bit MODP group given in
section 2 of the RFC is prime.  But there may be more features of the
number than can be tested.

Nico
-- 

Nico
--

---

From: Tom Yu <[email-masked]>
Date: Wed, 14 Mar 2012 00:11:19 -0400

>> I suppose the answer is: subtract 1, div 2, confirm that the result is

Sophie Germain primes are paired with safe primes.  I believe for any
Q that is a Sophie Germain prime, P = 2Q + 1 is a safe prime by
definition.

>>   The prime is: 2^1536 - 2^1472 - 1 + 2^64 * { [2^1406 pi] + 741804 }

It's a fairly simple arithmetic expression that produces the prime in
question.  I don't have enough digits of pi handy to compute it,
though.

> number than can be tested.

The 1536-bit MODP group in RFC 3526 has a safe prime as the modulus,
according to RFC 2412.

I was hoping that someone whose number theory or crypto background is
more substantial than my readings of Wikipedia articles could confirm
my analyses of the RFC 3526 primes.

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 14 Mar 2012 06:11:11 +0200

> >> experience than me please confirm whether the RFC 3526 primes are

The primes in the RFC3526 are generated using the same method than for
RFC2409, i.e. using the method described in the RFC2412:

----------------------------------------------------------------------
2.8 Additional Security for Privacy Keys: Private Groups
...
   The security of a modular exponentiation group depends on the largest
   prime factor of the group size.  In order to maximize this, one can
   choose "strong" or Sophie Germaine primes, P = 2Q + 1, where P and Q
   are prime.  However, if P = kQ + 1, where k is small, then the
   strength of the group is still considerable.  These groups are known
   as Schnorr subgroups, and they can be found with much less
   computational effort than Sophie-Germaine primes.
...
APPENDIX E The Well-Known Groups
...
   The primes for groups 1 and 2 were selected to have certain
   properties.  The high order 64 bits are forced to 1.  This helps the
   classical remainder algorithm, because the trial quotient digit can
   always be taken as the high order word of the dividend, possibly +1.
   The low order 64 bits are forced to 1.  This helps the Montgomery-
   style remainder algorithms, because the multiplier digit can always
   be taken to be the low order word of the dividend.  The middle bits
   are taken from the binary expansion of pi.  This guarantees that they
   are effectively random, while avoiding any suspicion that the primes
   have secretly been selected to be weak.

   Because both primes are based on pi, there is a large section of
   overlap in the hexadecimal representations of the two primes.  The
   primes are chosen to be Sophie Germain primes (i.e., (P-1)/2 is also
   prime), to have the maximum strength against the square-root attack
   on the discrete logarithm problem.

   The starting trial numbers were repeatedly incremented by 2^64 until
   suitable primes were located.

   Because these two primes are congruent to 7 (mod 8), 2 is a quadratic
   residue of each prime.  All powers of 2 will also be quadratic
   residues.  This prevents an opponent from learning the low order bit
   of the Diffie-Hellman exponent (AKA the subgroup confinement
   problem).  Using 2 as a generator is efficient for some modular
   exponentiation algorithms.  [Note that 2 is technically not a
   generator in the number theory sense, because it omits half of the
   possible residues mod P.  From a cryptographic viewpoint, this is a
   virtue.]

----------------------------------------------------------------------

>    The prime is: 2^1536 - 2^1472 - 1 + 2^64 * { [2^1406 pi] + 741804 }

That representation was taken from RFC2412 and it means we take 1406
bits of pi, add 741804 to it and add 64 bits of 1 in the beginning and
to the end to get a Sophie-Germain prime.

Those primes have also been proven to be primes (the original draft
had reference to the proofs, but that was not considered stable enough
and it was removed).
-- 
[email-masked]

---

From: Tom Yu <[email-masked]>
Date: Thu, 15 Mar 2012 09:01:46 -0400

> RFC2409, i.e. using the method described in the RFC2412:

Thanks.  The Abstract of RFC 3526 mentions criteria established by
Schroeppel, but the RFC doesn't elaborate or provide a citation to
these criteria.

> had reference to the proofs, but that was not considered stable enough

That is also useful to know.  I think that gives me enough information
to write a reasonable erratum for RFC 4556.  (though the errata
database is closed for a website upgrade at the moment...)