RSA Key Sizes: 2048 or 4096 bits?

Looking for ZRTP, TLS and 4096 bit RSA in a 100% free and open-source Android app? Lumicall


Many people are taking a fresh look at IT security strategies in the wake of the NSA revelations. One of the issues that comes up is the need for stronger encryption, using public key cryptography instead of just passwords. This is sometimes referred to as certificate authentication, but certificates are just one of many ways to use public key technology.

One of the core decisions in this field is the key size. Most people have heard that 1024 bit RSA keys have been cracked and are not used any more for web sites or PGP. The next most fashionable number after 1024 appears to be 2048, but a lot of people have also been skipping that and moving to 4096 bit keys. This has lead to some confusion as people try to make decisions about which smartcards to use, which type of CA certificate to use, etc. The discussion here is exclusively about RSA key pairs, although the concepts are similar for other algorithms (although key lengths are not equivalent)

The case for using 2048 bits instead of 4096 bits

  • Some hardware (many smart cards, some card readers, and some other devices such as Polycom phones) don't support anything bigger than 2048 bits.
  • Uses less CPU than a longer key during encryption and authentication
  • Using less CPU means using less battery power (important for mobile devices)
  • Uses less storage space: while not an issue on disk, this can be an issue in small devices like smart cards that measure their RAM in kilobytes rather than gigabytes

So there are some clear benefits of using 2048 bit keys and not just jumping on the 4096 bit key bandwagon

The case for using 4096 bits

  • For some types of attack, security is not just double, it is exponential. 4096 is significantly more secure in this scenario. If an attack is found that allows a 2048 bit key to be hacked in 100 hours, that does not imply that a 4096 bit key can be hacked in 200 hours. The hack that breaks a 2048 bit key in 100 hours may still need many years to crack a single 4096 bit key
  • Some types of key (e.g. an OpenPGP primary key which is signed by many other people) are desirable to keep for an extended period of time, perhaps 10 years or more. In this context, the hassle of replacing all those signatures may be quite high and it is more desirable to have a long-term future-proof key length.

The myth of certificate expiration

Many types of public key cryptography, such as X.509, offer an expiry feature. This is not just a scheme to force you to go back to the certificate authority and pay more money every 12 months. It provides a kind of weak safety net in the case where somebody is secretly using an unauthorised copy of the key or a certificate that the CA issued to an imposter.

However, the expiry doesn't eliminate future algorithmic compromises. If, in the future, an attacker succeeds in finding a shortcut to break 2048 bit keys, then they would presumably crack the root certificate as easily as they crack the server certificates and then, using their shiny new root key, they would be in a position to issue new server certificates with extended expiry dates.

Therefore, the expiry feature alone doesn't protect against abuse of the key in the distant future. It does provide some value though: forcing people to renew certificates periodically allows the industry to bring in new minimum key length standards from time to time.

In practical terms, content signed with a 2048 bit key today will not be valid indefinitely. Imagine in the year 2040 you want to try out a copy of some code you released with a digital signature in 2013. In 2040, that signature may not be trustworthy: most software in that era would probably see the key and tell you there is no way you can trust it. The NIST speculates that 2048 bit keys will be valid up to about the year 2030, so that implies that any code you sign with a 2048 bit key today will have to be resigned with a longer key in the year 2029. You would do that re-signing in the 2048 bit twilight period while you still trust the old signature. Fortunately, there are likely to be few projects where such old code will be in demand.

4096 in practice

One of the reasons I decided to write this blog is the fact that some organisations have made the 4096 bit keys very prominent (although nobody has made them mandatory as far as I am aware).

Debian's guide to key creation currently recommends 4096 bit keys (although it doesn't explicitly mandate their use)

Fedora's archive keys are all 4096 bit keys.

The CACert.org project has developed a 4096 bit root

These developments may leave people feeling a little bit naked if they have to use a shorter 2048 bit key for any of the reasons suggested above (e.g. for wider choice of smart cards and compatibility with readers). It has also resulted in some people spending time looking for 4096 bit smart cards and compatible readers when they may be better off just using 2048 bits and investing their time in other security improvements.

In fact, the "risk" of using only 2048 rather than 4096 bits in the smartcard may well be far outweighed by the benefits of hardware security (especially if a smartcard reader with pin-pad is used)

My own conclusion is that 2048 is not a dead duck and using this key length remains a valid decision and is very likely to remain so for the next 5 years at least. The US NIST makes a similar recommendation and suggests it will be safe until 2030, although it is the minimum key length they have recommended.

My feeling is that the Debian preference for 4096 bit PGP keys is not based solely on security, rather, it is also influenced by the fact that Debian is a project run by volunteers. Given this background, there is a perception that if everybody migrates from 1024 to 2048, then there would be another big migration effort to move all users from 2048 to 4096 and that those two migrations could be combined into a single effort going directly from 1024 to 4096, reducing the future workload of the volunteers who maintain the keyrings. This is a completely rational decision for administrative reasons, but it is not a decision that questions the security of using 2048 bit keys today. Therefore, people should not see Debian's preference to use 4096 bit keys as a hint that 2048 bit keys are fundamentally flawed.

Unlike the Debian keys (which are user keys), the CACert.org roots and Fedora archive signing keys are centrally managed keys with a long lifetime and none of the benefits of using 2048 bit keys is a compelling factor in those use cases.

Practical issues to consider when choosing key-length

Therefore, the choice of using 2048 or 4096 is not pre-determined, and it can be balanced with a range of other decisions:

  • Key lifetime: is it a long life key, such as an X.509 root for an in-house CA or an OpenPGP primary key? Or is it just for a HTTPS web server or some other TLS server that can be replaced every two years?
  • Is it for a dedicated application (e.g. a closed user group all using the same software supporting 4096 bit) or is it for a widespread user base where some users need to use 2048 bit due to old software/hardware?
  • Is it necessary to use the key(s) in a wide variety of smartcard readers?
  • Is it a mobile application (where battery must be conserved) or a server that is likely to experience heavy load?

Looking for ZRTP, TLS and 4096 bit RSA in a1 100% free and open-source Android app? Lumicall

Comments

I enjoyed reading your post and think it puts forth sound arguments.

But to say 1024-bit RSA is broken is a bit of a stretch. :)

The linked paper describes how a team of researchers were able to conduct a fault injection attack against a specific implementation under specific conditions.

This has happened before - compare e.g. the history of fault injection and differential power analysis against smartcards or timing attacks against software implementations.

I don't see anything that would make such an attack infeasible against RSA with larger key size in principle. Or make it a cryptographic break of 1024-bit RSA for that matter.

There are probably good reasons to assume that sufficiently motivated (=funded) attackers may be able to break 1024-bit RSA but I don't think an actual cryptographic break has been demonstrated just yet :)

Hi Max,

You made an interesting comment where you said:

"There are probably good reasons to assume that sufficiently motivated (=funded) attackers may be able to break 1024-bit RSA but I don't think an actual cryptographic break has been demonstrated just yet :) "

However in my opinion, there would be a good reason not to let it be known that there was an actual cryptographic break of RSA 1024 bit. My point is just because you dont know about it dosent mean it hasnt happened. So it is just smart to use something higher than the baseline/minimum accepted key length.

The NIST states that it would take an RSA key size of 15360 bits to be equivalent to 256 bit AES. Sure, RSA takes more time, but it's only used to exchange an AES key anyway. So if we aren't bothering to use a key size providing security equivalent to the AES, why are we even bothering?
http://en.wikipedia.org/wiki/Key_size