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 &amp; 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 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."