1024-bit DHE vs 2048-bit RSA

Question

Currently with apache/mod_ssl, if DHE is enabled then a 1024-bit ephemeral key will be used. I found the following quote in Adam Langley's blog:

Ideally the DH group would match or exceed the RSA key size but 1024-bit DHE is arguably better than straight 2048-bit RSA so you can get away with that if you want to.

So it appears that he is advocating something like DHE-RSA-AES256-SHA with 1024-bit ephemeral DH keys over AES256-SHA with a 2048-bit RSA key. My understanding is that 1024-bit DH (ephemeral or not) is of comparable security to 1024-bit RSA. Why would he make such a recommendation? Does he value the forward secrecy offered by DHE that much?

Answer 1

There are two sides to the question:

• Perfect Forward Secrecy: by using a "DHE" cipher suite, you actually encrypt the data with regards to a DH private key which never gets stored on any disk. For any given SSL session, the encryption may be cracked if the attacker succeeds at cryptanalysing the public key used for encryption (DH for a DHE cipher suite, RSA for a RSA cipher suite), or if the attacker steals a copy of the private key. The latter occurrence is actually much more probable in practice for a RSA-based cipher suite; and the point of PFS is to remove that threat.

• RSA vs Diffie-Hellman: for the time being, the best known methods for breaking RSA and DH entail solving two hard problems, integer factorization and discrete logarithm respectively. It so happens that for both problem, the fastest known algorithm is the General Number Field Sieve (though initially a factorization algorithm, a variant of GNFS can be applied to discrete logarithm). For asymptotic complexity, RSA and DH are thus of equivalent hardness when the DH modulus has the same size as the RSA modulus.

  However, in practical term, DH is a tad harder. GNFS includes several phases, the two main being the sieve and then the linear reduction. For a big modulus, the linear reduction becomes the bottleneck because of the sheer size of the matrix. For a given modulus size, you will get the same number of elements in the two matrices (the one for RSA and the one for DH), but the matrix elements are simple bits in the RSA case, vs integers modulo p in the DH case. Thus, the DH matrix is larger.

  It won't make n-bit DH as "hard" as 2n-bit RSA, though. If we look at the records, we see 768-bit for RSA, 530-bit for DH; and the DH case used less raw power. Moreover, it is not completely justified to compare the hardness of 1024-bit DH with the hardness of 2048-bit RSA, since both are in the "cannot break it" zone.

A summary of all this goes thus: while 1024-bit DH is somewhat stronger (theoretically) than 1024-bit RSA, the difference is slight (say, 1024-bit DH is like 1200-bit RSA at most). But in practical terms the risk of private key theft, for a non-ephemeral key, dwarfs out any cryptanalytic risk for any RSA or DH of 1024 bits or more; in that sense, PFS is a must-have and DHE with a 1024-bit DH key is much safer than RSA-based cipher suites, regardless of the RSA key size.

Answer 2

Concur with everything Tom Leek said, but a few more points to consider:

• recent mod_ssl does support DH parameters larger than 1024 and older ones can be patched: http://blog.ivanristic.com/2013/08/increasing-dhe-strength-on-apache.html (updated)

• if you need (or want) to follow US government requirements, NIST Special Pub 800-57 (at csrc.nist.gov) as of last month requires minimum 2048 for integer-based algorithms RSA, DSA and DH (versus 224 ECC, and hash and 112 symmetric).

• if you (may) have Java clients, the (very common) Suncle Java, and I believe also (closely linked) OpenJDK, through current 7, does not handle DH over 1024 bits. To be exact, it implements original DSA (FIPS 186-0) sizes of P 512 to 1024 by 64 and Q 160, not the FIPS 186-3 improvements 2048/224,256 and 3072/256, and for no good reason imposes the same limits on DH. I've seen a bugs.java.com entry that says this will be fixed in Java 8, but google doesn't find it. See also https://stackoverflow.com/questions/6851461/java-why-does-ssl-handshake-give-could-not-generate-dh-keypair-exception OTOH Suncle Java 7 (and 6 if you add an ECC provider) does implement ECDH right and by default gives ECDHE suites preference over DHE, so if your server supports both DH-2048 and ECDH-reasonable, it's okay. (For web clients in general ECDH P-256 seems best.)