What is the effect of the different AES key lengths?

Question

How does a changing key length affects the ciphertext, not only in case of AES, but in general? I know that the key spaces become much larger and the number of rounds in case of AES changes, but is security really that much enhanced that if I choose 256 bits as key length it is sort of unbreakable?

Something else what I'm thinking about currently, any idea if it is possible to get any details about key length or algorithm of an observed ciphertext? For example when measuring the entropy (or anything else) is there any difference e.g. between AES and DES?

Answer 1

For symmetric algorithms (like AES or DES or RC4 -- but not for RSA or ECDSA), a key is a sequence of bits, such that any sequence of bits of the same size is a potential key. So longer keys means more possible keys.

Exhaustive search is about trying all possible keys until a match is found. It is an absolute limit to the strength of an algorithm: exhaustive search is always applicable, there is nothing an algorithm can do against it. The only defence against exhaustive search is to expand the space of possible keys, i.e. have longer keys. Fortunately, this is very effective: the largest exhaustive search experiment which was ever reported to have been performed was for a 64-bit key (a search for a 72-bit key is underway, but not completed yet). Traditionally we use "80 bits" as the practical limit, but technology improvement may force us to increase that. Every additional bit doubles the hardness of exhaustive search. See this answer on security.SE for some additional discussion. Bottom line: 128 bits are safe.

It is somewhat delicate to compare strengths of 128-bit and 256-bit keys: while the latter is a much wider key space, the former is already in the "can't break it" zone, and you cannot get better than that, practically speaking. Thus, stating that AES-256 is stronger than AES-128 would be kind of abusive.

There are a few gotchas:

• DES uses 64-bit keys (and 3DES uses 192-bit keys). However, the algorithm specification is such that DES totally ignores 8 of the 64 key bits (24 ignored bits for 3DES). Thus, the key size of DES is often said to be 56 bits (168 bits for 3DES).

• AES morphs with the key size: with a longer key, there are more rounds. This is not about exhaustive key search; this is because a longer key is a promise of "higher academic strength" ("academic" means "we assume that the attacker can perform 300-bit exhaustive searches"). In an academic way, AES needs exhaustive search to be the best attack (i.e. attacks on the algorithm internal structure must be slower). A 256-bit key raises the bar: the non-exhaustive-search attacks must not be more effective than $2^{256}$ work factor. Hence the extra rounds. In practice, the extra rounds do not buy you more security (just like the larger key does not make the algorithm really less breakable than the already unbreakable AES-128); what the extra rounds do is that they make encryption 40% slower.

• When an algorithm morphs with the key size, this is no longer "the same" algorithm, so anything goes. AES-256 could theoretically have weaknesses that AES-128 does not have (there is no guarantee that the extra rounds do not harm security).

• Symmetric key size is very rarely the weak point of a system which uses cryptography. If you use 64-bit keys and that key size is indeed the best attack point, then you can consider yourself extremely lucky: the rest of the system must be inordinately robust.

Answer 2

To answer your first question on key length: DES uses a 56 bit key. A brute-force attack will need a maximum complexity of $2^{56}$ to find the correct key. Now by today's standards this is not much. A complexity of $2^{90}$ or more is considered secure enough. By that standard AES with any key size – 128, 192 or 256 – is strong enough to use. As far as their relative security is concerned, read this post. In this post Bruce Schneier advises to use AES-128 over AES-256.

For your second question: AES, DES or any other good encryption algorithm is basically a PRF (Pseudo Random Function). The property of a good PRF is that one should not be able to distinguish between a PRF and a TRF (Truly Random Function) by just observing their outputs.

So, if one is able to observe the ciphertext and tell whether it came from AES or DES then it completely defeats the purpose. One should not be even able to tell whether the ciphertext was generated from a PRF (like AES) or a TRF, let alone identifying the type of PRF.

Answer 3

A longer key length means a greater search space for someone trying to brute force the key. There are $2^{128}$ times more 256-bit keys than 128-bit keys. So, all other things being equal, a brute force search for a 256-bit key could be impractical by a factor of billions in a case where a brute force search for a 128-bit key might be practical.

However, all other things are rarely equal. And they are unequal for AES. 256-bit AES has key schedule vulnerabilities that 128-bit AES does not have. As a result, many (including myself) believe that there is no reason to think 256-bit AES is any stronger than 128-bit AES.

I should also point out that AES uses the same block size regardless of key length. However, AES uses more rounds with larger keys. 10 for 128-bit keys, 14 for 256-bit keys. Generally, more rounds would be expected to make an algorithm stronger, and this is believed to be the case for AES.

Answer 4

Modern block encryption algorithms are so secure that trying to keep the choice of algorithm secret usually results in more harm than good! An encrypted message is garbage if it cannot be successfully decrypted by the recipient. And if you're going to the trouble of encrypting it, that implies it's a very important message. So it's best to make sure there is enough information in the message so the intended recipient has all the information they need to decrypt it - apart from the secret key, of course.

With modern block encryption algorithms, they are of high enough quality that there aren't known statistical tests to reveal the algorithm used. In the practical sense, however, there is sufficient data to indicate the algorithm used, such as an SSL header, PGP header, an X.509 certificate, etc. If not, there often is something else in the context in which it was found, such as a file named "Secret_Plans.DES", or examining their computer and finding a copy of AES128.EXE.

Classical enciphering algorithms, such as Vigniere, Caesar ciphers, Playfair cribs, etc., will indeed have statistical attributes that can be analyzed, and the algorithm surmised.