Diffie-Hellman: choosing wrong generator “g” parameter and its implications of practical attacks

Question

In traditional DH one chooses two shared parameters: a large prime "p" and base "g", which is primitive root mod "p". Suppose generation algorithm is broken and "g" generates only a subgroup (group with less elements than number of coprimes to "p"), what could be the possible attack ? what's the complexity ? are there any real-world examples of attacking wrong DH parameters (implementation) ?

Answer 1

As far as we know, Diffie-Hellman is secure as long as the subgroup generated by g is impervious to discrete logarithm. When working modulo a prime p, this is achieved when the following are met:

• p is large enough (at least 1024 bits, go to 2048 bits for a bigger safety margin) and is not a "special form" prime (a randomly generated prime will be fine with overwhelming probability).

• the subgroup generated by g has an order t which is such that there is at least one prime factor q of t which is "big enough", i.e. more than 2k bits, when k is the "security level" (e.g. to have at least 80-bit security, q should be at least 160 bits).

Note that it is in no way necessary that g generates all non-zero integers modulo p. It is fine if it generates a strict subgroup, as long as that subgroup cannot be split into several subgroups, each being very small. This is the essence of the necessity of at least one medium-sized prime q in the factorization of the subgroup order t.

The order of g, called t above, is a divisor of p-1. With overwhelming probability, a randomly generated g will imply an order which will not be much smaller than p. Indeed, there is only one chance in a billion to hit a g which implies an order t smaller than p by more than 30 bits (because 2³⁰ is about one billion). It is preposterous to imagine that a random g, modulo a 1024-bit prime p, will imply a subgroup order smaller than 900 bits.

The biggest prime factor of a random integer of n bits will have length, on average, about 0.3*n. It is extremely improbable that the biggest prime factor will be much shorter than that.

Bottom-line is that a purely random prime p (of at least 1024 bits) and a purely random g modulo p will be fine. To get bad DH parameters, you have to do it on purpose.

---

However, some people are arguing for ensuring that p and g are fine with "stronger" arguments than the probabilistic properties explained above (mathematically, these probabilities are extremely strong, but convincing people is not only about mathematics, but also about psychology). First, p will be generated as a "nothing up my sleeve" number with a completely open and fully described pseudo-random generator. See appendix A of FIPS 186-4 for an illustration (this is for DSA, but it may apply to DH as well). Then there are two ways for g:

• The smaller prime q could be generated first; then p is produced randomly as p = qr + 1 for random r of the right size, until a prime p is reached. Then a random h modulo p is produced, and g is set to g = h^(p-1)/q mod p. This yields either g = 1 (with extremely small probability) or a g with an order exactly equal to q, which is fine.

• p could be generated as a so-called "safe prime". I.e. random odd integers u are generated until both u and p = 2u + 1 are both prime. Then set g = 2: the order of g is then necessarily equal to u or 2u, and both are fine. Generating a safe prime is computationally expensive, but having g = 2 yields a slight performance boost when doing the actual Diffie-Hellman.

When the whole process is fully described, as in Appendix A of FIPS 186-4, it can be verified, which guarantees against DH parameters which have been made weak on purpose.