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

<ol>
<li><strong>Encryption schemes:</strong> Which can have varying key lengths; and</li>
<li><strong>Block ciphers:</strong> Which have fixed-length black and key lengths.</li>
</ol>

<p>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.</p>

<p>However, chapter 5 mainly discusses block ciphers. These are <strong>practical</strong> constructs based on the <strong>theoretical</strong> 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. </p>

<p>That said, there has been some attempts at defining security notions for concrete security as well. Rogaway, for instance, has written a <a href="http://www.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf" rel="nofollow noreferrer">nice paper</a> on defining security for "ordinary" hash functions (in contrast to "families" of hash functions).</p>

<p>A related question on CSTheory is <a href="https://cstheory.stackexchange.com/q/1206/873">Hardness Guarantees for AES</a>, where the OP asked about provable measures for the AES <strong>block cipher</strong>.</p>

CC BY-SA 2.5
2011-02-23T11:46:38.437Z
OK, I get it now -- thanks a lot for your explanation! (But I  feel like it's pointless to prove asymptotic security of encryption schemes if the security parameter will usually be small in practice)
josh
CC BY-SA 2.5
2011-02-23T12:45:22.127Z
@josh: Yeah, all researchers had felt that it was pointless, until Rogaway found a workaround, termed "constructive" security. Though that's a story for another day :)
Sadeq Dousti
CC BY-SA 2.5
2011-02-23T11:17:20.773Z
2011-02-23T11:17:20.773Z
2017-04-13T12:32:28.053Z
Sadeq Dousti
<p>Reading <a href="http://www.cs.umd.edu/~jkatz/imc.html" rel="nofollow">Introduction to Modern Cryptography</a> 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)$".</p>

<p>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).</p>

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

<p>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?</p>

<cr.crypto-security>
CPA security for block ciphers?
josh
# CPA security for block ciphers?

(Asked by: username_0 on 2011-02-23)

Reading [Introduction to Modern Cryptography](http://www.cs.umd.edu/~jkatz/imc.html) 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?

**Tags:** cr.crypto-security

---

## 1 answers

### Answer by username_1 on 2011-02-23. Score: 4 | Accepted answer

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](http://www.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf) on defining security for "ordinary" hash functions (in contrast to "families" of hash functions).

A related question on CSTheory is [Hardness Guarantees for AES](https://cstheory.stackexchange.com/q/1206/873), where the OP asked about provable measures for the AES **block cipher**.

> **Comments:**
> **username_0**: OK, I get it now -- thanks a lot for your explanation! (But I  feel like it's pointless to prove asymptotic security of encryption schemes if the security parameter will usually be small in practice)  
> **username_1**: @josh: Yeah, all researchers had felt that it was pointless, until Rogaway found a workaround, termed "constructive" security. Though that's a story for another day :)  

---

