7

In Chapter 7 of Applied Cryptography, Bruce Schneier claims that, due to thermodynamic limitations, "brute-force attacks against 256-bit [symmetric] keys will be infeasible until computers are built from something other than matter and occupy something other than space." Looking at a few other questions, it seems that it hasn't somehow become possible.

As per this answer, we might lose a few bits of entropy in a real-world scenario, but I'd think that this would imply that even a really paranoid person would still be more than adequately protected by a 512-bit key.

So why do I often see keys being used that are 1024 or even 2048 bits long? Is it to protect against some other type of attack? Or are we just paranoid?

Community
  • 1
KnightOfNi
  • 2,267
  • 3
  • 19
  • 23
  • Maybe to protect them from aliens, as we don't know what type of computers they might have. :P Interesting question +1 – ρss Jun 13 '15 at 14:47
  • 1
    You might get a better (or at least different) answer to this on [crypto.stackexchange.com](https://crypto.stackexchange.com) – Mike Ounsworth Jun 13 '15 at 15:25

3 Answers3

17

Your quote describes symmetric key strength, but your counter examples (1024, 2048 bits) reference keys used for asymmetric cryptography. The number of bits required for strength is different between the two.

Your quote is from section 7.1 of Applied Cryptography; if you move ahead to section 7.2, for example, you'll see Schneier's predictions on what lengths will be required to have secure asymmetric keys over time:

Applied Cryptography Figure 7.6

Printed in 1994, his predictions turned out reasonably sound except insofar as it is flatter across segments (e.g., individuals don't accept lesser key lengths). (For non-historical purposes, you should look for more up-to-date recommendations, such as NIST as summarized by KeyLength.com)

gowenfawr
  • 72,355
  • 17
  • 162
  • 199
  • 1
    Right, because asymmetric has the factoring vector. Now I feel really stupid :). Thanks! – KnightOfNi Jun 13 '15 at 15:28
  • Note that at the current day and age a script kiddie may have a larger network than major corporations. Better keep to the Lenstra equations or the ECRYPT II / NIST recommendations. I agree that Schneier was reasonably correct, but that's still a pretty old book. – Maarten Bodewes Jun 13 '15 at 16:27
  • 1
    I agree completely, @MaartenBodewes, I only intended to counterpoint OP's source quote against the same source material. I'll edit to clarify. – gowenfawr Jun 13 '15 at 18:08
  • 6
    These lengths aren't recommended for asymmetric crypto in general, but only for RSA and finite field discrete lograrithm based algorithms. ECC needs smaller keys (twice as long as symmetric keys), McEliece needs much larger keys. – CodesInChaos Jun 13 '15 at 19:18
  • Note that those columns don't mean "for use by", but "to be secure agains that type of attacker". Individuals don't want to be secure just against other individuals. – Paŭlo Ebermann Jun 14 '15 at 19:58
7

There are a few reasons to use larger keys.

Your quote only mentions brute-force attacks against symmetric keys. If there is a weakness in the algorithm, then there are faster attacks than brute-force. That is a good reason to design algorithms with some safety margin such that it doesn't get broken as soon as somebody finds a little weakness in the algorithm.

Asymmetrical algorithms necessarily have a lot more structure than symmetrical algorithms. And that additional structure means larger keys to achieve same security level. In some cases that additional key size can be quantified very accurately. For example it is possible to build a signature scheme using a cryptographic hash as the only primitive. The key size needed to match the security of an underlying 256 bit cryptographic hash can be computed very precisely.

In other cases the relation between strength of asymmetrical vs. symmetrical algorithm is based on estimates computed from best known attacks. You can't directly compare the security of a certain key size for RSA to a certain output length of a SHA2 hash. But you can compute how much computing power each would take to break given the most efficient published attacks.

Additionally there is quantum computing to keep in mind. Our current understanding of quantum computing suggests that for symmetric keys you need to double the key size in order for them to remain secure if quantum computing becomes a reality. I do not know whether the 256 bit figure is supposed to be before or after this doubling.

kasperd
  • 5,442
  • 1
  • 19
  • 38
  • +1 for such a detailed and informative answer! Pretty sure it's before accounting for quantum computing. Schneier does mention quantum computers briefly, but only to say it's not terribly likely they'll be a concern in the foreseeable future. Also, I would note that key length probably won't make a difference if the algorithm itself is insecure (although I guess it could). – KnightOfNi Jun 14 '15 at 00:33
  • @KnightOfNi Symmetrical algorithms usually don't have a lot of freedom in choice of key size. So using a larger key for a symmetrical primitive usually means using a different primitive. – kasperd Jun 14 '15 at 07:33
3

Key with a strength of 128 bits or higher are currently considered impossible to break. However, that doesn't necessarily mean that the key itself is 128 bit. The key size is related to key strength, but it doesn't even have to be linear with the key strength. Take for instance RSA; you need a 15K bit key to be near 256 bit security. The best way to see how key size and key strength relates to each other is to take a look at keylength.com (scroll down to the second table).

That's just the key size as related to strength though. If you encode a private RSA key you need at least two times the key size, for modulus and private key (unless you want to generate the entire key pair from scratch again, then you could do with a 128 to 256 bit seed for a random number generator and a lot of CPU time). If you include the CRT parameters, ASN.1 overhead and ASCII armor, the encoding of the key quickly grows. Secret keys are usually encoded as raw bytes though. So an encoded secret key of 128 bit may indeed take just 16 bytes.

Note that unless the key size is clearly insufficient that other attacks may be much more feasible. Think about protocol mistakes, side channel attacks, key generation mistakes - the list goes on. I think about 10% of the questions asked on StackOverflow shows an implementation that could rely on sound cryptographic practices. Choosing the right key size is probably the easiest part of any secure system.

Maarten Bodewes
  • 4,602
  • 15
  • 29
  • Note that a symmetric key strength of 256 bit key strength or higher may be impossible to break with a quantum computer. For asymmetric cryptography you may need to look at different primitives than RSA and ECC though. – Maarten Bodewes Jun 13 '15 at 15:38
  • Thanks for your correction; I tend to use length and strength interchangeably when I clearly shouldn't. – KnightOfNi Jun 13 '15 at 15:47
  • @KnightOfNi Key size is a tricky subject. For instance DH keys have both a `p` and a `q` parameter, both of them may influence key strength (that's the Discrete Logarithm part of the NIST recommendations). Usually we use the size of the prime `p` for indicating the size, but... A key for the SIV algorithm actually consists of two secret keys, but it therefore only has half the key strength. – Maarten Bodewes Jun 13 '15 at 15:54
  • In short, key size is an *abstraction* to make it easier to discuss/understand/communicate key strength during communication. I probably should add something about how cryptanalysis may influence the actual key strength as well. – Maarten Bodewes Jun 13 '15 at 15:57
  • 2
    See my answer to [Can a public key have a different length (encryption) than the private key?](http://stackoverflow.com/a/19345083/445517) for a discussion of what key size means for RSA. – CodesInChaos Jun 13 '15 at 19:21