\head{An obvious approach}
A simple approach would be to generate a random key for some secure (i.e.,
- IND-CCA) symmetric scheme, encrypt the message under that key, and, encrypt
- the key under the recipient's public key (using some IND-CCA2 public-key
- scheme).
+ IND-CCA2) symmetric scheme, encrypt the message under that key, and,
+ encrypt the key under the recipient's public key (using some IND-CCA2
+ public-key scheme).
This is obviously secure. But the security results for most public-key
schemes are less than encouraging: the reductions, even for OAEP+, are
\InSec{ind-cca2}(\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}; t, q_D) \\
& \le
2 \cdot \InSec{ohd}(\mathcal{K}; t + O(q_D), q_D) +
- \InSec{ftg-cca}(\mathcal{E}; t + O(q_D), 0, q_D).
+ \InSec{ftg-cca2}(\mathcal{E}; t + O(q_D), 0, q_D).
\end{eqnarray*}
Note how weak the security requirements on the encryption scheme are: no
chosen-plaintext queries are permitted!
simulation of $A$'s attack game, and hence wins with probability
\[ \frac{\Adv{ind-cca2}{\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}}}{2} +
\frac{1}{2}. \]%
- We construct a new adversary $C$, attacking $\mathcal{E}$ in the FTG-CCA
+ We construct a new adversary $C$, attacking $\mathcal{E}$ in the FTG-CCA2
sense, to help us bound $B$'s probability of success when $h$ is chosen
randomly.
\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
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}
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.
~mdw / doc / ips / commitdiff