X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/tripe/blobdiff_plain/b4e566689f469cc1cffe99e50e16a346d0f9832d..494a7ac04de2a38bf6aade234602f831be314c55:/doc/wrestlers.tex 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