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?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
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.
answered Mar 7, 2012 at 2:20
-
4$\begingroup$ Can you recommend some material about deliberately weak $p$,$q$,$g$ sets? $\endgroup$ Commented Dec 22, 2012 at 21:08
-
$\begingroup$ I'd recommend that anyone reading this answer should research the recent Logjam attack on Diffie-Hellman exchanges. Everyone using well known primes from a small global list, may be vulnerable to a pre-computation attack. $\endgroup$ Commented Jun 7, 2015 at 6:30
-
$\begingroup$ Logjam works against any too-small DH group; shared/global only increases the payoff. They argue 1024 is probably unsafe and recommend 2048 but don't criticize 1536, and those are the smallest values in rfc3526. $\endgroup$ Commented Jun 10, 2015 at 8:59
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ Thank you! I was wondering - are the primes defined in the RFC special in any other way than being derived from Pi? Have they undergone any other testing? If so, what makes them safer or better studied? $\endgroup$ Commented Mar 6, 2012 at 2:16
-
6$\begingroup$ Actually, it's not actually true that "it doesn't matter what prime you use"; certain primes (say, primes where $p-1$ is smooth) are a really bad idea. In addition, it's a good to generate $p$ so that you know a large prime factor $q$, so that you can generate a generator for a subgroup that size. $\endgroup$– ponchoCommented Mar 6, 2012 at 2:26
-
$\begingroup$ Thank you for the clarification, poncho. I was trying not to get into the details, but the gist of it. But you are correct, I should have been more weasely. $\endgroup$ Commented Mar 14, 2012 at 3:01
-
1$\begingroup$ @JonCallas: Won't RSA generally fail entirely (i.e. generate public and private "keys" which don't complement each other) if numbers that are supposed to be prime, aren't? Construction of an RSA key pair requires that one knows the prime factorization of the modulus. It need not have exactly two primes, but all primes within it must be known. While one might theoretically find a pair of numbers which aren't prime but yield an encryption/decryption pair, the I think probability of that happening by chance is essentially zero. $\endgroup$– supercatCommented Dec 18, 2014 at 18:33
$\begingroup$
$\endgroup$
1
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.
answered Jun 3, 2016 at 12:02
-
$\begingroup$ This is an old question, asked and answered long before the WeakDH advisory was created, but I think this answer deserves more attention. This gist of this answer - that the most common 1024-bit primes are probably already broken, and you should use at least 2048-bit primes instead - is important. $\endgroup$ Commented Jun 28, 2018 at 22:20