Isn't 128 bit security enough for most practical applications?
7 Answers
Why do people buy red sport cars ? They do not go faster than sport cars of any other colour...
AES comes with three standard key sizes (128, 192 and 256 bits). Many people see this and think that if there are three distinct sizes instead of just one, then there must be some difference, and since the 256-bit version is a bit slower than the 128-bit version (by about 40%), it must be "more secure". So they go for "the most secure" and choose 256-bit keys.
In reality, the AES has three distinct key sizes because it has been chosen as a US federal algorithm apt at being used in various areas under the control of the US federal government, and that includes US Army. US Army has a long-standing Tradition of using cryptography, and that Tradition crystallized into internal regulation with all the flexibility and subtlety that armies around the world constantly demonstrate (just listen to some "military music" and you'll understand what I mean). Unfortunately, this happend quite some time ago, before the invention of the computer, and at that time most encryption systems could be broken, and the more robust were also very hard and slow to use. So the fine military brains came up with the idea that there should be three "security levels", so that the most important secrets were encrypted with the heavy methods that they deserved, but the data of lower tactical value could be encrypted with more practical, if weaker, algorithms.
These regulations thus called for three distinct levels. Their designers just assumed that the lower level were necessarily weak in some way, but weakness was not mandatory. So the NIST decided to formally follow the regulations (ask for three key sizes) but to also do the smart thing (the lowest level had to be unbreakable with foreseeable technology). 128 bits are quite sufficient for security (see this answer for details). Therefore AES accepts 256-bit keys because of bureaucratic lassitude: it was easier to demand something slightly nonsensical (a key size overkill) than to amend military regulations.
Most people don't know or don't care about History, and they just go for big because they feel they deserve it.
answered Sep 4, 2012 at 22:20
-
13Can you provide sources that the three levels are really only to satisfy (old) military regulations? It doesn't make a lot of sense to me, if 128 bits was secure enough they might as well have used 128, 136 and 156 for that matter. The en/decryption time would have been shorter yet still secure according to you.– LucSep 6, 2012 at 16:05
-
6@Luc: the 128/192/256 bits are for aesthetics: powers of 2 are always better (and 3DES was already using, formally, a 192-bit key -- out of which 24 are ignored, but that's another story). For the source, it was what someone told me directly at that time (I think it was Schneier) so I do not have a written source. As for the decryption time, it is Rijndael-specific; some other candidates offered the same performance for all key lengths. Sep 6, 2012 at 18:15
-
33256 bit keys aren't completely useless. They do provide a defense against the possibility of Quantum Computers, specifically Grovers Algorithm which can reduce the search space by effectively half. We're still don't have real quantum computers yet, and nobody knows when we will. The point being though that if you wanted to protect your secrets for 50+ years, you might pick double the currently accepted key size. en.wikipedia.org/wiki/Post-quantum_cryptography Oct 1, 2015 at 17:10
-
11@SteveSether: this is the occasion to point out that the "128-bit" limit is in no way universal; we use 128-bit keys because this is substantially beyond what can be cracked with classical computing. Grover's algorithm theoretically turns the search in a 2^64 effort, but these are 2^64 quantum operations. Whether individual QC operations are similar in cost to individual classical operations remains to be seen. Right now, 2^64 QC operations is way harder than 2^64 classical operations, notably because QC computers do not exist yet. Oct 1, 2015 at 17:29
-
6@ThomasPornin I think the point is that 256 bits provides SOME additional level of security, however marginal. Much remains to be seen. For some people even the theoretical possibility of the message being cracked is enough to invoke the 40% cost of additional CPU cycles. The is largely relegated to the NSA, or CIA, etc. I'd make the same recommendations to anyone that claims to need to protect a secret for 50+ years. CPU is cheap. Oct 1, 2015 at 17:38
When you are building a security system you need to plan on failure. This is the idea behind a defense in depth strategy.
Cryptographic primitives become weaker over time. Although a 128 bit primitive is plenty, a flaw could be uncovered in the cipher which reduces this level of security. So you need to add a security margin when the underlining primitive fails.
For example md5 produces a 128 bit hash, however using a chosen-prefix attack an attacker can produce a collision with a complexity only 2^39.
-
14Essentially it's about security margin. The longer the key, the higher the effective security. If there is ever a break in AES that reduces the effective number of operations required to crack it, a bigger key gives you a better chance of staying secure. Besides, with commodity hardware available today, the performance difference between 256-bit AES and 128-bit AES is fairly small. That and, as CodeInChaos mentioned, bigger numbers sound better and more secure. Apr 23, 2012 at 9:49
-
Ok not a bad logic. but can anyone tell exactly how strong a 128 bit cipher is at the current time, assuming no considerable breach is found in it and large quantum computers aren't realized?– H MApr 23, 2012 at 10:24
-
1
-
regarding md5 story, i have heard that cryptographic hash algorithms are generally considered less reliable than cipher algorithms, because they have not as strong a security proof as cipher algorithms have. i don't know the details, and sorry for no reference, but i have read such words several times in several places, and so think a difference really exists between hash algorithms and cipher algorithms in this regard. also afaik no practically dangerous breach in modern and standard cipher algorithms like AES is discovered for years up now.– H MApr 23, 2012 at 11:59
-
2The comparison with MD5 is a bit misleading. The collision resistance of MD5 has never been better than 2^64 due to the birthday paradox.– PerseidsApr 25, 2014 at 11:05
I didn't see this mentioned in the answers or comments so I thought to add this as an answer. Key size does not always correlate directly to complexity of an algorithm. A common fallacy is to assume that a message encrypted using AES256 is more difficult to crack (an adversary getting any sort of meaning information given only the ciphertext) than the same information protected using AES128. It makes logical sense that a larger key size provide introduces greater complexity but as with any systems, implementations are subject to weaknesses.
Assuming you're talking about AES 128 versus AES 256, there is a known weakness in the key expansion function that affects AES256. Fundamentally, the weakness reduces the complexity of AES256 to that lower than AES128. There's a similar attack for AES192 as well, though in this case, the complexity of AES192 remains greater than AES128.
Moral of the story, people don't understand crypto... j/k (I'm not a mathematician). Reality is that people assume "big" with "secure." A big gun is better than having a small gun. Larger key sizes are more secure than smaller key sizes.
In reality, the implementation of crypto is more important than key size alone.
-
16If I remember correctly, that weakness is only relevant when using AES is quite unusual modes, and not any typical encryption mode where random keys are used. I'm pretty sure that AES-256 is stronger for normal use (CBC, CTR,...) May 3, 2012 at 9:14
-
3
A big gun is better than having a small gunAnd detonating the Tsar Bomba in someone's face is more lethal than detonating the Little Boy in their face, but they're dead either way.– forestMar 7, 2018 at 10:16 -
@CodesInChaos Also, don't larger keys require more rounds to achieve complete diffusion (if I recall, the number of extra rounds given to AES256 was based on a hunch, not any empirical testing or proofs)? Or is that only an issue if the key itself is not uniform?– forestApr 24, 2018 at 7:20
-
@forest I expect that to only matter if you either want to achieve the higher security level expected of a 256-bit key or if the key is badly non uniform (e.g. second half is constant). There is also the question of what you mean by diffusion, the number of rounds it takes a small change in the input to diffuse or the number of rounds it takes a small change in the key to diffuse. Apr 24, 2018 at 16:30
-
2It's confusing that the conclusion of the sources do not support the recommendation against AES256: "While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems", from eprint.iacr.org/2009/374– xperetaJan 21, 2020 at 13:43
FWIW, NIST draft on post quantum crypto is recommending 256.
http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf
-
2Though they say it might be "overly conservative" and does not account for "the possibility of more sophisticated quantum attacks", they do indeed say "For symmetric key systems, one simple heuristic is to double the key lengths to compensate for the quadratic speedup achieved by Grover’s algorithm." This seems a reasonable approach to take right now, knowing that a lot of advances have been made in quantum computers, and interest in the technology is growing. Messages sent today might be decrypted in a few years, if they use cryptography techniques that are not "quantum-safe".– youenApr 22, 2018 at 15:06
-
2
the possibility of more sophisticated quantum attacksIsn't there a proof that grover's algorithm is the most efficient possible way to traverse a finite keyspace? I.e. the equivalent keyspace can never possibly be reduced to less than 2^(n / 2) / √k where n is the bit length and k is the number of parallel instances of grover's algorithm. I might be misremembering though.– forestApr 24, 2018 at 7:15
Your premise seems wrong to me. I am not aware of any evidence that "most people use 256 bit encryption instead of 128 bit". Indeed, if I had to guess, I suspect the reverse is the case.
-
1I think you are right in that most SSL setups are, by default, set to prefer 128-bit. However, I think the point of the question is "why use a longer key if 128-bit is secure anyway?". Apr 23, 2012 at 9:51
-
13For example both Firefox and Opera prefer AES-256 cipher suites. They even prefer non (EC)DHE suites with AES-256 over (EC)DHE suites with AES-128, which IMO is insane. Apr 24, 2012 at 17:56
Eventually you run into a problem similar to compression software, too much compression can lead to data loss. While there is no finite number to the strength of encryption "theoretically" that doesn't mean you need to encrypt your data more than 256bit. You might technically be able to do it, but at the risk of what a machine that takes a month or years to boot up and load your os?
I'm assuming you are talking about symmetric cryptography. The answer is that it is never secure enough (even though I suspect that using 256 bit vs 128 bit keys is a marketing strategy to make the client feel more secure).
And don't forget the rise of quantum computing, which significantly lowers the amount of time needed for a brute-force attack.
answered Apr 23, 2012 at 5:56
-
2yes it's symmetric. about quantum computers wikipedia says: "Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case. Thus in the presence of large quantum computers an n-bit key can provide at least n/2 bits of security. Quantum brute force is easily defeated by doubling the key length."– H MApr 23, 2012 at 10:34
-
But seems to me that for such attacks becoming practical, very large fully fledged quantum computers are needed that i don't think this can be realized very soon. anyway it seems a good idea to use 256 bit if relatively long term protection is needed (and changing the keys/key length at need is not practical), although 256 bit will become 128 bit in the quantum computers era, so why not use 512 bit? but i personally don't remember any 512 bit supporting cipher!!– H MApr 23, 2012 at 10:34
-
@HM "Quantum brute force is easily defeated by doubling the key length". I don't know about this so I won't go into much detail, but it this is true, there you understand why you use 256 bits instead of 128 :) in any case, as you say, longer keys give you long term protection, which is probably important enough to justify their use. Apr 23, 2012 at 10:50
-
It would be easier to just run Schors algorithm on the public cryptography of the key exchange in a lot of cases anyway.– ewanm89Apr 23, 2012 at 11:12
-
3It can easily be secure enough. 2^128 is darn hard but somewhat theoretically plausible, and 2^256 is well out of the range of what we have any idea whatsoever to build a machine for. With a "perfectly efficient" computer (which I'm pretty sure that insofar as we know cannot exist) though, these limits become effectively meaningless. This really comes down to: theoretically hard, or merely hard given what we have any idea how to do? I suspect most people are more concerned with the latter.– userJan 19, 2017 at 22:35
2^(128/2) = 2^64 =conceivably brute-forceable on a quantum computer.2^(256/2) = 2^128 =still secure.