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}
\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
\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.
\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$,