Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526?

Question

I was wondering if the prime numbers defined for use with Diffie-Hellman in RFC 3526 are more trustworthy than generating one's own, especially considering the recent Arjen Lenstra paper (Ron was wrong, Whit is right) which criticized the similarities detected in public keys and prime numbers across the Internet. Am I better off generating my own safe primes, or am I better off using the ones defined in RFC 3526?

Answer 1

Generating your own group for Diffie-Hellman is not a tough issue; but it is somewhat expensive (it depends on the context, but a 25 MHz ARM device would not like to do it often) and it is not really needed: a good point of DH (and DSA) is that the group parameters can be shared between many users, with no ill effect on the confidentiality of their respective private keys.

For plain Diffie-Hellman, what you need is $p$, $q$ and $g$, such that:

• $p$ is a big enough prime (2048 bits are more than enough nowadays);
• $q$ is smaller, but still big enough (say 256 bits), prime value which divides $p-1$ ;
• $g$ is a generator of a subgroup modulo $p$ with an order that is a multiple of $q$.

The DSA standard (FIPS 186-3) includes a rather detailed procedure for generating adequate group parameters (see annex A), which would be fine for DH too.

There is another side to the issue. While randomly chosen $p$, $q$ and $g$ are good for DH with overwhelming probability, it is possible to specially craft $p$, $q$ and $g$ values such that breaking discrete logarithm modulo $p$ (with generator $g$) would be easy (or at least easier). This can be a problem if your application entails producing the DH group parameters and having other people use them for their own key pairs. If you generate the group parameters but do not tell how you generated them (in a verifiable way), then other people could suspect you of having purposely made them weak. For completely usable group parameters which are immune to such suspicions, you need "nothing up my sleeve" numbers. Annex A of FIPS 186-3 describes the generation process in full details precisely so that it can be verified to be random. RFC 3526 uses $\pi$ for the same reasons.

Therefore, reusing published group parameters is a good idea, both for performance (no need to do the generation yourself, you can save on CPU and also code size) and for trust that can be put into the results by other people.

Answer 2

There's nothing wrong with generating your own primes for DH, as long as you know what you're doing.

On the other hand, if you are a bit weak on number theory (or just glad that someone else has done the work, and had it double-checked), there's also nothing wrong with the modulii and generators in RFC 3526.

As for the paper, well, it chiefly noted that when RSA keys are being generated in practice, a common implementation flaw is a lack of entropy. While bad for RSA (because the entire security of RSA assumes that the keys can't be guessed), that's rather irrelevent for DH, because we're going to tell everyone what DH group we're using.

In fact, the DH groups in RFC 3526 have no entropy at all; they all are of the form:

$p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$

where $n$ is the number of bits within the modulus (1436, 2048, etc), and $i$ is the smallest nonnegative integer that makes both $p$ and $(p-1)/2$ prime.

There was no entropy used to generate these primes, hence the observation that some implementations may not have great entropy is irrelevent when selecting the modulii. Of course, entropy is critical when actually performing the DH operation, but that's true no matter which group you pick.

Answer 3

For Diffie-Hellman or any variants like Elgamal or DSA, you're better off using the established primes. It doesn't matter what primes you use, really, as long as they're prime.

The standard primes have had someone nod at them. If you generate your own prime and there's a problem (e.g. it's not really prime), then you're on your own and we will all laugh at you. Non-primes for DH are bad news, as you'll end up with subgroups, and other issues that mean you're not secure.

But more to the point, most of the public primes are public, they are not a security parameter (i.e. a secret). That's an even better reason not to use your own primes.

The primality testing we do is probabilistic. There's no actual guarantee that the number is prime. However, if you found a number that the usual gang of primality tests said was prime and it wasn't, that would be worthy of a paper, if not an assistant professorship.

For RSA, however, it matters that the two number you generate are secret more than they're prime. There are even three-prime variants of RSA. The problem in that paper was that they weren't secret, not that they weren't prime.

The real lesson we learned in this paper is to let your RNG warm up before you use it. Ironically, if the people with the badly-seeded RNGs had thrown in something with very low entropy like time(0), we wouldn't have had this problem because there would have been no easy way to find their crap primes through a simple test like a GCD.

Answer 4

Unlike the primes used in RSA the prime used in DH does not need to be a secret, so using a well-known prime is not a problem from that point of view.

On the other hand much of the work in breaking dh is per-prime not per dh session. That doesn't change the cost of breaking the first session but it does change the average cost of breaking a session.

This is particularly significant for 1024 bit DH. Current estimates say that breaking a 1024 bit DH prime is likely to be very expensive but not totally infeasible. It is suspected that the NSA may have cracked one or more of the most common 1024 bit primes. https://weakdh.org/

So for a given prime length using your own prime is safer. On the other hand a shorter custom prime is generally worse than a longer well-known prime.

If at all possible you should move up to at least 2048 bit, but if you are stuck with 1024 bit then using a self-generated prime is safer than using one of the well-known primes.