From d7891575df8f6673b4e4f65d556a171d8aab2ba0 Mon Sep 17 00:00:00 2001 From: mdw Date: Wed, 17 Jul 2002 08:52:06 +0000 Subject: [PATCH] Various small fixes. --- configure.in | 7 +++++-- enc-ies.tex | 10 +++++----- enc-symm.tex | 65 +++++++++++++++++++++++++++++++----------------------------- 3 files changed, 44 insertions(+), 38 deletions(-) diff --git a/configure.in b/configure.in index 463dd78..f5643d0 100644 --- a/configure.in +++ b/configure.in @@ -1,6 +1,6 @@ dnl -*-fundamental-*- dnl -dnl $Id: configure.in,v 1.1 2002/02/24 15:43:20 mdw Exp $ +dnl $Id: configure.in,v 1.2 2002/07/17 08:52:06 mdw Exp $ dnl dnl Dummy configuration script for ips dnl @@ -26,12 +26,15 @@ dnl Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. dnl ----- Revision history -------------------------------------------------- dnl dnl $Log: configure.in,v $ +dnl Revision 1.2 2002/07/17 08:52:06 mdw +dnl Various small fixes. +dnl dnl Revision 1.1 2002/02/24 15:43:20 mdw dnl New build system. dnl AC_INIT(ips.tex) -AM_INIT_AUTOMAKE(ips, 1.1.0) +AM_INIT_AUTOMAKE(ips, 1.1.1) AC_OUTPUT(Makefile) dnl ----- That's all, folks ------------------------------------------------- diff --git a/enc-ies.tex b/enc-ies.tex index 7150019..3f53936 100644 --- a/enc-ies.tex +++ b/enc-ies.tex @@ -29,9 +29,9 @@ in \cite{Abdalla:2001:DHIES}. \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 @@ -322,7 +322,7 @@ in \cite{Abdalla:2001:DHIES}. \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! @@ -349,7 +349,7 @@ in \cite{Abdalla:2001:DHIES}. 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} diff --git a/enc-symm.tex b/enc-symm.tex index 6434b4f..e3ec156 100644 --- a/enc-symm.tex +++ b/enc-symm.tex @@ -404,7 +404,7 @@ 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: @@ -421,12 +421,12 @@ 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 @@ -438,25 +438,28 @@ 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 @@ -808,7 +811,7 @@ 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} @@ -1016,7 +1019,7 @@ 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. @@ -1048,7 +1051,7 @@ 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)$: \+ \\ @@ -1073,9 +1076,9 @@ 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)$: \+ \\ @@ -1085,8 +1088,8 @@ 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 @@ -1147,8 +1150,8 @@ \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. -- 2.11.0