How large should a Diffie-Hellman p be?

Question

In a Diffie-Hellman exchange, the parties need to agree on a prime p and a base g in order to continue. Assuming some application that's going to want to initiate handshakes with some large portion of its users, each of which only need to be realistically secure for a few hours,

• Approximately how large should p be?
• How often should p be changed, if ever? Every n handshakes, every m hours/days/weeks?
• Is there a trade-off between dynamic generation/size of p? That is, is it better to find a single ~120 digit prime and constantly reuse it, or to generate a shit-ton of ~28-38 digit primes and randomly pick one per handshake?
• Am I even asking something approaching the right questions (and if not, could you point me in a better direction)?

Intuitively, it seems that size of the chosen secret integers has more to do with the security of the channel than the uniqueness of p, but I'm still asking since I'm no mathematician.

Answer 1

Well, to answer your questions in order:

• How big should $p$ be? Well, it should be large enough to defend against the known attacks against it. The most efficient attack is NFS; that has been used against numbers on the order of $2^{768}$ (a 232 digit number). It would appear wise to pick a $p$ that's considerably bigger than that; around 1024 bits at a minimum, and more realistically at least 1536 bits. Notes:

  • What was actually done is use NFS to factor a 232 digit number; NFS can be adjusted to perform discrete logs to bases of the same size without an undue increase of complexity.
  • Now, you said that the connections need be secure for only a few hours. Now, NFS on numbers of that size is a large effort, almost certain to take longer than a few hours. Now, if you really don't care if someone can retrieve the keys after the connection has ended, it might seem safe to use a smaller modulii; I would personally recommend against it.

  In addition, there's another important point about $p$; $p-1$ should have a large prime factor $q$, and you should know what the factorization of $p-1$ is (so you can pick a value $g$ that is of the order $q$; that is, the smallest value $x>0$ where $g^x = 1 \mod p$ is $x=q$). If you pick a random prime $p$, and a random generator $g$, well, you're probably secure, but you won't be certain (and you'll might leak a few bits of the private exponent if the order of your random $g$ happens to have some small factors).

• How often should $p$ be changed; well, if you pick good values for $p$ and $g$, they don't need to be changed.

• Is there a trade-off between dynamic generation and the size of p? Well, you're far better off picking one large (and well chosen) prime p and g, and sticking to it. From the NFS analysis, a 120 digit prime is of some questionable security; a 28-38 digit prime is far from adequate.

Now, as you might be able to tell from the above discussion, picking good $p$ and $g$ values is not straightforward (at least, if you don't understand the mathematics). One good news is that people have already done the work, and have published good values. See this for some well chosen $p$ and $g$ values; these were originally intended for use in the IKE protocol, but they can be used for other purposes as well. I would personally recommend the 2048 bit value.

Answer 2

Approximately how large should p be?

Current calculations say it's probablly possible to crack a 1024 bit prime today with NSA-level resources and there is speculation that the NSA has cracked some widely used 1024 bit primes.

2048 bit seems to be a common default these days.

How often should p be changed, if ever? Every n handshakes, every m hours/days/weeks?

A lot of the effort in cracking dh is per-prime, not per dh session. So by changing the dh prime you are increasing the average cost of cracking a session.

Is there a trade-off between dynamic generation/size of p? That is, is it better to find a single ~120 digit prime and constantly reuse it, or to generate a shit-ton of ~28-38 digit primes and randomly pick one per handshake?

In general while changing primes does create some extra work for the attacker using a single long prime will give you much better security than many short ones.