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

Question

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 2¹²⁸ 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?

Answer 1

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.

Answer 2

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.

Answer 3

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.