CPA security for block ciphers?

Question

Reading Introduction to Modern Cryptography by Katz and Lindell, I noticed that they talk about CPA security for block ciphers (in Section 3.6.4 where they explain mods of operation) -- and mention that most modes of operation described there are CPA-secure. Then they prove that CTR mode is CPA-secure using the key length as security parameter: "${\tt Gen}(1^n)$ chooses a random function ..." and later, in the displayed equation, $\left[ {\tt PrivK}^{cpa}_{{\cal A},\tilde\Pi}(n)=1 \right]\leq \frac{1}{2} + {\tt negl}(n)$".

However, in Chapter 5 (paragraph about "Attacks on block ciphers") they also mention that any pseudorandom permutation is secure againse CPA attacks, and that it makes no sense to use asymptotic notions of security for block ciphers, since their block and key length are fixed (and that makes perfect sense to me).

So I am confused now -- what is the point of the previous demonstrarion, on Chapter 3, that CTR mode is CPA-secure?

Or, making this question not specific to this book in particular: how do people define security against CPA (and known-plaintext, CCA etc) for block ciphers?

Answer 1

The book introduces two concepts, and warns not to confuse them with each other:

1. Encryption schemes: Which can have varying key lengths; and
2. Block ciphers: Which have fixed-length black and key lengths.

Chapter 3 of the book mainly speaks about encryption schemes. For instance, take a look at the proof of CPA-security of the CTR mode (Theorem 3.29, and Figure 3.8): The permutation $F_k$ used at the heart of the CTR construct can have varying key lengths.

However, chapter 5 mainly discusses block ciphers. These are practical constructs based on the theoretical ideas of encryption schemes (as the chapter title implies). The security of block ciphers (DES, AES, etc.) cannot be formally proved (at least at the present), since there exists no notion of concrete security, in contrast to asymptotic security.

That said, there has been some attempts at defining security notions for concrete security as well. Rogaway, for instance, has written a nice paper on defining security for "ordinary" hash functions (in contrast to "families" of hash functions).

A related question on CSTheory is Hardness Guarantees for AES, where the OP asked about provable measures for the AES block cipher.