Why should the dh keylength match rsa length in tls?

Question

A few sources state that the DH keylength (bits of the prime) should match the keylength of rsa for TLS. For example SSL_set_tmp_dh(3) from openssl has example code on how to match the dh parameters to the key being used.

Obviously, one doesn't want DH to be the weakest link in the chain. Using AES-256 and only securing the key-exchange with DH-512 is stupid, of course.

Is there any other reason for matching keylengths? Especially, is there anything to the protocols, that requires this?

The corollary question would be: If I always use DH-2048 (and everything else is either comparably secure or weaker), would this hurt anything (except maybe performance)?

Answer 1

In the "DHE_RSA" cipher suite, security is relative to both that offered by Diffie-Hellman, and that offered by RSA. "In general", the overall security will be that of the weakest of the two; so:

• it is harmful if the DH key is weaker than the RSA key, because then overall security is lowered (compared to what the RSA key alone offers);
• it is harmful if the DH key is stronger than the RSA key, because you do not get actual extra security (it is limited by that of the RSA key), but you still have to pay for the extra large key (larger messages, higher computational cost, and loss of interoperability with limited clients).

It so happens that DH and RSA seem to offer similar strength when used with keys of similar sizes, i.e. DH modulo a 1024-bit prime can be said to be somewhat as strong as RSA with a 1024-bit modulus (but a non-prime modulus, of course). So this gives the rule that the DH key and the RSA key should have the same length.

---

When you look at the details, things are less clear-cut:

• In a DHE_RSA cipher suite, DH and RSA are used for different purposes. RSA is for a signature and its security target is limited to the present. Suppose that you do a SSL connection today. The attacker records it. Then he sets out to break the connection. Five years from now, after extensive computations and thanks to technology improvements, the attacker succeeds to break the DH key: the attacker can then decrypt the recorded connection and learn your secrets. However, suppose that instead of concentrating on DH, the attacker broke the server's RSA key. The attacker then... has nothing ! Breaking the RSA key gives him power to impersonate the server for future connection, but it won't help him a bit with the decryption of past connections. Meanwhile, you renewed your server's certificate at least once or twice, with a new key each time, so all the attacker's efforts went to naught.

  For this reason, the security of RSA and the security of DH in a "DHE_RSA" cipher suite cannot be readily compared; they don't have the same scope or target level, and, overall, the security of RSA is less important than that of the DH.

• DH and RSA have comparable security for the same modulus length only in a rough sense. The known best algorithm for breaking RSA is the General Number Field Sieve, and the known best algorithm for breaking DH is also GNFS. However, for big modulus (say, 1024 bits or more), the bottleneck of GNFS is the "linear algebra" phase, which is last in the algorithm: it is a mathematically trivial computation on a matrix of extremely non-trivial size. This is very hard to compute in parallel, and requires a machine with a tremendously huge amount of very fast RAM. In fact there is no existing computer which would be up to the task for 1024-bit RSA or DH (a dedicated machine can be envisioned without breaking laws of physics, but it would cost a pretty penny).

  It turns out that the GNFS variant which breaks DH has the same linear algebra step, but with a "bigger" matrix; not with more elements, but the elements are now integers modulo p (the prime modulus) instead of mere bits. This means that the matrix for breaking DH is a thousand times bigger (conceptually) than the matrix for breaking RSA with a similar key size. This implies that, in practice, 1024-bit DH is harder to break than 1024-bit RSA.

  (Also in practice, 1024-bit DH and 1024-bit RSA are unbroken within the current economico-technological context, so any robustness comparison must be considered with a grain of salt; an algorithm cannot be less broken than not broken.)

• You cannot necessarily choose the DH modulus as you would like. Existing implementations can be limited, for a variety of historical reasons. Some clients may have trouble using a DH modulus longer than 1024 bits, even if they have no problem with a 2048-bit RSA key. Equality of robustness and security balance are fine things, but data must flow nonetheless. A failure to establish a connection is very secure but not very useful.

So while a systematic 2048-bit DH modulus will not hurt anything security wise, and will incur only moderate overhead (over a 1024-bit DH, this means 250 to 500 extra bytes per full handshake, and some extra CPU, but nothing critical), it may break compatibility with existing, old clients, so this calls for tests. At least, from the point of view of the standard, 2048-bit DH is fine, regardless of the size of any RSA key involved in the mix.

Answer 2

"Obviously, one doesn't want DH to be the weakest link in the chain. Using AES-256 and only securing the key-exchange with DH-512 is stupid, of course." Exactly. DH and RSA are different, but the most effective algorithm to brute force them is the same (see Tom Leeks's answer), so their security levels are similar. (DH is actually a little bit stronger.) Making your DH parameters and RSA keys the same size is the obvious thing to do.

"Is there any other reason for matching keylengths?" No, but you have every reason already.

"Especially, is there anything to the protocols, that requires this?" No, they don't have to match. You can do whatever you want. TLS doesn't care. Indeed, many websites use 2048-bit RSA keys but unfortunately still use 1024-bit DH. (Apache recently fixed this, finally.)

"If I always use DH-2048 (and everything else is either comparably secure or weaker), would this hurt anything (except maybe performance)?" Well, in a secure configuration, everything else will be comparably secure (RSA) or stronger (AES). If you're using something weaker, you should stop. :-) To answer your question, though, I think it would be fine.

Regarding performance, most clients support ECDHE, which is not much slower than non-PFS key exchange. Classic DHE is significantly slower, and it gets worse as the parameter size increases, but it won't make a big difference if most of your clients don't use it and your SSL terminator isn't running overloaded.

Be aware that some clients -- mostly Java -- are incompatible with DH parameters larger than 1024 bits. If you absolutely need compatibility with them, it might make sense to sacrifice some security and use 1024-bit DH, which is still secure, barely. It would be better to solve the problem another way, though. Newer Java versions support ECDHE, for example.

---

Edit: The point made by CodesInChaos and Tom Leek, that your RSA key only has to stay secure for a year or two until your certificate expires, and breaking it only allows impersonating you, but that your DH key has to remain secure for decades until you no longer care if your data is decrypted, is very good. It's probably more important than anything I said, so I shall copy and paste it in here. :-D

---

Edit: By the way, I would caution against exceeding 2048 bits. You'd be entering a realm of less-studied client compatibility issues. Firefox, for example, used to have a limit of around 2200 bits (really). (You could probably ask the GnuTLS community. They have experience with uncommonly large DH.)