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}
\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
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$; \\
\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}
\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.
$\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}$; \\
$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}$; \\
$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; \\
\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)$; \\
$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)$; \\
\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$; \\
\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
$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}
"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}
$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}
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
\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}
\bibliography{mdw-crypto,cryptography,cryptography2000,rfc}
\end{document}
-%%% Local Variables:
+%%% Local Variables:
%%% mode: latex
%%% TeX-master: "wrestlers"
%%% End:
~mdw / tripe / blobdiff