| 1 | \xcalways\section{Symmetric encryption}\x |
| 2 | |
| 3 | \xcalways\subsection{Syntax}\x |
| 4 | |
| 5 | \begin{slide} |
| 6 | \head{Symmetric encryption syntax} |
| 7 | |
| 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 |
| 10 | pair of algorithms: |
| 11 | \begin{itemize} |
| 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\}^*$. |
| 16 | \end{itemize} |
| 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$. |
| 20 | |
| 21 | We write $E_K(\cdot)$ rather than $E(K, \cdot)$, and $D_K(\cdot)$ rather |
| 22 | than $D(K, \cdot)$. |
| 23 | \end{slide} |
| 24 | |
| 25 | \xcalways\subsection{Security notions}\x |
| 26 | |
| 27 | \begin{slide} |
| 28 | \head{Symmetric encryption security notions} |
| 29 | |
| 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. |
| 33 | |
| 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. |
| 37 | |
| 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 } |
| 41 | \hlx*{hv} |
| 42 | Attack & D_0(c) & D_1(c) \\ \hlx{vhv} |
| 43 | CPA & \bot & \bot \\ |
| 44 | CCA1 & D_K(c) & \bot \\ |
| 45 | CCA2 & D_K(c) & D_K(c) \\ \hlx*{vh} |
| 46 | \end{tabular} |
| 47 | \end{slide} |
| 48 | |
| 49 | \begin{slide} |
| 50 | \topic{semantic security} |
| 51 | \head{Semantic security} |
| 52 | |
| 53 | The semantic security game is as for the asymmetric case, except for the |
| 54 | presence of encryption oracles. |
| 55 | |
| 56 | \begin{program} |
| 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$; \\ |
| 66 | \ELSE \RETURN $0$; |
| 67 | \end{program} |
| 68 | The distribution $\mathcal{M}$ must be \emph{valid}: all strings in |
| 69 | $\supp\mathcal{M}$ must have the same length. |
| 70 | \end{slide} |
| 71 | |
| 72 | \begin{slide} |
| 73 | \topic{find-then-guess} |
| 74 | \head{Find-then-guess indistinguishability} |
| 75 | |
| 76 | The `find-then-guess' (FTG) game corresponds to the standard public-key |
| 77 | indistinguishability notion. |
| 78 | \begin{program} |
| 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)$; \\ |
| 85 | \RETURN $b'$; |
| 86 | \end{program} |
| 87 | \end{slide} |
| 88 | |
| 89 | \begin{slide} |
| 90 | \topic{left-or-right} |
| 91 | \head{Left-or-right indistinguishability} |
| 92 | |
| 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 |
| 98 | the ciphertext. |
| 99 | \begin{program} |
| 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)$: \+ \\ |
| 105 | \RETURN $x_b$; |
| 106 | \end{program} |
| 107 | Note that, because the adversary only runs in one stage, we can only |
| 108 | consider chosen-plaintext and adaptive chosen-ciphertext attacks. |
| 109 | \end{slide} |
| 110 | |
| 111 | \begin{slide} |
| 112 | \topic{real-or-random} |
| 113 | \head{Real-or-random indistinguishability} |
| 114 | |
| 115 | The `real-or-random' (ROR) notion is somewhat less natural, but turns out |
| 116 | to be useful for analysing block cipher encryption modes. |
| 117 | |
| 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 |
| 120 | same length as $x$. |
| 121 | \begin{program} |
| 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|}$; \\ |
| 128 | \RETURN $x'$; |
| 129 | \next |
| 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)}$; \\ |
| 133 | \RETURN $b'$; |
| 134 | \end{program} |
| 135 | Again, only chosen-plaintext and adaptive chosen-ciphertext attacks are |
| 136 | applicable. |
| 137 | \end{slide} |
| 138 | |
| 139 | \begin{slide} |
| 140 | \topic{relations between notions} |
| 141 | \head{Relations between notions \cite{Bellare:2000:CST}} |
| 142 | |
| 143 | \[ \xymatrix @=2cm { |
| 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] |
| 148 | } \] |
| 149 | \begin{list}{}{ |
| 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 |
| 157 | factor. |
| 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. |
| 161 | \end{itemize} |
| 162 | \end{list} |
| 163 | \end{slide} |
| 164 | |
| 165 | \begin{proof} |
| 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. |
| 168 | \begin{enumerate} |
| 169 | |
| 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. |
| 172 | \begin{program} |
| 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|}$; \\ |
| 177 | \RETURN $E(x', x)$; |
| 178 | \end{program} |
| 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'), \]% |
| 182 | and hence |
| 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). \]% |
| 185 | |
| 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. |
| 188 | \begin{program} |
| 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}})$; |
| 196 | \end{program} |
| 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'), \]% |
| 205 | and hence |
| 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). \]% |
| 208 | |
| 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. |
| 213 | \begin{program} |
| 214 | Adversary $A^{E(\cdot, \cdot), D(\cdot)}$: \+ \\ |
| 215 | $(x_0, x_1, s) \gets A'^{\id{encrypt}(\cdot), D(\cdot)} |
| 216 | (\cookie{find})$; \\ |
| 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)$: \+ \\ |
| 222 | \RETURN $E(x, x)$; |
| 223 | \end{program} |
| 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'), \]% |
| 227 | and hence |
| 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). \]% |
| 230 | |
| 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. |
| 233 | |
| 234 | This proof is slightly more tricky than the others. Consider the |
| 235 | following `hybrid' games, defined for $0 \le i \le q_E$: |
| 236 | \begin{program} |
| 237 | Experiment $\Expt{hyb-$i$-\id{atk}-$b$}{\mathcal{E}}$: \+ \\ |
| 238 | $K \getsr \keys\mathcal{E}$; \\ |
| 239 | $j \gets 0$; \\ |
| 240 | $b' \gets A^{E(\id{lr-hack}_b(\cdot, \cdot)), D_1(\cdot)}$; \\ |
| 241 | \RETURN $b'$; \- \\[\smallskipamount] |
| 242 | \next |
| 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$; \\ |
| 247 | $j \gets j + 1$; \\ |
| 248 | \RETURN $E_K(x_b)$; |
| 249 | \end{program} |
| 250 | As usual, we define |
| 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]. \]% |
| 254 | |
| 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}} |
| 259 | \\ |
| 260 | \Expt{lor-\id{atk}-$1$}{\mathcal{E}} &\equiv |
| 261 | \Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}} |
| 262 | \\ |
| 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}}. |
| 266 | \end{eqnarray*} |
| 267 | Thus, |
| 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] |
| 272 | \\* |
| 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] |
| 275 | \\ |
| 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] |
| 284 | \\* |
| 285 | &=& \sum_{0\le i<q_E} \Adv{hyb-$i$-\id{atk}}{\mathcal{E}}(A) |
| 286 | \end{eqnarray*} |
| 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). \]% |
| 290 | |
| 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.} |
| 299 | \begin{enumerate} |
| 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 |
| 303 | $E(x_0)$. |
| 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'$. |
| 312 | \end{enumerate} |
| 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). \]% |
| 318 | |
| 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 |
| 323 | probability $p$. |
| 324 | \begin{program} |
| 325 | Algorithm $E'_K(x)$: \+ \\ |
| 326 | \IF $\id{maybe}(p) = 1$ \THEN \RETURN $1 \cat x$; \\ |
| 327 | \RETURN $0 \cat E_K(x)$; |
| 328 | \next |
| 329 | Algorithm $D'_K(y')$: \+ \\ |
| 330 | \PARSE $y'$ \AS $1\colon b, y$; \\ |
| 331 | \IF $b = 1$ \THEN \RETURN $y$; \\ |
| 332 | \RETURN $D_K(y)$; |
| 333 | \end{program} |
| 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. |
| 339 | \end{enumerate} |
| 340 | |
| 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 |
| 345 | need. |
| 346 | \end{proof} |
| 347 | |
| 348 | \begin{exercise} |
| 349 | Consider the following `ciphertext-or-random-string' security notion. |
| 350 | \begin{program} |
| 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|}$; \\ |
| 356 | \RETURN $x'$; |
| 357 | \next |
| 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)}$; \\ |
| 361 | \RETURN $b'$; |
| 362 | \end{program} |
| 363 | Relate this notion to the others we've already seen. |
| 364 | \answer% |
| 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}$. |
| 378 | \end{exercise} |
| 379 | |
| 380 | \begin{exercise} |
| 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: |
| 387 | \begin{program} |
| 388 | Algorithm $E_K(x)$: \\ |
| 389 | $i \getsr \{0, 1\}^l$; \\ |
| 390 | $n \gets \bigl\lceil \frac{|x|}{L} \bigr\rceil - 1$; \\ |
| 391 | $s \gets F_K(i)$; \\ |
| 392 | $p \gets g^{(n)}(s)$; \\ |
| 393 | $y \gets i \cat (x \xor p)$; \\ |
| 394 | \RETURN $y$; |
| 395 | \next |
| 396 | Algorithm $D_K(y)$: \\ |
| 397 | \PARSE $y$ \AS $l\colon i, y'$; \\ |
| 398 | $n \gets \bigl\lceil \frac{|x|}{L} \bigr\rceil - 1$; \\ |
| 399 | $s \gets F_K(i)$; \\ |
| 400 | $p \gets g^{(n)}(s)$; \\ |
| 401 | $x \gets y' \xor p$; \\ |
| 402 | \RETURN $x$; |
| 403 | \end{program} |
| 404 | Prove that |
| 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. |
| 410 | Hints: |
| 411 | \begin{parenum} |
| 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}$. |
| 417 | \end{parenum} |
| 418 | \answer% |
| 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)$. |
| 430 | |
| 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 |
| 442 | result. |
| 443 | |
| 444 | \def\H#1{\G[H]{#1}}% |
| 445 | |
| 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. |
| 463 | \end{exercise} |
| 464 | |
| 465 | \xcalways\subsection{Block cipher modes}\x |
| 466 | |
| 467 | \begin{slide} |
| 468 | \head{Block cipher modes} |
| 469 | |
| 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. |
| 473 | |
| 474 | We analyse three standard \emph{modes of operation}: |
| 475 | \begin{description} |
| 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$, |
| 480 | $i + 1$, \ldots |
| 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. |
| 485 | \end{description} |
| 486 | \end{slide} |
| 487 | |
| 488 | \begin{slide} |
| 489 | \head{General notation} |
| 490 | |
| 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 |
| 493 | than $E(K, \cdot)$. |
| 494 | |
| 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: |
| 498 | \begin{itemize} |
| 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. |
| 502 | \end{itemize} |
| 503 | |
| 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. |
| 506 | |
| 507 | We use $\emptystring$ to denote the empty string. |
| 508 | \end{slide} |
| 509 | |
| 510 | \begin{slide} |
| 511 | \topic{ECB} |
| 512 | \resetseq |
| 513 | \head{Electronic Code Book (ECB), \seq: description} |
| 514 | |
| 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$ |
| 517 | and |
| 518 | \begin{program} |
| 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)$; \\ |
| 523 | \RETURN $y$; |
| 524 | \next |
| 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)$; \\ |
| 529 | \RETURN $x$; |
| 530 | \end{program} |
| 531 | \end{slide} |
| 532 | |
| 533 | \begin{slide} |
| 534 | \head{Electronic Code Book (ECB), \seq: diagram} |
| 535 | |
| 536 | \vfil |
| 537 | \[ \begin{graph} |
| 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] |
| 551 | \end{graph} \] |
| 552 | \vfil |
| 553 | \end{slide} |
| 554 | |
| 555 | \begin{slide} |
| 556 | \head{Electronic Code Book (ECB), \seq: analysis} |
| 557 | |
| 558 | ECB fails to disguise equality of message blocks. Hence, it is insecure in |
| 559 | the left-or-right sense. |
| 560 | \begin{program} |
| 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$; \\ |
| 565 | \ELSE \RETURN $0$; |
| 566 | \end{program} |
| 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$. |
| 571 | |
| 572 | According to our formal definitions, then, ECB mode is \emph{completely |
| 573 | insecure}. |
| 574 | \end{slide} |
| 575 | |
| 576 | \begin{slide} |
| 577 | \topic{stateful counter mode} |
| 578 | \resetseq |
| 579 | \head{Counter (CTR), \seq: a stateful mode} |
| 580 | |
| 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 |
| 584 | define |
| 585 | \begin{program} |
| 586 | Algorithm $\Xid{E}{CTRS}^E_K(x)$: \+ \\ |
| 587 | $y \gets i$; \\ |
| 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$; \- \\ |
| 591 | \RETURN $y$; |
| 592 | \next |
| 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$; \- \\ |
| 599 | \RETURN $x$; |
| 600 | \end{program} |
| 601 | \end{slide} |
| 602 | |
| 603 | \begin{slide} |
| 604 | \head{Counter (CTR), \seq: diagram} |
| 605 | |
| 606 | \vfil |
| 607 | \[ \begin{graph} |
| 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] |
| 622 | \end{graph} \] |
| 623 | \vfil |
| 624 | \end{slide} |
| 625 | |
| 626 | \begin{slide} |
| 627 | \head{Counter (CTR), \seq: analysis of the stateful version} |
| 628 | |
| 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$. |
| 631 | |
| 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$. |
| 637 | |
| 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}}. \]% |
| 644 | \end{slide} |
| 645 | |
| 646 | \begin{exercise} |
| 647 | Fill in the gaps in the above proof. |
| 648 | \answer% |
| 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) |
| 659 | 2^{-L-1}$. |
| 660 | \end{exercise} |
| 661 | |
| 662 | \begin{slide} |
| 663 | \topic{randomized counter mode} |
| 664 | \head{Counter (CTR), \seq: a randomized mode} |
| 665 | |
| 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. |
| 670 | \begin{program} |
| 671 | Algorithm $\Xid{E}{CTR$\$$}^E_K(x)$: \+ \\ |
| 672 | $i \getsr \{0, 1\}^l$; \\ |
| 673 | $y \gets i$; \\ |
| 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$; \- \\ |
| 677 | \RETURN $y$; |
| 678 | \next |
| 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$; \- \\ |
| 685 | \RETURN $x$; |
| 686 | \end{program} |
| 687 | \end{slide} |
| 688 | |
| 689 | \begin{slide} |
| 690 | \head{Counter (CTR), \seq: analysis of the randomized version} |
| 691 | |
| 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}}. \]% |
| 701 | \end{slide} |
| 702 | |
| 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}} |
| 711 | \end{eqnarray*} |
| 712 | as required. |
| 713 | \end{proof} |
| 714 | |
| 715 | \begin{slide} |
| 716 | \topic{CBC} |
| 717 | \resetseq |
| 718 | \head{Ciphertext Block Chaining (CBC), \seq: description} |
| 719 | |
| 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$ |
| 722 | and |
| 723 | \begin{program} |
| 724 | Algorithm $\Xid{E}{CBC}^E_K(x)$: \+ \\ |
| 725 | $i \getsr \{0, 1\}^l$; \\ |
| 726 | $y \gets i$; \\ |
| 727 | \FOREACH $l\colon z$ \FROM $x$ \DO \\ \quad \= \+ \kill |
| 728 | $i \gets E_K(z \xor i)$; \\ |
| 729 | $y \gets y \cat i$; \- \\ |
| 730 | \RETURN $y$; |
| 731 | \next |
| 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))$; \\ |
| 737 | $i \gets z$; \- \\ |
| 738 | \RETURN $x$; |
| 739 | \end{program} |
| 740 | \end{slide} |
| 741 | |
| 742 | \begin{slide} |
| 743 | \head{Ciphertext Block Chaining (CBC), \seq: diagram} |
| 744 | |
| 745 | \vfil |
| 746 | \[ \begin{graph} |
| 747 | []!{0; <1cm, 0cm>: <0cm, 1.5cm>::} |
| 748 | *+=(1, 0)+[F]{\mathstrut x_0}="x" |
| 749 | :[d] *{\xor}="xor" |
| 750 | [ll] *+=(1, 0)+[F]{I} :"xor" |
| 751 | :[d] *+[F]{E}="e" :[dd] *+=(1, 0)+[F]{\mathstrut y_0}="i" |
| 752 | "e" [l] {K} :"e" "i" |
| 753 | [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x" |
| 754 | :[d] *{\xor}="xor" |
| 755 | "i" :`r [ru] `u "xor" "xor" |
| 756 | :[d] *+[F]{E}="e" :[dd] *+=(1, 0)+[F]{\mathstrut y_1}="i" |
| 757 | "e" [l] {K} :"e" "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" |
| 764 | :[d] *{\xor}="xor" |
| 765 | "i" :@{-->}`r [ru] `u "xor" "xor" |
| 766 | :[d] *+[F]{E}="e" :[dd] *+=(1, 0)+[F]{\mathstrut y_n}="i" |
| 767 | "e" [l] {K} :"e" "i" |
| 768 | \end{graph} \] |
| 769 | \vfil |
| 770 | \end{slide} |
| 771 | |
| 772 | \begin{slide} |
| 773 | \head{Ciphertext Block Chaining (CBC), \seq: analysis} |
| 774 | |
| 775 | As before, we set $q' = q\mu/l$ as the number of blocks queried by an |
| 776 | adversary attacking the encryption scheme. |
| 777 | |
| 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}.} % |
| 781 | we have the result |
| 782 | \[ \InSec{ror-cpa}(\Xid{\mathcal{E}}{CBC}^E; t, q, \mu) \le |
| 783 | \frac{q'(q' - 1)}{2^l}. \]% |
| 784 | \end{slide} |
| 785 | |
| 786 | \begin{slide} |
| 787 | \topic{requirement for random IVs in CBC mode} |
| 788 | \head{Ciphertext Block Chaining (CBC), \seq: on randomness of IVs} |
| 789 | |
| 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: |
| 795 | \begin{program} |
| 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$; \\ |
| 800 | \ELSE \RETURN $0$; |
| 801 | \end{program} |
| 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}. \] |
| 806 | \end{slide} |
| 807 | |
| 808 | \xcalways\subsection{Chosen-ciphertext security for symmetric encryption}\x |
| 809 | |
| 810 | \begin{exercise} |
| 811 | Show that CTR and CBC modes are not secure against adaptive |
| 812 | chosen-ciphertext attacks. |
| 813 | \answer% |
| 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$; |
| 817 | \end{exercise} |
| 818 | |
| 819 | \begin{slide} |
| 820 | \topic{integrity of ciphertexts} |
| 821 | \head{Integrity of ciphertexts \cite{Bellare:2000:AER}} |
| 822 | |
| 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$. |
| 828 | |
| 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 |
| 832 | proving anyway. |
| 833 | \end{slide} |
| 834 | |
| 835 | \begin{slide} |
| 836 | \head{Integrity of ciphertexts (cont.)} |
| 837 | |
| 838 | Consider the following game played by an adversary $A$: |
| 839 | \begin{program} |
| 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$; \\ |
| 845 | \ELSE \RETURN $0$; |
| 846 | \next |
| 847 | Oracle $\id{encrypt}(x)$: \+ \\ |
| 848 | $y \gets E_K(x)$; \\ |
| 849 | $\Xid{y}{list} \gets \Xid{y}{list} \cup \{y\}$; \\ |
| 850 | \RETURN $y$; |
| 851 | \end{program} |
| 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] \]% |
| 855 | and write that |
| 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. |
| 860 | \end{slide} |
| 861 | |
| 862 | \begin{slide} |
| 863 | \topic{INT-CTXT and LOR-CPA imply LOR-CCA} |
| 864 | \head{INT-CTXT and LOR-CPA together imply LOR-CCA} |
| 865 | |
| 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. |
| 870 | \begin{program} |
| 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)$; \+ \\ |
| 875 | \RETURN $\bot$; |
| 876 | \next |
| 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)$: \+ \\ |
| 884 | $x \gets D(y)$; \\ |
| 885 | \IF $x \ne \bot$ \THEN $y^* \gets y$; \\ |
| 886 | \RETURN $x$; |
| 887 | \end{program} |
| 888 | \end{slide} |
| 889 | |
| 890 | \begin{slide} |
| 891 | \head{INT-CTXT and LOR-CPA together imply LOR-CCA2 (cont.)} |
| 892 | |
| 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]. \] |
| 906 | Concluding, then, |
| 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). \]% |
| 910 | \end{slide} |
| 911 | |
| 912 | \begin{slide} |
| 913 | \topic{strong MACs provide INT-CTXT} |
| 914 | \head{A strong MAC provides integrity of ciphertexts} |
| 915 | |
| 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. |
| 919 | |
| 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}, |
| 924 | \mathcal{M}})$ by |
| 925 | \[ \keys\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}} = |
| 926 | \keys\mathcal{E} \times \keys\mathcal{M} \]% |
| 927 | and |
| 928 | \begin{program} |
| 929 | Algorithm |
| 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$; |
| 934 | \next |
| 935 | Algorithm |
| 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)$; |
| 940 | \end{program} |
| 941 | \end{slide} |
| 942 | |
| 943 | \begin{slide} |
| 944 | \head{A strong MAC provides integrity of ciphertexts (cont.)} |
| 945 | |
| 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}}; |
| 949 | t, q_E, q_D) \le |
| 950 | \InSec{suf-cma}(\mathcal{M}; t, q_E, q_D) \]% |
| 951 | and hence |
| 952 | \begin{eqnarray*}[Ll] |
| 953 | \InSec{lor-cca}(\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}; |
| 954 | t, q_E, q_D) \\ |
| 955 | & \le \InSec{lor-cpa}(\mathcal{E}; t, q_E) + |
| 956 | 2 \cdot \InSec{suf-cma}(\mathcal{M}; t, q_E, q_D). |
| 957 | \end{eqnarray*} |
| 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. |
| 960 | \end{slide} |
| 961 | |
| 962 | \begin{exercise} |
| 963 | Prove the above result. |
| 964 | \answer% |
| 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. |
| 971 | \end{exercise} |
| 972 | |
| 973 | \begin{slide} |
| 974 | \topic{mixing encryption and MACs} |
| 975 | \head{Notes on mixing encryption and MACs} |
| 976 | |
| 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. |
| 980 | |
| 981 | There are three constructions which look plausible. |
| 982 | \begin{description} |
| 983 | \item[Encrypt-then-MAC:] |
| 984 | % |
| 985 | $y \gets E_{K_E}(x)$; $\tau \gets T_{K_T}(y)$; \RETURN $\tau \cat y$; |
| 986 | \\ |
| 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 |
| 989 | of ciphertexts. |
| 990 | % |
| 991 | \item[MAC-then-encrypt:] |
| 992 | % |
| 993 | $\tau \gets T_{K_T}(x)$; $y \gets E_{K_E}(\tau \cat x)$; \RETURN $y$; |
| 994 | \\ |
| 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. |
| 997 | % |
| 998 | \item[Encrypt-and-MAC:] |
| 999 | % |
| 1000 | $y \gets E_{K_E}(x)$; $\tau \gets T_{K_T}(x)$; \RETURN $\tau \cat y$; |
| 1001 | \\ |
| 1002 | Separately MAC and encrypt the plaintext; used in SSH; \emph{never} |
| 1003 | secure against chosen-ciphertext, not generically secure against |
| 1004 | chosen-plaintext! |
| 1005 | \end{description} |
| 1006 | \end{slide} |
| 1007 | |
| 1008 | \begin{proof} |
| 1009 | We begin with a few words on our approach, before we embark on the proof |
| 1010 | proper. |
| 1011 | |
| 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. |
| 1016 | |
| 1017 | We demonstrate \emph{universal} insecurity by showing an attack which works |
| 1018 | given \emph{any} component encryption and MAC schemes. |
| 1019 | |
| 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 |
| 1024 | best. |
| 1025 | |
| 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 |
| 1028 | scheme. |
| 1029 | |
| 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} \]% |
| 1037 | and |
| 1038 | \begin{program} |
| 1039 | Algorithm |
| 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)$; |
| 1043 | \next |
| 1044 | Algorithm |
| 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$; \\ |
| 1049 | \ELSE \RETURN $x$; |
| 1050 | \end{program} |
| 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: |
| 1056 | \begin{program} |
| 1057 | Algorithm $E'_K(x)$: \+ \\ |
| 1058 | \RETURN $0 \cat E_K(x)$; |
| 1059 | \next |
| 1060 | Algorithm $D'_K(y')$: \+ \\ |
| 1061 | \PARSE $y'$ \AS $1\colon b, y$; \\ |
| 1062 | \RETURN $D_K(y)$; |
| 1063 | \end{program} |
| 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. |
| 1068 | |
| 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 |
| 1071 | \begin{program} |
| 1072 | Adversary $A^{E(\cdot, \cdot)}$: \+ \\ |
| 1073 | \RETURN $A'^{0 \cat E(\cdot, \cdot)}$; |
| 1074 | \end{program} |
| 1075 | has the same advantage. |
| 1076 | |
| 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: |
| 1080 | \begin{program} |
| 1081 | Adversary $B^{E(\cdot)}(\cookie{find})$: \+ \\ |
| 1082 | \RETURN $(0, 1, \bot)$; |
| 1083 | \next |
| 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)$; |
| 1087 | \end{program} |
| 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}}; |
| 1092 | t, 0, 1) = 1, \]% |
| 1093 | where $t$ is the running time of the adversary $B$ above. |
| 1094 | |
| 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} \]% |
| 1103 | and |
| 1104 | \begin{program} |
| 1105 | Algorithm |
| 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$; |
| 1110 | \next |
| 1111 | Algorithm |
| 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$; \\ |
| 1116 | \ELSE \RETURN $x$; |
| 1117 | \end{program} |
| 1118 | |
| 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. |
| 1124 | \begin{program} |
| 1125 | Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\ |
| 1126 | \RETURN $(0, 1, \bot)$; |
| 1127 | \next |
| 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$; \\ |
| 1134 | \ELSE \RETURN $0$; |
| 1135 | \end{program} |
| 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. |
| 1142 | |
| 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: |
| 1147 | \begin{program} |
| 1148 | Adversary $B'^{T(\cdot), V(\cdot)}$: \+ \\ |
| 1149 | $\tau \gets T(1)$; \\ |
| 1150 | \RETURN $(0, \tau)$; |
| 1151 | \end{program} |
| 1152 | We see readily that |
| 1153 | \[ \InSec{ftg-cca1}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}}; |
| 1154 | t, 1, 1) \ge |
| 1155 | 1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0), \]% |
| 1156 | where $t$ and $t'$ are the running times of adversaries $B$ and $B'$ |
| 1157 | respectively. |
| 1158 | |
| 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 |
| 1162 | present both here. |
| 1163 | \begin{itemize} |
| 1164 | |
| 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. |
| 1169 | |
| 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 |
| 1172 | adversary: |
| 1173 | \begin{program} |
| 1174 | Adversary $B^{E(\cdot)}(\cookie{find})$: \+ \\ |
| 1175 | \RETURN $(0, 1, \bot)$; |
| 1176 | \next |
| 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$; \\ |
| 1182 | \ELSE \RETURN $0$; |
| 1183 | \end{program} |
| 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}}; |
| 1188 | t, 1) \ge |
| 1189 | 1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0), \]% |
| 1190 | where $t$ and $t'$ are the running times of adversaries $B$ and $B'$ |
| 1191 | respectively. |
| 1192 | |
| 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 |
| 1197 | \begin{program} |
| 1198 | Algorithm $T'_K(x)$: \+ \\ |
| 1199 | \PARSE $x$ \AS $1\colon x_0, z$; \\ |
| 1200 | \RETURN $x_0 \cat T_K(x)$; |
| 1201 | \next |
| 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)$; |
| 1207 | \end{program} |
| 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: |
| 1211 | \begin{program} |
| 1212 | Algorithm $A^{T(\cdot), V(\cdot)}$: \\ |
| 1213 | $(x', \tau') \gets |
| 1214 | A'^{\Xid{T'}{sim}(\cdot), \Xid{V'}{sim}(\cdot)}$; \\ |
| 1215 | \PARSE $\tau'$ \AS $1\colon \tau_0, \tau$; \\ |
| 1216 | \RETURN $(x, \tau)$; |
| 1217 | \next |
| 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)$; |
| 1226 | \end{program} |
| 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) \]% |
| 1239 | as required. |
| 1240 | |
| 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: |
| 1243 | \begin{program} |
| 1244 | Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\ |
| 1245 | \RETURN $(0, 1, \bot)$; |
| 1246 | \next |
| 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^*$; \\ |
| 1250 | \RETURN $b$; |
| 1251 | \end{program} |
| 1252 | The leaky MAC simply tells us the right answer. So |
| 1253 | \[ \InSec{ftg-cpa}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}'}; |
| 1254 | t, 0) = 1, \]% |
| 1255 | where $t$ is the running time of adversary $B$ above. |
| 1256 | |
| 1257 | \end{itemize} |
| 1258 | |
| 1259 | This concludes the proof. |
| 1260 | \end{proof} |
| 1261 | |
| 1262 | %% TO DO: Include stuff about integrity-aware encryption modes some day. |
| 1263 | |
| 1264 | \endinput |
| 1265 | |
| 1266 | %%% Local Variables: |
| 1267 | %%% mode: latex |
| 1268 | %%% TeX-master: "ips" |
| 1269 | %%% End: |