against chosen-plaintext and chosen-ciphertext attacks. To make life more
complicated, we have three different indistinguishability notions.
- We use the same notation to decscribe the decryption oracles provided in
+ We use the same notation to describe the decryption oracles provided in
various types of attacks:
\begin{tabular}[C]{l Mc Mc }
\hlx*{hv}
Now we show that we can't obtain a better reduction. Suppose that
$\mathcal{E} = (E, D)$ is $(t, q_E, q_D, \epsilon)$-secure in the FTG
- sense. We contruct a \emph{$p$-leaky} version, $\mathcal{E}' = (E',
+ sense. We construct a \emph{$p$-leaky} version, $\mathcal{E}' = (E',
D')$. Let $\id{maybe}(p)$ denote a function which returns $1$ with
probability $p$.
\begin{program}
Prove that
\[ \InSec{lor-cpa}(\mathcal{E}; t, q, \mu) \le
2 \cdot \InSec{prf}(F; t, q) +
- 2 q \mu \cdot \InSec{prg}(g; t) + q(q - 1), \]%
+ 2 q \mu \cdot \InSec{prg}(g; t) + q(q - 1)/2^l, \]%
where $\mu$ is the maximum value of $n$, as computed by $E_K(\cdot)$, for
any encryption query.
Hints:
selected uniformly). Game~$\G1$ is the same, except that if, for any pair
of ciphertexts, the $i$-values are equal, the game ends immediately: the
standard collision bound shows that $|{\Pr[S_1]} - \Pr[S_0]| \le q(q -
- 1)/2$. In game~$\G2$, rather than using $F_K$ to compute the seeds~$s$, we
- just choose $s \in \{0, 1\}^l$ at random each time. Note that the
- $i$-values are distinct; hence considering an adversary attacking $F$ as a
- PRF, which simulates either $\G1$ or $\G2$ depending on whether its oracle
- is an instance of~$F$ or a random function respectively, shows that
- $|{\Pr[S_2]} - \Pr[S_1]| \le \InSec{prf}(F; t, q)$.
+ 1)/2^{l+1}$. In game~$\G2$, rather than using $F_K$ to compute the
+ seeds~$s$, we just choose $s \in \{0, 1\}^l$ at random each time. Note
+ that the $i$-values are distinct; hence considering an adversary attacking
+ $F$ as a PRF, which simulates either $\G1$ or $\G2$ depending on whether
+ its oracle is an instance of~$F$ or a random function respectively, shows
+ that $|{\Pr[S_2]} - \Pr[S_1]| \le \InSec{prf}(F; t, q)$.
In game~$\G3$, rather than using the PRG~$g^{(n)}$, we generate the strings
$p$ uniformly at random from $\{0, 1\}^{l(n+1)}$, and claim that
adversary's ciphertext, however, so $\Pr[S_4] = \Pr[S_3] = \frac{1}{2}$.
Tying all of this together, $(\Adv{lor-cpa}{\mathcal{E}}(A) + 1)/2 \le
\frac{1}{2} + \InSec{prf}(F; t, q) + q\mu \cdot \InSec{prg}(g; t) + q(q -
- 1)/2$. Multiplying through by~2 and rearranging yields the required
+ 1)/2^{l+1}$. Multiplying through by~2 and rearranging yields the required
result.
\def\H#1{\G[H]{#1}}%
+
We finally turn to the claim made earlier. In $\G2$, we use the PRG; in
- $\G3$ we don't. We construct a number of hybrid games~$\H{i}$ for $0 \le i
- \le q$ in which encryption query~$j$ (for $0 \le j < q$) is handled as
- follows: if $0 \le j < i$ then the query is handled as in $\G3$; if $i \le
- j < q$ then the query is handed as in $\G2$. Let $T_i$ be the event that
- the adversary wins in game $\H{i}$. Clearly, $\H0 \equiv \G2$, and $\H{q}
- \equiv \G3$. For each adjacent pair of hybrid games $\H{i}, \H{i+1}$ (for
- $0 \le i < q$), we can bound $|{\Pr[T_{i+1}} - \Pr[T_i]|$ by considering an
- adversary attacking~$g^{(n)}$ by running~$A$ and using its input as the XOR
- mask~$p$ for query~$i$, and following the rules of game~$\H{i}$ for the
- other queries: then if $y$~is random, it simulates $\H{i+1}$, whereas if
- $y$ is the output of $g^{(n)}$ then it simulates $\H{i}$. Thus
- $|{\Pr[T_{i+1}} - \Pr[T_i]| \le \mu \cdot \InSec{prg}(g; t)$ (by the answer
- to \ref{ex:dbl-prg}), and $|{\Pr[S_3]} - \Pr[S_2]| = |{\Pr[T_{q-1}]} -
- \Pr[T_0]| \le q \mu \cdot \InSec{prg}(g; t)$ as claimed.
+ $\G3$ we don't. Unfortunately, while the left-or-right attack game allows
+ multiple queries and hence multiple samples from the PRG, the PRG attack
+ game only provides one sample. To bridge the gap, we construct a number of
+ hybrid games~$\H{i}$ for $0 \le i \le q$ in which encryption query~$j$ (for
+ $0 \le j < q$) is handled as follows: if $0 \le j < i$ then the query is
+ handled as in $\G3$; if $i \le j < q$ then the query is handed as in $\G2$.
+ Let $T_i$ be the event that the adversary wins in game $\H{i}$. Clearly,
+ $\H0 \equiv \G2$, and $\H{q} \equiv \G3$. For each adjacent pair of hybrid
+ games $\H{i}, \H{i+1}$ (for $0 \le i < q$), we can bound $|{\Pr[T_{i+1}} -
+ \Pr[T_i]|$ by considering an adversary attacking~$g^{(n)}$ by running~$A$,
+ using as its input the XOR mask~$p$ for query~$i$, and following the rules
+ of game~$\H{i}$ for the other queries: then if $y$~is random, it simulates
+ $\H{i+1}$, whereas if $y$ is the output of $g^{(n)}$ then it simulates
+ $\H{i}$. Thus $|{\Pr[T_{i+1}} - \Pr[T_i]| \le \mu \cdot \InSec{prg}(g; t)$
+ (by the answer to \ref{ex:dbl-prg}), and $|{\Pr[S_3]} - \Pr[S_2]| =
+ |{\Pr[T_{q-1}]} - \Pr[T_0]| \le q \mu \cdot \InSec{prg}(g; t)$ as claimed.
\end{exercise}
\xcalways\subsection{Block cipher modes}\x
\begin{slide}
\topic{ECB}
- \head{Electronic Code Book (ECB), 1: description}
+ \resetseq
+ \head{Electronic Code Book (ECB), \seq: description}
We define the scheme $\Xid{\mathcal{E}}{ECB}^E = (\Xid{E}{ECB}^E,
\Xid{D}{ECB}^E))$ by setting $\keys\Xid{\mathcal{E}}{ECB}^E = \{0, 1\}^k$
\end{slide}
\begin{slide}
- \head{Electronic Code Book (ECB), 2: analysis}
+ \head{Electronic Code Book (ECB), \seq: diagram}
+
+ \vfil
+ \[ \begin{graph}
+ []!{0; <1cm, 0cm>: <0cm, 1.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x" :[dd] *+[F]{E}="e"
+ :[dd] *+=(1, 0)+[F]{\mathstrut y_0}
+ "e" [l] {K} :"e" "x" [rrr]
+ *+=(1, 0)+[F]{\mathstrut x_1}="x" :[dd] *+[F]{E}="e"
+ :[dd] *+=(1, 0)+[F]{\mathstrut y_1}
+ "e" [l] {K} :"e" "x" [rrr]
+ *+=(1, 0)+[F--]{\mathstrut x_i}="x" :@{-->}[dd] *+[F]{E}="e"
+ :@{-->}[dd] *+=(1, 0)+[F--]{\mathstrut y_i}
+ "e" [l] {K} :@{-->}"e" "x" [rrr]
+ *+=(1, 0)+[F]{\mathstrut x_n}="x" :[dd] *+[F]{E}="e"
+ :[dd] *+=(1, 0)+[F]{\mathstrut y_n}
+ "e" [l] {K} :"e" "x" [rrr]
+ \end{graph} \]
+ \vfil
+\end{slide}
+
+\begin{slide}
+ \head{Electronic Code Book (ECB), \seq: analysis}
ECB fails to disguise equality of message blocks. Hence, it is insecure in
the left-or-right sense.
\begin{slide}
\topic{stateful counter mode}
- \head{Counter (CTR), 1: a stateful mode}
+ \resetseq
+ \head{Counter (CTR), \seq: a stateful mode}
We define two schemes. Firstly, a stateful-sender scheme
$\Xid{\mathcal{E}}{CTRS}^E = (\Xid{E}{CTRS}^E, \Xid{D}{CTRS}^E))$. We set
\end{slide}
\begin{slide}
- \head{Counter (CTR), 2: analysis of the stateful version}
+ \head{Counter (CTR), \seq: diagram}
+
+ \vfil
+ \[ \begin{graph}
+ []!{0; <1cm, 0cm>: <0cm, 1.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x" :[dd] *{\xor}="xor"
+ :[dd] *+=(1, 0)+[F]{\mathstrut y_0}
+ "xor" [l] *+[F]{E}="e" [u] {c} :"e" [d] {K} :"e" :"xor" "x" [rrr]
+ *+=(1, 0)+[F]{\mathstrut x_1}="x" :[dd] *{\xor}="xor"
+ :[dd] *+=(1, 0)+[F]{\mathstrut y_1}
+ "xor" [l] *+[F]{E}="e" [u] {c+1} :"e" [d] {K} :"e" :"xor" "x" [rrr]
+ *+=(1, 0)+[F--]{\mathstrut x_i}="x" :@{-->}[dd] *{\xor}="xor"
+ :@{-->}[dd] *+=(1, 0)+[F--]{\mathstrut y_i}
+ "xor" [l] *+[F]{E}="e" [u] {c+i} :@{-->}"e" [d] {K} :@{-->}"e"
+ :@{-->}"xor" "x" [rrr]
+ *+=(1, 0)+[F]{\mathstrut x_n}="x" :[dd] *{\xor}="xor"
+ :[dd] *+=(1, 0)+[F]{\mathstrut y_n}
+ "xor" [l] *+[F]{E}="e" [u] {c+n} :"e" [d] {K} :"e" :"xor" "x" [rrr]
+ \end{graph} \]
+ \vfil
+\end{slide}
+
+\begin{slide}
+ \head{Counter (CTR), \seq: analysis of the stateful version}
We write $q' = q\mu/l$ for the total number of blocks queried by the
adversary, and we restrict our attention to the case $n \le 2^l$.
\begin{slide}
\topic{randomized counter mode}
- \head{Counter (CTR), 3: a randomized mode}
+ \head{Counter (CTR), \seq: a randomized mode}
The randomized scheme $\Xid{\mathcal{E}}{CTR$\$$}^E = (\Xid{E}{CTR$\$$}^E,
\Xid{D}{CTR$\$$}^E))$ differs from the stateful scheme in the encryption
\end{slide}
\begin{slide}
- \head{Counter (CTR), 4: analysis of the randomized version}
+ \head{Counter (CTR), \seq: analysis of the randomized version}
The randomized mode remains secure so long as a counter is never repeated.
This occurs with probability no greater than
\begin{slide}
\topic{CBC}
- \head{Ciphertext Block Chaining (CBC), 1: description}
+ \resetseq
+ \head{Ciphertext Block Chaining (CBC), \seq: description}
We define the scheme $\Xid{\mathcal{E}}{CBC}^E = (\Xid{E}{CBC}^E,
\Xid{D}{CBC}^E))$ by setting $\keys\Xid{\mathcal{E}}{CBC}^E = \{0, 1\}^k$
\end{slide}
\begin{slide}
- \head{Ciphertext Block Chaining (CBC), 2: analysis}
+ \head{Ciphertext Block Chaining (CBC), \seq: diagram}
+
+ \vfil
+ \[ \begin{graph}
+ []!{0; <1cm, 0cm>: <0cm, 1.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x"
+ :[d] *{\xor}="xor"
+ [ll] *+=(1, 0)+[F]{I} :"xor"
+ :[d] *+[F]{E}="e" :[dd] *+=(1, 0)+[F]{\mathstrut y_0}="i"
+ "e" [l] {K} :"e" "i"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x"
+ :[d] *{\xor}="xor"
+ "i" :`r [ru] `u "xor" "xor"
+ :[d] *+[F]{E}="e" :[dd] *+=(1, 0)+[F]{\mathstrut y_1}="i"
+ "e" [l] {K} :"e" "i"
+ [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x"
+ :@{-->}[d] *{\xor}="xor"
+ "i" :@{-->}`r [ru] `u "xor" "xor"
+ :@{-->}[d] *+[F]{E}="e" :@{-->}[dd] *+=(1, 0)+[F--]{\mathstrut y_i}="i"
+ "e" [l] {K} :@{-->}"e" "i"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_n}="x"
+ :[d] *{\xor}="xor"
+ "i" :@{-->}`r [ru] `u "xor" "xor"
+ :[d] *+[F]{E}="e" :[dd] *+=(1, 0)+[F]{\mathstrut y_n}="i"
+ "e" [l] {K} :"e" "i"
+ \end{graph} \]
+ \vfil
+\end{slide}
+
+\begin{slide}
+ \head{Ciphertext Block Chaining (CBC), \seq: analysis}
As before, we set $q' = q\mu/l$ as the number of blocks queried by an
adversary attacking the encryption scheme.
\begin{slide}
\topic{requirement for random IVs in CBC mode}
- \head{Ciphertext Block Chaining (CBC), 3: on randomness of IVs}
+ \head{Ciphertext Block Chaining (CBC), \seq: on randomness of IVs}
The initialization vector used in CBC encryption must be \emph{a priori}
unpredictable to the adversary. Suppose that $P(i)$, given an IV for a
Show that CTR and CBC modes are not secure against adaptive
chosen-ciphertext attacks.
\answer%
- We use the FTG-CCA2 notion. For CTR mode: \cookie{find}: \RETURN $(0, 1,
+ We use the FTG-CCA1 notion. For CTR mode: \cookie{find}: \RETURN $(0, 1,
\bot)$; \cookie{guess}: $y' \gets D(y \xor 0^L1)$; \RETURN $y' \xor 1$;
For CBC mode: same find stage, $y' \gets D(y \xor 1)$; \RETURN $y' \xor 1$;
\end{exercise}
\topic{strong MACs provide INT-CTXT}
\head{A strong MAC provides integrity of ciphertexts}
- That's a very nice result, but how do we acheive INT-CTXT? Well, the
+ That's a very nice result, but how do we achieve INT-CTXT? Well, the
game in the definition looks very much like the forgery games we played
when we were thinking about MACs.
We begin with a few words on our approach, before we embark on the proof
proper.
- To demonstrate the generic insecurity of a scheme, we assume the existance
+ To demonstrate the generic insecurity of a scheme, we assume the existence
of an encryption scheme and MAC (since if they don't exist, the result is
vacuously true) and construct modified schemes whose individual security
relates tightly to the originals, but the combined scheme is weak.
We prove security relationships using the LOR-CPA notion because this is
strongest, and bounds for other notions can be derived readily from the
- left-or-right analysis. We prove insecurity using the FTG-CCA or FTG-CPA
+ left-or-right analysis. We prove insecurity using the FTG-CCA1 or FTG-CPA
notions, because they are weakest and show the strength of our results
best.
We construct a new encryption scheme $\mathcal{E}' = (E', D')$ in terms of
$\mathcal{E}$, such that the combined scheme
$\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$ is insecure in the
- FTG-CCA sense. Our modified encryption scheme has $\keys\mathcal{E}' =
+ FTG-CCA1 sense. Our modified encryption scheme has $\keys\mathcal{E}' =
\keys\mathcal{E}$, and works as follows:
\begin{program}
Algorithm $E'_K(x)$: \+ \\
Secondly, we show that the combined MAC-then-encrypt scheme
$\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$ is insecure in the
- FTG-CCA sense. Consider this adversary:
+ FTG-CCA1 sense. Consider this adversary:
\begin{program}
- Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
+ Adversary $B^{E(\cdot)}(\cookie{find})$: \+ \\
\RETURN $(0, 1, \bot)$;
\next
Adversary $B^{E(\cdot), D(\cdot)}(\cookie{guess}, y', s)$: \+ \\
The ciphertext $1 \cat y$ was never returned by the encryption oracle
(because it always returns the first bit zero); but the plaintext of $1
\cat y$ is the challenge plaintext. Hence, $B$ wins always, and
- \[ \InSec{ftg-cca}(\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}};
- t, 0, 1) = 1, \]%
+ \[ \InSec{ftg-cca1}(\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}};
+ t, 0, 1) = 1, \]%
where $t$ is the running time of the adversary $B$ above.
We now address the separate encrypt-and-MAC scheme, which we define
\RETURN $(0, \tau)$;
\end{program}
We see readily that
- \[ \InSec{ftg-cca}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}};
- t, 1, 1) \ge
+ \[ \InSec{ftg-cca1}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}};
+ t, 1, 1) \ge
1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0), \]%
where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
respectively.
\ELSE \RETURN $V(x, \tau)$;
\end{program}
Here, $A$ simply simulates the environment expected by $A'$. It is clear
- that $A$ succeeds whenver $A'$ returns a valid tag for a \emph{new}
+ that $A$ succeeds whenever $A'$ returns a valid tag for a \emph{new}
message. However, suppose that $A'$ returns a new tag $\tau'$ for some
old message $x$, for which the tag $\tau$ was returned by the tagging
oracle. Let $x_0$, $\tau_0$ and $\tau'_0$ be the first bits of $x$,
~mdw / doc / ips / blobdiff