# How much added security do I really get with a longer key size?

Imagine I have a cipher which supports keys of 128, 192 or 256 bits. Suppose that there are no vulnerabilities in the cipher regardless of key length. I'm going to use it to encrypt something, and I'll use a password or passphrase.

If I use the same password, does it really matter what the key size is? Since it seems like bruteforcing all 2128 possible keys is not feasible in the foreseeable future, am I correct to assume the strength of the encryption is based almost solely on the password?

Assuming the key derivation function takes the same amount of time to generate a key of any size, doesn't this mean an attack on the password will take the same amount of time regardless of key size? Thus, isn't the strength of the encryption much more a function of the strength of the password than the key size?

If that holds up, what do I gain with a 256-bit or 192-bit key instead of a 128-bit key?

-

Once you've reached the "cannot break it" zone, increasing the key size does not change security: you cannot be more secure than that. A 128-bit key is already far into the "cannot break it" zone. Larger keys are for marketing people who need to impress gullible buyers, and for military people who must, by statute, make extensive displays of their collective manhood.

(The best marketing managers try to rationalize larger key sizes by talking about quantum computers.)

If you derive a key from a password, and extending the key from 128 to 256 bits changes anything to your security, then you are doing it very wrong.

-
Do you feel this also applies to keys not derived from passwords? – Stephen Touset Oct 19 '12 at 21:05
I like the other answers and upvoted them, but this is the most helpful one. – quantumSoup Oct 22 '12 at 23:36

Supposing there are no vulnerabilities in the cipher for different key lengths, and that the key derivation function generates output indistinguishable from random, with no collisions, then:

Mathematically speaking 2^256 = 2^128 * 2^128. The `2^X` algebra in this case refers to the total number of unique keys, called the key space. Since each bit can be either zero or one, there are two possibilities. Two bits gives you 2x2, three 2x2x2 and so on.

Anyway, as I say, 2^256 = 2^128 * 2^128 since 2^128 * 2^128 = 2^(128 + 128). By doubling the address space, you haven't doubled the number of possible keys - you've made it 340282366920938463463374607431768211456 extra possible keys. If 2^128 is outside the reach of humanity, then 2^256 is out of reach of Skynet.

If I use the same password, does it really matter what the key size is?

That depends on the KDF - PBKDF2, for example, generates blocks of the keyed hash function supplied as the input - and then feeds this into the next iteration as the salt. As such, the first 160-bits of the key generated for a 128-bit key are the same as the first 160 bits of the key generated for a 256-bit key.

The question is, then, does this compromise the key? Well, you've actually no stored value to work with, for starters, but let's assume you did somehow have a 128-bit key. You'd need to reliably be able to generate the other 128-bits to generate the 256-bit key - which you can't do from the output unless you have the input. So you'd need to find the preimage - the password. That might be considered easy, except that you'd have to break however many iterations of the HMAC function that were used.

Another question would be is this reusable? Proper PBKDF2 implementation uses a salt - so you would have the same problem as attacking any salted hash function.

isn't the strength of the encryption much more a function of the strength of the password than the key size?

Not really. However, the problem is that poor key generation technique might lead you to inadvertently reduce your key space size, making it easier to brute force your password. For example:

``````char encryption_key[16] = {0};
strncpy(encryption_key, 16, source);

aes_with_some_mode(encryption_key, plaintext, &ciphertext);
``````

is bad, since even if you ensure the password is 16 bytes long, you've restricted each byte to one of a number of possible ASCII characters and symbols. So assuming just uppercase characters, you've reduced the key space to only 26^16. You've just shot yourself in the foot by a factor of about 8 x 10^15.

KDFs are designed to avoid this situation (although a truly random source is more ideal) by mapping the password to the key space. The problem of finding a matching key becomes as hard as finding a preimage to a hash algorithm under the conditions it is used in the KDF.

Certainly, with PBKDF2 it would not be true that the KDF would take equal time for a 128 and 256 bit key.

-
I think you've missed the point of my question. I've edited it and added some emphasis on its key points. – quantumSoup Oct 19 '12 at 20:34
Could you explain your last sentence? – quantumSoup Oct 19 '12 at 21:06
Certainly - assume you have PBKDF2 using HMAC-SHA1 - then to generate the first 160 bits you do X iterations (a user-defined quantity, but let's say 1024, for example). To get 320 bits, you first need to generate block number 1 (160 bits), then block number 2. To get keys of different sizes to this, you just truncate, so you'd only need one block for 128-bits, but two for 256 bits. Hence, it'd be doing 2X HMAC-SHA1 computations, as opposed to X of them, for a 256-bit key. – user2213 Oct 19 '12 at 21:09
Of course, if you used something else, such as HMAC-SHA256, you would only need one set of iterations for both key sizes. It really depends on the KDF and the underlying constructs, if any. – user2213 Oct 19 '12 at 21:13
I see. When I asked the question, I had in mind that the KDF could generate 256-bit keys and truncate it to size. – quantumSoup Oct 19 '12 at 22:06

Simply put, the problem is with the assumption you've stated.

Suppose that there are no vulnerabilities in the cipher regardless of key length.

Security is about defense in depth. Just as a safecracker isn't going to bang at a safe with a hammer for days on end, attackers aren't generally sitting around brute forcing encryption keys.

It's probably inevitable that one day a security researcher will discover weaknesses in AES (or any other current symmetric encryption standard). The likely trajectory is that the weaknesses will become practically exploitable against ciphertexts with shorter key lengths first, and later be extended (through research, specialized hardware, or simply Moore's law) to ciphertexts using longer keys.

-
How inevitable? DES is older than me and as far as I know there are no viable attacks on it. – quantumSoup Oct 19 '12 at 21:10
There are three theoretical attacks, but attention on breaking DES may be diminished simply due to the fact that 56-bit keys are considered well within the realm of brute-forcing. Keep in mind also that just because no practical attacks are widely known doesn't necessarily mean that, 1) practical attacks aren't known by anyone, 2) practical attacks won't be discovered in the near future, or 3) that DES's resistance to attacks is in indicative of the resistance of any other cipher. – Stephen Touset Oct 19 '12 at 21:20
It looks like sometimes the longer key lengths could fall first: schneier.com/blog/archives/2009/07/another_new_aes.html – quantumSoup Oct 19 '12 at 22:04
They can. That attack takes advantage of particularly-bad key scheduling in the 256-bit variant, which didn't necessarily have to be the case. Most attacks, however, are more likely to bring ciphers with shorter key lengths within reach of attackers. Were a similar attack to have been feasible against AES-128, it may well have been considered to be broken entirely. – Stephen Touset Oct 19 '12 at 22:47