Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?]

From: Peter Gutmann <[email-masked]>
Date: Wed, 12 Mar 2014 00:25:12 +0000

Daniel Kahn Gillmor <[email-masked]> writes:

>More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of pi,
>followed by 64 more bits of 0xFF.  I don't know why this sequence was
>selected.  Does anyone have any pointers to reasons you might want the
>modulus structured this way?

    The prime for this group was 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.

    The prime is chosen to be a Sophie-Germain prime (i.e., (P-1)/2 is also
    prime), to have the maximum strength against the square-root attack.  The
    starting trial numbers were repeatedly incremented by 2^64 until suitable
    primes were located.

    Because this prime is congruent to 7 (mod 8), 2 is a quadratic residue.
    All powers of 2 will also be quadratic residues. This prevents an opponent
    from learning the low order bit of the Diffie-Hellman exponent.  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.]

This is from an early Oakley draft draft-ietf-ipsec-isakmp-oakley-03.txt that
references another Oakley draft draft-ietf-ipsec-oakley-01.txt which, however,
doesn't actually contain the text quoted above.  So I guess the reference
would be [Citation needed ^ 2] or [Apocryphal ^ 2].

(Oh, and if anyone feels like confirming the SHA-1 hashes of the primes I
posted last week....).

Peter.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 12 Mar 2014 13:38:59 -0400

On 03/12/2014 01:19 PM, Jeffrey Hutzelman wrote:
> The MODP groups given in RFC5114 are taken from DSS and NIST SP-800-56A,
> and do not have this same structure.  The RFC has nothing to say on how
> they were selected, and my recollection from the last time I looked was
> that the NIST publications don't say anything either.

It's not clear to me that there is any advantage in a DH key exchange to
using the RFC 5114 discrete log groups.

The selection of a discrete log group with a subgroup of targeted size q
(instead of using a group with a safe prime modulus, which only allows
subgroups of at worst (p-1)/2 if you exclude (p-1) as a valid public
key) makes it costly to check whether the peer is forcing your shared
secret into one of the other smaller subgroups.

Note that this kind of subgroup-forcing attack was used in the DHE
variant of Bhargavan et al's recent attack against client certification
in TLS (other mistakes in the TLS protocol played a role in these
attacks too, of course)

Using a group with a known safe prime modulus should avoid this concern.

	--dkg

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 12 Mar 2014 13:19:53 -0400

> would be [Citation needed ^ 2] or [Apocryphal ^ 2].

Actually, that text _does_ appear in RFC2412, in the introduction to
appendix E, where the first five well-known groups are defined.  The
groups defined in RFC3526 have the same structure, but while that
document does make reference to RFC2412, it does not actually claim the
same method was used to select them.  This should be relatively easy to
verify, however.

-- Jeff