protocol requires only two messages -- a challenge and a response -- and has
a number of useful properties. It is very similar to, though designed
independently of, a recent protocol by Stinson and Wu
-\cite{Stinson:2006:EST}; we discuss their protocol and compare it to ours in
-\ifshort the full version of this paper. \else
+\cite{cryptoeprint:2006:337}; we discuss their protocol and compare it to
+ours in \ifshort the full version of this paper. \else
section~\ref{sec:stinson-ident}. \fi
Identification protocols are typically less useful than they sound. As Shoup
-\cite{Shoup:1999:OFM} points out, it provides a `secure ping', by which Bob
-can know that Alice is `there', but provides no guarantee that any other
-communication was sent to or reached her. However, there are situations
-where this an authentic channel between two entities -- e.g., a device and a
-smartcard -- where a simple identification protocol can still be useful.
+\cite{cryptoeprint:1999:012} points out, it provides a `secure ping', by
+which Bob can know that Alice is `there', but provides no guarantee that any
+other communication was sent to or reached her. However, there are
+situations where this an authentic channel between two entities -- e.g., a
+device and a smartcard -- where a simple identification protocol can still be
+useful.
An authenticated key-exchange protocol lets Alice and Bob agree on a shared
secret, known to them alone, even if there is an enemy who can read and
tells us nothing at all about the security of a particular instance of a
protocol, or what parameter sizes one needs to choose for a given level of
security against a particular kind of adversary. Koblitz and Menezes
-\cite{Koblitz:2006:ALP} (among other useful observations) give examples of
-protocols, proven to meet asymptotic notions of security, whose security
+\cite{cryptoeprint:2006:229} (among other useful observations) give examples
+of protocols, proven to meet asymptotic notions of security, whose security
proofs guarantee nothing at all for the kinds of parameters typically used in
practice.
protocol, we follow here the `practice-oriented provable security' approach
largely inspired by Bellare and Rogaway, and exemplified by
\cite{Bellare:1994:SCB,Bellare:1995:XMN,Bellare:1995:OAE,Bellare:1996:ESD,%
-Bellare:1996:KHF,Bellare:2000:CST}; see also \cite{Bellare:1999:POP}.
+Bellare:1996:KHF,Bellare:1997:CST}; see also \cite{Bellare:1999:POP}.
Rather than attempting to say, formally, whether or not a protocol is
`secure', we associate with each protocol an `insecurity function' which
gives an upper bound on the advantage of any adversary attacking the protocol
The first model for studying the \emph{computational} security of
key-exchange protocols (rather than using protocol-analysis logics like that
-of \cite{Burrows:1989:LA}) was given by Bellare and Rogaway
+of \cite{Burrows:1989:LAa}) was given by Bellare and Rogaway
\cite{Bellare:1994:EAK}; the model has since been enhanced, both by the
original authors and others, in \cite{Bellare:1995:PSS,%
Blake-Wilson:1997:KAP,Blake-Wilson:1998:EAA}. The model defines security
in terms of a game: key-exchange protocols are secure if an adversary can't
distinguish the key agreed by a chosen `challenge session' from a key chosen
independently at random. Other models for key-exchange have been proposed in
-\cite{Bellare:1998:MAD} and \cite{Shoup:1999:OFM}; these use a different
-notion of security, involving implementation of an ideal functionality.
+\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}; these use a
+different notion of security, involving implementation of an ideal
+functionality.
\else
Many proposed key-exchange protocols have turned out to have subtle security
flaws. The idea of using formal methods to analyse key-exchange protocols
-begins with the logic of Burrows, Abadi and Needham \cite{Burrows:1989:LA}.
+begins with the logic of Burrows, Abadi and Needham \cite{Burrows:1989:LAa}.
Their approach requires a `formalising' step, in which one expresses in the
logic the contents of the message flows, and the \emph{beliefs} of the
participants.
ideal adversary~$I$, such that the outputs of $A$ and $I$ are computationally
indistinguishable.
-In \cite{Shoup:1999:OFM}, Shoup presents a new model for key-exchange, also
-based on the idea of simulation. He analyses the previous models,
+In \cite{cryptoeprint:1999:012}, Shoup presents a new model for key-exchange,
+also based on the idea of simulation. He analyses the previous models,
particularly \cite{Bellare:1994:EAK} and \cite{Bellare:1998:MAD}, and
highlights some of their inadequacies.
\fi
-Canetti and Krawczyk \cite{Canetti:2001:AKE} describe a new notion of
-security in the model of \cite{Bellare:1998:MAD}, based on the
+Canetti and Krawczyk \cite{cryptoeprint:2001:040,Canetti:2001:AKE} describe a
+new notion of security in the model of \cite{Bellare:1998:MAD}, based on the
challenge-session notion of \cite{Bellare:1994:EAK}. The security notion,
called `SK-security', seems weaker in various ways than those of earlier
-works such as \cite{Bellare:1994:EAK} or \cite{Shoup:1999:OFM}. However, the
-authors show that their notion suffices for constructing `secure channel'
-protocols, which they also define.
+works such as \cite{Bellare:1994:EAK} or \cite{cryptoeprint:1999:012}.
+However, the authors show that their notion suffices for constructing `secure
+channel' protocols, which they also define.
\ifshort\else
In \cite{Canetti:2001:UCS}, Canetti describes the `universal composition'
parties using the ideal functionality such that no `environment' can
distinguish the two. The environment is allowed to interact freely with the
adversary throughout, differentiating this approach from that of
-\cite{Bellare:1998:MAD} and \cite{Shoup:1999:OFM}, where the distinguisher
-was given only transcripts of the adversary's interaction with the parties.
-With security defined in this way, it's possible to prove a `universal
-composition theorem': one can construct a protocol, based upon various ideal
-functionalities, and then `plug in' secure implementations of the ideal
-functionalities and appeal to the theorem to prove the security of the entire
-protocol. The UC framework gives rise to very strong notions of security,
-due to the interactive nature of the `environment' distinguisher.
+\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}, where the
+distinguisher was given only transcripts of the adversary's interaction with
+the parties. With security defined in this way, it's possible to prove a
+`universal composition theorem': one can construct a protocol, based upon
+various ideal functionalities, and then `plug in' secure implementations of
+the ideal functionalities and appeal to the theorem to prove the security of
+the entire protocol. The UC framework gives rise to very strong notions of
+security, due to the interactive nature of the `environment' distinguisher.
\fi
Canetti and Krawczyk \cite{Canetti:2002:UCN} show that the SK-security notion
distinguish between the two except with very small probability.
Our proofs make frequent use of sequences of games; see
-\cite{Shoup:2004:SGT,Bellare:2004:CBG}. The presentation owes much to Shoup
-\cite{Shoup:2004:SGT}. We begin with a game $\G0$ based directly on a
-relevant security definition, and construct a sequence of games $\G1$, $\G2$,
-\dots, each slightly different from the last. We define all of the games in
-a sequence over the same underlying probability space -- the random coins
-tossed by the algorithms involved -- though different games may have slightly
-differently-defined events and random variables. Our goal in doing this is
-to bound the probability of the adversary winning the initial game $\G0$ by
-simultaneously (a) relating the probability of this event to that of
-corresponding events in subsequent games, and (b) simplifying the game until
-the probability of the corresponding event can be computed directly.
+\cite{cryptoeprint:2004:332,cryptoeprint:2004:331}. The presentation owes
+much to Shoup \cite{cryptoeprint:2004:332}. We begin with a game $\G0$ based
+directly on a relevant security definition, and construct a sequence of games
+$\G1$, $\G2$, \dots, each slightly different from the last. We define all of
+the games in a sequence over the same underlying probability space -- the
+random coins tossed by the algorithms involved -- though different games may
+have slightly differently-defined events and random variables. Our goal in
+doing this is to bound the probability of the adversary winning the initial
+game $\G0$ by simultaneously (a) relating the probability of this event to
+that of corresponding events in subsequent games, and (b) simplifying the
+game until the probability of the corresponding event can be computed
+directly.
The following simple lemma from \cite{Shoup:2001:OR} will be frequently
useful.
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:1985:PKC}. We can easily apply their
+encryption scheme \cite{ElGamal:1985:PKCb}. 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}
\label{sec:stinson-ident}
Our protocol is similar to a recent proposal by Stinson and Wu
-\cite{Stinson:2006:EST}. They restrict their attention to Schnorr groups $G
-\subset \F_p^*$. Let $\gamma$ be an element of order $q = \#G$. The
-prover's private key is $a \inr \gf{q}$ and her public key is $\alpha =
-\gamma^a$. In their protocol, the challenger chooses $r \inr \gf{q}$, computes
-$\rho = \gamma^r$ and $\psi = \alpha^r$, and sends a challenge $(\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.
+\cite{cryptoeprint:2006:337}. They restrict their attention to Schnorr
+groups $G \subset \F_p^*$. Let $\gamma$ be an element of order $q = \#G$.
+The prover's private key is $a \inr \gf{q}$ and her public key is
+$\alpha = \gamma^a$. In their protocol, the challenger chooses
+$r \inr \gf{q}$, computes $\rho = \gamma^r$ and $\psi = \alpha^r$, and sends
+a challenge $(\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
unnecessary for our protocol, since we can present an \emph{explicit}
extractor.
-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(\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'.
+The KEA assumption as stated in \cite{cryptoeprint:2006:337} 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(\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'.
Our protocol is just as strong as Stinson-Wu under attack from active
intruders: see table~\ref{tab:wident-active} for a very brief sketch of the
receives an invalid message, but we prefer to ignore invalid messages for the
sake of robustness.\footnote{%
Note that this protocol would therefore require modification before it was
- acceptable in the simulation-based model of \cite{Shoup:1999:OFM}. There
- it is required that a key-exchange protocol terminate after a
+ acceptable in the simulation-based model of \cite{cryptoeprint:1999:012}.
+ There it is required that a key-exchange protocol terminate after a
polynomially-bounded number of messages are delivered to it.}
\begin{figure}
protocol.
Our notion of deniability is taken from Di~Raimondo, Gennaro and Krawczyk
-\cite{DiRaimondo:2006:DAK}, except that, as usual, we opt for a concrete
+\cite{cryptoeprint:2006:280}, except that, as usual, we opt for a concrete
security approach.
\subsubsection{Discussion}
nontrivial.) However, injecting packets with bogus source addresses is very
easy.
-Layering the protocol over TCP \cite{RFC0793} ameliorates this problem because
+Layering the protocol over TCP \cite{rfc793} ameliorates this problem because
an adversary needs to guess or eavesdrop in order to obtain the correct
sequence numbers for a spoofed packet; but the Wrestlers protocol is
sufficiently simple that we'd like to be able to run it over UDP
-\cite{RFC0768}, for which spoofing is trivial.
+\cite{rfc768}, for which spoofing is trivial.
Therefore, it's possible for anyone on the 'net to send Alice a spurious
challenge message $(R, c)$. She will then compute $Y = a R$, recover $r' = c
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
+\cite{Rogaway:2003:OBC,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a
great imposition.
\subsubsection{Optimization and piggybacking}
\end{itemize}
\subsubsection{Unreliable transports}
-The Internet UDP \cite{RFC0768} is a simple, unreliable protocol for
+The Internet UDP \cite{rfc768} is a simple, unreliable protocol for
transmitting datagrams. However, it's very efficient, and rather attractive
as a transport for datagram-based applications such as virtual private
networks (VPNs). Since UDP is a best-effort rather than a reliable
%%%--------------------------------------------------------------------------
-\bibliography{mdw-crypto,cryptography2000,cryptography,rfc,std}
+\bibliography{%
+ mdw-crypto,%
+ eprint,%
+ focs1990,stoc1990,tissec,jacm,%
+ lncs1997a,lncs1997b,lncs1998a,lncs2001a,%
+ cryptography1990,cryptography2000,cryptography2010,cryptography,%
+ rfc,std}
%%%--------------------------------------------------------------------------
~mdw / doc / wrestlers / commitdiff