Why do predefined FFDHE parameters containt '///////////'?

Question

Recently, Mozilla published a new and excellent version of its SSL Configuration Generator. One of the changes compared to previous versions was to use predefined FFDHE (Finite Field Diffie-Hellman Ephemeral) parameters from RFC 7919 instead of custom generated ones.

These parameters are mandatory in TLS 1.3 - if one wants to use DHE instead of ECDHE - and it makes sense to me to also use them in older versions of TLS.

After downloading the parameters from Mozilla's webserver, I noticed that the file contained many sections of /////////// which I have never seen in a DH parameter file (e.g. generated with OpenSSL) before.

When pasting the file into an ASN.1 decoder, I eventually figured out that the slashes might have something to do with padding. 0xFFFFFF encoded with base64 results in ////. The 0xFF bytes are always at the start and end of the encoded integer. But why do these particular parameters contain a padding, and why do the ones generated with OpenSSL do seemingly not contain such a padding?

Question:

• Why do these particular parameters contain a padding (or many 0xFF bytes at the start and end) and others not?
• Where can I find more information/documentation about the structure of a DH parameter file?

Answer 1

You can use openssl asn1parse -in ffdhe4096.txt to decode the file into two numeric values, called p and g (but those names are not encoded in the file, they are named this way in the Diffie Hellman protocol, see ANSI X9.42 which costs $100 but you can find pirated copies).

Mozilla's value is 4096-bit MODP Group from RFC 3526. The RFC has the formula that produces it, but not an explanation why that formula was chosen.

The ffdhe4096 value from RFC 7919 (which you must use if you use FFDHE with TLS 1.3, which nobody does) also has those "FF" at start and end.

The upper and lower 64 bits (8 bytes, 16 hex chars) are forced to 1, resulting in 16 "F" in the beginning and end of the value of p. This is true for standard DH groups as far as I could find: Appendix E of RFC 2412 "The OAKLEY Key Determination Protocol" from November 1998 defines the so-called Oakley groups, long used for FFDHE, and provides an explanation for this choice:

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.]

Note that openssl dhparam has a -check option, but it is too strict (demanding that if g is 2 then p mod 24 == 11), and though this value doesn't pass this test, it is safe to use. There is an answer about this on Crypto.SE.