X-Git-Url: https://git.distorted.org.uk/~mdw/tripe/blobdiff_plain/b4e566689f469cc1cffe99e50e16a346d0f9832d..44e2927917faa9ab4ad4f3e4931d746192a241b0:/doc/wrestlers.tex?ds=inline

diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex
index 8d1c2a94..f2d9ac47 100644
--- a/doc/wrestlers.tex
+++ b/doc/wrestlers.tex
@@ -1,7 +1,5 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: wrestlers.tex,v 1.7 2004/04/08 01:36:17 mdw Exp $
-%%%
 %%% Description of the Wrestlers Protocol
 %%%
 %%% (c) 2001 Mark Wooding
@@ -186,7 +184,7 @@ order.
   with the property that, for any $K \in \keys \mathcal{E}$, any plaintext
   message $x$, and any ciphertext $y$ returned as a result of $E_K(x)$, we
   have $D_K(y) = x$.
-\end{definition}  
+\end{definition}
 
 \begin{definition}[Chosen plaintext security for symmetric encryption]
   \label{def:sym-cpa}
@@ -239,10 +237,10 @@ $g^\gamma$.  This is the \emph{decision Diffie-Hellman problem}
     \begin{eqnalign}[rl]
       \Adv{ddh}{G}(A) =
       & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q} :
-            A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
+	    A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
       & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q};
-            \gamma \getsr \Nupto{q} :
-            A(g^\alpha, g^\beta, g^\gamma) = 1].
+	    \gamma \getsr \Nupto{q} :
+	    A(g^\alpha, g^\beta, g^\gamma) = 1].
     \end{eqnalign}
   \end{equation}
   The \emph{insecurity function of the decision Diffie-Hellman problem in
@@ -362,7 +360,7 @@ and then decrypts the ciphertext $y$.
     Function $\id{decrypt}(k, \id{ty}, c)$: \+ \\
       $(i, y, \tau) \gets c$; \\
       \IF $V_{k.\Xid{K}{mac-in}}((\id{ty}, i, y), \tau) = 0$ \THEN \\ \ind
-        \RETURN $\bot$; \- \\
+	\RETURN $\bot$; \- \\
       \IF $i < k.\id{seq-in}$ \THEN \RETURN $\bot$; \\
       $m \gets D_{k.\Xid{K}{enc-in}}(y)$; \\
       $k.\id{seq-in} \gets i + 1$; \\
@@ -411,28 +409,28 @@ in figure~\ref{fig:kx-support}.
 
 \begin{table}
   \begin{tabularx}{\textwidth}{Mr X}
-    G                     & A cyclic group known by all participants \\
-    q = |G|               & The prime order of $G$ \\
-    g                     & A generator of $G$ \\
-    E_K(\cdot)            & Encryption under key $K$, here used to denote
-                            application of the $\id{encrypt}(K, \cdot)$
-                            operation \\ 
+    G			  & A cyclic group known by all participants \\
+    q = |G|		  & The prime order of $G$ \\
+    g			  & A generator of $G$ \\
+    E_K(\cdot)		  & Encryption under key $K$, here used to denote
+			    application of the $\id{encrypt}(K, \cdot)$
+			    operation \\
     \alpha \inr \Nupto{q} & Alice's private key \\
-    a = g^{\alpha}        & Alice's public key \\
+    a = g^{\alpha}	  & Alice's public key \\
     \rho_A \inr \Nupto{q} & Alice's secret Diffie-Hellman value \\
-    r_A = g^{\rho_A}      & Alice's public \emph{challenge} \\
+    r_A = g^{\rho_A}	  & Alice's public \emph{challenge} \\
     c_A = H(\cookie{cookie}, r_A)
-                          & Alice's \emph{cookie} \\
+			  & Alice's \emph{cookie} \\
     v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})
-                          & Alice's challenge \emph{check value} \\
+			  & Alice's challenge \emph{check value} \\
     r_B^\alpha = a^{\rho_B}
-                          & Alice's reply \\
+			  & Alice's reply \\
     K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}
-                          & Alice and Bob's shared secret key \\
+			  & Alice and Bob's shared secret key \\
     w_A = H(\cookie{switch-request}, c_A, c_B)
-                          & Alice's \emph{switch request} value \\
+			  & Alice's \emph{switch request} value \\
     u_A = H(\cookie{switch-confirm}, c_A, c_B)
-                          & Alice's \emph{switch confirm} value \\
+			  & Alice's \emph{switch confirm} value \\
   \end{tabularx}
 
   \caption{Names used during key-exchange}
@@ -452,7 +450,7 @@ in figure~\ref{fig:kx-support}.
   \caption{Message contents, as sent by Alice}
   \label{tab:kx-messages}
 \end{table}
-  
+
 \begin{messages}
 \item[kx-pre-challenge] Contains a plain statement of Alice's challenge.
   This is Alice's first message of a session.
@@ -641,33 +639,33 @@ clog up all of Alice's slots.
       $\id{send}(\cookie{kx-pre-challenge}, r_A)$; \- \\[\medskipamount]
     Procedure $\id{kx-receive}(\id{type}, \id{data})$: \\ \ind
       \IF $\id{type} = \cookie{kx-pre-challenge}$ \THEN \\ \ind
-        \id{msg-pre-challenge}(\id{data}); \- \\
+	\id{msg-pre-challenge}(\id{data}); \- \\
       \ELSE \IF $\id{type} = \cookie{kx-cookie}$ \THEN \\ \ind
-        \id{msg-cookie}(\id{data}); \- \\
+	\id{msg-cookie}(\id{data}); \- \\
       \ELSE \IF $\id{type} = \cookie{kx-challenge}$ \THEN \\ \ind
-        \id{msg-challenge}(\id{data}); \- \\
+	\id{msg-challenge}(\id{data}); \- \\
       \ELSE \IF $\id{type} = \cookie{kx-reply}$ \THEN \\ \ind
-        \id{msg-reply}(\id{data}); \- \\
+	\id{msg-reply}(\id{data}); \- \\
       \ELSE \IF $\id{type} = \cookie{kx-switch}$ \THEN \\ \ind
-        \id{msg-switch}(\id{data}); \- \\
+	\id{msg-switch}(\id{data}); \- \\
       \ELSE \IF $\id{type} = \cookie{kx-switch-ok}$ \THEN \\ \ind
-        \id{msg-switch-ok}(\id{data}); \-\- \\[\medskipamount]
+	\id{msg-switch-ok}(\id{data}); \-\- \\[\medskipamount]
     Procedure $\id{msg-pre-challenge}(\id{data})$: \+ \\
       \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
       $r \gets \id{data}$; \\
       \IF $\Xid{n}{chal} \ge \Xid{n}{chal-thresh}$ \THEN \\ \ind
-        $\id{send}(\cookie{kx-cookie}, r_A, \id{cookie}(r_A)))$; \- \\
+	$\id{send}(\cookie{kx-cookie}, r_A, \id{cookie}(r_A)))$; \- \\
       \ELSE \+ \\
-        $\id{new-chal}(r)$; \\
-        $\id{send}(\cookie{kx-challenge}, r_A,
-                   \id{cookie}(r), \id{checkval}(r))$; \-\-\\[\medskipamount]
+	$\id{new-chal}(r)$; \\
+	$\id{send}(\cookie{kx-challenge}, r_A,
+		   \id{cookie}(r), \id{checkval}(r))$; \-\-\\[\medskipamount]
     Procedure $\id{msg-cookie}(\id{data})$: \+ \\
       \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
       $(r, c_A) \gets \id{data}$; \\
       \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
       $\id{new-chal}(r)$; \\
       $\id{send}(\cookie{kx-challenge}, r_A,
-                 \id{cookie}(r), \id{checkval}(r))$; \- \\[\medskipamount]
+		 \id{cookie}(r), \id{checkval}(r))$; \- \\[\medskipamount]
     Procedure $\id{msg-challenge}(\id{data})$: \+ \\
       \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
       $(r, c_A, v) \gets \id{data}$; \\
@@ -677,7 +675,7 @@ clog up all of Alice's slots.
       $k \gets \id{chal-tab}[i].k$; \\
       $y \gets \id{encrypt}(k, \cookie{kx-reply}, r^\alpha)$; \\
       $\id{send}(\cookie{kx-reply}, c_A, \id{cookie}(r),
-                 \id{checkval}(r), y)$
+		 \id{checkval}(r), y)$
     \next
     Procedure $\id{msg-reply}(\id{data})$: \+ \\
       $(c, c_A, v, y) \gets \id{data}$; \\
@@ -685,7 +683,7 @@ clog up all of Alice's slots.
       $i \gets \id{find-chal}(c)$; \\
       \IF $i = \bot$ \THEN \RETURN; \\
       \IF $\id{check-reply}(i, \id{chal-tab}[i].r, v) = \bot$ \THEN \\ \ind
-        \RETURN; \- \\
+	\RETURN; \- \\
       $k \gets \id{chal-tab}[i].k$; \\
       $x \gets \id{decrypt}(k, \cookie{kx-reply}, y)$; \\
       \IF $x = \bot$ \THEN \RETURN; \\
@@ -706,8 +704,8 @@ clog up all of Alice's slots.
       \IF $x = \bot$ \THEN \RETURN; \\
       $(x, w) \gets x$; \\
       \IF $\id{state} = \cookie{challenge}$ \THEN \\ \ind
-        \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
-        $\id{chal-commit} \gets \id{chal-tab}[i]$; \- \\
+	\IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
+	$\id{chal-commit} \gets \id{chal-tab}[i]$; \- \\
       \ELSE \IF $c \ne \id{chal-commit}.c$ \THEN \RETURN; \\
       \IF $w \ne H(\cookie{switch-request}, c, c_A)$ \THEN \RETURN; \\
       $w \gets H(\cookie{switch-confirm}, c_A, c)$; \\
@@ -736,13 +734,13 @@ clog up all of Alice's slots.
       $r$; $c$; $\id{replied}$; $k$; \- \\[\medskipamount]
     Function $\id{find-chal}(c)$: \+ \\
       \FOR $i = 0$ \TO $\Xid{n}{chal}$ \DO \\ \ind
-        \IF $\id{chal-tab}[i].c = c$ \THEN \RETURN $i$; \- \\
+	\IF $\id{chal-tab}[i].c = c$ \THEN \RETURN $i$; \- \\
       \RETURN $\bot$; \- \\[\medskipamount]
     Function $\id{cookie}(r)$: \+ \\
       \RETURN $H(\cookie{cookie}, r)$; \- \\[\medskipamount]
     Function $\id{check-reply}(i, r, v)$: \+ \\
       \IF $i \ne \bot \land \id{chal-tab}[i].\id{replied} = 1$ \THEN \\ \ind
-        \RETURN $i$; \- \\
+	\RETURN $i$; \- \\
       $\rho \gets v \xor H(\cookie{expected-reply}, r, r_A, r^\alpha)$; \\
       \IF $g^\rho \ne r$ \THEN \RETURN $\bot$; \\
       \IF $i = \bot$ \THEN $i \gets \id{new-chal}(r)$; \\
@@ -752,17 +750,17 @@ clog up all of Alice's slots.
     \next
     Function $\id{checkval}(r)$: \\ \ind
       \RETURN $\rho_A \xor H(\cookie{expected-reply},
-                             r_A,r, b^{\rho_A})$; \- \\[\medskipamount]
+			     r_A,r, b^{\rho_A})$; \- \\[\medskipamount]
     Function $\id{new-chal}(r)$: \+ \\
       $c \gets \id{cookie}(r)$; \\
       $i \gets \id{find-chal}(c)$; \\
       \IF $i \ne \bot$ \THEN \RETURN $i$; \\
       \IF $\Xid{n}{chal} < \Xid{n}{chal-max}$ \THEN \\ \ind
-        $i \gets \Xid{n}{chal}$; \\
-        $\id{chal-tab}[i] \gets \NEW \id{chal-slot}$; \\
-        $\Xid{n}{chal} \gets \Xid{n}{chal} + 1$; \- \\
+	$i \gets \Xid{n}{chal}$; \\
+	$\id{chal-tab}[i] \gets \NEW \id{chal-slot}$; \\
+	$\Xid{n}{chal} \gets \Xid{n}{chal} + 1$; \- \\
       \ELSE \\ \ind
-        $i \getsr [\Xid{n}{chal-max}]$; \- \\
+	$i \getsr [\Xid{n}{chal-max}]$; \- \\
       $\id{chal-tab}[i].r \gets r$; \\
       $\id{chal-tab}[i].c \gets c$; \\
       $\id{chal-tab}[i].\id{replied} \gets 0$; \\
@@ -835,7 +833,7 @@ See figure~\ref{fig:cbc} for a diagram of CBC encryption.
   \caption{Encryption using CBC mode}
   \label{fig:cbc}
 \end{figure}
-    
+
 \begin{definition}[CBC mode]
   \label{def:cbc}
   Let $P\colon \keys P \times \Bin^\ell to \Bin^\ell$ be a pseudorandom
@@ -848,20 +846,20 @@ See figure~\ref{fig:cbc} for a diagram of CBC encryption.
       $I \getsr \Bin^\ell$; \\
       $y \gets I$; \\
       \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
-        $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
-        $y_i \gets P_K(x_i \xor I)$; \\
-        $I \gets y_i$; \\
-        $y \gets y \cat y_i$; \- \\
+	$x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
+	$y_i \gets P_K(x_i \xor I)$; \\
+	$I \gets y_i$; \\
+	$y \gets y \cat y_i$; \- \\
       \RETURN $y$;
     \next
     Algorithm $\Xid{D}{CBC}^P_K(y)$: \+ \\
       $I \gets y[0 \bitsto \ell]$; \\
       $x \gets \emptystring$; \\
       \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
-        $y_i \gets y[\ell i  \bitsto  \ell (i + 1)]$; \\
-        $x_i \gets P^{-1}_K(y_i) \xor I$; \\
-        $I \gets y_i$; \\
-        $x \gets x \cat x_i$; \- \\
+	$y_i \gets y[\ell i  \bitsto  \ell (i + 1)]$; \\
+	$x_i \gets P^{-1}_K(y_i) \xor I$; \\
+	$I \gets y_i$; \\
+	$x \gets x \cat x_i$; \- \\
       \RETURN $x$;
   \end{program}
 \end{definition}
@@ -925,39 +923,39 @@ figure~\ref{fig:cbc-steal} for a diagram.
       "e" [dd] ="x"
       "i" [uu] ="y"
       []!{"x"; "e" **{}, "x"+/4pt/ ="p",
-          "x"; "y" **{}, "x"+/4pt/ ="q",
-          "y"; "x" **{}, "y"+/4pt/ ="r",
-          "y"; "i" **{}, "y"+/4pt/ ="s",
-          "e";
-          "p" **\dir{-};
-          "q" **\crv{"x"};
-          "r" **\dir{-};
-          "s" **\crv{"y"};
-          "i" **\dir{-}?>*\dir{>}}
+	  "x"; "y" **{}, "x"+/4pt/ ="q",
+	  "y"; "x" **{}, "y"+/4pt/ ="r",
+	  "y"; "i" **{}, "y"+/4pt/ ="s",
+	  "e";
+	  "p" **\dir{-};
+	  "q" **\crv{"x"};
+	  "r" **\dir{-};
+	  "s" **\crv{"y"};
+	  "i" **\dir{-}?>*\dir{>}}
       "xor" :[dd] *+[F]{E}="e"
       "e" [l] {K} :"e"
       "e" [dddddlll] *+=(1, 0)+[F]{\mathstrut y_{n-2}}="i"
       "e" [dd] ="x"
       "i" [uu] ="y"
       []!{"x"; "e" **{}, "x"+/4pt/ ="p",
-          "x"; "y" **{}, "x"+/4pt/ ="q",
-          "y"; "x" **{}, "y"+/4pt/ ="r",
-          "y"; "i" **{}, "y"+/4pt/ ="s",
-          "x"; "y" **{} ?="c" ?(0.5)/-4pt/ ="cx" ?(0.5)/4pt/ ="cy",
-          "e";
-          "p" **\dir{-};
-          "q" **\crv{"x"};
-          "cx" **\dir{-};
-          "c" *[@]\cir<4pt>{d^u};
-          "cy";
-          "r" **\dir{-};
-          "s" **\crv{"y"};
-          "i" **\dir{-}?>*\dir{>}}
+	  "x"; "y" **{}, "x"+/4pt/ ="q",
+	  "y"; "x" **{}, "y"+/4pt/ ="r",
+	  "y"; "i" **{}, "y"+/4pt/ ="s",
+	  "x"; "y" **{} ?="c" ?(0.5)/-4pt/ ="cx" ?(0.5)/4pt/ ="cy",
+	  "e";
+	  "p" **\dir{-};
+	  "q" **\crv{"x"};
+	  "cx" **\dir{-};
+	  "c" *[@]\cir<4pt>{d^u};
+	  "cy";
+	  "r" **\dir{-};
+	  "s" **\crv{"y"};
+	  "i" **\dir{-}?>*\dir{>}}
   \end{graph} \]
 
   \caption{Encryption using CBC mode with ciphertext stealing}
   \label{fig:cbc-steal}
-\end{figure}  
+\end{figure}
 
 \begin{definition}[CBC stealing]
   \label{def:cbc-steal}
@@ -974,34 +972,34 @@ figure~\ref{fig:cbc-steal} for a diagram.
       $t = |x| \bmod \ell$; \\
       \IF $t \ne 0$ \THEN $x \gets x \cat 0^{\ell-t}$; \\
       \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
-        $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
-        $y_i \gets P_K(x_i \xor I)$; \\
-        $I \gets y_i$; \\
-        $y \gets y \cat y_i$; \- \\
+	$x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
+	$y_i \gets P_K(x_i \xor I)$; \\
+	$I \gets y_i$; \\
+	$y \gets y \cat y_i$; \- \\
       \IF $t \ne 0$ \THEN \\ \ind
-        $b \gets |y| - 2\ell$; \\
-        $y \gets $\=$y[0 \bitsto b] \cat
-                     y[b + \ell \bitsto |y|] \cat {}$ \\
-                  \>$y[b \bitsto b + t]$; \- \\
+	$b \gets |y| - 2\ell$; \\
+	$y \gets $\=$y[0 \bitsto b] \cat
+		     y[b + \ell \bitsto |y|] \cat {}$ \\
+		  \>$y[b \bitsto b + t]$; \- \\
       \RETURN $y$;
     \next
     Algorithm $\Xid{D}{CBC-steal}^P_K(y)$: \+ \\
       $I \gets y[0 \bitsto \ell]$; \\
       $t = |y| \bmod \ell$; \\
       \IF $t \ne 0$ \THEN \\ \ind
-        $b \gets |y| - t - \ell$; \\
-        $z \gets P^{-1}_K(y[b \bitsto b + \ell])$; \\
-        $y \gets $\=$y[0 \bitsto b] \cat
-                     y[b + \ell \bitsto |y|] \cat {}$ \\
-                  \>$z[t \bitsto \ell]$; \- \\
+	$b \gets |y| - t - \ell$; \\
+	$z \gets P^{-1}_K(y[b \bitsto b + \ell])$; \\
+	$y \gets $\=$y[0 \bitsto b] \cat
+		     y[b + \ell \bitsto |y|] \cat {}$ \\
+		  \>$z[t \bitsto \ell]$; \- \\
       $x \gets \emptystring$; \\
       \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
-        $y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\
-        $x_i \gets P^{-1}_K(y_i) \xor I$; \\
-        $I \gets y_i$; \\
-        $x \gets x \cat x_i$; \- \\
+	$y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\
+	$x_i \gets P^{-1}_K(y_i) \xor I$; \\
+	$I \gets y_i$; \\
+	$x \gets x \cat x_i$; \- \\
       \IF $t \ne 0$ \THEN \\ \ind
-        $x \gets x \cat z[0 \bitsto t] \xor y[b \bitsto b + t]$; \- \\
+	$x \gets x \cat z[0 \bitsto t] \xor y[b \bitsto b + t]$; \- \\
       \RETURN $x$;
   \end{program}
 \end{definition}
@@ -1038,9 +1036,9 @@ figure~\ref{fig:cbc-steal} for a diagram.
     Function $\id{steal}(l, y)$: \+ \\
       $t \gets l \bmod \ell$; \\
       \IF $t \ne 0$ \THEN \\ \ind
-        $b \gets |y| - 2\ell$; \\
-        $y \gets $\=$y[0 \bitsto b] \cat
-                     y[b + \ell \bitsto |y|] \cat y[b \bitsto b + t]$; \- \\
+	$b \gets |y| - 2\ell$; \\
+	$y \gets $\=$y[0 \bitsto b] \cat
+		     y[b + \ell \bitsto |y|] \cat y[b \bitsto b + t]$; \- \\
       \RETURN $y$;
   \end{program}
   Comparing this to definition~\ref{def:cbc-steal} shows that $A'$ simlates
@@ -1093,9 +1091,9 @@ $2^\ell$ possible values for $y^*$ and in the second there are $2^\ell - n +
   \Pr[C_n]
   & = \sum_{x \in \Bin^\ell} \Pr[C_n \mid x^* = x] \Pr[x^* = x] \\
   & = \sum_{x \in \Bin^\ell}
-          \Pr[x^* = x] \sum_{0\le i<n} \Pr[y^* = z_i \xor x] \\
+	  \Pr[x^* = x] \sum_{0\le i<n} \Pr[y^* = z_i \xor x] \\
   & \le \sum_{0\le i<n} \frac{1}{2^\ell - n}
-        \sum_{x \in \Bin^\ell} \Pr[x^* = x] \\
+	\sum_{x \in \Bin^\ell} \Pr[x^* = x] \\
   & = \frac{n}{2^\ell - n}
 \end{eqnarray}
 
@@ -1141,7 +1139,7 @@ as required.
 \bibliography{mdw-crypto,cryptography,cryptography2000,rfc}
 \end{document}
 
-%%% Local Variables: 
+%%% Local Variables:
 %%% mode: latex
 %%% TeX-master: "wrestlers"
 %%% End:
