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) ?
migrated from security.stackexchange.com Aug 28 '13 at 6:56
This question came from our site for Information security professionals.
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:
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 230 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:
When the whole process is fully described, as in Annex A of FIPS 186-4, it can be verified, which guarantees against DH parameters which have been made weak on purpose.