CS276 Lecture 5: Encryption Using Pseudorandom Functions

Posted on February 13, 2009 by luca

Scribed by Manohar Jonnalagedda

Summary

Having introduced the notion of CPA security in the past lecture, we shall now see constructions that achieve it. Such constructions shall require either pseudorandom functions or pseudorandom permutations. We shall see later how to construct such objects.

1. Pseudorandom Functions

To understand the definition of a pseudorandom function, it’s good to think of it as a pseudorandom generator whose output is exponentially long, and such that each bit of the output is efficiently computable given the seed. The security is against efficient adversaries that are allowed to look at at any subset of the exponentially many output bits.

Definition 1 (Pseudorandom Function) A function ${F: \{ 0,1 \}^k \times \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ is a ${(t,\epsilon)}$ -secure pseudorandom function if for every oracle algorithm ${T}$ that has complexity at most ${t}$ we have

$\displaystyle | \mathop{\mathbb P}_{K \in \{ 0,1 \}^k} [ T^{F_K} () =1 ] - \mathop{\mathbb P}_{R: \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m} [T^{R} () = 1] | \leq \epsilon$

Intuitively, this means that an adversary wouldn’t be able to distinguish outputs from a purely random function and a pseudorandom function (upto a certain ${\epsilon}$ additive error). Typical parameters are ${k=m=128}$ , in which case security as high as ${(2^{60},2^{-40})}$ is conjectured to be possible.

As usual, it is possible to give an asymptotic definition, in which ${\epsilon(k)}$ is required to be negligible, ${t(k)}$ is allowed to be any polynomial, and ${F}$ is required to be computable in polynomial time.

2. Encryption Using Pseudorandom Functions

Suppose ${F: \{ 0,1 \}^k \times \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ is a pseudorandom function. We define the following encryption scheme.

${Enc(K,M)}$ : pick a random ${r\in \{ 0,1 \}^m}$ , output ${(r,F_K(r) \oplus M)}$
${Dec(K,(C_0,C_1)):= F_K(C_0) \oplus C_1}$

This construction achieves CPA security.

Theorem 2 Suppose ${F}$ is a ${(t,\epsilon)}$ secure pseudorandom function. Then the above scheme is ${(\frac{t}{O(m)}, 2\epsilon + t\cdot 2^{-m})}$ -secure against CPA.

The proof of Theorem 2 will introduce another key idea that will often reappear in this course: to first pretend that our pseudorandom object is truly random, and perform our analysis accordingly. Then extend the analysis from the pseudorandom case to the truly random case.

Let us therefore consider a modified scheme ${(\overline{Enc}, \overline{Dec})}$ , where instead of performing ${F_K(r) \oplus M}$ , we do ${R(r) \oplus M}$ , where ${ R : \{0,1\}^m \rightarrow \{0,1\}^m }$ is a truly random function. We need to look at how secure this scheme is. In fact, we will actually prove that

Lemma 3 ${(\overline{Enc}, \overline{Dec})}$ is ${(t, \frac{t}{2^m}) -}$ CPA secure.

Proof:

In the computation ${T^{\overline{Enc}}(\overline{Enc}(r,C))}$ of algorithm ${T}$ given oracle ${\overline{Enc}}$ and input the ciphertext ${(r,C)}$ , let us define REP to be the event where ${T}$ gets the messages ${(r_1,C_1),\ldots,(r_t,C_t)}$ from the oracle, such that ${r}$ equals one of the ${r_i}$ .

Then we have

$\displaystyle \mathop{\mathbb P} [ T^{\overline{Enc}} (\overline{Enc}(M)) = 1]$

$\displaystyle = \mathop{\mathbb P}[T^{\overline{Enc}} (\overline{Enc}(M)) = 1 \wedge REP]$

$\displaystyle + \mathop{\mathbb P} [T^{\overline{Enc}} (\overline{Enc}(M)) = 1 \wedge \neg REP]$

similarly,

$\displaystyle \mathop{\mathbb P} [ T^{\overline{Enc}} (\overline{Enc}(M')) = 1]$

$\displaystyle = \mathop{\mathbb P} [T^{\overline{Enc}} (\overline{Enc}(K,M')) = 1 \wedge REP]$

$\displaystyle + \mathop{\mathbb P} [T^{\overline{Enc}} (\overline{Enc}(M')) = 1 \wedge \neg REP]$

$\displaystyle \left| \mathop{\mathbb P} [ T^{\overline{Enc}} (\overline{Enc}(K,M)) = 1] - \mathop{\mathbb P} [ T^{\overline{Enc}} (\overline{Enc}(K,M')) = 1] \right|$

$\displaystyle \leq \left| \mathop{\mathbb P} [T^{\overline{Enc}} (\overline{Enc}(M)) = 1 \wedge REP] - \mathop{\mathbb P} [T^{\overline{Enc}} (\overline{Enc}(M')) = 1 \wedge REP] \right|$

$\displaystyle + \left | \mathop{\mathbb P}[T^{\overline{Enc}} (\overline{Enc}(M)) = 1 \wedge \neg REP] - \mathop{\mathbb P} [T^{\overline{Enc}} (\overline{Enc}(M')) = 1 \wedge \neg REP] \right|$

Now the first difference is the difference between two numbers which are both between ${0}$ and ${\mathop{\mathbb P}[REP]}$ , so it is at most ${\mathop{\mathbb P}[REP]}$ , which is at most ${\frac{t}{2^m}}$ .

The second difference is zero, because with a purely random function there is a 1-1 mapping between every random choice (of ${R,r,r_1,\ldots,r_t}$ ) which makes the first event happen and every random choice that makes the second event happen. ◻

We have shown that with a purely random function, the above encryption scheme is CPA-secure. We can now turn our eyes to the pseudorandom scheme ${(Enc,Dec)}$ , and prove Theorem 2.

Proof: Consider the following four probabilities, for messages ${M}$ , ${M'}$ , and algorithm ${T}$ :

(a) ${\mathop{\mathbb P}_{K} [ T^{Enc(K, \cdot)} (Enc(K,M)) = 1 ]}$
(b) ${\mathop{\mathbb P}_{K} [ T^{Enc(K, \cdot)} (Enc(K,M')) = 1 ]}$
(c) ${\mathop{\mathbb P}_{R} [T^{\overline{Enc}(\cdot)} (\overline{Enc}(M)) = 1]}$
(d) ${\mathop{\mathbb P}_{R} [T^{\overline{Enc}(\cdot)} (\overline{Enc}(M')) = 1]}$

From the previous proof, we have ${|(c) - (d)| \leq \frac{t}{2^m}}$ . If we are able to show that ${|(a)-(c)| \leq \epsilon}$ , ${|(b)-(d)| \leq \epsilon}$ , then we have ${|(a)-(b)| \leq 2\epsilon + \frac{t}{2^m}}$ .

So, it remains to show that

$\displaystyle |\mathop{\mathbb P}_{K} [ T^{Enc(K, \cdot)} (Enc(K,M)) = 1 ] - \mathop{\mathbb P}_{R} [T^{\overline{Enc}(\cdot)} (\overline{Enc}(M)) = 1]| \leq \epsilon \ \ \ \ \ (1)$

Suppose, by contradiction, this is not the case. We will show that such a contradiction implies that ${F}$ is not secure, by constructing an oracle algorithm ${T'}$ that distinguishes ${F}$ from a truly random function.

For an oracle ${G}$ , we define ${T'^{G}}$ to be the following algorithm:

pick a random ${r\in \{ 0,1 \}^m}$ and compute ${C:= (r,G(r) \oplus M)}$
simulate ${T (C)}$ ; every time ${C}$ makes an oracle query ${M_i}$ , pick a random ${r_i}$ and respond to the query with ${(r_i,G(r_i) \oplus M)}$

Note that if ${T'}$ is given the oracle ${F_K}$ , then the computation ${T'^{F_K}}$ is exactly the same as the computation ${T^{Enc}(Enc(M))}$ , and if ${T'}$ is given the oracle ${R}$ , where ${R}$ is a random function, then the computation ${T^{\overline{Enc}}(\overline{Enc}(M))}$ .

Thus, we have

$\displaystyle \mathop{\mathbb P}_{K \in \{ 0,1 \}^k} [ T'^{F_K} () =1 ] = \mathop{\mathbb P}_{K} [ T^{Enc(K, \cdot)} (Enc(K,M)) = 1 ] \ \ \ \ \ (2)$

$\displaystyle \mathop{\mathbb P}_{R: \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m} [T'^{R} () = 1] = \mathop{\mathbb P}_{R} [T^{\overline{Enc}(\cdot)} (\overline{Enc}(M)) = 1] \ \ \ \ \ (3)$

which means that

$\displaystyle \left|\mathop{\mathbb P}_{K \in \{ 0,1 \}^k} [ T'^{F_K} () =1 ] - \mathop{\mathbb P}_{R: \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m} [T'^{R} () = 1]\right| > \epsilon \ \ \ \ \ (4)$

The complexity of ${T'}$ is at most the complexity of ${T}$ times ${O(m)}$ (the time needed to translate between oracle queries of ${T}$ and oracle queries of ${T'}$ ), and so if ${T}$ has complexity ${t/O(m)}$ then ${T'}$ has complexity ${\leq t}$ . This means that (4) contradicts the assumption that ${F}$ is ${(t,\epsilon)-}$ secure. ◻

CS 276 Lecture 6 (Draft)

Posted on February 5, 2009 by luca

Summary

The encryption scheme we saw last time, based on pseudorandom functions, works and is CPA-secure, but it is not used in practice. A disadvantage of the scheme is that the length of the encryption is twice the length of the message being sent.

Today we see the “counter mode” generalization of that scheme, which has considerably smaller overhead for long messages, and see that this generalizes preserves CPA-security.

We then give the definition of pseudorandom permutation, which is a rigorous formalization of the notion of block cipher from applied cryptography, and see two ways of using block ciphers to perform encryption. One is totally insecure, the other achieves CPA security.

1. The Randomized Counter Mode

Suppose we have a pseudorandom function ${F: \{ 0,1 \}^k \rightarrow \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ ; we describe an encryption scheme that works for messages of variable length. We assume without loss of generality that the length of the message is a multiple of ${m}$ , and we write a plaintext ${M}$ of length ${cm}$ as ${M_1,\ldots,M_c}$ , a sequence of ${c}$ blocks of length ${m}$ .

:
- pick a random ${r\in \{ 0,1 \}^m}$ ;
- output ${(r,F_K(r+1) \oplus M_1,\ldots,F_K(r+c)\oplus M_c}$
${Dec(K,C_0,C_1,\ldots,C_k):= C_1 \oplus F_K(C_0+1),\ldots,C_c \oplus F_K(C_0+c)}$

(When ${r}$ is a binary string in ${\{ 0,1 \}^m}$ and ${i}$ is an integer, ${r+i}$ means the binary representation of the sum mod ${2^m}$ of ${r}$ (seen as an integer) and ${i}$ .)

Theorem 1 Suppose ${F}$ is a ${(t,\epsilon)}$ -secure pseudorandom function; then, when used to encrypt messages of length ${cm}$ , the above scheme is ${(t-O(cm),O(\epsilon + t^2 \cdot 2^{-m}))}$ -secure against CPA

2. Pseudorandom Permutations

Denote by ${{\cal P}_n}$ the set of permutations ${P: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ ,

Definition 2 (Pseudorandom Permutation) A pair of functions ${F: \{ 0,1 \}^k \times \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ ${I: \{ 0,1 \}^k \times \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ is a ${(t,q,\epsilon)}$ -secure pseudorandom permutation if:

For every ${r \in \{ 0,1 \}^k}$ , the functions ${x\rightarrow F_r (x)}$ and ${y\rightarrow I_r(x)}$ are permutations and are one the inverse of the other;
For every oracle algorithm ${T}$ that has complexity at most ${t}$ and that makes at most ${q}$ oracle queries we have
$\displaystyle | \mathop{\mathbb P}_{K \in \{ 0,1 \}^k} [ T^{F_K,I_K} () =1 ] - \mathop{\mathbb P}_{P \in {\cal P}_n} [T^{P,P^{(-1)}} () = 1] | \leq \epsilon$

That is, without knowing the random key ${K}$ , the permutation ${F_r(\cdot)}$ and its inverse ${I_r(\cdot)}$ look like a completely random permutation and its inverse.

In the applied cryptography literature, pseudorandom permutations are called block ciphers.

How do we construct pseudorandom permutations? There are a number of block ciphers proposal, including the AES standard, that have been studied extensively and are considered safe for the time being. We shall prove later that any construction of pseudorandom functions can be turned into a construction of pseudorandom permutations; also, every construction of pseudorandom generators can be turned into a pseudorandom function, and every one-way function can be used to construct a pseudorandom generator. Ultimately, this will mean that it is possible to construct a block cipher whose security relies, for example, on the hardness of factoring random integers. Such a construction, however, would not be practical.

3. Encryption Using Pseudorandom Permutations

Here are two ways of using Pseudorandom Functions and Permutations to perform encryption. Both are used in practice.

3.1. ECB Mode

The Electronic Code-Book mode of encryption works as follows

${Enc(K,M) := F_K(M)}$
${Dec(K,M) := I_K(M)}$

Exercise 1 Show that ECB is message-indistinguishable for one-time encryption but not for two encryptions.

3.2. CBC Mode

In its simplest instantiation the Cipher Block-Chaining mode works as follows:

${Enc(K,M):}$ pick a random string ${r\in \{ 0,1 \}^n}$ , output ${( r,F_K(r \oplus M))}$
${Dec(K,(C_0,C_1)) := C_0 \oplus I_K (C_1)}$

Note that this similar to (but a bit different from) the scheme based on pseudorandom functions that we saw last time. In CBC, we take advantage of the fact that ${F_K}$ is now a permutation that is efficiently invertible given the secret key, and so we are allowed to put the ${\oplus M}$ inside the computation of ${F_k}$ .

There is a generalization in which one can use the same random string to send several messages. (It requires synchronization and state information.)

- pick a random string ${C_0\in \{ 0,1 \}^n}$ ;
- and output ${(C_0,C_1,\ldots,C_c)}$ where ${C_i := F_K(C_{i-1} \oplus M_i)}$
${Dec(K,C_0,C_1,\ldots,C_c):= M_1,\ldots,M_c}$ where ${M_i := I_K (C_i) \oplus C_{i-1}}$

This mode achieves CPA security.

4. The Ultimate Security

CPA security is not yet the strongest possible definition of security. It does not capture the possibility that an active adversary might obtain plaintext-ciphertext pairs in which the ciphertext depends arbitrarily on the challenge that the adversary is trying to decode. Suppose that the encryption scheme is part of a larger protocol in which sender and receiver are expected to exchange messages in a certain format. Then the attacker can send a ciphertext (of which it does not know the decoding), and then see whether it receives a short reply (indicative that it is the encryption of “message invalid”) or a longer one (which would be the continuation of the protocol).

In a chosen ciphertext attack (CCA), an attacker is allowed to gain decodings of ciphertexts of her choice. A system is secure if, for any two messages ${M,M'}$ , their encodings are indistinguishable even to an adversary that can make arbitrary use of an encoding and a decoding oracle, with the only provision that it cannot query the decryption oracle on the challenge string.

Definition 3 (CCA Security) An encryption scheme ${(Enc,Dec)}$ is ${(t,\epsilon)}$ -CCA Secure if for every two messages ${M,M'}$ and for every oracle algorithm ${T}$ that satisfies the following two properties

has complexity ${\leq t}$ ;
when given input ${C}$ and oracles ${E,D}$ , ${T^{E,D}(C)}$ never queries oracle ${D}$ with the string ${C}$ ;

We have

$\displaystyle | \mathop{\mathbb P} [ T^{Enc(K,\cdot),Dec(K,\cdot)} (Enc(K,M)) = 1]$

$\displaystyle - \mathop{\mathbb P} [ T^{Enc(K,\cdot),Dec(K,\cdot)} (Enc(K,M')) = 1] | \leq \epsilon$

It is not hard to show that all the encryption schemes we have seen so far fail CCA security.

Instead of trying to tweak the schemes in order to try and gain CCA security, we shall adopt a more modular design approach.

First, we will move on to discuss message authentication, which is an important goal in itself, for example when communicating with your online banking system. Then, we shall see that a CPA-secure encryption scheme, augmented with a proper message authentication scheme, automatically guarantees CCA security, because an attacker can never make any use of a decryption oracle.

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

Tag Archives: CPA security

CS276 Lecture 5: Encryption Using Pseudorandom Functions

CS 276 Lecture 6 (Draft)