dh.md

Diffie-Hellman

Subgroup confinement attacks

The papers by van Oorshot and Wiener [OorWie96] rsp. Lim and Lee [LimLee98] show that Diffie-Hellman keys can be found much faster if the short exponents are used and if the multiplicative group modulo p contains small subgroups. In particular an attacker can try to send a public key that is an element of a small subgroup. If the receiver does not check for such elements then may be possible to find the private key modulo the order of the small subgroup. Several countermeasures against such attacks have been proposed: For example IKE uses fields of order p where p is a safe prime (i.e. $$q=(p-1)/2),$$ hence the only elements of small order are 1 and p-1.

[NIST-SP800-56A] rev. 2, Section 5.5.1.1 only requires that the size of the subgroup generated by the generator g is big enough to prevent the baby-step giant-step algorithm. I.e. for 80-bit security p must be at least 1024 bits long and the prime q must be at least 160 bits long. A 2048 bit prime p and a 224 bit prime q are sufficient for 112 bit security. To avoid subgroup confinment attacks NIST requires that public keys are validated, i.e. by checking that a public key y satisfies the conditions $$2 \leq y \leq p-2$$ and $$y^q \mod p = 1$$ (Section 5.6.2.3.1). Further, after generating the shared secret $$z = y_a^{x_b} \mod p$$ each party should check that $$z \neq 1.$$ RFC 2785 contains similar recommendations. The public key validation described by NIST requires that the order q of the generator g is known to the verifier. Unfortunately, the order q is missing in [PKCS #3]. [PKCS #3] describes the Diffie-Hellman parameters only by the values p, g and optionally the key size in bits:

DHParameter ::= SEQUENCE {
 prime INTEGER, -- p
 base INTEGER, -- g
 privateValueLength INTEGER OPTIONAL }

In comparison RFC 2459 uses the following structure to describe the domain parameters for Diffie-Hellman keys.

DomainParameters ::= SEQUENCE {
     p       INTEGER, -- odd prime, p=jq +1
     g       INTEGER, -- generator, g
     q       INTEGER, -- factor of p-1
     j       INTEGER OPTIONAL, -- subgroup factor, j>= 2
     validationParms  ValidationParms OPTIONAL }

The class DHParameterSpec that defines the Diffie-Hellman parameters in JCE contains the same values as [PKCS #3]. In particular, it does not contain the order of the subgroup q. Moreover, the SUN provider uses the minimal sizes specified by NIST for q. Essentially the provider reuses the parameters for DSA.

Therefore, there is no guarantee that an implementation of Diffie-Hellman is secure against subgroup confinement attacks. Without a key validation it is insecure to use the key-pair generation from [NIST-SP800-56A] Section 5.6.1.1 (The key-pair generation there only requires that static and ephemeral private keys are randomly chosen in the range $$1..q-1)$$.

To avoid big disasters the tests below require that key sizes are not minimal. I.e., currently the tests require at least 512 bit keys for 1024 bit fields. We use this lower limit because that is what the SUN provider is currently doing.

Weak parameters

The DH parameters must be carefully chosen to avoid security issues. A panel at Eurocrypt'92 discussed the possiblity of trapdoors in DL based primitives [Eurocrypt92-panel]. A. Lenstra pointed out that the primes chould be chosen such that the special number field sieve can be used to compute discrete logarithms. Gordon has analyzed methods to generate and detect weak parameters [Gordon92]. Section 4 of Gordons paper describes a method that can detect some special cases, but no general method was given. Recently Fried et al. showed that 1024 bit discrete logarithms with the special number field sieve are feasible [FGHT16]. Moreover some libraries use primes that are susceptible to this attack [FGHT16].

There are only a small number of tests for weak DH parameters such as primes close to a power of two or smooth group orders. These tests are far from exhaustive. Using predefined DH groups (e.g., RFC 3526) avoids many of the problems with weak DH parameters.

DH implementations are sometimes misconfigured. The authors of [WeakDh] analyzed various implementations and found for example the following problems in the parameters: p is sometimes composite, p-1 contains no large prime factor, q is used instead of the generator g.