CS276 Lecture 8: CCA-Secure Encryption

Scribed by James Cook

Summary

Last time we described a secure MAC (message authentication code) based on pseudorandom functions. Its disadvantage was the length of the tag, which grew with the length of the message.

Today we describe the CBC-MAC, also based on pseudorandom functions, which has the advantage of short tags. We skip its security analysis.

Next, we show that combining a CPA-secure encryption with a secure MAC gives a CCA-secure encryption scheme.

1. CBC-MAC

Suppose we have a pseudorandom function ${F: \{ 0,1 \}^k \times \{ 0,1 \}^m \rightarrow \{ 0,1 \}^m}$ .

Last time we described a provably secure MAC in which a message ${M}$ is broken up into blocks ${M_1,\ldots,M_\ell}$ , each of length ${m/4}$ , and the tag of ${M}$ is the sequence

$\displaystyle (r,F_K(r,\ell,1,M_1),F_K(r,\ell,2,M_2),\ldots,F_K(r,\ell,\ell,M_\ell))$

where ${r}$ is a random string and ${K}$ is the key of the authentication scheme. Jonah suggested a more compact scheme, in which ${M}$ is broken into blocks ${M_1,\ldots,M_\ell}$ of length ${m/3}$ and the tag is

$\displaystyle (r,F_K(r,0,1,M_1),F_K(r,0,2,M_2),\ldots,F_K(r,1,\ell,M_\ell))$

for a random string ${r}$ . That is, the length of the message is not explicitly authenticated in each block, but we authenticate a single bit that says whether this is, or isn’t, the last block of the message.

Exercise 1 Prove that if ${F}$ is ${(t,\epsilon)}$ -secure then this scheme is ${(t/O(\ell m), \epsilon + t^2 \cdot 2^{-m/3} + 2^{-m})}$ -secure, where ${\ell}$ is an upper bound to the number of blocks of the message that we are going to authenticate.

A main disadvantage of such schemes is the length of the final tag.

The CBC-MAC scheme has the advantage of producing a tag whose length is only ${m}$ .

CBC-MAC scheme:

:
- ${T_0 := F_K(\ell)}$
- for ${i:=1}$ to ${\ell}$ : ${T_i := F_K(T_{i-1} \oplus M_i )}$
- return ${T_\ell}$
${Verify(K,M,T)}$ : check that ${Tag(K,M) == T}$

This scheme is similar to in structure to CBC encryption:

We will not prove CBC-MAC to be secure, but the general approach is to show that all the inputs to ${F_{K}}$ are distinct with high probability.

2. Combining MAC and Encryption

Suppose that we have an encryption scheme ${(E,D)}$ and a MAC ${(T,V)}$ . We can combine them to produce the following encryption scheme, in which a key is made of pair ${(K_1,K_2)}$ where ${K_1}$ is a key for ${(E,D)}$ and ${K_2}$ is a key for ${(T,V)}$ :

:
- ${C:= E(K_1,M)}$
- ${T:= T(K_2,C)}$
- return ${(C,T)}$
:
- if ${V(K_2,C,T)}$ : return ${D(K_1,C)}$
- else return ERROR

The scheme ${(E',D')}$ is an encrypt-then-authenticate scheme in which we first encrypt the plaintext with key ${K_1}$ and then authenticate the ciphertext with key ${K_2}$ . The decryption aborts if given an incorrectly tagged ciphertext.

The idea of this scheme is that an adversary mounting a CCA attack (and hence having access to both an encryption oracle and a decryption oracle) has no use for the decryption oracle, because the adversary already knows the answer that the decryption oracle is going to provide for each oracle query:

if the adversary queries a ciphertext previously obtained from the encryption oracle, then it already knows the corresponding plaintext
if the adversary queries a ciphertext not previously obtained from the encryption oracle, then almost surely (assuming the security of the MAC), the tag in the ciphertext will be incorrect, and the oracle answer is going to be “ERROR”

This intuition is formalized in the proof of the following theorem.

Theorem 1 If ${(E,D)}$ is ${(t,\epsilon)}$ CPA secure, and ${(T,V)}$ is ${(t,\epsilon/t)}$ secure, then ${(E',D')}$ is ${(t/(r+O(\ell)), 3\epsilon)}$ CCA secure, where ${r}$ is an upper bound to the running time of the encryption algorithm ${E}$ and the tag algorithm ${T}$ , and ${\ell}$ is an upper bound to the length of the messages that we encrypt.

Proof: Suppose ${(E',D')}$ is not CCA-secure. Then there exist an algorithm ${A'}$ of complexity ${t' \le t / (r + O(\ell))}$ and two messages ${M_1}$ and ${M_2}$ such that

$\displaystyle |\mathop{\mathbb P}[A'^{E',D'} (E'(M_1))=1] -\mathop{\mathbb P}[A'^{E',D'}(E'(M_2))=1]|>3\epsilon \ \ \ \ \ (1)$

(In (1), ${E'()}$ and ${D'()}$ should take keys ${(K_1,K_2)}$ as input; we have omitted the keys to simplify notation.)

Without loss of generality, we assume ${A'}$ never queries ${D'}$ on any ciphertext previously returned by ${E'}$ . We can make this assumption because we can modify ${A'}$ to keep a record of all the queries it makes to ${E'}$ , and to use the record to avoid redundant queries to ${D'}$ .

We now wish to convert ${A'}$ to a new algorithm ${A_{1}}$ such that

$\displaystyle \forall M\ \mathop{\mathbb P}_{K}[A_{1}^{E_{K}}(E_{K}(M))=1]\approx\mathop{\mathbb P}_{K_1,K_2}[A'^{E'_{(K_{1}, K_{2})},D'_{(K_{1}, K_{2})}}(E'_{(K_1, K_2)}(M))] \ldotp$

Note that ${A'}$ is given the oracles ${E'}$ and ${D'}$ , but ${A_{1}}$ is given as an oracle just the original CPA-secure encryption algorithm ${E}$ .

Define

:
- pick a random key ${K_{2}'}$
- ${T := T(K_{2}', C)}$
- simulate with these oracles:
  - ${O_{1}(M)}$ returns ${E'((K_{1}, K_{2}'), M)}$ ;
  - ${O_{2}}$ always returns ERROR.

${A_{1}}$ has to run the tagging algorithm ${T}$ , which has complexity ${r}$ , every time ${A'}$ makes an oracle call. Since ${A'}$ has complexity at most ${t/r}$ , ${A_{1}}$ has complexity at most ${t}$ .

Now, assuming the attack ${A'}$ works, we can apply the triangle inequality to (1) to obtain:

$\displaystyle 3\epsilon < |\mathop{\mathbb P}[A'^{E',D'}(E'(M_{1}))=1]-\mathop{\mathbb P}[A_{1}^{E}(E(M_{1}))=1]| \ \ \ \ \ (2)$

$\displaystyle +|\mathop{\mathbb P}[A_{1}^{E}(E(M_{1})=1]-\mathop{\mathbb P}[A_{1}^{E}(E(M_{2})=1]| \ \ \ \ \ (3)$

$\displaystyle +|\mathop{\mathbb P}[A_{1}^{E}(E(M_{2})=1]-\mathop{\mathbb P}[A'^{E',D'}(E'(M_{2})=1]| \ \ \ \ \ (4)$

One of (2), (3) or (4) must be greater than ${\epsilon}$ .

If (3) ${>\epsilon}$ , then algorithm ${A_{1}}$ breaks the CPA-security of ${E}$ . We assumed ${E}$ was CPA-secure, so one of (2) or (4) must be greater than ${\epsilon}$ . In either case, there exists a message ${M}$ with the property that

$\displaystyle |\mathop{\mathbb P}_{K}[A_{1}^{E}(E(M))=1]-\mathop{\mathbb P}_{K_{1},K_{2}}[A'^{E',D'}(E'(M))=1]|>\epsilon\ldotp \ \ \ \ \ (5)$

If when ${A_{1}}$ is simulating ${A'}$ , ${A'}$ never makes a call to ${D'}$ which results in an output other than “ERROR”, then ${A_{1}}$ behaves exactly as ${A'}$ would with the same key ${K_{2}}$ . So (5) implies that with probability greater than ${\epsilon}$ , ${A'^{E',O'}(E'(M))}$ makes a call to the decryption oracle resulting in an output other than “ERROR”. This means ${A'}$ manages to generate valid messages that it has never seen before, and we can use this fact to define an algorithm ${A_{2}}$ that breaks the Message Authentication Code ${(T, V)}$ .

${A'^{E',D'}}$ makes at most ${t}$ oracle queries to ${D'}$ , and with probability ${\epsilon}$ , at least one of those results in an output other than “ERROR”. There must exist a number ${i}$ such that with probability at least ${\epsilon/t}$ , the ${i}$ -th query ${A'^{E',D'}}$ makes to ${D'}$ is the first one that does not result in an error. Then define algorithm ${A_{2}}$ as follows.

(no input)
- choose a random key ${K_{1}}$
- ${C := E(K_{1}, M)}$
- ${T := T(C)}$
- simulate , with the following two oracles…
  - :
    - ${C := E(K_{1},M_{1})}$
    - ${T := T(C)}$
    - return ${(C, T)}$
  - ${O_{2}}$ always returns ERROR
  …until ${A'}$ makes its ${i}$ -th query to ${O_{2}}$
- Let ${(C_{i}, T_{i})}$ be the ${i}$ -th query ${A'}$ made to ${O_{2}}$ .
- return ${(C_{i}, T_{i})}$

Note that ${A_{2}}$ has complexity at most ${t}$ , and by our analysis of algorithm ${A'}$ , ${A_{2}^{T}}$ produces a correct tage for a message it has never seen before with probability at least ${\epsilon/t}$ .

Since we assumed ${(T, V)}$ was ${(T, \epsilon/t)}$ -secure, we have reached a contradiction: ${(E', D')}$ is therefore CCA secure. $\Box$

in theory

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

CS276 Lecture 8: CCA-Secure Encryption

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply