\usepackage[within = subsection, mdwmargin]{mdwthm}
\usepackage{mdwlist}
\usepackage{sverb}
- \PassOptionsToPackage{dvips}{xy}
+ \if0\ifx\pdfoutput\xxundefined0\else\the\pdfoutput\fi
+ \PassOptionsToPackage{dvips}{xy}
+ \fi
\else
\documentclass[a4paper]{llncs}
\usepackage{a4wide}
%%%--------------------------------------------------------------------------
\maketitle
+\iffancystyle \thispagestyle{empty} \fi
\begin{abstract}
We describe and prove (in the random-oracle model) the security of a simple
\iffancystyle
\newpage
+\thispagestyle{empty}
\columnsep=2em \columnseprule=0pt
\tableofcontents[\begin{multicols}{2}\raggedright][\end{multicols}]
%%\listoffigures[\begin{multicols}{2}\raggedright][\end{multicols}]
\end{itemize}
Our key-exchange protocol also has a number of desirable
-properties.\footnote{%
- We don't claim resistance to `key-compromise impersonation' (KCI) attacks.
- To perform a KCI attack, an adversary learns a party's -- say Alice's --
- secret and somehow uses this to impersonate Bob to Alice. Our model
- doesn't consider this to be a legitimate attack. The purpose of a
- key-exchange protocol is to provide a shared secret for some other,
- high-level protocol between the participants. If one of the parties is
- already corrupted -- i.e., the adversary could be impersonating her -- then
- it is impossible for us to make any meaningful security statement about the
- high-level protocol anyway, so it seems unreasonable to expect the
- key-exchange protocol to cope.}
+properties.
\begin{itemize}
\item It is fairly \emph{simple} to understand and implement, though there
are a few subtleties. In particular, it is \emph{symmetrical}. We have
authors show that their notion suffices for constructing `secure channel'
protocols, which they also define.
-In \cite{Canetti:2001:UCP}, Canetti describes the `universal composition'
+In \cite{Canetti:2001:UCS}, Canetti describes the `universal composition'
framework. Here, security notions are simulation-based: one defines security
notions by presenting an `ideal functionality'. A protocol securely
implements a particular functionality if, for any adversary interacting with
(Our protocols can be modified to make use of bilinear pairings so as to
provide identity-based identification and key-exchange, using the techniques
-of \cite{Boneh:2001:IBE}. Proving the security of the modifications we
+of \cite{Boneh:2003:IBE}. Proving the security of the modifications we
discuss would involve `programming' random oracles, but this doesn't affect
the zero-knowledge or deniability of the resulting protocols.)
\subsection{An identity-based identification scheme}
\label{sec:wident-id}
-Boneh and Franklin \cite{Boneh:2001:IBE} showed how to construct an
+Boneh and Franklin \cite{Boneh:2003:IBE} showed how to construct an
identity-based encryption scheme using bilinear pairings. The resulting
encryption scheme looks somewhat like a pairing-based version of ElGamal's
-encryption scheme \cite{ElGamal:1984:PKC}. We can easily apply their
+encryption scheme \cite{ElGamal:1985:PKC}. We can easily apply their
techniques to our identification protocol, and thereby obtain an
identity-based identification scheme. Providing the necessary formalisms to
prove theorems analogous to our theorems~\ref{thm:wident-sound}
\subsubsection{Bilinear pairings}
Before we describe the necessary modifications to the protocol, we first give
a (very brief!) summary of cryptographic pairings. (The Boneh-Franklin paper
-\cite{Boneh:2001:IBE} gives more detail; also \cite{Menezes:2006:IPB}
+\cite{Boneh:2003:IBE} gives more detail; also \cite{Menezes:2005:IPB}
provides a useful introduction to the topic.)
Let $(G, +)$, $(G', +)$ and $(G_T, \times)$ be cyclic groups with prime order
prover's private key is $a \inr \Nupto{q}$ and her public key is $\alpha =
\gamma^a$. In their protocol, the challenger chooses $r \inr \Nupto{q}$,
computes $\rho = \gamma^r$ and $\psi = \alpha^r$, and sends a challenge
-$(\rho, H(\rho, \psi))$. The prover checks that $\rho^q \ne 1$, computes
-$\psi = \rho^a$, checks the hash, and sends $\psi$ back by way of response.
-They prove their protocol's security in the random-oracle model.
+$(\rho, H(\psi))$. The prover checks that $\rho^q \ne 1$, computes $\psi =
+\rho^a$, checks the hash, and sends $\psi$ back by way of response. They
+prove their protocol's security in the random-oracle model.
Both the Wrestlers protocol and Stinson-Wu require both prover and verifier
to compute two exponentiations (or scalar multiplications) each. The
The KEA assumption as stated in \cite{Stinson:2006:EST} allows the extractor
to fail with some negligible probability, over and above the probability that
-a dishonest verifier managed to guess the correct $h = H(\rho, \psi)$ without
+a dishonest verifier managed to guess the correct $h = H(\psi)$ without
making this random-oracle query. Not only does our protocol achieve zero-
knowledge without the KEA, our extractor is, in this sense, `perfect'.
implement the modified protocol. This is certainly possible, since the
messages contain (hashes of) public values. We omit the details.
+However, while the extra message doesn't affect the security of our protocol,
+it would be annoying if an adversary could forge the switch request message,
+since this would be a denial of service. In the strong adversarial model,
+this doesn't matter, since the adversary can deny service anyway, but it's a
+concern against less powerful adversaries. Most IND-CCA symmetric encryption
+schemes also provide integrity of plaintexts \cite{Bellare:2000:AER} (e.g.,
+the encrypt-then-MAC generic composition approach \cite{Bellare:2000:AER,%
+Krawczyk:2001:OEA}, and the authenticated-encryption modes of
+\cite{Rogaway:2003:OCB,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a
+great imposition.
+
\subsubsection{Optimization and piggybacking}
We can optimize the number of messages sent by combining them. Here's one
possible collection of combined messages:
\subsubsection{Key reuse}
Suppose our symmetric encryption scheme $\E$ is not only IND-CCA secure
(definition~\ref{def:ind-cca}) but also provides integrity of plaintexts
-\cite{Bellare:2000:AER} (or, alternatively, is an AEAD scheme \fixme{AEAD
-cite}) Then we can use it to construct a secure channel, by including message
-type and sequence number fields in the plaintexts, along with the message
-body. If we do this, we can actually get away with just the one key $K =
-H_K(Z)$ rather than both $K_0$ and $K_1$.
+\cite{Bellare:2000:AER} (or, alternatively, is an AEAD scheme
+\cite{Rogaway:2002:AEA}. Then we can use it to construct a secure channel,
+by including message type and sequence number fields in the plaintexts, along
+with the message body. If we do this, we can actually get away with just the
+one key $K = H_K(Z)$ rather than both $K_0$ and $K_1$.
To do this, it is essential that the plaintext messages (or additional data)
clearly distinguish between the messages sent as part of the key-exchange
protocol and messages sent over the `secure channel'. Otherwise, there is a
-protocol-interference attack: an adversary can replay key-exchange ciphertexts
-to insert the corresponding plaintexts into the channel.
+protocol-interference attack: an adversary can replay key-exchange
+ciphertexts to insert the corresponding plaintexts into the channel.
We offer a sketch proof of this claim in appendix~\ref{sec:sc-proof}.
%%%--------------------------------------------------------------------------
-\bibliography{mdw-crypto,cryptography2000,cryptography,rfc}
+\bibliography{mdw-crypto,cryptography2000,cryptography,rfc,std}
%%%--------------------------------------------------------------------------