From 4331bf844ebc460672f36174f706e4de144dba6c Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Tue, 3 Oct 2017 03:33:10 +0100 Subject: [PATCH] wrestlers.tex: Fix citations to catch up with Bibtex database changes. --- wrestlers.tex | 134 +++++++++++++++++++++++++++++++--------------------------- 1 file changed, 72 insertions(+), 62 deletions(-) diff --git a/wrestlers.tex b/wrestlers.tex index 63e428e..8a05c61 100644 --- a/wrestlers.tex +++ b/wrestlers.tex @@ -214,16 +214,17 @@ of recognising Alice; for instance, he might know her public key. Our 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 @@ -285,8 +286,8 @@ connections to complexity theory. Unfortunately, such an asymptotic result 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. @@ -294,7 +295,7 @@ Since, above all, we're interested in analysing a practical and implemented 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 @@ -307,21 +308,22 @@ within given resource bounds. 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. @@ -363,20 +365,20 @@ if, for any adversary~$A$ in the \textsc{am} or \textsc{um}, there is an 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' @@ -387,14 +389,14 @@ parties who use the protocol, there is an adversary which interacts with 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 @@ -542,17 +544,18 @@ winning, or we consider two different games and require that no adversary can 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. @@ -1835,7 +1838,7 @@ The following two trivial lemmata will be useful, both now and later. 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} @@ -1918,14 +1921,14 @@ through the details. \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 @@ -1950,11 +1953,12 @@ high probability. This is a very strong assumption, and one which is 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 @@ -2360,8 +2364,8 @@ We observe that the protocol never aborts. We could make it do so if it 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} @@ -2573,7 +2577,7 @@ the protocol's symmetry), and prove the deniability of the resulting 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} @@ -2913,11 +2917,11 @@ are tricks one can play involving subversion of DNS servers, but this is also 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 @@ -2984,7 +2988,7 @@ 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 +\cite{Rogaway:2003:OBC,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a great imposition. \subsubsection{Optimization and piggybacking} @@ -3006,7 +3010,7 @@ The combination is safe: \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 @@ -3076,7 +3080,13 @@ Clive Jones and I worked out the initial design. %%%-------------------------------------------------------------------------- -\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} %%%-------------------------------------------------------------------------- -- 2.11.0