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

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?

-
I don't have the book, but might Viega and Messier have actually said "the effective strength ... is actually half the block size"; which might be one way of expressing that if you have a block cipher with a block size of $n$ bits, you generally don't want to use it for more than $2^{n/2}$ blocks ??? –  poncho Jul 12 at 18:37
I'm way out of my depth here, but perhaps what they mean is that if the key is 128 bits, then on average after trying half the possible values (2**127), you'll have guessed the key... again, ON AVERAGE. So it's important to understand also that this means 127 bits, not 64 bits! –  Dan Jul 12 at 18:51

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."

-

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.

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.

-

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.

-