In traditional DH one chooses two shared parameters: a large prime $p$ and base $g$, which is primitive root $\bmod p$. Suppose that the generation algorithm is broken and $g$ generates only a subgroup (the group with fewer elements than the 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)?
-
$\begingroup$ if $g$ generates only a subgroup, then it can be attacked by using small subgroup, only given that the protocol doesn't verify the validation of elements. you can refer to this link. In this page, i give a example of small subgroup attack. $\endgroup$ – T.B Sep 1 '13 at 14:20
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 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:
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.
-
$\begingroup$ Actually, I would have to disagree that, as long as you pick your DH values randomly, you're probably safe. If your value $g$ has an order $n$ with a small factor $q$, then the attacker can compute the secret exponents modulo $q$. If you pick $g$ and $p$ totally at random, there's a nonnegliable probability that $n$ will have a number of small factors; and hence you'll leak a nontrivial part of the secret. Yes, if you make the secret exponents larger to compensate -- you have to know to do so. $\endgroup$ – poncho Apr 16 '15 at 13:46