1 \xcalways\section{Symmetric encryption
}\x
3 \xcalways\subsection{Syntax
}\x
6 \head{Symmetric encryption syntax
}
8 A
\emph{symmetric encryption scheme
} $
\mathcal{E
} = (E, D)$ is a set of
9 keys $
\keys\mathcal{E
}$ (usually $\
{0,
1\
}^k$ for some integer $k$) and
12 \item an
\emph{encryption
} algorithm $E
\colon \keys\mathcal{E
} \times \
{0,
13 1\
}^*
\to \
{0,
1\
}^*$; and
14 \item a
\emph{decryption
} algorithm $D
\colon \keys\mathcal{E
} \times \
{0,
15 1\
}^*
\to \
{0,
1\
}^*$.
17 We also have a
\emph{correctness
} requirement: for any $K
\in
18 \keys\mathcal{E
}$, and any plaintext $x$, if $E(K, x)$ returns $y$ then
19 $D(K, y)$ returns $x$.
21 We write $E_K(
\cdot)$ rather than $E(K,
\cdot)$, and $D_K(
\cdot)$ rather
25 \xcalways\subsection{Security notions
}\x
28 \head{Symmetric encryption security notions
}
30 In symmetric scheme, an adversary who doesn't know the key can't encrypt
31 data for itself. To modify our security notions by providing the adversary
32 with an encryption oracle.
34 We consider semantic security, indistinguishability and non-malleability,
35 against chosen-plaintext and chosen-ciphertext attacks. To make life more
36 complicated, we have three different indistinguishability notions.
38 We use the same notation to describe the decryption oracles provided in
39 various types of attacks:
40 \begin{tabular
}[C
]{l Mc Mc
}
42 Attack & D_0(c) & D_1(c) \\
\hlx{vhv
}
44 CCA1 & D_K(c) &
\bot \\
45 CCA2 & D_K(c) & D_K(c) \\
\hlx*
{vh
}
50 \topic{semantic security
}
51 \head{Semantic security
}
53 The semantic security game is as for the asymmetric case, except for the
54 presence of encryption oracles.
57 Experiment $
\Expt{sem-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$: \+ \\
58 $K
\getsr \keys\mathcal{E
}$; \\
59 $(
\mathcal{M
}, s)
\gets A^
{E_K(
\cdot), D_0(
\cdot)
}
60 (
\cookie{select
})$; \\
61 $x_0
\getsr \mathcal{M
}$; $x_1
\getsr \mathcal{M
}$; \\
62 $y
\gets E_K(x_1)$; \\
63 $(f,
\alpha)
\gets A^
{E_K(
\cdot), D_1(
\cdot)
}
64 (
\cookie{predict
}, y, s)$; \\
65 \IF $f(x_b) =
\alpha$
\THEN \RETURN $
1$; \\
68 The distribution $
\mathcal{M
}$ must be
\emph{valid
}: all strings in
69 $
\supp\mathcal{M
}$ must have the same length.
73 \topic{find-then-guess
}
74 \head{Find-then-guess indistinguishability
}
76 The `find-then-guess' (FTG) game corresponds to the standard public-key
77 indistinguishability notion.
79 Experiment $
\Expt{ftg-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$: \+ \\
80 $K
\getsr \keys\mathcal{E
}$; \\
81 $(x_0, x_1, s)
\gets A^
{E_K(
\cdot), D_0(
\cdot)
}(
\cookie{find
})$; \\
82 \IF $|x_0|
\ne |x_1|$
\THEN \RETURN $
0$; \\
83 $y
\gets E_K(x_b)$; \\
84 $b'
\gets A^
{E_K(
\cdot), D_1(
\cdot)
}(
\cookie{guess
}, y, s)$; \\
91 \head{Left-or-right indistinguishability
}
93 The `left-or-right' (LOR) notion is a natural extension of find-then-guess.
94 Rather than having to guess the hidden bit using a single challenge
95 ciphertext, the adversary is allowed to request more as it likes. It is
96 given an encryption oracle which accepts two arguments: it selects either
97 the left or the right plaintext, according to the hidden bit, and returns
100 Experiment $
\Expt{lor-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$; \+ \\
101 $K
\getsr \keys\mathcal{E
}$; \\
102 $b'
\gets A^
{E_K(
\id{lr
}_b(
\cdot,
\cdot)), D_1(
\cdot)
}$; \\
103 \RETURN $b'$; \- \\
[\smallskipamount]
104 Function $
\id{lr
}_b(x_0, x_1)$: \+ \\
107 Note that, because the adversary only runs in one stage, we can only
108 consider chosen-plaintext and adaptive chosen-ciphertext attacks.
112 \topic{real-or-random
}
113 \head{Real-or-random indistinguishability
}
115 The `real-or-random' (ROR) notion is somewhat less natural, but turns out
116 to be useful for analysing block cipher encryption modes.
118 The adversary is given an oracle which, when given a plaintext $x$, either
119 returns an encryption of $x$ or an encryption of a random string with the
122 Experiment $
\Expt{ror-
\id{atk
}-$
0$
}{\mathcal{E
}}(A)$; \+ \\
123 $K
\getsr \keys\mathcal{E
}$; \\
124 $b'
\gets A^
{E_K(
\id{rand
}(
\cdot)), D_1(
\cdot)
}$; \\
125 \RETURN $b'$; \- \\
[\smallskipamount]
126 Function $
\id{rand
}(x)$: \+ \\
127 $x'
\getsr \
{0,
1\
}^
{|x|
}$; \\
130 Experiment $
\Expt{ror-
\id{atk
}-$
1$
}{\mathcal{E
}}(A)$; \+ \\
131 $K
\getsr \keys\mathcal{E
}$; \\
132 $b'
\gets A^
{E_K(
\cdot), D_1(
\cdot)
}$; \\
135 Again, only chosen-plaintext and adaptive chosen-ciphertext attacks are
140 \topic{relations between notions
}
141 \head{Relations between notions
\cite{Bellare:
2000:CST
}}
144 \txt{LOR
} \ar@<
0.5ex>
[r
]^
1 \ar@<-
0.5ex>
[d
]_3 &
145 \txt{ROR
} \ar@<
0.5ex>
[l
]^
2 \\
146 \txt{FTG
} \ar@
{-->
}@<-
0.5ex>
[u
]_4
\ar@<
0.5ex>
[r
] &
147 \txt{SEM
} \ar@<
0.5ex>
[l
]
150 \settowidth{\labelwidth}{\textbf{Key
}}
151 \leftmargin\labelwidth\advance\leftmargin\labelsep
152 \itemindent0pt\let\makelabel\textbf}
153 \item[Key
] \begin{itemize
}
154 \item A solid arrow $
\xy\ar*+
{A
};<
1.5cm,
0cm>*+
{B
}\endxy$ indicates an
155 \emph{security-preserving
} reduction: if a scheme is secure in notion
156 $A$ then it is as secure in notion $B$, to within a small constant
158 \item A broken arrow $
\xy\ar@
{-->
}*+
{A
};<
1.5cm,
0cm>*+
{B
}\endxy$
159 indicates a non-security-preserving reduction.
160 \item The numbers refer to sections of the proof provided in the notes.
166 We deal with the propositions one at a time. Most of them are pretty easy,
167 with the exception of the security-losing reduction from FTG to LOR.
170 \item We show that $
\text{LOR-
\id{atk
}} \implies \text{ROR-
\id{atk
}}$.
171 Suppose $A'$ attacks $
\mathcal{E
}$ in the real-or-random sense.
173 Adversary $A^
{E(
\cdot,
\cdot), D(
\cdot)
}$: \+ \\
174 \RETURN $A'^
{\id{ror-hack
}(
\cdot), D(
\cdot)
}$; \-\\
[\smallskipamount]
175 Oracle $
\id{ror-hack
}(x)$: \+ \\
176 $x'
\getsr \
{0,
1\
}^
{|x|
}$; \\
179 Since this provides a perfect simulation of the ROR game,
180 \
[ \Adv{lor-
\id{atk
}}{\mathcal{E
}}(A) =
181 \Adv{ror-
\id{atk
}}{\mathcal{E
}}(A'), \
]%
183 \
[ \InSec{ror-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)
\le
184 \InSec{lor-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D). \
]%
186 \item We show that $
\text{ROR-
\id{atk
}} \implies \text{LOR-
\id{atk
}}$.
187 Suppose $A'$ attacks $
\mathcal{E
}$ in the left-or-right sense.
189 Adversary $A^
{E(
\cdot), D(
\cdot)
}$: \+ \\
190 $
\hat{b
} \gets \
{0,
1\
}$; \\
191 $b'
\gets A'^
{\id{lor-hack
}(
\cdot,
\cdot), D(
\cdot)
}$; \\
192 \IF $b' =
\hat{b
}$
\THEN \RETURN $
1$; \\
193 \ELSE \RETURN $
0$; \- \\
[\smallskipamount]
194 Oracle $
\id{lor-hack
}(x_0, x_1)$: \+ \\
195 \RETURN $E(x_
{\hat{b
}})$;
197 If the ROR oracle is returning correct encryptions, then $A'$ will return
198 the correct bit $
\hat{b
}$ with probability
199 \
[ \frac{\Adv{lor-
\id{atk
}}{\mathcal{E
}}(A')
}{2} +
\frac{1}{2}; \
]
200 if the ROR oracle is returning ciphertexts for random plaintexts, then
201 $A'$ is being given no information about $
\hat{b
}$, and hence guesses
202 correctly with probability exactly $
\frac{1}{2}$. We conclude that
203 \
[ \Adv{ror-
\id{atk
}}{\mathcal{E
}}(A) =
204 \frac{1}{2}\Adv{lor-
\id{atk
}}{\mathcal{E
}}(A'), \
]%
206 \
[ \InSec{lor-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)
\le
207 2 \cdot \InSec{ror-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D). \
]%
209 \item We show that $
\text{LOR-
\id{atk
}} \implies \text{FTG-
\id{atk
}}$.
210 Suppose $A'$ attacks $
\mathcal{E
}$ in the find-then-guess sense. We
211 assume, without loss of generality, that $A'$ never queries its
212 decryption oracle on ciphertexts it obtained from its encryption oracle.
214 Adversary $A^
{E(
\cdot,
\cdot), D(
\cdot)
}$: \+ \\
215 $(x_0, x_1, s)
\gets A'^
{\id{encrypt
}(
\cdot), D(
\cdot)
}
217 $y
\gets E(x_0, x_1)$; \\
218 $b'
\gets A'^
{\id{encrypt
}(
\cdot), D(
\cdot)
}
219 (
\cookie{guess
}, y, s);$ \\
220 \RETURN $b'$; \- \\
[\smallskipamount]
221 Oracle $
\id{encrypt
}(x)$: \+ \\
224 Since this provides a perfect simulation of the FTG game,
225 \
[ \Adv{lor-
\id{atk
}}{\mathcal{E
}}(A) =
226 \Adv{ftg-
\id{atk
}}{\mathcal{E
}}(A'), \
]%
228 \
[ \InSec{ftg-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)
\le
229 \InSec{lor-
\id{atk
}}(
\mathcal{E
}; t, q_E +
1, q_D). \
]%
231 \item We show that $
\text{FTG-
\id{atk
}} \implies \text{LOR-
\id{atk
}}$,
232 though with a factor of $q_E$ loss of security.
234 This proof is slightly more tricky than the others. Consider the
235 following `hybrid' games, defined for $
0 \le i
\le q_E$:
237 Experiment $
\Expt{hyb-$i$-
\id{atk
}-$b$
}{\mathcal{E
}}$: \+ \\
238 $K
\getsr \keys\mathcal{E
}$; \\
240 $b'
\gets A^
{E(
\id{lr-hack
}_b(
\cdot,
\cdot)), D_1(
\cdot)
}$; \\
241 \RETURN $b'$; \- \\
[\smallskipamount]
243 Function $
\id{lr-hack
}_b(x_0, x_1)$: \+ \\
244 \IF $j < i$
\THEN $x
\gets x_0$; \\
245 \ELSE \IF $j > i$
\THEN $x
\gets x_1$; \\
246 \ELSE $x
\gets x_b$; \\
251 \
[ \Adv{hyb-$i$-
\id{atk
}}{\mathcal{E
}}(A) =
252 \Pr[\Expt{hyb-$i$-
\id{atk
}-$
1$
}{\mathcal{E
}} =
1] -
253 \Pr[\Expt{hyb-$i$-
\id{atk
}-$
0$
}{\mathcal{E
}} =
1]. \
]%
255 Observe that we have the identities
256 \begin{eqnarray*
}[rl
]
257 \Expt{lor-
\id{atk
}-$
0$
}{\mathcal{E
}} &
\equiv
258 \Expt{hyb-$(q_E
{-
}1)$-
\id{atk
}-$
0$
}{\mathcal{E
}}
260 \Expt{lor-
\id{atk
}-$
1$
}{\mathcal{E
}} &
\equiv
261 \Expt{hyb-$
0$-
\id{atk
}-$
1$
}{\mathcal{E
}}
263 \tabpause{and, for $
0 \le i < q_E$,
}
264 \Expt{hyb-$i$-
\id{atk
}-$
0$
}{\mathcal{E
}} &
\equiv
265 \Expt{hyb-$(i
{+
}1)$-
\id{atk
}-$
1$
}{\mathcal{E
}}.
268 \begin{eqnarray*
}[rclclc
]
269 \Adv{lor-
\id{atk
}}{\mathcal{E
}}(A)
270 &=&
\Pr[\Expt{lor-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] &-&
271 \Pr[\Expt{lor-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1]
273 &=&
\Pr[\Expt{hyb-$
0$-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] &-&
274 \Pr[\Expt{hyb-$(q_E
{-
}1)$-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1]
276 &=&
\Pr[\Expt{hyb-$
0$-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] &-&
277 \Pr[\Expt{hyb-$
0$-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1] &+ \\*
278 & &
\Pr[\Expt{hyb-$
1$-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] &-&
279 \Pr[\Expt{hyb-$
1$-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1] &+ \\*
280 & &
\multicolumn{1}{c
}{\smash\vdots} &-&
281 \multicolumn{1}{c
}{\smash\vdots} &+ \\*
282 & &
\Pr[\Expt{hyb-$(q_E
{-
}1)$-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] &-&
283 \Pr[\Expt{hyb-$(q_E
{-
}1)$-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1]
285 &=&
\sum_{0\le i<q_E
} \Adv{hyb-$i$-
\id{atk
}}{\mathcal{E
}}(A)
287 Now, there must be at least one $i$ for which
288 \
[ \Adv{hyb-$i$-
\id{atk
}}{\mathcal{E
}}(A)
\ge
289 \frac{1}{q_E
} \Adv{lor-
\id{atk
}}{\mathcal{E
}}(A). \
]%
291 Suppose that $A'$ is an adversary attacking $
\mathcal{E
}$ in the LOR
292 sense. We can construct an FTG adversary $A$ for which
293 \
[ \Adv{ftg-
\id{atk
}}{\mathcal{E
}}(A)
\ge
294 \frac{1}{q_E
} \Adv{lor-
\id{atk
}}{\mathcal{E
}}(A') \
]%
295 as follows:
\footnote{%
296 The expression of the FTG adversary requires control flow operations
297 which aren't easily expressed in the pseudocode language we've used so
298 far, hence the cop-out into English.
}
300 \item When invoked in the $
\cookie{find
}$ stage, run the LOR adversary,
301 passing it $A$'s decryption oracle.
302 \item Respond to its first $i$ left-or-right queries $(x_0, x_1)$ with
304 \item On the $(i +
1)$-th left-or-right query, $(x_0, x_1)$, package up
305 all of $A'$'s state, and return that, together with the pair $(x_0,
306 x_1)$ as the result of $A$'s $
\cookie{find
}$ stage.
307 \item When reinvoked in the $
\cookie{guess
}$ stage, return the challenge
308 ciphertext $y$ as the result of $A'$'s $(i +
1)$-th query.
309 \item Respond to the remaining $q_E - i -
1$ left-or-right queries
310 $(x_0, x_1)$ with $E(x_1)$.
311 \item Return the bit output by $A'$.
313 This evidently simulates the environment of
314 $
\Expt{hyb-$i$-
\id{atk
}-$b$
}{\mathcal{E
}}(A')$; hence $A$ achieves the
315 claimed advantage. Thus,
316 \
[ \InSec{lor-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)
\le
317 q_E
\cdot \InSec{ftg-
\id{atk
}}(
\mathcal{E
}; t, q_E -
1, q_D). \
]%
319 Now we show that we can't obtain a better reduction. Suppose that
320 $
\mathcal{E
} = (E, D)$ is $(t, q_E, q_D,
\epsilon)$-secure in the FTG
321 sense. We construct a
\emph{$p$-leaky
} version, $
\mathcal{E
}' = (E',
322 D')$. Let $
\id{maybe
}(p)$ denote a function which returns $
1$ with
325 Algorithm $E'_K(x)$: \+ \\
326 \IF $
\id{maybe
}(p) =
1$
\THEN \RETURN $
1 \cat x$; \\
327 \RETURN $
0 \cat E_K(x)$;
329 Algorithm $D'_K(y')$: \+ \\
330 \PARSE $y'$
\AS $
1\colon b, y$; \\
331 \IF $b =
1$
\THEN \RETURN $y$; \\
334 A simple simulation argument shows that this scheme is still secure,
335 except for an additional term $p$, handling the case where the challenge
336 ciphertext $y^* =
1 \cat x^*$. It is easy to see that
337 \
[ \InSec{lor-
\id{atk
}}(
\mathcal{E
}'; t, q_E,
0)
\ge q_E p, \
]
338 concluding the proof.
341 The proofs that $
\text{FTG-
\id{atk
}} \implies \text{SEM-
\id{atk
}}$ and
342 $
\text{SEM-
\id{atk
}} \implies \text{FTG-
\id{atk
}}$ are just as in the
343 public-key case (page~
\pageref{pf:pub-ind-eq-sem
}), except for the presence
344 of encryption oracles (which are passed on unmolested). And that's all we
349 Consider the following `ciphertext-or-random-string' security notion.
351 Experiment $
\Expt{cor-
\id{atk
}-$
0$
}{\mathcal{E
}}(A)$: \+ \\
352 $b'
\gets A^
{\id{rand
}(E_K(
\cdot)), D_1(
\cdot)
}$; \\
353 \RETURN $b'$; \- \\
[\smallskipamount]
354 Function $
\id{rand
}(x)$: \+ \\
355 $x'
\getsr \
{0,
1\
}^
{|x|
}$; \\
358 Experiment $
\Expt{cor-
\id{atk
}-$
1$
}{\mathcal{E
}}(A)$; \+ \\
359 $K
\getsr \keys\mathcal{E
}$; \\
360 $b'
\gets A^
{E_K(
\cdot), D_1(
\cdot)
}$; \\
363 Relate this notion to the others we've already seen.
365 It's not hard to see that $
\text{COR
} \implies \text{LOR
}$; the proof is
366 similar to $
\text{ROR
} \implies \text{LOR
}$, and we have
367 $
\InSec{cor-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)
\le 2\cdot
368 \InSec{lor-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)$. On the other hand,
369 $
\text{LOR
} \not\implies \text{COR
}$. To see this, let $
\mathcal{E
} = (E,
370 D)$ be an encryption scheme secure in the LOR-
\id{atk
} sense, and define
371 $
\mathcal{E
}' = (E', D')$ by $E'_K(x) =
0^n
\cat E_K(x)$ and $D'_K(y') =
372 D_K(y)$ if $y' =
0^n
\cat y$ for some $y$, or $
\bot$ otherwise. Because
373 the fixed padding is independent of the plaintext,
374 $
\InSec{lor-
\id{atk
}}(
\mathcal{E
}'; t, q_E, q_D)
\le
375 \InSec{lor-
\id{atk
}}(
\mathcal{E
}; t, q_E, q_D)$. But $
\mathcal{E
}'$ is not
376 COR-CPA secure because an adversary can check for the fixed padding; hence
377 $
\InSec{cor-cpa
}(
\mathcal{E
}'; t, q_E, q_D)
\ge 1 - q_E
2^
{-n
}$.
381 Let $F
\colon \
{0,
1\
}^k
\times \
{0,
1\
}^l
\to \
{0,
1\
}^l$ be a PRF, and let
382 $g
\colon \
{0,
1\
}^l
\to \
{0,
1\
}^
{2l}$ be a length-doubling PRG. Recall
383 from Exercise~
\ref{ex:dbl-prg
} the construction $g^(i)$, defined by
384 \
[ g^
{(
1)
}(x) = g(x);
\qquad
385 g^
{(i+
1)
}(x) = g_0(x)
\cat g^
{(i)
}(g_1(x)). \
]%
386 We define an encryption scheme $
\mathcal{E
} = (E, D)$ as follows:
388 Algorithm $E_K(x)$: \\
389 $i
\getsr \
{0,
1\
}^l$; \\
390 $n
\gets \bigl\lceil \frac{|x|
}{L
} \bigr\rceil -
1$; \\
392 $p
\gets g^
{(n)
}(s)$; \\
393 $y
\gets i
\cat (x
\xor p)$; \\
396 Algorithm $D_K(y)$: \\
397 \PARSE $y$
\AS $l
\colon i, y'$; \\
398 $n
\gets \bigl\lceil \frac{|x|
}{L
} \bigr\rceil -
1$; \\
400 $p
\gets g^
{(n)
}(s)$; \\
401 $x
\gets y'
\xor p$; \\
405 \
[ \InSec{lor-cpa
}(
\mathcal{E
}; t, q,
\mu)
\le
406 2 \cdot \InSec{prf
}(F; t, q) +
407 2 q
\mu \cdot \InSec{prg
}(g; t) + q(q -
1)/
2^l, \
]%
408 where $
\mu$ is the maximum value of $n$, as computed by $E_K(
\cdot)$, for
409 any encryption query.
412 \item use a sequence of games, ending with one in which the `ciphertext'
413 are random strings of the right length;
414 \item attack the PRF first;
415 \item use a hybrid argument to attack the PRG, as was used in the proof
416 that $
\text{FTG
} \implies \text{LOR
}$.
419 For each game~$
\G{i
}$, $S_i$~is the event that the adversary guesses
420 correctly. Game~$
\G0$ is the original attack game (with the hidden bit~$b$
421 selected uniformly). Game~$
\G1$ is the same, except that if, for any pair
422 of ciphertexts, the $i$-values are equal, the game ends immediately: the
423 standard collision bound shows that $|
{\Pr[S_1
]} -
\Pr[S_0
]|
\le q(q -
424 1)/
2^
{l+
1}$. In game~$
\G2$, rather than using $F_K$ to compute the
425 seeds~$s$, we just choose $s
\in \
{0,
1\
}^l$ at random each time. Note
426 that the $i$-values are distinct; hence considering an adversary attacking
427 $F$ as a PRF, which simulates either $
\G1$ or $
\G2$ depending on whether
428 its oracle is an instance of~$F$ or a random function respectively, shows
429 that $|
{\Pr[S_2
]} -
\Pr[S_1
]|
\le \InSec{prf
}(F; t, q)$.
431 In game~$
\G3$, rather than using the PRG~$g^
{(n)
}$, we generate the strings
432 $p$ uniformly at random from $\
{0,
1\
}^
{l(n+
1)
}$, and claim that
433 $|
{\Pr[S_3
]} -
\Pr[S_2
]|
\le q
\mu \cdot \InSec{prg
}(g; t)$ (proven below).
434 Finally, in game~$
\G4$, rather than computing the ciphertext as $i
\cat (x
435 \xor p)$, we just generate a random string $\
{0,
1\
}^
{l(n+
2)
}$. Since $i$
436 and $p$ are uniform and random anyway, this doesn't affect the
437 distribution; it does show that the result is independent of the
438 adversary's ciphertext, however, so $
\Pr[S_4
] =
\Pr[S_3
] =
\frac{1}{2}$.
439 Tying all of this together, $(
\Adv{lor-cpa
}{\mathcal{E
}}(A) +
1)/
2 \le
440 \frac{1}{2} +
\InSec{prf
}(F; t, q) + q
\mu \cdot \InSec{prg
}(g; t) + q(q -
441 1)/
2^
{l+
1}$. Multiplying through by~
2 and rearranging yields the required
446 We finally turn to the claim made earlier. In $
\G2$, we use the PRG; in
447 $
\G3$ we don't. Unfortunately, while the left-or-right attack game allows
448 multiple queries and hence multiple samples from the PRG, the PRG attack
449 game only provides one sample. To bridge the gap, we construct a number of
450 hybrid games~$
\H{i
}$ for $
0 \le i
\le q$ in which encryption query~$j$ (for
451 $
0 \le j < q$) is handled as follows: if $
0 \le j < i$ then the query is
452 handled as in $
\G3$; if $i
\le j < q$ then the query is handed as in $
\G2$.
453 Let $T_i$ be the event that the adversary wins in game $
\H{i
}$. Clearly,
454 $
\H0 \equiv \G2$, and $
\H{q
} \equiv \G3$. For each adjacent pair of hybrid
455 games $
\H{i
},
\H{i+
1}$ (for $
0 \le i < q$), we can bound $|
{\Pr[T_
{i+
1}} -
456 \Pr[T_i
]|$ by considering an adversary attacking~$g^
{(n)
}$ by running~$A$,
457 using as its input the XOR mask~$p$ for query~$i$, and following the rules
458 of game~$
\H{i
}$ for the other queries: then if $y$~is random, it simulates
459 $
\H{i+
1}$, whereas if $y$ is the output of $g^
{(n)
}$ then it simulates
460 $
\H{i
}$. Thus $|
{\Pr[T_
{i+
1}} -
\Pr[T_i
]|
\le \mu \cdot \InSec{prg
}(g; t)$
461 (by the answer to
\ref{ex:dbl-prg
}), and $|
{\Pr[S_3
]} -
\Pr[S_2
]| =
462 |
{\Pr[T_
{q-
1}]} -
\Pr[T_0
]|
\le q
\mu \cdot \InSec{prg
}(g; t)$ as claimed.
465 \xcalways\subsection{Block cipher modes
}\x
468 \head{Block cipher modes
}
470 Block ciphers (which we model as PRPs) are readily available components,
471 and we have good tools for analysing their (heuristic) security. It'd be
472 good if we could use them to construct secure encryption schemes.
474 We analyse three standard
\emph{modes of operation
}:
476 \item[Electronic Code Book (ECB)
] Each plaintext block is encrypted
477 independently of the others, using the block cipher.
478 \item[Counter (CTR)
] Choose a random starting point $i$. The plaintext
479 blocks are XORed with the result of encrypting the counter values $i$,
481 \item[Ciphertext Block Chaining (CBC)
] The first plaintext block is XORed
482 with a random
\emph{initialization vector
} and encrypted using the block
483 cipher; thereafter, each plaintext block are XORed with the previous
484 ciphertext block and then encrypted with the block cipher.
489 \head{General notation
}
491 We consider pseudorandom permutations $E
\colon \
{0,
1\
}^k
\times \
{0,
1\
}^l
492 \to \
{0,
1\
}^l$ operating on $l$-bit blocks. We write $E_K(
\cdot)$ rather
495 For the sake of simplicity, we assume that plaintexts are a multiple of $l$
496 bits in length. We shall consider chosen-plaintext attacks, and we shall
497 be quantifying our results in terms of:
499 \item the running time $t$ of adversaries;
500 \item the number $q$ of queries made to the encryption oracle; and
501 \item the maximum size in bits $
\mu$ of any individual encryption query.
504 We shall write `
\FOREACH $l
\colon z$
\FROM $x$
\DO \ldots' to denote
505 iteration over each $l$-bit block $z$ of $x$ in turn.
507 We use $
\emptystring$ to denote the empty string.
513 \head{Electronic Code Book (ECB),
\seq: description
}
515 We define the scheme $
\Xid{\mathcal{E
}}{ECB
}^E = (
\Xid{E
}{ECB
}^E,
516 \Xid{D
}{ECB
}^E))$ by setting $
\keys\Xid{\mathcal{E
}}{ECB
}^E = \
{0,
1\
}^k$
519 Algorithm $
\Xid{E
}{ECB
}^E_K(x)$: \+ \\
520 $y
\gets \emptystring$; \\
521 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
522 \quad $y
\gets y
\cat E_K(z)$; \\
525 Algorithm $
\Xid{D
}{ECB
}^E_K(y)$: \+ \\
526 $x
\gets \emptystring$; \\
527 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
528 \quad $x
\gets x
\cat E_K^
{-
1}(z)$; \\
534 \head{Electronic Code Book (ECB),
\seq: diagram
}
538 []!
{0; <
1cm,
0cm>: <
0cm,
1.5cm>::
}
539 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x" :
[dd
] *+
[F
]{E
}="e"
540 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}
541 "e"
[l
] {K
} :"e" "x"
[rrr
]
542 *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x" :
[dd
] *+
[F
]{E
}="e"
543 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_1
}
544 "e"
[l
] {K
} :"e" "x"
[rrr
]
545 *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x" :@
{-->
}[dd
] *+
[F
]{E
}="e"
546 :@
{-->
}[dd
] *+=(
1,
0)+
[F--
]{\mathstrut y_i
}
547 "e"
[l
] {K
} :@
{-->
}"e" "x"
[rrr
]
548 *+=(
1,
0)+
[F
]{\mathstrut x_n
}="x" :
[dd
] *+
[F
]{E
}="e"
549 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_n
}
550 "e"
[l
] {K
} :"e" "x"
[rrr
]
556 \head{Electronic Code Book (ECB),
\seq: analysis
}
558 ECB fails to disguise equality of message blocks. Hence, it is insecure in
559 the left-or-right sense.
561 Adversary $A^
{E(
\cdot,
\cdot)
}$: \+ \\
562 $y
\gets E(
0^l
\cat 1^l,
0^l
\cat 0^l)$; \\
563 \PARSE $y$
\AS $l
\colon y_0, l
\colon y_1$; \\
564 \IF $y_0 = y_1$
\THEN \RETURN $
1$; \\
567 Since $
\Xid{\mathcal{E
}}{ECB
}^E$ always encrypts blocks independently, and
568 the block cipher $E$ is deterministic, $A$ always succeeds. Hence,
569 \
[ \InSec{lor-cpa
}(
\Xid{\mathcal{E
}}{ECB
}^E; t,
1,
2 l) =
1 \
]
570 for some small $t$ describing the running-time of the adversary $A$.
572 According to our formal definitions, then, ECB mode is
\emph{completely
577 \topic{stateful counter mode
}
579 \head{Counter (CTR),
\seq: a stateful mode
}
581 We define two schemes. Firstly, a stateful-sender scheme
582 $
\Xid{\mathcal{E
}}{CTRS
}^E = (
\Xid{E
}{CTRS
}^E,
\Xid{D
}{CTRS
}^E))$. We set
583 $
\keys\Xid{\mathcal{E
}}{ECB
}^E = \
{0,
1\
}^k$, initialize $i
\gets 0$, and
586 Algorithm $
\Xid{E
}{CTRS
}^E_K(x)$: \+ \\
588 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
\quad \= \+
\kill
589 $y
\gets y
\cat (z
\xor E_K(i))$; \\
590 $i
\gets i +
1$; \- \\
593 Algorithm $
\Xid{D
}{CTRS
}^E_K(y)$: \+ \\
594 \PARSE $y$
\AS $l
\colon i, y$; \\
595 $x
\gets \emptystring$; \\
596 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
\quad \= \+
\kill
597 $x
\gets x
\cat (z
\xor E_K(i))$; \\
598 $i
\gets i +
1$; \- \\
604 \head{Counter (CTR),
\seq: diagram
}
608 []!
{0; <
1cm,
0cm>: <
0cm,
1.5cm>::
}
609 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x" :
[dd
] *
{\xor}="xor"
610 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}
611 "xor"
[l
] *+
[F
]{E
}="e"
[u
] {c
} :"e"
[d
] {K
} :"e" :"xor" "x"
[rrr
]
612 *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x" :
[dd
] *
{\xor}="xor"
613 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_1
}
614 "xor"
[l
] *+
[F
]{E
}="e"
[u
] {c+
1} :"e"
[d
] {K
} :"e" :"xor" "x"
[rrr
]
615 *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x" :@
{-->
}[dd
] *
{\xor}="xor"
616 :@
{-->
}[dd
] *+=(
1,
0)+
[F--
]{\mathstrut y_i
}
617 "xor"
[l
] *+
[F
]{E
}="e"
[u
] {c+i
} :@
{-->
}"e"
[d
] {K
} :@
{-->
}"e"
618 :@
{-->
}"xor" "x"
[rrr
]
619 *+=(
1,
0)+
[F
]{\mathstrut x_n
}="x" :
[dd
] *
{\xor}="xor"
620 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_n
}
621 "xor"
[l
] *+
[F
]{E
}="e"
[u
] {c+n
} :"e"
[d
] {K
} :"e" :"xor" "x"
[rrr
]
627 \head{Counter (CTR),
\seq: analysis of the stateful version
}
629 We write $q' = q
\mu/l$ for the total number of blocks queried by the
630 adversary, and we restrict our attention to the case $n
\le 2^l$.
632 Firstly, suppose that, rather than a block cipher, we use a completely
633 random function $R
\in \Func{l
}{l
}$. Then $E(
0)
\cat E(
1)
\cat \cdots$ is
634 a string of uniformly distributed and independent bits. Hence
635 \
[ \InSec{lor-cpa
}(
\Xid{\mathcal{E
}}{CTRS
}^
{\Func{l
}{l
}}; t, q,
\mu) =
0 \
]
636 for arbitrary $t$, and for $q
\mu/l
\le 2^l$.
638 A simple reduction shows that, for a pseudorandom function $F$, we have
639 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTRS
}^F; t, q,
\mu)
\le
640 \InSec{prf
}(F; t, q'), \
]%
641 and hence, for a pseudorandom permutation $E$,
642 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTRS
}^E; t, q,
\mu)
\le
643 \InSec{prp
}(E; t, q') +
\frac{q'(q' -
1)
}{2^
{l+
1}}. \
]%
647 Fill in the gaps in the above proof.
649 The reduction from the PRF distinguisher to the counter-with-PRF scheme
650 works as follows. Let $A$ attack $
\Xid{\mathcal{E
}}{CTRS
}^F$ in the ROR
651 sense; consider adversary $B^
{F(
\cdot)
}$: \
{ $b
\gets
652 A^
{\Xid{E
}{CTRS
}^F(
\cdot)
}$;
\RETURN $b$;~\
}. If $F(
\cdot)$ is an instance
653 of the PRF then $B$ encrypts messages chosen by $A$ faithfully; if
654 $F(
\cdot)$ is a random function then the ciphertexts $B$ returns consists
655 of a counter followed by a random string, which is therefore distributed
656 identically to a ciphertext of a
\emph{random
} plaintext. Thus, $B$
657 simulates the real-or-random game perfectly. The result for a PRP follows
658 because $
\InSec{prf
}(F; t, q)
\le \InSec{prp
}(F; t, q) + q(q -
1)
663 \topic{randomized counter mode
}
664 \head{Counter (CTR),
\seq: a randomized mode
}
666 The randomized scheme $
\Xid{\mathcal{E
}}{CTR$\$$
}^E = (
\Xid{E
}{CTR$\$$
}^E,
667 \Xid{D
}{CTR$\$$
}^E))$ differs from the stateful scheme in the encryption
668 algorithm only. We simply choose the starting value for the counter at
669 random, rather than remembering it.
671 Algorithm $
\Xid{E
}{CTR$\$$
}^E_K(x)$: \+ \\
672 $i
\getsr \
{0,
1\
}^l$; \\
674 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
\quad \= \+
\kill
675 $y
\gets y
\cat (z
\xor E_K(i))$; \\
676 $i
\gets i +
1$; \- \\
679 Algorithm $
\Xid{D
}{CTR$\$$
}^E_K(y)$: \+ \\
680 \PARSE $y$
\AS $l
\colon i, y$; \\
681 $x
\gets \emptystring$; \\
682 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
\quad \= \+
\kill
683 $x
\gets x
\cat (z
\xor E_K(i))$; \\
684 $i
\gets i +
1$; \- \\
690 \head{Counter (CTR),
\seq: analysis of the randomized version
}
692 The randomized mode remains secure so long as a counter is never repeated.
693 This occurs with probability no greater than
694 \
[ \frac{q
\mu(q -
1)
}{2^
{l+
1}}. \
]
695 Hence, we have, for a pseudorandom function $F$,
696 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTR$\$$
}^F; t, q,
\mu)
\le
697 \InSec{prf
}(F; t, q') +
\frac{q
\mu(q -
1)
}{2^
{l+
1}}, \
]%
698 and, for a pseudorandom permutation $E$,
699 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTR$\$$
}^E; t, q,
\mu)
\le
700 \InSec{prp
}(E; t, q') +
\frac{q'(q' -
1 + l(q -
1))
}{2^
{l+
1}}. \
]%
703 \begin{proof
}[Proof of the collision bound
]
704 Suppose all of the queries are maximum length. Then the probability that
705 two randomly started counter sequences overlap is $
\mu\cdot 2^
{-l
}$.
706 Hence, an upper bound on the collision probability is given by
707 \begin{eqnarray*
}[rl
]
708 \Pr[\text{no collision
}] &
\le \frac{\mu}{2^l
}(
1 +
2 +
\cdots + q -
1) \\
709 &=
\frac{\mu}{2^l
} \frac{q(q -
1)
}{2} \\
710 &=
\frac{q
\mu(q -
1)
}{2^
{l+
1}}
718 \head{Ciphertext Block Chaining (CBC),
\seq: description
}
720 We define the scheme $
\Xid{\mathcal{E
}}{CBC
}^E = (
\Xid{E
}{CBC
}^E,
721 \Xid{D
}{CBC
}^E))$ by setting $
\keys\Xid{\mathcal{E
}}{CBC
}^E = \
{0,
1\
}^k$
724 Algorithm $
\Xid{E
}{CBC
}^E_K(x)$: \+ \\
725 $i
\getsr \
{0,
1\
}^l$; \\
727 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
\quad \= \+
\kill
728 $i
\gets E_K(z
\xor i)$; \\
729 $y
\gets y
\cat i$; \- \\
732 Algorithm $
\Xid{D
}{CBC
}^E_K(y)$: \+ \\
733 \PARSE $y$
\AS $l
\colon i, y$; \\
734 $x
\gets \emptystring$; \\
735 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
\quad \= \+
\kill
736 $x
\gets x
\cat (i
\xor E_K^
{-
1}(z))$; \\
743 \head{Ciphertext Block Chaining (CBC),
\seq: diagram
}
747 []!
{0; <
1cm,
0cm>: <
0cm,
1.5cm>::
}
748 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
750 [ll
] *+=(
1,
0)+
[F
]{I
} :"xor"
751 :
[d
] *+
[F
]{E
}="e" :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
753 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
755 "i" :`r
[ru
] `u "xor" "xor"
756 :
[d
] *+
[F
]{E
}="e" :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
758 [rrruuuu
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x"
759 :@
{-->
}[d
] *
{\xor}="xor"
760 "i" :@
{-->
}`r
[ru
] `u "xor" "xor"
761 :@
{-->
}[d
] *+
[F
]{E
}="e" :@
{-->
}[dd
] *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="i"
762 "e"
[l
] {K
} :@
{-->
}"e" "i"
763 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_n
}="x"
765 "i" :@
{-->
}`r
[ru
] `u "xor" "xor"
766 :
[d
] *+
[F
]{E
}="e" :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut y_n
}="i"
773 \head{Ciphertext Block Chaining (CBC),
\seq: analysis
}
775 As before, we set $q' = q
\mu/l$ as the number of blocks queried by an
776 adversary attacking the encryption scheme.
778 As if by magic,
\footnote{%
779 The proof of this result is omitted. The interested reader is directed
780 towards
\cite{Bellare:
2000:CST
}.
} %
782 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CBC
}^E; t, q,
\mu)
\le
783 \frac{q'(q' -
1)
}{2^l
}. \
]%
787 \topic{requirement for random IVs in CBC mode
}
788 \head{Ciphertext Block Chaining (CBC),
\seq: on randomness of IVs
}
790 The initialization vector used in CBC encryption must be
\emph{a priori
}
791 unpredictable to the adversary. Suppose that $P(i)$, given an IV for a
792 ciphertext, can predict the IV which will be used with the next ciphertext
793 with probability $
\epsilon$. Then we construct this adversary, attacking
794 $
\Xid{\mathcal{E
}}{CBC
}$ in the ROR-CPA sense:
796 Adversary $A^
{E(
\cdot)
}$: \+ \\
797 $y
\gets E(
0^l)$;
\PARSE $y$
\AS $l
\colon i, z$; \\
798 $j
\gets P(y)$; $y'
\gets E(j)$;
\PARSE $y'$
\AS $l
\colon i', z'$; \\
799 \IF $i' = j
\land y = y'$
\THEN \RETURN $
1$; \\
802 The adversary succeeds when it guesses the IV correctly,
\emph{except
} when
803 the random encryption oracle happens to choose the same plaintext as we
804 wanted to encrypt anyway. So, therefore,
805 \
[ \Adv{ror-cpa
}{\Xid{\mathcal{E
}}{CBC
}^E
} \ge \epsilon -
2^
{-l
}. \
]
808 \xcalways\subsection{Chosen-ciphertext security for symmetric encryption
}\x
811 Show that CTR and CBC modes are not secure against adaptive
812 chosen-ciphertext attacks.
814 We use the FTG-CCA1 notion. For CTR mode:
\cookie{find
}:
\RETURN $(
0,
1,
815 \bot)$;
\cookie{guess
}: $y'
\gets D(y
\xor 0^L1)$;
\RETURN $y'
\xor 1$;
816 For CBC mode: same find stage, $y'
\gets D(y
\xor 1)$;
\RETURN $y'
\xor 1$;
820 \topic{integrity of ciphertexts
}
821 \head{Integrity of ciphertexts
\cite{Bellare:
2000:AER
}}
823 Informally, we say that an encryption scheme $
\mathcal{E
} = (E, D)$ has
824 \emph{integrity of ciphertexts
} (whose confusing short name is INT-CTXT) if
825 it's hard for an adversary equipped with an encryption oracle to come with
826 a new
\emph{valid
} ciphertext, i.e., one for which the decryption function
827 $D_K$ does not return the symbol $
\bot$.
829 We shall see later that integrity of ciphertexts
\emph{and
}
830 indistinguishability under chosen-plaintext attacks together imply
831 chosen-ciphertext security. This is intuitively clear, but it's worth
836 \head{Integrity of ciphertexts (cont.)
}
838 Consider the following game played by an adversary $A$:
840 Experiment $
\Expt{int-ctxt
}{\mathcal{E
}}(A)$: \+ \\
841 $K
\getsr \keys\mathcal{E
}$; $
\Xid{y
}{list
} \gets \emptyset$;
842 $y
\gets A^
{\id{encrypt
}(
\cdot), D_K(
\cdot)
}$; \\
843 \IF $y
\notin \Xid{y
}{list
} \land D_K(y)
\ne \bot$
844 \THEN \RETURN $
1$; \\
847 Oracle $
\id{encrypt
}(x)$: \+ \\
849 $
\Xid{y
}{list
} \gets \Xid{y
}{list
} \cup \
{y\
}$; \\
852 We define $A$'s success probability in this game by
853 \
[ \Succ{int-ctxt
}{\mathcal{E
}}(A) =
854 \Pr[\Expt{int-ctxt
}{\mathcal{E
}}(A) =
1] \
]%
856 \
[ \InSec{int-ctxt
}(
\mathcal{E
}; t, q_E, q_D) =
857 \max_A \Succ{int-ctxt
}{\mathcal{E
}}(A), \
]%
858 where the maximum is over all adversaries running in time $t$ and issuing
859 $q_E$ encryption and $q_D$ decryption queries.
863 \topic{INT-CTXT and LOR-CPA imply LOR-CCA
}
864 \head{INT-CTXT and LOR-CPA together imply LOR-CCA
}
866 We now prove the claim made earlier. Suppose that the adversary $A$
867 attacks $
\mathcal{E
}$ in the LOR-CCA sense. We consider these two
868 adversaries, attacking the chosen-plaintext security and ciphertext
869 integrity of $
\mathcal{E
}$ respectively.
871 Adversary $B^
{E(
\cdot,
\cdot)
}$: \+ \\
872 $b
\gets A^
{E(
\cdot,
\cdot),
\Xid{D
}{sim
}(
\cdot)
}$; \\
873 \RETURN $b$; \- \\
[\smallskipamount]
874 Oracle $
\Xid{D
}{sim
}(y)$; \+ \\
877 Adversary $C^
{E(
\cdot), D(
\cdot)
}$: \+ \\
878 $b
\getsr \
{0,
1\
}$; $y^*
\gets \bot$; \\
879 $b'
\gets A^
{E(
\id{lr
}_b(
\cdot,
\cdot)),
\Xid{D
}{sim
}(
\cdot)
}$; \\
880 \RETURN $y^*$; \- \\
[\smallskipamount]
881 Function $
\id{lr
}_b(x_0, x_1)$: \+ \\
882 \RETURN $x_b$; \- \\
[\smallskipamount]
883 Oracle $
\Xid{D
}{sim
}(y)$: \+ \\
885 \IF $x
\ne \bot$
\THEN $y^*
\gets y$; \\
891 \head{INT-CTXT and LOR-CPA together imply LOR-CCA2 (cont.)
}
893 We analyse the advantage of $B$, attacking $
\mathcal{E
}$ in the LOR-CPA
894 sense. Obviously, $B$ is lying through its teeth in its simulation of
895 $A$'s decryption oracle. If in fact all of $A$'s decryption queries were
896 for invalid ciphertexts, $B$ can't notice. So let $V$ be the event that at
897 least one of $A$'s ciphertexts was valid. Then
898 \
[ \Adv{lor-cpa
}{\mathcal{E
}}(A)
\ge
899 \Adv{lor-cca
}{\mathcal{E
}}(A) -
2\Pr[V
]. \
]%
900 To bound $
\Pr[V
]$, we consider adversary $C$, which simply records any of
901 $A$'s decryption queries which returns a valid ciphertext. Since $A$ is
902 forbidden from passing any ciphertexts obtained from its encryption oracle
903 to its decryption oracle, $C$'s returned ciphertext $y^*$ is not one it
904 obtained from
\emph{its
} encryption oracle. So
905 \
[ \Succ{int-ctxt
}{\mathcal{E
}}(A) =
\Pr[V
]. \
]
907 \
[ \InSec{lor-cca
}(
\mathcal{E
}; t, q_E, q_D)
\le
908 \InSec{lor-cpa
}(
\mathcal{E
}; t, q_E) +
909 2 \cdot \InSec{int-ctxt
}(
\mathcal{E
}; t, q_E, q_D). \
]%
913 \topic{strong MACs provide INT-CTXT
}
914 \head{A strong MAC provides integrity of ciphertexts
}
916 That's a very nice result, but how do we achieve INT-CTXT? Well, the
917 game in the definition looks very much like the forgery games we played
918 when we were thinking about MACs.
920 Suppose that $
\mathcal{E
} = (E, D)$ is an encryption scheme secure in the
921 LOR-CPA sense, and $
\mathcal{M
} = (T, V)$ is a strong MAC (in the SUF-CMA
922 sense). Then we can define $
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{M
}} =
923 (
\Xid{E
}{auth
}^
{\mathcal{E
},
\mathcal{M
}},
\Xid{D
}{auth
}^
{\mathcal{E
},
925 \
[ \keys\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}} =
926 \keys\mathcal{E
} \times \keys\mathcal{M
} \
]%
930 $
\Xid{E
}{auth
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(x)$: \+ \\
931 $y
\gets E_
{K_E
}(x)$; \\
932 $
\tau \gets T_
{K_T
}(y)$; \\
933 \RETURN $
\tau \cat y$;
936 $
\Xid{D
}{auth
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(y')$: \+ \\
937 \PARSE $y'$
\AS $
\tau, y$; \\
938 \IF $V_
{K_T
}(y,
\tau) =
0$
\THEN \RETURN $
\bot$; \\
939 \ELSE \RETURN $D_
{K_E
}(y)$;
944 \head{A strong MAC provides integrity of ciphertexts (cont.)
}
946 The security proof for $
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}}$
947 is left as a trivial exercise. We end up with the result that
948 \
[ \InSec{int-ctxt
}(
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}};
950 \InSec{suf-cma
}(
\mathcal{M
}; t, q_E, q_D) \
]%
952 \begin{eqnarray*
}[Ll
]
953 \InSec{lor-cca
}(
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}};
955 &
\le \InSec{lor-cpa
}(
\mathcal{E
}; t, q_E) +
956 2 \cdot \InSec{suf-cma
}(
\mathcal{M
}; t, q_E, q_D).
958 A MAC, therefore, can help us to attain a strong notion of secrecy, even if
959 no actual integrity appears to be required. This is an important lesson.
963 Prove the above result.
965 Let $A$ attack INT-CTXT. Construct adversary $B^
{T(
\cdot), V(
\cdot)
}$: \
{
966 $K
\getsr \keys\mathcal{E
}$; $(y,
\tau)
\gets A^
{\id{encrypt
}(
\cdot),
967 \id{decrypt
}(
\cdot)
}$;
\RETURN $(y,
\tau)$;~\
} Oracle $
\id{encrypt
}(x)$:
968 \
{ $y
\gets E_K(x)$; $
\tau \gets T(y)$;
\RETURN $(y,
\tau)$;~\
} Oracle
969 $
\id{decrypt
}(y,
\tau)$: \
{ \IF $V(y,
\tau) =
1$
\THEN \RETURN $D_K(y)$;
970 \ELSE \RETURN $
\bot$;~\
}. The simulation of the INT-CTXT game is perfect.
974 \topic{mixing encryption and MACs
}
975 \head{Notes on mixing encryption and MACs
}
977 To construct $
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}}$, we
978 applied a MAC to the
\emph{ciphertext
}. This isn't perhaps the most
979 intuitive way to combine an encryption scheme with a MAC.
981 There are three constructions which look plausible.
983 \item[Encrypt-then-MAC:
]
985 $y
\gets E_
{K_E
}(x)$; $
\tau \gets T_
{K_T
}(y)$;
\RETURN $
\tau \cat y$;
987 Encrypt the plaintext, and MAC the ciphertext; used in IPsec and nCipher
988 Impath; we've proven its generic security, using the notion of integrity
991 \item[MAC-then-encrypt:
]
993 $
\tau \gets T_
{K_T
}(x)$; $y
\gets E_
{K_E
}(
\tau \cat x)$;
\RETURN $y$;
995 MAC the plaintext, and encrypt both the plaintext and tag; used in SSL
996 and TLS; not
\emph{generically
} secure against chosen-ciphertext attacks.
998 \item[Encrypt-and-MAC:
]
1000 $y
\gets E_
{K_E
}(x)$; $
\tau \gets T_
{K_T
}(x)$;
\RETURN $
\tau \cat y$;
1002 Separately MAC and encrypt the plaintext; used in SSH;
\emph{never
}
1003 secure against chosen-ciphertext, not generically secure against
1009 We begin with a few words on our approach, before we embark on the proof
1012 To demonstrate the generic insecurity of a scheme, we assume the existence
1013 of an encryption scheme and MAC (since if they don't exist, the result is
1014 vacuously true) and construct modified schemes whose individual security
1015 relates tightly to the originals, but the combined scheme is weak.
1017 We demonstrate
\emph{universal
} insecurity by showing an attack which works
1018 given
\emph{any
} component encryption and MAC schemes.
1020 We prove security relationships using the LOR-CPA notion because this is
1021 strongest, and bounds for other notions can be derived readily from the
1022 left-or-right analysis. We prove insecurity using the FTG-CCA1 or FTG-CPA
1023 notions, because they are weakest and show the strength of our results
1026 We've dealt with the generic security of encrypt-then-MAC already. We turn
1027 our attention first first to the generic insecurity of the MAC-then-encrypt
1030 Let $
\mathcal{E
} = (E, D)$ be a symmetric encryption scheme, and let
1031 $
\mathcal{M
} = (T, V)$ be a MAC. We define the MAC-then-encrypt scheme
1032 $
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
},
\mathcal{M
}} =
1033 (
\Xid{E
}{MtE
}^
{\mathcal{E
},
\mathcal{M
}},
\Xid{D
}{MtE
}^
{\mathcal{E
},
1034 \mathcal{M
}})$ as follows:
1035 \
[ \keys\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
},
\mathcal{M
}} =
1036 \keys\mathcal{E
} \times \keys\mathcal{M
} \
]%
1040 $
\Xid{E
}{MtE
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(x)$: \+ \\
1041 $
\tau \gets T_
{K_T
}(x)$; \\
1042 $
\RETURN E_
{K_E
}(
\tau \cat x)$;
1045 $
\Xid{D
}{MtE
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(y)$: \+ \\
1046 $x'
\gets D_
{K_E
}(y)$; \\
1047 \PARSE $x'$
\AS $
\tau, x$; \\
1048 \IF $V_
{K_T
}(x,
\tau) =
0$
\THEN \RETURN $
\bot$; \\
1051 We construct a new encryption scheme $
\mathcal{E
}' = (E', D')$ in terms of
1052 $
\mathcal{E
}$, such that the combined scheme
1053 $
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
}',
\mathcal{M
}}$ is insecure in the
1054 FTG-CCA1 sense. Our modified encryption scheme has $
\keys\mathcal{E
}' =
1055 \keys\mathcal{E
}$, and works as follows:
1057 Algorithm $E'_K(x)$: \+ \\
1058 \RETURN $
0 \cat E_K(x)$;
1060 Algorithm $D'_K(y')$: \+ \\
1061 \PARSE $y'$
\AS $
1\colon b, y$; \\
1064 That is, the encryption scheme prepends a single bit to the ciphertext, and
1065 doesn't check its value during decryption. Intuitively, this makes the
1066 scheme malleable: we can change the ciphertext by flipping the first bit,
1067 but the MAC tag remains valid because the plaintext is unaffected.
1069 Firstly, we prove that $
\mathcal{E
}'$ is LOR-CPA if $
\mathcal{E
}$ is.
1070 Suppose $A'$ attacks $
\mathcal{E
}'$ in the LOR-CPA sense: then
1072 Adversary $A^
{E(
\cdot,
\cdot)
}$: \+ \\
1073 \RETURN $A'^
{0 \cat E(
\cdot,
\cdot)
}$;
1075 has the same advantage.
1077 Secondly, we show that the combined MAC-then-encrypt scheme
1078 $
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
}',
\mathcal{M
}}$ is insecure in the
1079 FTG-CCA1 sense. Consider this adversary:
1081 Adversary $B^
{E(
\cdot)
}(
\cookie{find
})$: \+ \\
1082 \RETURN $(
0,
1,
\bot)$;
1084 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{guess
}, y', s)$: \+ \\
1085 \PARSE $y'$
\AS $
1\colon b, y$; \\
1086 \RETURN $D(
1 \cat y)$;
1088 The ciphertext $
1 \cat y$ was never returned by the encryption oracle
1089 (because it always returns the first bit zero); but the plaintext of $
1
1090 \cat y$ is the challenge plaintext. Hence, $B$ wins always, and
1091 \
[ \InSec{ftg-cca1
}(
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
}',
\mathcal{M
}};
1093 where $t$ is the running time of the adversary $B$ above.
1095 We now address the separate encrypt-and-MAC scheme, which we define
1096 formally. Let $
\mathcal{E
} = (E, D)$ be a symmetric encryption scheme, and
1097 let $
\mathcal{M
} = (T, V)$ be a MAC. Then the the encrypt-and-MAC scheme
1098 $
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}} =
1099 (
\Xid{E
}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}},
\Xid{D
}{E\&M
}^
{\mathcal{E
},
1100 \mathcal{M
}})$ is defined by:
1101 \
[ \keys\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}} =
1102 \keys\mathcal{E
} \times \keys\mathcal{M
} \
]%
1106 $
\Xid{E
}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(x)$: \+ \\
1107 $y
\gets E_
{K_E
}(x)$; \\
1108 $
\tau \gets T_
{K_T
}(x)$; \\
1109 $
\RETURN \tau \cat y$;
1112 $
\Xid{D
}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(y')$: \+ \\
1113 \PARSE $y'$
\AS $
\tau, y$; \\
1114 $x
\gets D_
{K_E
}(y)$; \\
1115 \IF $V_
{K_T
}(x,
\tau) =
0$
\THEN \RETURN $
\bot$; \\
1119 We first show that this scheme is
\emph{universally
} insecure against
1120 chosen-ciphertext attack. Let $
\mathcal{E
}$ and $
\mathcal{M
}$ be an
1121 arbitrary symmetric encryption scheme and MAC, respectively. The attack
1122 works because the MACs can be detached and used in chosen-ciphertext
1123 queries to test for equality of messages.
1125 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
1126 \RETURN $(
0,
1,
\bot)$;
1128 Adversary $B^
{E(
\cdot), D(
\cdot)
}$(
\cookie{guess
}, y', s): \+ \\
1129 $y_1'
\gets E(
1)$; \\
1130 \PARSE $y'$
\AS $
\tau, y$; \\
1131 \PARSE $y_1'$
\AS $
\tau_1, y_1$; \\
1132 \IF $
\tau =
\tau_1 \lor D(
\tau \cat y_1)
\ne \bot$
1133 \THEN \RETURN $
1$; \\
1136 After receiving the challenge ciphertext, the adversary requests an
1137 additional encryption of the plaintext $
1$. If the tags are equal on the
1138 two ciphertexts then we announce that the hidden bit is $
1$. Otherwise, we
1139 attempt a decryption of the new ciphertext, using the tag from the
1140 challenge. If it decrypts successfully, we announce that the bit is $
1$;
1141 otherwise we claim it is zero.
1143 Certainly, this strategy is always correct when the hidden bit is indeed
1144 $
1$. However, there is a possibility that the MACs are equal or verify
1145 correctly even when the hidden bit is $
0$. To bound this probability, we
1146 construct the following simple adversary against the MAC:
1148 Adversary $B'^
{T(
\cdot), V(
\cdot)
}$: \+ \\
1149 $
\tau \gets T(
1)$; \\
1150 \RETURN $(
0,
\tau)$;
1153 \
[ \InSec{ftg-cca1
}(
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}};
1155 1 -
\InSec{suf-cma
}(
\mathcal{M
}; t',
1,
0), \
]%
1156 where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
1159 Finally, we show that the encrypt-and-MAC scheme is generically insecure
1160 against chosen-plaintext attacks only. There are two strategies we could
1161 use. Since both offer useful insights into the properties of MACs, we
1165 \item \emph{Deterministic MACs.
} In the proof of the universal weakness of
1166 the encrypt-and-MAC scheme, we used the check on the MAC to decide on the
1167 equality of two plaintexts given the ciphertexts. If the MAC is
1168 deterministic (e.g., a PRF) then we don't need a decryption query.
1170 Let $
\mathcal{E
} = (E, D)$ be a symmetric cipher, and let $
\mathcal{M
} =
1171 (T, V)$ be a deterministic MAC, e.g., a PRF, or HMAC. Then consider this
1174 Adversary $B^
{E(
\cdot)
}(
\cookie{find
})$: \+ \\
1175 \RETURN $(
0,
1,
\bot)$;
1177 Adversary $B^
{E(
\cdot)
}(
\cookie{guess
}, y', s)$: \+ \\
1178 $y_1'
\gets E(
1)$; \\
1179 \PARSE $y'$
\AS $
\tau, y$; \\
1180 \PARSE $y_1'$
\AS $
\tau_1, y_1$; \\
1181 \IF $
\tau =
\tau_1$
\THEN \RETURN $
1$; \\
1184 Since the MAC is deterministic, the tag attached to a ciphertext $
1$ is
1185 always the same. We bound the probability that $T_K(
0) = T_K(
1)$ using
1186 the adversary $B'$ above, and conclude that
1187 \
[ \InSec{ftg-cpa
}(
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}};
1189 1 -
\InSec{suf-cma
}(
\mathcal{M
}; t',
1,
0), \
]%
1190 where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
1193 \item \emph{Leaky MACs.
} A MAC doesn't have to conceal information about
1194 messages. Suppose $
\mathcal{M
} = (T, V)$ is a secure MAC. We define the
1195 leaky MAC $
\mathcal{M
}' = (T', V')$ by stating that $
\keys\mathcal{M
}' =
1196 \keys\mathcal{M
}''$ and
1198 Algorithm $T'_K(x)$: \+ \\
1199 \PARSE $x$
\AS $
1\colon x_0, z$; \\
1200 \RETURN $x_0
\cat T_K(x)$;
1202 Algorithm $V'_K(x,
\tau')$: \+ \\
1203 \PARSE $
\tau'$
\AS $
1\colon \tau_0,
\tau$; \\
1204 \PARSE $x$
\AS $
1\colon x_0, z$; \\
1205 \IF $x_0
\ne \tau_0$
\THEN \RETURN $
0$; \\
1206 \ELSE \RETURN $V_K(x,
\tau)$;
1208 We must first prove that $
\mathcal{M
}'$ remains secure. To do this,
1209 consider an adversary $A'$ attacking $
\mathcal{M
}'$. We construct $A$
1210 attacking $
\mathcal{M
}$ in the obvious way:
1212 Algorithm $A^
{T(
\cdot), V(
\cdot)
}$: \\
1214 A'^
{\Xid{T'
}{sim
}(
\cdot),
\Xid{V'
}{sim
}(
\cdot)
}$; \\
1215 \PARSE $
\tau'$
\AS $
1\colon \tau_0,
\tau$; \\
1216 \RETURN $(x,
\tau)$;
1218 Oracle $
\Xid{T'
}{sim
}(x)$: \+ \\
1219 \PARSE $x$
\AS $
1\colon x_0, z'$; \\
1220 \RETURN $x_0
\cat T(x)$; \- \\
[\smallskipamount]
1221 Oracle $
\Xid{V'
}{sim
}(x,
\tau')$: \+ \\
1222 \PARSE $
\tau'$
\AS $
1\colon \tau_0,
\tau$; \\
1223 \PARSE $x$
\AS $
1\colon x_0, z$; \\
1224 \IF $x_0
\ne \tau_0$
\THEN \RETURN $
0$; \\
1225 \ELSE \RETURN $V(x,
\tau)$;
1227 Here, $A$ simply simulates the environment expected by $A'$. It is clear
1228 that $A$ succeeds whenever $A'$ returns a valid tag for a
\emph{new
}
1229 message. However, suppose that $A'$ returns a new tag $
\tau'$ for some
1230 old message $x$, for which the tag $
\tau$ was returned by the tagging
1231 oracle. Let $x_0$, $
\tau_0$ and $
\tau'_0$ be the first bits of $x$,
1232 $
\tau$ and $
\tau'$ respectively, and let $
\tau^*$ be the remaining bits
1233 of $
\tau'$. If the pair $(x,
\tau')$ is to be a valid
1234 $
\mathcal{M
}'$-forgery, we must have $x_0 =
\tau_0 =
\tau'_0$. Hence,
1235 $
\tau$ and $
\tau'$ must differ in at least one other bit, and $(x,
1236 \tau^*)$ is a valid $
\mathcal{M
}$-forgery. We conclude that
1237 \
[ \InSec{suf-cma
}(
\mathcal{M
}'; t, q_T, q_V)
\le
1238 \InSec{suf-cma
}(
\mathcal{M
}; t, q_T, q_V) \
]%
1241 Now we show that the combined encrypt-and-MAC scheme is weak in the
1242 FTG-CPA sense. Consider this adversary attacking the scheme:
1244 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
1245 \RETURN $(
0,
1,
\bot)$;
1247 Adversary $B^
{E(
\cdot), D(
\cdot)
}$(
\cookie{guess
}, y', s): \+ \\
1248 \PARSE $y'$
\AS $
\tau, y$; \\
1249 \PARSE $
\tau$
\AS $
1\colon b,
\tau^*$; \\
1252 The leaky MAC simply tells us the right answer. So
1253 \
[ \InSec{ftg-cpa
}(
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}'
};
1255 where $t$ is the running time of adversary $B$ above.
1259 This concludes the proof.
1262 %% TO DO: Include stuff about integrity-aware encryption modes some day.
1266 %%% Local Variables:
1268 %%% TeX-master: "ips"