1

Just heard a podcast that claimed the SSL was broken for small key sizes.

They said that you should use as strong a key as you can afford, without really saying which key sizes should be avoided.

So the question is there a recommend minimum key size?

4 Answers 4

4

Large modulus sizes are a defense against brute-force attempts to rebuild your private key by an attacker who has only your public key. More bits is more variations to check, but in practice, even the "smaller" key sizes are pretty difficult to try to attack.

As to the specific sizes, a 512-bit key is considered pretty insecure at this point, as they've been demonstrated to be breakable in a matter of months with sufficient computing resources. 1024-bit keys are still a bit out of reach, but expect them to be breakable (by someone with massive computing resources) within the next 5 years. 2048-bit keys are probably untouchable until quantum computers become workable, at which point everything using public key cryptography is pretty much out the window.

Separate from the direct security of the key pair, there are other weaknesses around the hashing algorithms used for signing; MD5 is thoroughly broken at this point, and any certificate authority that will sign a cert using MD5 is vulnerable to collision attacks. This was demonstrated a couple years back by a team that created a rogue certificate authority by matching its MD5 hash to that of a legitimate certificate that they had gotten signed by one of the trusted root providers.

Oh, and the myriad of issues in other aspects, including insecure implementations like SSL v2, weaknesses in the specifications like the renegotiation attack, and weak ciphers that are still enabled on most web servers because of legacy clients. All of these aspects must be accounted for in your SSL security considerations.

For key size, though; there's no reason not to use big ones. The costs associated with using larger keys is trivial (extra compute time to validate the certificate).

1
  • 2
    2048-bit keys are probably untouchable - there is nothing that's "untouchable" with cryptography - weaknesses in algorithms hitherto deemed secure did occur in the past and will occur in the future. However, the nature of the weaknesses often just reduces the available keyspace by some orders of magnitude. It is good to have a key which is long enough so you wouldn't need to bother even if the keyspace would be 10^300 times smaller.
    – the-wabbit
    Jun 5, 2011 at 18:55
3

Just heard a podcast that claimed the SSL was broken for small key sizes.

Ehmn, no. SSL (which today presumably means TLS 1.0 or later) isn't broken.

The RSA key exchange is known to have weaknesses when used with smaller key sizes (768 bit and below). That's generally mitigated by increasing the key size.

So the question is there a recommend minimum key size?

Yes. NIST Special Publication 800-57 recommends 2048 bit from 2011 to 2030 (table 4). This blog post provides a quick overview.

So, if you want an official recommendation, it is 2048 bit. But think of what you're securing and what your risk profile is. For example, if you're just securing a user login state (think a user who is logged in to a social network, and needs his login kept secure, but the actual information presented is public), then a 1024 bit or 1536 bit RSA key is probably a good choice too. See these discussions on Security.Stackexchange for some qualified opinions on key sizes and CPU use tradeoffs -- here and here.

2

Sounds to be the famous Debian SSL Bug. Although the bug was Debian Specific it rendered, to my knowledge, all the smaller key sizes useless.

I don't have a link right now but in my mind there's at least 2048 bit for keysizes floating around. For some additional info: A lot of tools break when the certificates have md5 as the hash algorithm - that hit me some time ago and took a while to figure out since the certificates and keys themselves were absolutely OK

2
  • The Debian bug was in the random number generator (basically along these lines) - it caused certain certificates to be generated with predicable random numbers, and affected all key sizes. Jun 5, 2011 at 18:46
  • To be more precise, it rendered all key sizes useless as the generator used for random key generation has been broken by the Debian OpenSSL maintainer.
    – the-wabbit
    Jun 5, 2011 at 18:46
1

I like Bruce Schneier's take on it: "Cryptography is all about safety margins". The larger the key size, the larger the safety margin (and the larger the performance hit). A 512-bit key is probably OK, but probably not for very long. As Shane Madden mentioned, there's ample evidence that they can be broken by a concerted attack in under a few months. If that is enough of a safety margin for you, then you don't immediately need to replace them. 1024-bit keys are probably next to go.

So if you already have Digital Certificates you have purchased that use these key sizes and you are NOT protecting vital company/nuclear secrets you are probably OK for the short term, but you will want to purchase SSL certificates with a larger key size in the future. Is there a big enough safety margin for you? Is it worth the performance hit? Who would be attacking your cryptosystem? A little threat analysis is good for A) figuring out whether you need to do something RIGHT AWAY and B) covering your ass in case something bad happens.

How large a key should be used in the RSA cryptosystem?

As for the slowdown caused by increasing the key size (see Question 3.1.2), doubling the modulus length will, on average, increase the time required for public key operations (encryption and signature verification) by a factor of four, and increase the time taken by private key operations (decryption and signing) by a factor of eight.

As for what that performance penalty will look like in the real world it's really dependent on your application and implementation. It might increase the time by a factor four which only works out to an extra 4/10ths of a second, or it might be four seconds. Testing is important here.

It looks like at this point NIST (SP800-131A) only considers RSA and DSA 2048 key-sizes to be acceptable after 2011-2014 and they must have at least 112 bits of security strength. See the section in SP800-131A on Digital Certificates for more information.

In my opinion it all boils down to this: your safety margin is "small" with 512-bit keys, "not bad" with 1024-bit keys, and "pretty good" with 2048-bit keys. Do a bit of threat analysis and decide how fat your organization's safety margin needs to be, what kind of data you are protecting and what you stand to lose if the cryptosystem protecting it is broken. Make sure to consider existing policy, and any legal requirements you need to comply with.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .