Effective security of block cipher – equal the key size, or half the key size?

Question

The Wikipedia “Key Size” article states:

The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. … … … Most symmetric-key algorithms in common use are designed to have security equal to their key length.

^{(emphasis mine)}

The book “Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More” by John Viega and Matt Messier states (on page 161, 2nd half of 4th §):

The general rule of thumb is that the effective strength of a block cipher is actually half the key size, assuming the cipher has no known attacks that are better than brute force.

^{(emphasis mine)}

Now…

To avoid nit-picking, let’s keep it simple and assume that an individual block cipher does not use an algorithm that loses some of the effective security a key provides. Also, let’s assume that no known attacks exist.

Would it be more correct to claim that the effective security of that cipher is equal the key size, or is it half the key size? Simpler asked: which of the two quoted statements is correct, and why?

Answer 1

I just read that chapter of the book, and the authors don't really justify their claim.

They also talk about "using random data to prevent collision and precomputation attacks" (which would then give you back the full key-size crypto strength) – this is about using random initialization vectors and such.

But if you are using an insecure mode of operation, or a non-random IV where a random one is required, using a bigger key-size doesn't really help, as the attacks possible here are not really key-recovery attacks.

Where such stuff could work would be for hash functions (which have at most $2^{n/2}$ tries collision resistance, assuming $n$-bit output), and a secret key included in the hash makes the brute-forcing impossible. But this certainly is not "symmetric encryption".

Another possibility which would reduce complexity to half the key-size would be assuming a (large enough) quantum computer – that could do a brute-force key search in $2^{n/2}$ steps instead of $2^{n}$ steps. But the text in the chapter doesn't really look like they are referring to this.

The crypto strength of an ideal symmetric cipher in absence of new generic attacks is equal to its key size (i.e. you need in average $2^n/2$ tries for a brute force key search attack).

Generally this is valid for all non-broken encryption algorithms, too (just by definition of "non-broken"): A symmetric cipher with key-size $n$ bit should offer $n$ bit crypto strength.

So my say would be: "Use a bigger key-size if you are concerned about future quantum computer attacks (or generally attacks on the algorithm which shave off some of the security, but not all of it), otherwise stay at 128 bit."

Answer 2

It is certainly possible to conceive protocols, for which a 128 bit key might cause collisions that might be avoided by using a 256 bit key.

For instance, suppose you have a protocol that uses AES-CCM with a 56 bit nonce for bulk encryption. If the nonce is generated randomly, there is at least a $2^{-28}$ collision rate. It is essential that you ensure such collisions do not happen.

Now, if you wish to reduce that risk of collisions by renegotiating the bulk encryption key more often, it does matter if you are using AES-CCM-128 or AES-CCM-256. In the former case, the risk you will get a collision in both the nonce and the bulk encryption key at the same time, is $2^{-28}2^{-64} = 2^{-92}$, which clearly is greater than the corresponding collision rate $2^{-28}2^{-128} = 2^{-156}$ if AES-CCM-256 is used.

So, to answer the question:

The general rule of thumb is that the effective strength of a block cipher is actually half the key size, assuming the cipher has no known attacks that are better than brute force.

No, I don't think this is entirely correct. However, the security strength of a protocol does not necessarily equal the effective strength of the least secure constituent primitive. There might be cases (as above) when you actually have to use AES-192 or AES-256 to get 128 bit security from the overall protocol.

Answer 3

When talking about effective security level, one first have to say what type of attack is considered. There are two main attack types on a blockcipher with block size $n$ in the mode of operation $\Pi$:

1. Key-recovery attack: an attacker finds the secret key of length $k$.
2. Distinguishing attack: an attacker distinguishes the ciphertexts, produced by $\Pi$, from random strings.

For the first attack the block size does not matter. The number of operations needed to find the key (assuming no weaknesses) is $2^{k-1}$ block encryptions on average.

For the second attack the key size does not matter unless it is smaller than $n/2$ (for all major modes of operation). The number of trial encryptions needed to distinguish $\Pi$ from a random function is $$ \min(2^k, 2^{n/2}). $$

As you may see, half of the key size does not appear anywhere, so this value does not define the effective security in any case.

Answer 4

If the attacker can make related-key chosen-plaintext queries, then there is a generic attack that can break any block cipher with $n$-bit keys in $2^{n/2}$ time, using $2^{n/2}$ related-key queries and $2^{n/2}$ memory. So against a related-key attacker, the effective strength of a block cipher can be no more than half the key length.

However, the related-key model is controversial. Putting aside the plausibility of such an attack model, related-key attackers can sometimes be "too powerful". For example, if you permit a related-key attacker to transpose individual bits of the key (i.e. request the encryption of a message under both $K_1$ and $K_2$, where $K_2$ equals $K_1$ with bits $b_x$ and $b_y$ swapped), then the attacker can easily recover the $n$-bit key with just $n-1$ requests, using the following attack: swap bits $b_0$ and $b_1$ and see if that makes a difference in the output ciphertext (if it does, then $b_0 \neq b_1$, and $b_0 = b_1$ if it doesn't); repeat with bits $b_1$ and $b_2$, and so on for each of the $n-1$ adjacent pairs of bits; then at the end you only have to guess the value of a single bit (e.g. $b_0$) and you have the entire key. A similar devastatingly fast attack exists for a related-key attacker who is permitted to make requests using both 'xor' differences (i.e. $K_2 = K_1 \oplus \Delta$) and 'additive' differences (i.e. $K_2 = K_1 + \Delta \mod 2^w$, for some word length $w >1$).

So you have to be careful about what kind of relations you permit the related-key attacker to request. The attack I mentioned in the first paragraph exists in what is perhaps the least controversial model - where the attacker can use 'xor' differences only. The attack is as follows:

Versus a block cipher with an $n$-bit key, initialize a $n/2$ bit counter $X$ at zero, choose some particular fixed plaintext P, and do this loop:

while $X < 2^{n/2}$:

1. Request $E(P,K \oplus X||0^{n/2})$ from the Challenger/Oracle, where $E(x,y)$ is the encryption of $x$ under the key $y$, $||$ denotes concatenation, and $0^{n/2}$ is a string of zeros of length $n/2$.
2. Store resulting ciphertext in an array of size $2^{n/2}$ at index $X$.
3. Let $X = X + 1$.

Once the loop is done, then initialize another counter $Y$ at zero and do this loop:

while $Y < 2^{n/2}$:

1. Compute $E(P, 0^{n/2}||Y)$.
2. Check the resulting ciphertext against the array (using e.g. hash table collision-checking), to see if there is a collision with any of the stored ciphertexts. If there is a collision with an element of the array at index $X$, then with overwhelming probability the secret key is $X||Y$.
3. Let $Y = Y + 1$.

This will find the key with probability 1. You can also invert the two loops, i.e. pre-compute $E(P, 0^{n/2}||Y)$ and store the results in an array before the online attack, and check the 'requested' outputs against that array.

Answer 5

Your question here has two answers, depending on what you mean.

The first is the distinction between birthday attacks and exhaustion attacks. In a birthday attack, the attacker wins if he gets two messages that have the same key. And in that case the security is proportional to half the key length. In an exhaustion attack, the attacker has a specific message or messages all with the same key and needs to find the key. In that case the key's security is proportional to the key length.

The second is the distinction between "noise" keys and "passwords." Passwords chosen from any natural language's vocabulary, or minor variations on its spelling, have far less value (maybe 1/3 the value if compression utilities are a good guide) as keys than properly random sequences of bits the same length, because there is far less information in them.

So if I want to make an attacker do work proportional to 2^128 operations, I would use:

A 128-bit random key to protect against an exhaustion attack.

A 256-bit random key to protect against a birthday attack.

and (assuming passwords have 1/4 the value of noise keys),

A 512-bit passphrase to protect against an exhaustion attack

A 1024-bit passphrase to protect against a birthday attack.

Hope that helps...