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 decscribe 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 contruct 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), \
]%
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$. In game~$
\G2$, rather than using $F_K$ to compute the seeds~$s$, we
425 just choose $s
\in \
{0,
1\
}^l$ at random each time. Note that the
426 $i$-values are distinct; hence considering an adversary attacking $F$ as a
427 PRF, which simulates either $
\G1$ or $
\G2$ depending on whether its oracle
428 is an instance of~$F$ or a random function respectively, shows that
429 $|
{\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$. Multiplying through by~
2 and rearranging yields the required
445 We finally turn to the claim made earlier. In $
\G2$, we use the PRG; in
446 $
\G3$ we don't. We construct a number of hybrid games~$
\H{i
}$ for $
0 \le i
447 \le q$ in which encryption query~$j$ (for $
0 \le j < q$) is handled as
448 follows: if $
0 \le j < i$ then the query is handled as in $
\G3$; if $i
\le
449 j < q$ then the query is handed as in $
\G2$. Let $T_i$ be the event that
450 the adversary wins in game $
\H{i
}$. Clearly, $
\H0 \equiv \G2$, and $
\H{q
}
451 \equiv \G3$. For each adjacent pair of hybrid games $
\H{i
},
\H{i+
1}$ (for
452 $
0 \le i < q$), we can bound $|
{\Pr[T_
{i+
1}} -
\Pr[T_i
]|$ by considering an
453 adversary attacking~$g^
{(n)
}$ by running~$A$ and using its input as the XOR
454 mask~$p$ for query~$i$, and following the rules of game~$
\H{i
}$ for the
455 other queries: then if $y$~is random, it simulates $
\H{i+
1}$, whereas if
456 $y$ is the output of $g^
{(n)
}$ then it simulates $
\H{i
}$. Thus
457 $|
{\Pr[T_
{i+
1}} -
\Pr[T_i
]|
\le \mu \cdot \InSec{prg
}(g; t)$ (by the answer
458 to
\ref{ex:dbl-prg
}), and $|
{\Pr[S_3
]} -
\Pr[S_2
]| = |
{\Pr[T_
{q-
1}]} -
459 \Pr[T_0
]|
\le q
\mu \cdot \InSec{prg
}(g; t)$ as claimed.
462 \xcalways\subsection{Block cipher modes
}\x
465 \head{Block cipher modes
}
467 Block ciphers (which we model as PRPs) are readily available components,
468 and we have good tools for analysing their (heuristic) security. It'd be
469 good if we could use them to construct secure encryption schemes.
471 We analyse three standard
\emph{modes of operation
}:
473 \item[Electronic Code Book (ECB)
] Each plaintext block is encrypted
474 independently of the others, using the block cipher.
475 \item[Counter (CTR)
] Choose a random starting point $i$. The plaintext
476 blocks are XORed with the result of encrypting the counter values $i$,
478 \item[Ciphertext Block Chaining (CBC)
] The first plaintext block is XORed
479 with a random
\emph{initialization vector
} and encrypted using the block
480 cipher; thereafter, each plaintext block are XORed with the previous
481 ciphertext block and then encrypted with the block cipher.
486 \head{General notation
}
488 We consider pseudorandom permutations $E
\colon \
{0,
1\
}^k
\times \
{0,
1\
}^l
489 \to \
{0,
1\
}^l$ operating on $l$-bit blocks. We write $E_K(
\cdot)$ rather
492 For the sake of simplicity, we assume that plaintexts are a multiple of $l$
493 bits in length. We shall consider chosen-plaintext attacks, and we shall
494 be quantifying our results in terms of:
496 \item the running time $t$ of adversaries;
497 \item the number $q$ of queries made to the encryption oracle; and
498 \item the maximum size in bits $
\mu$ of any individual encryption query.
501 We shall write `
\FOREACH $l
\colon z$
\FROM $x$
\DO \ldots' to denote
502 iteration over each $l$-bit block $z$ of $x$ in turn.
504 We use $
\emptystring$ to denote the empty string.
509 \head{Electronic Code Book (ECB),
1: description
}
511 We define the scheme $
\Xid{\mathcal{E
}}{ECB
}^E = (
\Xid{E
}{ECB
}^E,
512 \Xid{D
}{ECB
}^E))$ by setting $
\keys\Xid{\mathcal{E
}}{ECB
}^E = \
{0,
1\
}^k$
515 Algorithm $
\Xid{E
}{ECB
}^E_K(x)$: \+ \\
516 $y
\gets \emptystring$; \\
517 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
518 \quad $y
\gets y
\cat E_K(z)$; \\
521 Algorithm $
\Xid{D
}{ECB
}^E_K(y)$: \+ \\
522 $x
\gets \emptystring$; \\
523 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
524 \quad $x
\gets x
\cat E_K^
{-
1}(z)$; \\
530 \head{Electronic Code Book (ECB),
2: analysis
}
532 ECB fails to disguise equality of message blocks. Hence, it is insecure in
533 the left-or-right sense.
535 Adversary $A^
{E(
\cdot,
\cdot)
}$: \+ \\
536 $y
\gets E(
0^l
\cat 1^l,
0^l
\cat 0^l)$; \\
537 \PARSE $y$
\AS $l
\colon y_0, l
\colon y_1$; \\
538 \IF $y_0 = y_1$
\THEN \RETURN $
1$; \\
541 Since $
\Xid{\mathcal{E
}}{ECB
}^E$ always encrypts blocks independently, and
542 the block cipher $E$ is deterministic, $A$ always succeeds. Hence,
543 \
[ \InSec{lor-cpa
}(
\Xid{\mathcal{E
}}{ECB
}^E; t,
1,
2 l) =
1 \
]
544 for some small $t$ describing the running-time of the adversary $A$.
546 According to our formal definitions, then, ECB mode is
\emph{completely
551 \topic{stateful counter mode
}
552 \head{Counter (CTR),
1: a stateful mode
}
554 We define two schemes. Firstly, a stateful-sender scheme
555 $
\Xid{\mathcal{E
}}{CTRS
}^E = (
\Xid{E
}{CTRS
}^E,
\Xid{D
}{CTRS
}^E))$. We set
556 $
\keys\Xid{\mathcal{E
}}{ECB
}^E = \
{0,
1\
}^k$, initialize $i
\gets 0$, and
559 Algorithm $
\Xid{E
}{CTRS
}^E_K(x)$: \+ \\
561 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
\quad \= \+
\kill
562 $y
\gets y
\cat (z
\xor E_K(i))$; \\
563 $i
\gets i +
1$; \- \\
566 Algorithm $
\Xid{D
}{CTRS
}^E_K(y)$: \+ \\
567 \PARSE $y$
\AS $l
\colon i, y$; \\
568 $x
\gets \emptystring$; \\
569 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
\quad \= \+
\kill
570 $x
\gets x
\cat (z
\xor E_K(i))$; \\
571 $i
\gets i +
1$; \- \\
577 \head{Counter (CTR),
2: analysis of the stateful version
}
579 We write $q' = q
\mu/l$ for the total number of blocks queried by the
580 adversary, and we restrict our attention to the case $n
\le 2^l$.
582 Firstly, suppose that, rather than a block cipher, we use a completely
583 random function $R
\in \Func{l
}{l
}$. Then $E(
0)
\cat E(
1)
\cat \cdots$ is
584 a string of uniformly distributed and independent bits. Hence
585 \
[ \InSec{lor-cpa
}(
\Xid{\mathcal{E
}}{CTRS
}^
{\Func{l
}{l
}}; t, q,
\mu) =
0 \
]
586 for arbitrary $t$, and for $q
\mu/l
\le 2^l$.
588 A simple reduction shows that, for a pseudorandom function $F$, we have
589 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTRS
}^F; t, q,
\mu)
\le
590 \InSec{prf
}(F; t, q'), \
]%
591 and hence, for a pseudorandom permutation $E$,
592 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTRS
}^E; t, q,
\mu)
\le
593 \InSec{prp
}(E; t, q') +
\frac{q'(q' -
1)
}{2^
{l+
1}}. \
]%
597 Fill in the gaps in the above proof.
599 The reduction from the PRF distinguisher to the counter-with-PRF scheme
600 works as follows. Let $A$ attack $
\Xid{\mathcal{E
}}{CTRS
}^F$ in the ROR
601 sense; consider adversary $B^
{F(
\cdot)
}$: \
{ $b
\gets
602 A^
{\Xid{E
}{CTRS
}^F(
\cdot)
}$;
\RETURN $b$;~\
}. If $F(
\cdot)$ is an instance
603 of the PRF then $B$ encrypts messages chosen by $A$ faithfully; if
604 $F(
\cdot)$ is a random function then the ciphertexts $B$ returns consists
605 of a counter followed by a random string, which is therefore distributed
606 identically to a ciphertext of a
\emph{random
} plaintext. Thus, $B$
607 simulates the real-or-random game perfectly. The result for a PRP follows
608 because $
\InSec{prf
}(F; t, q)
\le \InSec{prp
}(F; t, q) + q(q -
1)
613 \topic{randomized counter mode
}
614 \head{Counter (CTR),
3: a randomized mode
}
616 The randomized scheme $
\Xid{\mathcal{E
}}{CTR$\$$
}^E = (
\Xid{E
}{CTR$\$$
}^E,
617 \Xid{D
}{CTR$\$$
}^E))$ differs from the stateful scheme in the encryption
618 algorithm only. We simply choose the starting value for the counter at
619 random, rather than remembering it.
621 Algorithm $
\Xid{E
}{CTR$\$$
}^E_K(x)$: \+ \\
622 $i
\getsr \
{0,
1\
}^l$; \\
624 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
\quad \= \+
\kill
625 $y
\gets y
\cat (z
\xor E_K(i))$; \\
626 $i
\gets i +
1$; \- \\
629 Algorithm $
\Xid{D
}{CTR$\$$
}^E_K(y)$: \+ \\
630 \PARSE $y$
\AS $l
\colon i, y$; \\
631 $x
\gets \emptystring$; \\
632 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
\quad \= \+
\kill
633 $x
\gets x
\cat (z
\xor E_K(i))$; \\
634 $i
\gets i +
1$; \- \\
640 \head{Counter (CTR),
4: analysis of the randomized version
}
642 The randomized mode remains secure so long as a counter is never repeated.
643 This occurs with probability no greater than
644 \
[ \frac{q
\mu(q -
1)
}{2^
{l+
1}}. \
]
645 Hence, we have, for a pseudorandom function $F$,
646 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTR$\$$
}^F; t, q,
\mu)
\le
647 \InSec{prf
}(F; t, q') +
\frac{q
\mu(q -
1)
}{2^
{l+
1}}, \
]%
648 and, for a pseudorandom permutation $E$,
649 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CTR$\$$
}^E; t, q,
\mu)
\le
650 \InSec{prp
}(E; t, q') +
\frac{q'(q' -
1 + l(q -
1))
}{2^
{l+
1}}. \
]%
653 \begin{proof
}[Proof of the collision bound
]
654 Suppose all of the queries are maximum length. Then the probability that
655 two randomly started counter sequences overlap is $
\mu\cdot 2^
{-l
}$.
656 Hence, an upper bound on the collision probability is given by
657 \begin{eqnarray*
}[rl
]
658 \Pr[\text{no collision
}] &
\le \frac{\mu}{2^l
}(
1 +
2 +
\cdots + q -
1) \\
659 &=
\frac{\mu}{2^l
} \frac{q(q -
1)
}{2} \\
660 &=
\frac{q
\mu(q -
1)
}{2^
{l+
1}}
667 \head{Ciphertext Block Chaining (CBC),
1: description
}
669 We define the scheme $
\Xid{\mathcal{E
}}{CBC
}^E = (
\Xid{E
}{CBC
}^E,
670 \Xid{D
}{CBC
}^E))$ by setting $
\keys\Xid{\mathcal{E
}}{CBC
}^E = \
{0,
1\
}^k$
673 Algorithm $
\Xid{E
}{CBC
}^E_K(x)$: \+ \\
674 $i
\getsr \
{0,
1\
}^l$; \\
676 \FOREACH $l
\colon z$
\FROM $x$
\DO \\
\quad \= \+
\kill
677 $i
\gets E_K(z
\xor i)$; \\
678 $y
\gets y
\cat i$; \- \\
681 Algorithm $
\Xid{D
}{CBC
}^E_K(y)$: \+ \\
682 \PARSE $y$
\AS $l
\colon i, y$; \\
683 $x
\gets \emptystring$; \\
684 \FOREACH $l
\colon z$
\FROM $y$
\DO \\
\quad \= \+
\kill
685 $x
\gets x
\cat (i
\xor E_K^
{-
1}(z))$; \\
692 \head{Ciphertext Block Chaining (CBC),
2: analysis
}
694 As before, we set $q' = q
\mu/l$ as the number of blocks queried by an
695 adversary attacking the encryption scheme.
697 As if by magic,
\footnote{%
698 The proof of this result is omitted. The interested reader is directed
699 towards
\cite{Bellare:
2000:CST
}.
} %
701 \
[ \InSec{ror-cpa
}(
\Xid{\mathcal{E
}}{CBC
}^E; t, q,
\mu)
\le
702 \frac{q'(q' -
1)
}{2^l
}. \
]%
706 \topic{requirement for random IVs in CBC mode
}
707 \head{Ciphertext Block Chaining (CBC),
3: on randomness of IVs
}
709 The initialization vector used in CBC encryption must be
\emph{a priori
}
710 unpredictable to the adversary. Suppose that $P(i)$, given an IV for a
711 ciphertext, can predict the IV which will be used with the next ciphertext
712 with probability $
\epsilon$. Then we construct this adversary, attacking
713 $
\Xid{\mathcal{E
}}{CBC
}$ in the ROR-CPA sense:
715 Adversary $A^
{E(
\cdot)
}$: \+ \\
716 $y
\gets E(
0^l)$;
\PARSE $y$
\AS $l
\colon i, z$; \\
717 $j
\gets P(y)$; $y'
\gets E(j)$;
\PARSE $y'$
\AS $l
\colon i', z'$; \\
718 \IF $i' = j
\land y = y'$
\THEN \RETURN $
1$; \\
721 The adversary succeeds when it guesses the IV correctly,
\emph{except
} when
722 the random encryption oracle happens to choose the same plaintext as we
723 wanted to encrypt anyway. So, therefore,
724 \
[ \Adv{ror-cpa
}{\Xid{\mathcal{E
}}{CBC
}^E
} \ge \epsilon -
2^
{-l
}. \
]
727 \xcalways\subsection{Chosen-ciphertext security for symmetric encryption
}\x
730 Show that CTR and CBC modes are not secure against adaptive
731 chosen-ciphertext attacks.
733 We use the FTG-CCA2 notion. For CTR mode:
\cookie{find
}:
\RETURN $(
0,
1,
734 \bot)$;
\cookie{guess
}: $y'
\gets D(y
\xor 0^L1)$;
\RETURN $y'
\xor 1$;
735 For CBC mode: same find stage, $y'
\gets D(y
\xor 1)$;
\RETURN $y'
\xor 1$;
739 \topic{integrity of ciphertexts
}
740 \head{Integrity of ciphertexts
\cite{Bellare:
2000:AER
}}
742 Informally, we say that an encryption scheme $
\mathcal{E
} = (E, D)$ has
743 \emph{integrity of ciphertexts
} (whose confusing short name is INT-CTXT) if
744 it's hard for an adversary equipped with an encryption oracle to come with
745 a new
\emph{valid
} ciphertext, i.e., one for which the decryption function
746 $D_K$ does not return the symbol $
\bot$.
748 We shall see later that integrity of ciphertexts
\emph{and
}
749 indistinguishability under chosen-plaintext attacks together imply
750 chosen-ciphertext security. This is intuitively clear, but it's worth
755 \head{Integrity of ciphertexts (cont.)
}
757 Consider the following game played by an adversary $A$:
759 Experiment $
\Expt{int-ctxt
}{\mathcal{E
}}(A)$: \+ \\
760 $K
\getsr \keys\mathcal{E
}$; $
\Xid{y
}{list
} \gets \emptyset$;
761 $y
\gets A^
{\id{encrypt
}(
\cdot), D_K(
\cdot)
}$; \\
762 \IF $y
\notin \Xid{y
}{list
} \land D_K(y)
\ne \bot$
763 \THEN \RETURN $
1$; \\
766 Oracle $
\id{encrypt
}(x)$: \+ \\
768 $
\Xid{y
}{list
} \gets \Xid{y
}{list
} \cup \
{y\
}$; \\
771 We define $A$'s success probability in this game by
772 \
[ \Succ{int-ctxt
}{\mathcal{E
}}(A) =
773 \Pr[\Expt{int-ctxt
}{\mathcal{E
}}(A) =
1] \
]%
775 \
[ \InSec{int-ctxt
}(
\mathcal{E
}; t, q_E, q_D) =
776 \max_A \Succ{int-ctxt
}{\mathcal{E
}}(A), \
]%
777 where the maximum is over all adversaries running in time $t$ and issuing
778 $q_E$ encryption and $q_D$ decryption queries.
782 \topic{INT-CTXT and LOR-CPA imply LOR-CCA
}
783 \head{INT-CTXT and LOR-CPA together imply LOR-CCA
}
785 We now prove the claim made earlier. Suppose that the adversary $A$
786 attacks $
\mathcal{E
}$ in the LOR-CCA sense. We consider these two
787 adversaries, attacking the chosen-plaintext security and ciphertext
788 integrity of $
\mathcal{E
}$ respectively.
790 Adversary $B^
{E(
\cdot,
\cdot)
}$: \+ \\
791 $b
\gets A^
{E(
\cdot,
\cdot),
\Xid{D
}{sim
}(
\cdot)
}$; \\
792 \RETURN $b$; \- \\
[\smallskipamount]
793 Oracle $
\Xid{D
}{sim
}(y)$; \+ \\
796 Adversary $C^
{E(
\cdot), D(
\cdot)
}$: \+ \\
797 $b
\getsr \
{0,
1\
}$; $y^*
\gets \bot$; \\
798 $b'
\gets A^
{E(
\id{lr
}_b(
\cdot,
\cdot)),
\Xid{D
}{sim
}(
\cdot)
}$; \\
799 \RETURN $y^*$; \- \\
[\smallskipamount]
800 Function $
\id{lr
}_b(x_0, x_1)$: \+ \\
801 \RETURN $x_b$; \- \\
[\smallskipamount]
802 Oracle $
\Xid{D
}{sim
}(y)$: \+ \\
804 \IF $x
\ne \bot$
\THEN $y^*
\gets y$; \\
810 \head{INT-CTXT and LOR-CPA together imply LOR-CCA2 (cont.)
}
812 We analyse the advantage of $B$, attacking $
\mathcal{E
}$ in the LOR-CPA
813 sense. Obviously, $B$ is lying through its teeth in its simulation of
814 $A$'s decryption oracle. If in fact all of $A$'s decryption queries were
815 for invalid ciphertexts, $B$ can't notice. So let $V$ be the event that at
816 least one of $A$'s ciphertexts was valid. Then
817 \
[ \Adv{lor-cpa
}{\mathcal{E
}}(A)
\ge
818 \Adv{lor-cca
}{\mathcal{E
}}(A) -
2\Pr[V
]. \
]%
819 To bound $
\Pr[V
]$, we consider adversary $C$, which simply records any of
820 $A$'s decryption queries which returns a valid ciphertext. Since $A$ is
821 forbidden from passing any ciphertexts obtained from its encryption oracle
822 to its decryption oracle, $C$'s returned ciphertext $y^*$ is not one it
823 obtained from
\emph{its
} encryption oracle. So
824 \
[ \Succ{int-ctxt
}{\mathcal{E
}}(A) =
\Pr[V
]. \
]
826 \
[ \InSec{lor-cca
}(
\mathcal{E
}; t, q_E, q_D)
\le
827 \InSec{lor-cpa
}(
\mathcal{E
}; t, q_E) +
828 2 \cdot \InSec{int-ctxt
}(
\mathcal{E
}; t, q_E, q_D). \
]%
832 \topic{strong MACs provide INT-CTXT
}
833 \head{A strong MAC provides integrity of ciphertexts
}
835 That's a very nice result, but how do we acheive INT-CTXT? Well, the
836 game in the definition looks very much like the forgery games we played
837 when we were thinking about MACs.
839 Suppose that $
\mathcal{E
} = (E, D)$ is an encryption scheme secure in the
840 LOR-CPA sense, and $
\mathcal{M
} = (T, V)$ is a strong MAC (in the SUF-CMA
841 sense). Then we can define $
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{M
}} =
842 (
\Xid{E
}{auth
}^
{\mathcal{E
},
\mathcal{M
}},
\Xid{D
}{auth
}^
{\mathcal{E
},
844 \
[ \keys\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}} =
845 \keys\mathcal{E
} \times \keys\mathcal{M
} \
]%
849 $
\Xid{E
}{auth
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(x)$: \+ \\
850 $y
\gets E_
{K_E
}(x)$; \\
851 $
\tau \gets T_
{K_T
}(y)$; \\
852 \RETURN $
\tau \cat y$;
855 $
\Xid{D
}{auth
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(y')$: \+ \\
856 \PARSE $y'$
\AS $
\tau, y$; \\
857 \IF $V_
{K_T
}(y,
\tau) =
0$
\THEN \RETURN $
\bot$; \\
858 \ELSE \RETURN $D_
{K_E
}(y)$;
863 \head{A strong MAC provides integrity of ciphertexts (cont.)
}
865 The security proof for $
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}}$
866 is left as a trivial exercise. We end up with the result that
867 \
[ \InSec{int-ctxt
}(
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}};
869 \InSec{suf-cma
}(
\mathcal{M
}; t, q_E, q_D) \
]%
871 \begin{eqnarray*
}[Ll
]
872 \InSec{lor-cca
}(
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}};
874 &
\le \InSec{lor-cpa
}(
\mathcal{E
}; t, q_E) +
875 2 \cdot \InSec{suf-cma
}(
\mathcal{M
}; t, q_E, q_D).
877 A MAC, therefore, can help us to attain a strong notion of secrecy, even if
878 no actual integrity appears to be required. This is an important lesson.
882 Prove the above result.
884 Let $A$ attack INT-CTXT. Construct adversary $B^
{T(
\cdot), V(
\cdot)
}$: \
{
885 $K
\getsr \keys\mathcal{E
}$; $(y,
\tau)
\gets A^
{\id{encrypt
}(
\cdot),
886 \id{decrypt
}(
\cdot)
}$;
\RETURN $(y,
\tau)$;~\
} Oracle $
\id{encrypt
}(x)$:
887 \
{ $y
\gets E_K(x)$; $
\tau \gets T(y)$;
\RETURN $(y,
\tau)$;~\
} Oracle
888 $
\id{decrypt
}(y,
\tau)$: \
{ \IF $V(y,
\tau) =
1$
\THEN \RETURN $D_K(y)$;
889 \ELSE \RETURN $
\bot$;~\
}. The simulation of the INT-CTXT game is perfect.
893 \topic{mixing encryption and MACs
}
894 \head{Notes on mixing encryption and MACs
}
896 To construct $
\Xid{\mathcal{E
}}{auth
}^
{\mathcal{E
},
\mathcal{M
}}$, we
897 applied a MAC to the
\emph{ciphertext
}. This isn't perhaps the most
898 intuitive way to combine an encryption scheme with a MAC.
900 There are three constructions which look plausible.
902 \item[Encrypt-then-MAC:
]
904 $y
\gets E_
{K_E
}(x)$; $
\tau \gets T_
{K_T
}(y)$;
\RETURN $
\tau \cat y$;
906 Encrypt the plaintext, and MAC the ciphertext; used in IPsec and nCipher
907 Impath; we've proven its generic security, using the notion of integrity
910 \item[MAC-then-encrypt:
]
912 $
\tau \gets T_
{K_T
}(x)$; $y
\gets E_
{K_E
}(
\tau \cat x)$;
\RETURN $y$;
914 MAC the plaintext, and encrypt both the plaintext and tag; used in SSL
915 and TLS; not
\emph{generically
} secure against chosen-ciphertext attacks.
917 \item[Encrypt-and-MAC:
]
919 $y
\gets E_
{K_E
}(x)$; $
\tau \gets T_
{K_T
}(x)$;
\RETURN $
\tau \cat y$;
921 Separately MAC and encrypt the plaintext; used in SSH;
\emph{never
}
922 secure against chosen-ciphertext, not generically secure against
928 We begin with a few words on our approach, before we embark on the proof
931 To demonstrate the generic insecurity of a scheme, we assume the existance
932 of an encryption scheme and MAC (since if they don't exist, the result is
933 vacuously true) and construct modified schemes whose individual security
934 relates tightly to the originals, but the combined scheme is weak.
936 We demonstrate
\emph{universal
} insecurity by showing an attack which works
937 given
\emph{any
} component encryption and MAC schemes.
939 We prove security relationships using the LOR-CPA notion because this is
940 strongest, and bounds for other notions can be derived readily from the
941 left-or-right analysis. We prove insecurity using the FTG-CCA or FTG-CPA
942 notions, because they are weakest and show the strength of our results
945 We've dealt with the generic security of encrypt-then-MAC already. We turn
946 our attention first first to the generic insecurity of the MAC-then-encrypt
949 Let $
\mathcal{E
} = (E, D)$ be a symmetric encryption scheme, and let
950 $
\mathcal{M
} = (T, V)$ be a MAC. We define the MAC-then-encrypt scheme
951 $
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
},
\mathcal{M
}} =
952 (
\Xid{E
}{MtE
}^
{\mathcal{E
},
\mathcal{M
}},
\Xid{D
}{MtE
}^
{\mathcal{E
},
953 \mathcal{M
}})$ as follows:
954 \
[ \keys\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
},
\mathcal{M
}} =
955 \keys\mathcal{E
} \times \keys\mathcal{M
} \
]%
959 $
\Xid{E
}{MtE
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(x)$: \+ \\
960 $
\tau \gets T_
{K_T
}(x)$; \\
961 $
\RETURN E_
{K_E
}(
\tau \cat x)$;
964 $
\Xid{D
}{MtE
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(y)$: \+ \\
965 $x'
\gets D_
{K_E
}(y)$; \\
966 \PARSE $x'$
\AS $
\tau, x$; \\
967 \IF $V_
{K_T
}(x,
\tau) =
0$
\THEN \RETURN $
\bot$; \\
970 We construct a new encryption scheme $
\mathcal{E
}' = (E', D')$ in terms of
971 $
\mathcal{E
}$, such that the combined scheme
972 $
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
}',
\mathcal{M
}}$ is insecure in the
973 FTG-CCA sense. Our modified encryption scheme has $
\keys\mathcal{E
}' =
974 \keys\mathcal{E
}$, and works as follows:
976 Algorithm $E'_K(x)$: \+ \\
977 \RETURN $
0 \cat E_K(x)$;
979 Algorithm $D'_K(y')$: \+ \\
980 \PARSE $y'$
\AS $
1\colon b, y$; \\
983 That is, the encryption scheme prepends a single bit to the ciphertext, and
984 doesn't check its value during decryption. Intuitively, this makes the
985 scheme malleable: we can change the ciphertext by flipping the first bit,
986 but the MAC tag remains valid because the plaintext is unaffected.
988 Firstly, we prove that $
\mathcal{E
}'$ is LOR-CPA if $
\mathcal{E
}$ is.
989 Suppose $A'$ attacks $
\mathcal{E
}'$ in the LOR-CPA sense: then
991 Adversary $A^
{E(
\cdot,
\cdot)
}$: \+ \\
992 \RETURN $A'^
{0 \cat E(
\cdot,
\cdot)
}$;
994 has the same advantage.
996 Secondly, we show that the combined MAC-then-encrypt scheme
997 $
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
}',
\mathcal{M
}}$ is insecure in the
998 FTG-CCA sense. Consider this adversary:
1000 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
1001 \RETURN $(
0,
1,
\bot)$;
1003 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{guess
}, y', s)$: \+ \\
1004 \PARSE $y'$
\AS $
1\colon b, y$; \\
1005 \RETURN $D(
1 \cat y)$;
1007 The ciphertext $
1 \cat y$ was never returned by the encryption oracle
1008 (because it always returns the first bit zero); but the plaintext of $
1
1009 \cat y$ is the challenge plaintext. Hence, $B$ wins always, and
1010 \
[ \InSec{ftg-cca
}(
\Xid{\mathcal{E
}}{MtE
}^
{\mathcal{E
}',
\mathcal{M
}};
1012 where $t$ is the running time of the adversary $B$ above.
1014 We now address the separate encrypt-and-MAC scheme, which we define
1015 formally. Let $
\mathcal{E
} = (E, D)$ be a symmetric encryption scheme, and
1016 let $
\mathcal{M
} = (T, V)$ be a MAC. Then the the encrypt-and-MAC scheme
1017 $
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}} =
1018 (
\Xid{E
}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}},
\Xid{D
}{E\&M
}^
{\mathcal{E
},
1019 \mathcal{M
}})$ is defined by:
1020 \
[ \keys\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}} =
1021 \keys\mathcal{E
} \times \keys\mathcal{M
} \
]%
1025 $
\Xid{E
}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(x)$: \+ \\
1026 $y
\gets E_
{K_E
}(x)$; \\
1027 $
\tau \gets T_
{K_T
}(x)$; \\
1028 $
\RETURN \tau \cat y$;
1031 $
\Xid{D
}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}}_
{K_E, K_T
}(y')$: \+ \\
1032 \PARSE $y'$
\AS $
\tau, y$; \\
1033 $x
\gets D_
{K_E
}(y)$; \\
1034 \IF $V_
{K_T
}(x,
\tau) =
0$
\THEN \RETURN $
\bot$; \\
1038 We first show that this scheme is
\emph{universally
} insecure against
1039 chosen-ciphertext attack. Let $
\mathcal{E
}$ and $
\mathcal{M
}$ be an
1040 arbitrary symmetric encryption scheme and MAC, respectively. The attack
1041 works because the MACs can be detached and used in chosen-ciphertext
1042 queries to test for equality of messages.
1044 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
1045 \RETURN $(
0,
1,
\bot)$;
1047 Adversary $B^
{E(
\cdot), D(
\cdot)
}$(
\cookie{guess
}, y', s): \+ \\
1048 $y_1'
\gets E(
1)$; \\
1049 \PARSE $y'$
\AS $
\tau, y$; \\
1050 \PARSE $y_1'$
\AS $
\tau_1, y_1$; \\
1051 \IF $
\tau =
\tau_1 \lor D(
\tau \cat y_1)
\ne \bot$
1052 \THEN \RETURN $
1$; \\
1055 After receiving the challenge ciphertext, the adversary requests an
1056 additional encryption of the plaintext $
1$. If the tags are equal on the
1057 two ciphertexts then we announce that the hidden bit is $
1$. Otherwise, we
1058 attempt a decryption of the new ciphertext, using the tag from the
1059 challenge. If it decrypts successfully, we announce that the bit is $
1$;
1060 otherwise we claim it is zero.
1062 Certainly, this strategy is always correct when the hidden bit is indeed
1063 $
1$. However, there is a possibility that the MACs are equal or verify
1064 correctly even when the hidden bit is $
0$. To bound this probability, we
1065 construct the following simple adversary against the MAC:
1067 Adversary $B'^
{T(
\cdot), V(
\cdot)
}$: \+ \\
1068 $
\tau \gets T(
1)$; \\
1069 \RETURN $(
0,
\tau)$;
1072 \
[ \InSec{ftg-cca
}(
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}};
1074 1 -
\InSec{suf-cma
}(
\mathcal{M
}; t',
1,
0), \
]%
1075 where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
1078 Finally, we show that the encrypt-and-MAC scheme is generically insecure
1079 against chosen-plaintext attacks only. There are two strategies we could
1080 use. Since both offer useful insights into the properties of MACs, we
1084 \item \emph{Deterministic MACs.
} In the proof of the universal weakness of
1085 the encrypt-and-MAC scheme, we used the check on the MAC to decide on the
1086 equality of two plaintexts given the ciphertexts. If the MAC is
1087 deterministic (e.g., a PRF) then we don't need a decryption query.
1089 Let $
\mathcal{E
} = (E, D)$ be a symmetric cipher, and let $
\mathcal{M
} =
1090 (T, V)$ be a deterministic MAC, e.g., a PRF, or HMAC. Then consider this
1093 Adversary $B^
{E(
\cdot)
}(
\cookie{find
})$: \+ \\
1094 \RETURN $(
0,
1,
\bot)$;
1096 Adversary $B^
{E(
\cdot)
}(
\cookie{guess
}, y', s)$: \+ \\
1097 $y_1'
\gets E(
1)$; \\
1098 \PARSE $y'$
\AS $
\tau, y$; \\
1099 \PARSE $y_1'$
\AS $
\tau_1, y_1$; \\
1100 \IF $
\tau =
\tau_1$
\THEN \RETURN $
1$; \\
1103 Since the MAC is deterministic, the tag attached to a ciphertext $
1$ is
1104 always the same. We bound the probability that $T_K(
0) = T_K(
1)$ using
1105 the adversary $B'$ above, and conclude that
1106 \
[ \InSec{ftg-cpa
}(
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}};
1108 1 -
\InSec{suf-cma
}(
\mathcal{M
}; t',
1,
0), \
]%
1109 where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
1112 \item \emph{Leaky MACs.
} A MAC doesn't have to conceal information about
1113 messages. Suppose $
\mathcal{M
} = (T, V)$ is a secure MAC. We define the
1114 leaky MAC $
\mathcal{M
}' = (T', V')$ by stating that $
\keys\mathcal{M
}' =
1115 \keys\mathcal{M
}''$ and
1117 Algorithm $T'_K(x)$: \+ \\
1118 \PARSE $x$
\AS $
1\colon x_0, z$; \\
1119 \RETURN $x_0
\cat T_K(x)$;
1121 Algorithm $V'_K(x,
\tau')$: \+ \\
1122 \PARSE $
\tau'$
\AS $
1\colon \tau_0,
\tau$; \\
1123 \PARSE $x$
\AS $
1\colon x_0, z$; \\
1124 \IF $x_0
\ne \tau_0$
\THEN \RETURN $
0$; \\
1125 \ELSE \RETURN $V_K(x,
\tau)$;
1127 We must first prove that $
\mathcal{M
}'$ remains secure. To do this,
1128 consider an adversary $A'$ attacking $
\mathcal{M
}'$. We construct $A$
1129 attacking $
\mathcal{M
}$ in the obvious way:
1131 Algorithm $A^
{T(
\cdot), V(
\cdot)
}$: \\
1133 A'^
{\Xid{T'
}{sim
}(
\cdot),
\Xid{V'
}{sim
}(
\cdot)
}$; \\
1134 \PARSE $
\tau'$
\AS $
1\colon \tau_0,
\tau$; \\
1135 \RETURN $(x,
\tau)$;
1137 Oracle $
\Xid{T'
}{sim
}(x)$: \+ \\
1138 \PARSE $x$
\AS $
1\colon x_0, z'$; \\
1139 \RETURN $x_0
\cat T(x)$; \- \\
[\smallskipamount]
1140 Oracle $
\Xid{V'
}{sim
}(x,
\tau')$: \+ \\
1141 \PARSE $
\tau'$
\AS $
1\colon \tau_0,
\tau$; \\
1142 \PARSE $x$
\AS $
1\colon x_0, z$; \\
1143 \IF $x_0
\ne \tau_0$
\THEN \RETURN $
0$; \\
1144 \ELSE \RETURN $V(x,
\tau)$;
1146 Here, $A$ simply simulates the environment expected by $A'$. It is clear
1147 that $A$ succeeds whenver $A'$ returns a valid tag for a
\emph{new
}
1148 message. However, suppose that $A'$ returns a new tag $
\tau'$ for some
1149 old message $x$, for which the tag $
\tau$ was returned by the tagging
1150 oracle. Let $x_0$, $
\tau_0$ and $
\tau'_0$ be the first bits of $x$,
1151 $
\tau$ and $
\tau'$ respectively, and let $
\tau^*$ be the remaining bits
1152 of $
\tau'$. If the pair $(x,
\tau')$ is to be a valid
1153 $
\mathcal{M
}'$-forgery, we must have $x_0 =
\tau_0 =
\tau'_0$. Hence,
1154 $
\tau$ and $
\tau'$ must differ in at least one other bit, and $(x,
1155 \tau^*)$ is a valid $
\mathcal{M
}$-forgery. We conclude that
1156 \
[ \InSec{suf-cma
}(
\mathcal{M
}'; t, q_T, q_V)
\le
1157 \InSec{suf-cma
}(
\mathcal{M
}; t, q_T, q_V) \
]%
1160 Now we show that the combined encrypt-and-MAC scheme is weak in the
1161 FTG-CPA sense. Consider this adversary attacking the scheme:
1163 Adversary $B^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
1164 \RETURN $(
0,
1,
\bot)$;
1166 Adversary $B^
{E(
\cdot), D(
\cdot)
}$(
\cookie{guess
}, y', s): \+ \\
1167 \PARSE $y'$
\AS $
\tau, y$; \\
1168 \PARSE $
\tau$
\AS $
1\colon b,
\tau^*$; \\
1171 The leaky MAC simply tells us the right answer. So
1172 \
[ \InSec{ftg-cpa
}(
\Xid{\mathcal{E
}}{E\&M
}^
{\mathcal{E
},
\mathcal{M
}'
};
1174 where $t$ is the running time of adversary $B$ above.
1178 This concludes the proof.
1181 %% TO DO: Include stuff about integrity-aware encryption modes some day.
1185 %%% Local Variables:
1187 %%% TeX-master: "ips"