Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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) ?

share|improve this question

migrated from security.stackexchange.com Aug 28 '13 at 6:56

This question came from our site for Information security professionals.

    
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. –  Alex Sep 1 '13 at 14:20

1 Answer 1

up vote 11 down vote accepted

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 Annex A of FIPS 186-4, it can be verified, which guarantees against DH parameters which have been made weak on purpose.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.