X-Git-Url: https://git.distorted.org.uk/~mdw/doc/wrestlers/blobdiff_plain/d8139f2c31e93c80a17e6edf2b19b9344ab18b56..HEAD:/wrestlers.tex diff --git a/wrestlers.tex b/wrestlers.tex index 2ee5702..4705316 100644 --- a/wrestlers.tex +++ b/wrestlers.tex @@ -5,35 +5,41 @@ %%% (c) 2006 Mark Wooding %%% -\newif\iffancystyle\fancystylefalse -\newif\ifshort\shortfalse -\fancystyletrue -\InputIfFileExists{wr.cfg}\relax\relax +\makeatletter +\def\@doit#1{#1} +\ifx\iffancystyle\xxundefined\expandafter\@doit\else\expandafter\@gobble\fi +{\newif\iffancystyle\fancystyletrue} +\ifx\ifshort\xxundefined\expandafter\@doit\else\expandafter\@gobble\fi +{\newif\ifshort\shortfalse} +\iffancystyle\expandafter\@gobble\else\expandafter\@doit\fi{\newif\ifpdfing} +\makeatother + +\typeout{Options:} +\typeout{ Fancy style: \iffancystyle ON\else OFF\fi} +\typeout{ Short version: \ifshort ON\else OFF\fi} + \errorcontextlines=\maxdimen \showboxdepth=\maxdimen \showboxbreadth=\maxdimen \iffancystyle - \documentclass - [a4paper, article, 10pt, numbering, noherefloats, notitlepage, - runinsubsubsec] - {strayman} + \documentclass[indentpar]{strayman} \usepackage[T1]{fontenc} \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} \usepackage[within = subsection, mdwmargin]{mdwthm} \usepackage{mdwlist} \usepackage{sverb} - \if0\ifx\pdfoutput\xxundefined0\else\the\pdfoutput\fi + \ifpdfing\else \PassOptionsToPackage{dvips}{xy} \fi \else - \documentclass[a4paper]{llncs} - \usepackage{a4wide} + \PassOptionsToClass{runningheads}{llncs} + \documentclass{llncs} \fi \PassOptionsToPackage{show}{slowbox} %\PassOptionsToPackage{hide}{slowbox} -\usepackage{mdwtab, mathenv, mdwmath, crypto} +\usepackage{mdwtab, mdwmath, crypto} \usepackage{slowbox} \usepackage{amssymb, amstext} \usepackage{url, multicol} @@ -43,14 +49,20 @@ \usepackage[all]{xy} \turnradius{4pt} \fi +\usepackage{mathenv} +\newcommand{\Nupto}[1]{\{0, 1, \ldots, #1 - 1\}} \iffancystyle - \def\next{\title[The Wrestlers Protocol]} + \let\next\title \else - \def\next{\title} + \def\next[#1]{\titlerunning{#1}\title} \fi \next - {The Wrestlers Protocol \\ + [The Wrestlers Protocol] + {The Wrestlers Protocol% + \ifshort\thanks{This is an extended abstract; the full version + \cite{wooding-2006:wrestlers} is available from + \texttt{http://eprint.iacr.org/2006/386/}.}\fi \\ A simple, practical, secure, deniable protocol for key-exchange} \iffancystyle \author{Mark Wooding \\ \email{mdw@distorted.org.uk}} @@ -70,16 +82,11 @@ \numberwithin{equation}{subsection} \let\random\$ \else - \bibliographystyle{plain} + \bibliographystyle{splncs} \expandafter\let\csname claim*\endcsname\claim \expandafter\let\csname endclaim*\endcsname\endclaim \fi -\iffancystyle - \newcommand{\Nupto}[1]{\N_{<{#1}}} -\else - \newcommand{\Nupto}[1]{\{0, 1, \ldots, #1 - 1\}} -\fi \let\Bin\Sigma \let\emptystring\lambda \edef\Pr{\expandafter\noexpand\Pr\nolimits} @@ -98,6 +105,13 @@ \def\fixme#1{\marginpar{FIXME}[FIXME: #1]} \def\hex#1{\texttt{#1}_{x}} +\newenvironment{longproof}[1]{% + \ifshort#1\expandafter\ignore + \else\proof\fi +}{% + \ifshort\else\endproof\fi +} + \def\dbox#1{% \vtop{% \def\\{\unskip\egroup\hbox\bgroup\strut\ignorespaces}% @@ -129,6 +143,14 @@ \def\PRreveal{\textsf{Session-state reveal}\ar[r]} \def\protocolrun#1{\[\xymatrix @R=0pt @C=2em {#1}\]} +\def\protocol{% + \unskip\bigskip + \begin{tabular*}{\linewidth}% + {@{\qquad}l@{\extracolsep{0ptplus1fil}}r@{\qquad}}} +\def\endprotocol{\end{tabular*}} +\def\send#1#2{\noalign{% + \centerline{\xy\ar @{#1}|*+{\mathstrut#2}<.5\linewidth, 0pt>\endxy}}} + %% class-ids for proof of extractor lemma \let\Cid=\Lambda \let\Csession=S @@ -141,6 +163,10 @@ \def\HG#1{\mathbf{H}_{#1}} +\iffancystyle\else + \let\xsssec\subsubsection\def\subsubsection#1{\xsssec[#1]{#1.}} +\fi + \begin{document} %%%-------------------------------------------------------------------------- @@ -151,9 +177,9 @@ \begin{abstract} We describe and prove (in the random-oracle model) the security of a simple but efficient zero-knowledge identification scheme, whose security is based - on the computational Diffie-Hellman problem. Unlike other recent proposals - for efficient identification protocols, we don't need any additional - assumptions, such as the Knowledge of Exponent assumption. + on the computational Diffie--Hellman problem. Unlike other recent + proposals for efficient identification protocols, we don't need any + additional assumptions, such as the Knowledge of Exponent assumption. From this beginning, we build a simple key-exchange protocol, and prove that it achieves `SK-security' -- and hence security in Canetti's Universal @@ -175,10 +201,8 @@ \fi %%%-------------------------------------------------------------------------- - \section{Introduction} - This paper proposes protocols for \emph{identification} and \emph{authenticated key-exchange}. @@ -187,15 +211,18 @@ really talking to another party, say Alice. It assumes that Bob has some way 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; we discuss their -protocol in section~\ref{sec:stinson-ident}. +independently of, a recent protocol by Stinson and Wu +\cite{stinson-wu-2006:two-flow-zero-knowledge}; 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{shoup-1999:formal-model-key-exchange} 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 @@ -214,7 +241,7 @@ Our identification protocol has a number of desirable properties. \item It is fairly \emph{efficient}, requiring two scalar multiplications by each of the prover and verifier. \item It is provably \emph{secure} (in the random oracle model), assuming the - intractability of the computational Diffie-Hellman problem. + intractability of the computational Diffie--Hellman problem. \end{itemize} Our key-exchange protocol also has a number of desirable @@ -227,7 +254,7 @@ properties. participant. The communication can be reduced to three messages by breaking the protocol's symmetry. \item It is provably \emph{secure} (again, in the random oracle model), - assuming the intractability of the computational Diffie-Hellman problem, + assuming the intractability of the computational Diffie--Hellman problem, and the security of a symmetric encryption scheme. \item It provides \emph{perfect forward secrecy}. That is, even if a user's long-term secrets are compromised, past sessions remain secure. @@ -239,6 +266,7 @@ properties. a given protocol execution. \end{itemize} +\ifshort\else \subsection{Asymptotic and concrete security results} Most security definitions for identification (particularly zero-knowledge) @@ -256,107 +284,143 @@ 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 -proofs guarantee nothing at all for the kinds of parameters typically used in -practice. +\cite{koblitz-menezes-2006:another-look-provable-security-ii} (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. 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}. +\cite{bellare-1994:security-cbc,bellare-1995:xor-macs,% +bellare-rogaway-1995:oaep,bellare-rogaway-1996:exact-security-sigs,% +bellare-1996:hmac,bellare-1997:concrete-symmetric}; see also +\cite{bellare-1999:practice-oriented-provable-security}. 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 within given resource bounds. - +\fi \subsection{Formal models for key-exchange} +\ifshort + +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:logic-authn}) was given by Bellare and Rogaway +\cite{bellare-rogaway-1994:entity-authn-key-distrib}; the model has since +been enhanced, both by the original authors and others, in +\cite{bellare-rogaway-1995:session-key-distrib,% + blake-wilson-1997:key-agreement,% + blake-wilson-menezes-1998:asymm-key-transport}. +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:modular-key-exchange} and +\cite{shoup-1999:formal-model-key-exchange}; 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}. -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. - -Bellare and Rogaway \cite{Bellare:1994:EAK} describe a model for studying the -computational security of authentication and key-exchange protocols in a -concurrent setting, i.e., where multiple parties are running several -instances of a protocol simultaneously. They define a notion of security in -this setting, and show that several simple protocols achieve this notion. -Their original paper dealt with pairs of parties using symmetric -cryptography; they extended their definitions in \cite{Bellare:1995:PSS} to -study three-party protocols involving a trusted key-distribution centre. - -Blake-Wilson, Johnson and Menezes \cite{Blake-Wilson:1997:KAP} applied the -model of \cite{Bellare:1994:EAK} to key-exchange protocols using asymmetric -cryptography, and Blake-Wilson and Menezes \cite{Blake-Wilson:1998:EAA} -applied it to protocols based on the Diffie-Hellman protocol. - -The security notion of \cite{Bellare:1994:EAK} is based on a \emph{game}, in -which an adversary nominates a \emph{challenge session}, and is given either -the key agreed by the participants of the challenge session, or a random -value independently sampled from an appropriate distribution. The -adversary's advantage -- and hence the insecurity of the protocol -- is -measured by its success probability in guessing whether the value it was -given is really the challenge key. This challenge-session notion was also -used by the subsequent papers described above. - -Bellare, Canetti and Krawczyk \cite{Bellare:1998:MAD} described a pair of -models which they called the \textsc{am} (for `authenticated links model') -and \textsc{um} (`unauthenticated links model'). They propose a modular -approach to the design of key-exchange protocols, whereby one first designs a -protocol and proves its security in the \textsc{am}, and then applies a -authenticating `compiler' to the protocol which they prove yields a protocol -secure in the realistic \textsc{um}. Their security notion is new. They -define an `ideal model', in which an adversary is limited to assigning -sessions fresh, random and unknown keys, or matching up one session with -another, so that both have the same key. They define a protocol to be secure -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, -particularly \cite{Bellare:1994:EAK} and \cite{Bellare:1998:MAD}, and -highlights some of their inadequacies. - -Canetti and Krawczyk \cite{Canetti:2001:AKE} describe a new notion of -security in the basic 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. - -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 -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 +begins with the logic of Burrows, Abadi and Needham +\cite{burrows-1989:logic-authn}. 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. + +Bellare and Rogaway \cite{bellare-rogaway-1994:entity-authn-key-distrib} +describe a model for studying the computational security of authentication +and key-exchange protocols in a concurrent setting, i.e., where multiple +parties are running several instances of a protocol simultaneously. They +define a notion of security in this setting, and show that several simple +protocols achieve this notion. Their original paper dealt with pairs of +parties using symmetric cryptography; they extended their definitions in +\cite{bellare-rogaway-1995:session-key-distrib} to study three-party +protocols involving a trusted key-distribution centre. + +Blake-Wilson, Johnson and Menezes \cite{blake-wilson-1997:key-agreement} +applied the model of \cite{bellare-rogaway-1994:entity-authn-key-distrib} to +key-exchange protocols using asymmetric cryptography, and Blake-Wilson and +Menezes \cite{blake-wilson-menezes-1998:asymm-key-transport} applied it to +protocols based on the Diffie-Hellman protocol. + +The security notion of \cite{bellare-rogaway-1994:entity-authn-key-distrib} +is based on a \emph{game}, in which an adversary nominates a \emph{challenge +session}, and is given either the key agreed by the participants of the +challenge session, or a random value independently sampled from an +appropriate distribution. The adversary's advantage -- and hence the +insecurity of the protocol -- is measured by its success probability in +guessing whether the value it was given is really the challenge key. This +challenge-session notion was also used by the subsequent papers described +above. + +Bellare, Canetti and Krawczyk \cite{bellare-1998:modular-key-exchange} +described a pair of models which they called the \textsc{am} (for +`authenticated links model') and \textsc{um} (`unauthenticated links model'). +They propose a modular approach to the design of key-exchange protocols, +whereby one first designs a protocol and proves its security in the +\textsc{am}, and then applies a authenticating `compiler' to the protocol +which they prove yields a protocol secure in the realistic \textsc{um}. +Their security notion is new. They define an `ideal model', in which an +adversary is limited to assigning sessions fresh, random and unknown keys, or +matching up one session with another, so that both have the same key. They +define a protocol to be secure 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:formal-model-key-exchange}, Shoup presents a new model +for key-exchange, also based on the idea of simulation. He analyses the +previous models, particularly +\cite{bellare-rogaway-1994:entity-authn-key-distrib} and +\cite{bellare-1998:modular-key-exchange}, and highlights some of their inadequacies. + +\fi + +Canetti and Krawczyk +\cite{canetti-krawczyk-2001:secure-channels-eprint,% + canetti-krawczyk-2001:secure-channels} +describe a new notion of security in the model of +\cite{bellare-1998:modular-key-exchange}, based on the challenge-session +notion of \cite{bellare-rogaway-1994:entity-authn-key-distrib}. The security +notion, called `SK-security', seems weaker in various ways than those of +earlier works such as \cite{bellare-rogaway-1994:entity-authn-key-distrib} or +\cite{shoup-1999:formal-model-key-exchange}. However, the authors show that +their notion suffices for constructing `secure channel' protocols, which they +also define. + +\ifshort\else In \cite{canetti-2001:uc-security-eprint,% + canetti-2001:uc-security}, +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 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:modular-key-exchange} and +\cite{shoup-1999:formal-model-key-exchange}, 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. +due to the interactive nature of the `environment' distinguisher. \fi -Canetti and Krawczyk \cite{Canetti:2002:UCN} show that the SK-security notion -of \cite{Canetti:2001:AKE} is \emph{equivalent} to a `relaxed' notion of -key-exchange security in the UC framework, and suffices for the construction -of UC secure channels. +Canetti and Krawczyk \cite{canetti-krawczyk-2002:uc-key-exchange} show that +the SK-security notion of \cite{canetti-krawczyk-2001:secure-channels} is +\emph{equivalent} to a `relaxed' notion of key-exchange security in the UC +framework\ifshort\space of \cite{canetti-2001:uc-security}\fi, and suffices +for the construction of UC secure channels. -The result of \cite{Canetti:2002:UCN} gives us confidence that SK-security is -the `right' notion of security for key-exchange protocols. Accordingly, -SK-security is the standard against which we analyse our key-exchange -protocol. +The result of \cite{canetti-krawczyk-2002:uc-key-exchange} gives us +confidence that SK-security is the `right' notion of security for +key-exchange protocols. Accordingly, SK-security is the standard against +which we analyse our key-exchange protocol. \subsection{Outline of the paper} @@ -371,26 +435,34 @@ The remaining sections of this paper are as follows. \item Section \ref{sec:kx} describes the simple version of our key-exchange protocol, and proves its security and deniability. It also describes some minor modifications which bring practical benefits without damaging - security. + security. \item Finally, section \ref{sec:conc} presents our conclusions. \end{itemize} -%%%-------------------------------------------------------------------------- +\ifshort +The full version of this paper describes how to make our protocols +identity-based by using bilinear pairings using the techniques introduced in +\cite{boneh-franklin-2003:ibe-weil-pairing}. It also contains proofs of the +various theorems stated here. +\fi +%%%-------------------------------------------------------------------------- \section{Preliminaries} \label{sec:prelim} -\subsection{Miscellaneous notation} - -We write $\Func{D}{R}$ for the set of all functions with domain $D$ and range -$R$. -\iffancystyle -We write $\Nupto{n} = \{\, i \in \Z \mid 0 \le i < n \,\} = \{0, 1, \ldots, n -- 1\}$ for the set of nonnegative integers less than $n$. +\ifshort +\subsection{Basics} +\let\prelimsec\subsubsection +\else +\let\prelimsec\subsection \fi +\prelimsec{Miscellaneous notation} -\subsection{Groups} +We write $\#S$ for the cardinality of a set $S$. We write $\Func{D}{R}$ for +the set of all functions with domain $D$ and range $R$. + +\prelimsec{Groups} Let $(G, +)$ be a cyclic group\footnote{ We find that additive group notation is easier to read. In particular, in @@ -399,10 +471,13 @@ Let $(G, +)$ be a cyclic group\footnote{ of prime order $q$, and generated by an element $P$. We shall write the identity of $G$ as $0_G$, or simply as $0$ when no ambiguity is likely to arise. Thus, we have $\langle P \rangle = G$ and $q P = 0$. Any $X \in G$ -can be written as $X = x P$ for some $x \in \Nupto{q}$. +can be written as $X = x P$ for some $x \in \{0, 1, \ldots, q - 1\}$. +We consider a cyclic group of order $n$ as a $\Z/n\Z$-module, and in +particular our group $G$ can be seen as a vector space over $\gf{q}$. This +makes the notation slightly more convenient. -\subsection{Bit strings and encodings} +\prelimsec{Bit strings and encodings} \label{sec:bitenc} Let $\Bin = \{0, 1\}$ be the set of binary digits. Then $\Bin^n$ is the set @@ -412,23 +487,30 @@ string $x \in \Bin^n$, and for $0 \le i < n$, we write $x[i]$ as the $i$th bit of $x$. The empty string is denoted $\emptystring$. Let $x$ and $y$ be two bit strings. If $|x| = |y| = n$, we write $x \xor y$ -to mean the bitwise exclusive-or of $x$ and $y$: if $z = x \xor y$ then $|z| -= n$, and $z[i] = (x[i] + y[i]) \bmod 2$ for $0 \le i < n$. We write $x \cat -y$ to mean the concatenation of $x$ and $y$: if $z = x \cat y$ then $|z| = -|x| + |y|$ and $z[i] = x[i]$ if $0 \le i < |x|$ and $z[i] = y[i - |x|]$ if -$|x| < i \le |x| + |y|$. +to mean the bitwise exclusive-or of $x$ and $y$\ifshort\else: if $z = x \xor +y$ then $|z| = n$, and $z[i] = (x[i] + y[i]) \bmod 2$ for $0 \le i < n$\fi. +We write $x \cat y$ to mean the concatenation of $x$ and $y$\ifshort\else: if +$z = x \cat y$ then $|z| = |x| + |y|$ and $z[i] = x[i]$ if $0 \le i < |x|$ +and $z[i] = y[i - |x|]$ if $|x| < i \le |x| + |y|$\fi. Finally, we let $\bot$ be a value distinct from any bit string. We shall want to encode group elements $X \in G$ and indices $x \in I = -\Nupto{|G|}$ as bit strings. To this end, we shall assume the existence of +\gf{q}$ as bit strings. +\ifshort +To this end, we shall assume the existence of efficient, unambiguous +encodings of group elements as $\ell_G$-bit strings, and indices as +$\ell_I$-bit strings. To reduce clutter, we shall leave encoding and +decoding as implicit operations. +\else +To this end, we shall assume the existence of integers $\ell_G, \ell_I > 0$ and functions \[ e_S\colon S \to \Bin^{\ell_S} \quad \textrm{and} \quad d_S\colon \Bin^{\ell_S} \to S \cup \{ \bot \} \qquad - \textrm{for } S \in \{ G, I \}. + \textrm{for } S \in \{ G, \F \}. \] with the following properties. \begin{itemize} @@ -449,9 +531,10 @@ the security of our protocols. We shall frequently abuse notation by omitting the encoding and decoding functions where it is obvious that they are required. +\fi - -\subsection{Games, adversaries, and oracles} +\ifshort\else +\prelimsec{Games, adversaries, and oracles} \label{sec:games} Many of the security definitions and results given here make use of @@ -469,52 +552,56 @@ The games provide models of someone trying to attack a construction or protocol. For security, we will either define a notion of `winning' the game, and require that all adversaries have only a very small probability of winning, or we consider two different games and require that no adversary can -distinguish between the two except with very small probability. +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. - -The following simple lemma from \cite{Shoup:2001:OR} will be frequently -useful. +\cite{bellare-rogaway-2006:triple-enc,shoup-2004:sequences-of-games}. +The presentation owes much to Shoup \cite{shoup-2004:sequences-of-games}. 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:oaep-reconsidered} will be +frequently useful. \begin{lemma}[Difference Lemma] \label{lem:shoup} - Let $S$, $T$, $F$ be events. Suppose $\Pr[S|\bar F] = \Pr[T|\bar F]$. - Then $|\Pr[S] - \Pr[T]| \le \Pr[F]$. + Let $S$, $T$, $F$ be events. Suppose $\Pr[S \mid \bar F] = + \Pr[T \mid \bar F]$. Then $|\Pr[S] - \Pr[T]| \le \Pr[F]$. \end{lemma} \begin{proof} A simple calculation: \begin{eqnarray*}[rl] |\Pr[S] - \Pr[T]| - & = |(\Pr[S|F]\Pr[F] + \Pr[S|\bar F]\Pr[\bar F]) - - (\Pr[T|F]\Pr[F] + \Pr[T|\bar F]\Pr[\bar F])| \\ - & = \Pr[F] \cdot |\Pr[S|F] - \Pr[T|F]| \\ + & = |(\Pr[S \mid F]\Pr[F] + \Pr[S \mid \bar F]\Pr[\bar F]) - + (\Pr[T \mid F]\Pr[F] + \Pr[T \mid \bar F]\Pr[\bar F])| \\ + & = \Pr[F] \cdot |\Pr[S \mid F] - \Pr[T \mid F]| \\ & \le \Pr[F] \end{eqnarray*} and we're done! \end{proof} +\fi -\subsection{The random oracle model} +\prelimsec{The random oracle model} \label{sec:ro} +\ifshort\else In particular, most of our results will make use of the \emph{random oracle} -model \cite{Bellare:1993:ROP}, in which all the participants, including the -adversary, have access to a number of `random oracles'. A random oracle with -domain $D$ and range $R$ is an oracle which computes a function chosen -uniformly at random from the set of all such functions. (In the original -paper \cite{Bellare:1993:ROP}, random oracles are considered having domain -$\Bin^*$ and range $\Bin^\omega$; we use finite random oracles here, because -they're easier to work with.) +model \cite{bellare-rogaway-1993:random-oracles}, in which all the +participants, including the adversary, have access to a number of `random +oracles'. A random oracle with domain $D$ and range $R$ is an oracle which +computes a function chosen uniformly at random from the set of all such +functions. (In the original paper +\cite{bellare-rogaway-1993:random-oracles}, random oracles are considered +having domain $\Bin^*$ and range $\Bin^\omega$; we use finite random oracles +here, because they're easier to work with.) Given a protocol proven secure in the random oracle model, we can instantiate each random oracle by a supposedly-secure hash function and be fairly @@ -522,12 +609,14 @@ confident that either our protocol will be similarly secure, or one of the hash functions we chose has some unfortunate property. Proofs in the random oracle must be interpreted carefully. For example, -Canetti, Goldreich and Halevi \cite{Canetti:2004:ROM} show that there are -schemes which can be proven secure in the random oracle model but provably -have no secure instantiation in the standard model. +Canetti, Goldreich and Halevi \cite{canetti-2004:rand-oracle-revisit} show +that there are schemes which can be proven secure in the random oracle model +but provably have no secure instantiation in the standard model. +\fi -The random oracle model is useful for constructing reductions and simulators -for two main reasons. +The random oracle model \ifshort\cite{bellare-rogaway-1993:random-oracles} +\fi is useful for constructing reductions and simulators for two main +reasons. \begin{enumerate} \item One can use the transcript of an adversary's queries to random oracles in order to extract knowledge from it. @@ -545,14 +634,17 @@ that the only sensible way of working out (anything about) the hash of a particular string is to actually compute the hash function, and the random oracle model is, we hope, just giving us a `hook' into this process. +\ifshort\else (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: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.) +of \cite{boneh-franklin-2003:ibe-weil-pairing}. 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.) +\fi -\subsection{Notation for algorithms} +\ifshort\else +\prelimsec{Notation for algorithms} We shall have occasion to describe algorithms by means of a pseudocode. Our choice of pseudocode is unlikely to be particularly controversial. We let $x @@ -575,9 +667,9 @@ explicitly, leaving the reader to determine these from context. Finally, the notation $\Pr[\textit{algorithm} : \textit{condition}]$ denotes the probability that \textit{condition} is true after running the given \textit{algorithm}. +\fi - -\subsection{Diffie-Hellman problems} +\prelimsec{Diffie-Hellman problems} \label{sec:dhp} The security of our protocols is related to the hardness of the @@ -586,12 +678,13 @@ We define these problems and what it means for them to be `hard' here. The \emph{computational} Diffie-Hellman problem (CDH) is as follows: given two group elements $X = x P$ and $Y = y P$, find $Z = x y P$. +\ifshort\else \begin{definition}[The computational Diffie-Hellman problem] Let $(G, +)$ be a cyclic group generated by $P$. For any adversary $A$, we say that $A$'s \emph{success probability} at solving the computational Diffie-Hellman problem in $G$ is \[ \Succ{cdh}{G}(A) = - \Pr[ x \getsr I; y \getsr \Nupto{|G|} : A(x P, y P) = x y P ] + \Pr[ x \getsr I; y \getsr \Z/\#G\Z : A(x P, y P) = x y P ] \] where the probability is taken over the random choices of $x$ and $y$ and any random decisions made by $A$. We say that the \emph{CDH insecurity @@ -601,42 +694,31 @@ two group elements $X = x P$ and $Y = y P$, find $Z = x y P$. \end{definition} Certainly, if one can compute discrete logarithms in the group $G$ (i.e., given $x P$, find $x$), then one can solve the computational Diffie-Hellman -problem. The converse is not clear, though. Shoup \cite{Shoup:1997:LBD} -gives us some confidence in the difficulty of the problem by showing that a -\emph{generic} adversary -- i.e., one which makes no use of the specific -structure of a group -- has success probability no greater than $q^2/|G|$. +problem. The converse is not clear, though. Shoup +\cite{shoup-1997:dh-lower-bounds} gives us some confidence in the difficulty +of the problem by showing that a \emph{generic} adversary -- i.e., one which +makes no use of the specific structure of a group -- has success probability +no greater than $q^2/\#G$. This isn't quite sufficient for our purposes. Our proofs will be able to come up with (possibly) a large number of guesses for the correct answer, and at most one of them will be correct. Unfortunately, working out which one is right seems, in general, to be difficult. This is the \emph{decision} -Diffie-Hellman problem (DDH), which \cite{Shoup:1997:LBD} shows, in the -generic group model, is about as hard as CDH. (See \cite{Boneh:1998:DDP} for -a survey of the decision Diffie-Hellman problem.) - +Diffie-Hellman problem (DDH), which \cite{shoup-1997:dh-lower-bounds} shows, +in the generic group model, is about as hard as CDH. (See +\cite{boneh-1998:ddh} for a survey of the decision Diffie-Hellman problem.) +\par\fi Our reference problem will be a `multiple-guess computational Diffie-Hellman problem' (MCDH), which is captured by a game as follows. An adversary is given a pair of group elements $(x P, y P)$, and an oracle $V(\cdot)$ which accepts group elements as input. The adversary wins the game if it queries $V(x y P)$. -\begin{definition}[The multiple-guess computational Diffie-Hellman problem] - \label{def:mcdh} - Let $(G, +)$ be a cyclic group generated by $P$. For some adversary $A$, - we say that $A$'s \emph{success probability} at solving the multiple-guess - computational Diffie-Hellman problem in $G$ is - \[ \Succ{mcdh}{G}(A) = \Pr[\Game{mcdh}{G}(A) = 1] \] - where $\Game{mcdh}{G}(A)$ is shown in figure~\ref{fig:mcdh}. We say that - the \emph{MCDH insecurity function of $G$} is - \[ \InSec{mcdh}(G; t, q_V) = \max_A \Succ{mcdh}{G}(A) \] - where the maximum is taken over adversaries which complete in time $t$ and - make at most $q_V$-oracle queries. -\end{definition} \begin{figure} \begin{program} $\Game{mcdh}{G}(A)$: \+ \\ $w \gets 0$; \\ - $x \getsr \Nupto{|G|}$; $y \getsr \Nupto{|G|}$; \\ + $x \getsr \Z/\#G\Z$; $y \getsr \Z/\#G\Z$; \\ $A^{V(\cdot)}(x P, y P)$; \\ \RETURN $w$; \next @@ -652,6 +734,23 @@ $V(x y P)$. \label{fig:mcdh} \end{figure} +\begin{definition}[The multiple-guess computational Diffie-Hellman problem] + \label{def:mcdh} + Let $(G, +)$ be a cyclic group generated by $P$. For some adversary $A$, + we say that $A$'s \emph{success probability} at solving the multiple-guess + computational Diffie-Hellman problem in $G$ is + \[ \Succ{mcdh}{G}(A) = \Pr[\Game{mcdh}{G}(A) = 1] \] + where $\Game{mcdh}{G}(A)$ is shown in figure~\ref{fig:mcdh}. We say that + the \emph{MCDH insecurity function of $G$} is + \[ \InSec{mcdh}(G; t, q_V) = \max_A \Succ{mcdh}{G}(A) \] + where the maximum is taken over adversaries which complete in time $t$ and + make at most $q_V$-oracle queries. +\end{definition} +\ifshort +We can (loosely) relate the difficulty of MCDH to the difficulty of +the standard CDH problem, in which the adversary is allowed only a single +guess. +\else Note that our MCDH problem is not quite the `gap Diffie-Hellman problem' (GDH). The gap problem measures the intractibility of solving CDH even with the assistance of an oracle for solving (restricted) decision Diffie-Hellman @@ -663,11 +762,16 @@ Clearly MCDH is at least as hard as GDH, since our simple verification oracle $V(Z)$ can be simulated with the gap problem's DDH oracle, as $D(Y, Z)$. However, we can (loosely) relate the difficulty of MCDH to the difficulty of CDH. +\fi \begin{proposition}[Comparison of MCDH and CDH security] For any cyclic group $(G, +)$, - \[ \InSec{mcdh}(G; t, q_V) \le q_V\,\InSec{cdh}(G; t + O(q_V)). \] + \[ \InSec{mcdh}(G; t, q_V) \le + \ifshort q_V\,\InSec{mcdh}(G; t + O(q_V), 1) \else + q_V\,\InSec{cdh}(G; t + O(q_V)) \fi. + \] \end{proposition} -\begin{proof} +\begin{longproof}{The proof of this proposition may be found in the full + version of this paper.} Let $A$ be an adversary attacking the multiple-guess computational Diffie-Hellman problem in $G$, and suppose that it runs in time $t$ and issues $q_V$ queries to its verification oracle. @@ -701,14 +805,13 @@ CDH. \RETURN $0$; \end{program} Observe that $B$ provides $A$ with an accurate simulation of game $\G1$. - Moreover, at the end of the algorithm, we have $0 < n \le q_V$, the - output of $A$ is stored in $Q_{n-1}$ and the values $Q_0$, $Q_1$, \dots, - $Q_{n-1}$ are the values of $A$'s oracle queries. Hence, with probability - $Pr[S_1]$, at least of one of the $Q_i$ is the correct answer to the CDH - problem. Let $\epsilon = \Pr[S_1] = \Pr[S_0]$; we claim that $B$'s - probability of success is at least $\epsilon/q_V$. The proposition - follows directly from this claim and that, because $A$ was chosen - arbitrarily, we can maximize and count resources. + Moreover, at the end of the algorithm, we have $0 < n \le q_V$, and the + values $Q_0$, $Q_1$, \dots, $Q_{n-1}$ are the values of $A$'s oracle + queries. Hence, with probability $Pr[S_1]$, at least of one of the $Q_i$ + is the correct answer to the CDH problem. Let $\epsilon = \Pr[S_1] = + \Pr[S_0]$; we claim that $B$'s probability of success is at least + $\epsilon/q_V$. The proposition follows directly from this claim and that, + because $A$ was chosen arbitrarily, we can maximize and count resources. We now prove the above claim. For $0 \le i < q_V$, let $W_i$ be the event that $Q_i = x y P$, i.e., that $Q_i$ is the correct response. A @@ -727,10 +830,10 @@ CDH. & = \frac{\epsilon}{q_V}. \end{eqnarray*} which completes the proof. -\end{proof} - +\end{longproof} -\subsection{Example groups and encodings} +\ifshort\else +\prelimsec{Example groups and encodings} For nonnegative integers $0 \le n < 2^\ell$, there is a natural binary encoding $N_\ell\colon \Nupto{2^\ell} \to \Bin^\ell$ which we can define @@ -754,23 +857,23 @@ using the functions $(e, d)$: The reader can verify that the functions $e(L, \ell, \cdot)$ and $d(L, \ell, \cdot)$ satisfy the requirements of section~\ref{sec:bitenc}. -Given some $q < 2^{\ell_I}$ and $I = \Nupto{q}$, then, we can define an -encoding $(e_I, d_I)$ by $e_I(n) = e(q, \ell_I, n)$ and $d_I(a) = d(q, -\ell_I, a)$. - -Let $p$ and $q$ be primes, with $q|(p - 1)$. Then there is an order-$q$ -subgroup of $(\Z/p\Z)^*$. In practice, an order-$q$ element can be found -easily by taking elements $h \in (\Z/p\Z)^*$ at random and computing $g = -h^{(p-1)/2}$ until $g \ne 1$; then $G = \langle g \rangle$ is a group of $q$ -elements. Assuming that $p$ and $q$ are sufficiently large, the -Diffie-Hellman problems seem to be difficult in $G$. Some texts recommend -additional restrictions on $p$, in particular that $(p - 1)/2q$ be either -prime or the product of large primes. Primes of this form protect against -small-subgroup attacks; but our protocols are naturally immune to these -attacks, so such precautions are unnecessary here. Elements of $G$ can be -encoded readily, since each element $n + p\Z$ of $\Z/p\Z$ has an obvious -`representative' integer $n$ such that $0 \le n < p$, and given $2^{\ell_G} > -p$, we can encode $n$ as $e(p, \ell_G, n)$, as above. +Given some $q$ with $q < 2^{\ell_I}$, then, we can define an encoding +$(e_\F, d_\F)$ by $e_\F(n) = e(q, \ell_I, n)$ and $d_\F(a) = d(q, \ell_I, +a)$. + +Let $p$ and $q$ be primes, with $q \mid (p - 1)$. Then there is an order-$q$ +subgroup of $\F_p^*$. In practice, an order-$q$ element can be found easily +by taking elements $h \in \F_p^*$ at random and computing $g = h^{(p-1)/2}$ +until $g \ne 1$; then $G = \langle g \rangle$ is a group of $q$ elements. +Assuming that $p$ and $q$ are sufficiently large, the Diffie-Hellman problems +seem to be difficult in $G$. Some texts recommend additional restrictions on +$p$, in particular that $(p - 1)/2q$ be either prime or the product of large +primes. Primes of this form protect against small-subgroup attacks; but our +protocols are naturally immune to these attacks, so such precautions are +unnecessary here. Elements of $G$ can be encoded readily, since each element +$n + p\Z$ of $\F_p = \Z/p\Z$ has an obvious `representative' integer $n$ such +that $0 \le n < p$, and given $2^{\ell_G} > p$, we can encode $n$ as $e(p, +\ell_G, n)$, as above. Alternatively, let $\F = \gf{p^f}$ be a finite field, and $E$ be an elliptic curve defined over $\F$ such that the group $E(\F)$ of $\F$-rational points @@ -783,9 +886,10 @@ $r(x)$ with degree less than $f$, and coefficients $c_i \in \{0, 1\}$, i.e., \[ r(x) = \sum_{0\le i 4$. However, in -the Schnorr groups used by Stinson and Wu, the cofactor is much larger than -$q$, and their new variant is more efficient.) +\cite{certicom-2000:sec1} recommends rejecting groups with cofactor $f > 4$. +However, in the Schnorr groups used by Stinson and Wu, the cofactor is much +larger than $q$, and their new variant is more efficient.) -We note that the zero-knowledge property of the Stinson-Wu protocol requires +We note that the zero-knowledge property of the Stinson--Wu protocol requires the Diffie-Hellman knowledge of exponent assumption (KEA). Very briefly: suppose $A$ is a randomized algorithm which takes as input $X \in G$ and outputs a pair $(r P, r X)$; intuitively, the KEA asserts $A$ must have done @@ -1816,13 +1967,14 @@ 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(\rho, \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{stinson-wu-2006:two-flow-zero-knowledge} 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 +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 case-analysis which would be the basis of a proof of this. @@ -1835,7 +1987,7 @@ case-analysis which would be the basis of a proof of this. \\ \hlx{v[1]hv} %% unpleasant hacking to make the R and c columns the same width :-( \settowidth{\dimen0}{\textbf{Challenge}}% - \dimen0=.5\dimen0 + \dimen0=.5\dimen0 \advance\dimen0by-\tabcolsep \advance\dimen0by-.5\arrayrulewidth \hbox to\dimen0{\hfil$R$\hfil} @@ -1852,23 +2004,23 @@ case-analysis which would be the basis of a proof of this. (lemma~\ref{lem:dlext}); $Y'$ probably wrong by theorem~\ref{thm:wident-sound}. \\ \hlx{vh} \end{tabular} - + \caption{Security of $\Wident$ against active intruders (summary)} \label{tab:wident-active} \end{table} -An identity-based analogue of Stinson-Wu can be defined using a bilinear +An identity-based analogue of Stinson--Wu can be defined using a bilinear pairing, just as we did in section~\ref{sec:wident-id}. However, to prove the zero-knowledge property, one needs to make a bilinear analogue of the knowledge of exponent assumption. We suspect that a key-exchange protocol like ours can be constructed using -Stinson-Wu rather than the Wrestlers identification scheme. We haven't, +Stinson--Wu rather than the Wrestlers identification scheme. We haven't, however, gone through all the details, since we believe our protocol is just as efficient and is based on much more conservative assumptions. +\fi %%%-------------------------------------------------------------------------- - \section{A simple key-exchange protocol} \label{sec:kx} @@ -1910,10 +2062,10 @@ $H_I\colon \Bin^{2\ell_G} \to \Bin^{\ell_I}$ and $H_K\colon \Bin^{\ell_G+1} Suppose that Alice's and Bob's private keys are $a$ and $b$ respectively, and their public keys are $A = a P$ and $B = b P$. \begin{enumerate} -\item Alice chooses a random index $r \inr \Nupto{|G|}$. She computes $R = r - P$ and $c = r \xor H_I(R, r B)$. She sends the pair $(R, c)$ to Bob. -\item Similarly, Bob chooses a random $s \inr \Nupto{|G|}$. He computes $S - = s P$ and $d = s \xor H_I(S, s A)$. He sends $(S, d)$ to Alice. +\item Alice chooses a random index $r \inr \gf{q}$. She computes $R = r P$ and + $c = r \xor H_I(R, r B)$. She sends the pair $(R, c)$ to Bob. +\item Similarly, Bob chooses a random $s \inr \gf{q}$. He computes $S = s P$ + and $d = s \xor H_I(S, s A)$. He sends $(S, d)$ to Alice. \item Alice receives $(S', d')$ from Bob. She computes $s' = d' \xor H_I(S', a S')$, and verifies that $S' = s' P$. If so, she computes $K_A = H_K(0 \cat r S')$, and sends $R, E_{K_A}(a S')$ to Bob. @@ -1934,40 +2086,32 @@ figure~\ref{fig:wkx}. \begin{figure} \begin{description} - \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime. + \item[Setup] Group $G = \langle P \rangle$; $\#G = q$ is prime. $H_I(\cdot, \cdot)$ and $H_K(\cdot)$ are secure hashes. $\E = (\kappa, E, D)$ is an IND-CCA2 symmetric encryption scheme. \item[Parties] $U_i$ for $0 \le i < n$. - \item[Private keys] $x_i \inr \Nupto{q}$. + \item[Private keys] $x_i \inr \gf{q}$. \item[Public keys] $X_i = x_i P$. \end{description} - \[ \begin{graph} - !{0; <8cm, 0cm>: <0cm, 3cm>::} - *+[F]\dbox{$r_i \getsr I$; $R_i \gets r_i P$ \\ - $c_i \gets r_i \xor H_I(R_i, r_i X_j)$} ="i0" - [d] - *+[F]\dbox{Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$ \\ - $Z \gets r_i R_j$; $K \gets H_K(0, Z)$ \\ - $\chi_i \gets E_K(x_i R_j)$} ="i1" - [d] - *+[F]\dbox{Check $D_K(\chi_j) = r_i X_j$ \\ - Shared key is $H_K(1, Z)$} ="i2" - "i0" [r] - *+[F]\dbox{$r_j \getsr I$; $R_j \gets r_j P$ \\ - $c_j \gets r_j \xor H_I(R_j, r_j X_i)$} ="j0" - [d] - *+[F]\dbox{Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$ \\ - $Z \gets r_j R_i$; $K \gets H_K(0, Z)$ \\ - $\chi_j \gets E_K(x_j R_i)$} ="j1" - [d] - *+[F]\dbox{Check $D_K(\chi_i) = r_j X_i$ \\ - Shared key is $H_K(1, Z)$} ="j2" - % - "i0" : |(0)/3.25cm/*+{(R_i, c_i)} "j1" - "i1" : |(0)/3.25cm/*+{(R_i, \chi_i)} "j2" - "j0" : |(0)/3.25cm/*+{(R_j, c_j)} "i1" - "j1" : |(0)/3.25cm/*+{(R_j, \chi_j)} "i2" - \end{graph} \] + \begin{protocol} + $r_i \getsr I$; $R_i \gets r_i P$; & + $r_j \getsr I$; $R_j \gets r_j P$; \\ + $c_i \gets r_i \xor H_I(R_i, r_i X_j)$; & + $c_j \gets r_j \xor H_I(R_j, r_j X_i)$; \\ + \send{->}{(R_i, c_i)} + \send{<-}{(R_j, c_j)} + Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$; & + Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$; \\ + $Z \gets r_i R_j$; $(K_0, K_1) \gets H_K(Z)$; & + $Z \gets r_j R_i$; $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi_i \gets E_{K_0}(x_i R_j)$; & + $\chi_j \gets E_{K_0}(x_j R_i)$; \\ + \send{->}{(R_i, \chi_i)} + \send{<-}{(R_j, \chi_j)} + Check $D_{K_0}(\chi_j) = r_i X_j$; & + Check $D_{K_0}(\chi_i) = r_j X_i$; \\ + Shared key is $K_1$. & Shared key is $K_1$. + \end{protocol} \caption{Summary of the Wrestlers Key Exchange protocol, $\Wkx$} \label{fig:wkx} @@ -1983,7 +2127,7 @@ Then: responds to Alice's message; \item $b R' = b R = b (r P) = r (b P) = r B$, and $a S' = a S = a (s P) = s (a P) = s A$, and therefore both parties compute their responses correctly; - and + and \item $r S' = r S = r (s P) = s (r P) = s R = s R'$, so $K_A = K_B$, and therefore they can decrypt each others' responses, and agree the same shared secret. @@ -2009,7 +2153,8 @@ version we present here. \label{sec:um} Our model is very similar to that of Canetti and Krawczyk -\cite{Canetti:2001:AKE}, though we have modified it in two ways. +\cite{canetti-krawczyk-2001:secure-channels}, though we have modified it in +two ways. \begin{enumerate} \item We allow all the participants (including the adversary) in the protocol access to the various random oracles required to implement it. @@ -2019,6 +2164,14 @@ Our model is very similar to that of Canetti and Krawczyk SK-security game. \end{enumerate} +\ifshort + +Readers interested in the details of the model should see Canetti and +Krawczyk's paper \cite{canetti-krawczyk-2001:secure-channels}, or the full +version of this paper. + +\else + \subsubsection{Overview} We briefly describe our modified model, pointing out the changes we have made, and how they apply to our protocol. Much of Canetti and Krawczyk's @@ -2044,13 +2197,13 @@ $n$ components, and party $P_i$ is given $(i_U, \mathbf{i}[i])$ as input. \subsubsection{Sessions} Parties don't act directly. Instead, each party runs a number of -\emph{sessions}. A session a triple $S = (P_i, P_j, s)$, where $i, j \in -\Nupto{n}$ identify the owning party and a \emph{partner}, and $s \in -\Bin^{\ell_S}$ is a \emph{session-id}. (The original model includes a -r\^ole, for distinguishing between initiators and responders. Our protocol -is symmetrical, so this distinction isn't useful.) If $P_i$ runs a session -$S = (P_i, P_j, s)$ and $P_j$ runs a session $S' = (P_j, P_i, s)$ then we say -that $S$ and $S'$ are \emph{matching}, and that $P_j$ is $P_i$'s +\emph{sessions}. A session is represented by a triple $S = (P_i, P_j, s)$, +where $i, j \in \Nupto{n}$ identify the owning party and a \emph{partner}, +and $s \in \Bin^{\ell_S}$ is a \emph{session-id}. (The original model +includes a r\^ole, for distinguishing between initiators and responders. Our +protocol is symmetrical, so this distinction isn't useful.) If $P_i$ runs a +session $S = (P_i, P_j, s)$ and $P_j$ runs a session $S' = (P_j, P_i, s)$ +then we say that $S$ and $S'$ are \emph{matching}, and that $P_j$ is $P_i$'s \emph{partner} for the session. At most one participant in the game is \emph{active} at any given time. @@ -2144,11 +2297,13 @@ it. The adversary \emph{wins} the game if either \item the adversary correctly guesses the hidden bit~$b^*$. \end{enumerate} More formally, we make the following definition. +\fi \begin{definition}[SK-security] \label{def:sk} Let $\Pi^{H_0(\cdot), H_1(\cdot), \ldots}$ be a key-exchange protocol which makes use of random oracles $H_0(\cdot)$, $H_1(\cdot)$, \dots, and - let $A$ be an adversary playing the game described previously, where $n$ + let $A$ be an adversary playing the game described \ifshort in + \cite{canetti-krawczyk-2001:secure-channels}\else previously\fi, where $n$ parties run the protocol~$\Pi$. Let $V$ be the event that any pair of matching, unexposed sessions completed, but output different session keys. Let $W$ be the event that the adversary's output bit matches the game's @@ -2170,7 +2325,7 @@ More formally, we make the following definition. \subsection{Security} In order to analyse our protocol $\Wkx^{G, \E}$ properly, we must describe -exactly how it fits into the formal model described in our formal model. +exactly how it fits into our formal model. \subsubsection{Sessions and session-ids} Our formal model introduced the concept of sessions, which the informal @@ -2224,15 +2379,16 @@ 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 - polynomially-bounded number of messages are delivered to it.} + acceptable in the simulation-based model of + \cite{shoup-1999:formal-model-key-exchange}. There it is required that a + key-exchange protocol terminate after a polynomially-bounded number of + messages are delivered to it.} \begin{figure} \begin{program} Function $\id{init}(n)$: \+ \\ \FOR $i \in \Nupto{n}$ \DO \\ \ind - $x \getsr \Nupto{|G|}$; \\ + $x \getsr \gf{q}$; \\ $\mathbf{i}[i] \gets x$; \\ $\mathbf{p}[i] \gets x P$; \- \\ \RETURN $(\mathbf{p}, \mathbf{i})$; @@ -2242,7 +2398,7 @@ sake of robustness.\footnote{% $X \gets \mathbf{p}[i]$; $X' \gets \mathbf{p}[j]$; $C \gets \emptyset$; \\ - $r \getsr \Nupto{|G|}$; + $r \getsr \gf{q}$; $R \gets r P$; $Y \gets r X'$; \\ $h \gets H_I(X, s, R, Y)$; @@ -2276,7 +2432,7 @@ sake of robustness.\footnote{% \OUTPUT $K_1$; \STOP; \end{program} - + \caption{Formalization of $\Wkx$} \label{fig:wkx-formal} \end{figure} @@ -2308,7 +2464,8 @@ We conclude that the only `interesting' session state is $r$. \subsubsection{Security} Having formally presented the protocol, we can now state our main theorem -about its security. The proof is given in appendix~\ref{sec:sk-proof}. +about its security. The proof is given in \ifshort the full version of the +paper\else appendix~\ref{sec:sk-proof}\fi. \begin{theorem}[SK-security of $\Wkx$] \label{thm:sk} Let $G$ be a cyclic group. Let $\E = (\kappa, E, D)$ be a symmetric @@ -2318,13 +2475,14 @@ about its security. The proof is given in appendix~\ref{sec:sk-proof}. 2 q_S \bigl( \InSec{ind-cca}(\E; t', q_M, q_M) + {} \\ \InSec{mcdh}(G; t', q_K) + n \,\InSec{mcdh}(G; t', q_M + q_I) \bigr) + - \frac{n (n - 1)}{|G|} + + \frac{n (n - 1)}{q} + \frac{2 q_M}{2^{\ell_I}}. \end{spliteqn*} where $t' = t + O(n) + O(q_S) + O(q_M q_I) + O(q_K)$. \end{theorem} +\ifshort\else \subsection{Insecure protocol variants} \label{sec:kx-insecure} @@ -2422,7 +2580,7 @@ set up. Although each of Alice and Bob have two sessions with session-id~$s$, this is allowed, since they are with different partners. The rest of the attack in fact proceeds identically to the previous case. - +\fi \subsection{Deniability} \label{sec:denial} @@ -2435,8 +2593,8 @@ 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 -security approach. +\cite{raimondo-2006:deniable-authn-key-exchange}, except that, as usual, we +opt for a concrete security approach. \subsubsection{Discussion} Our definition for deniability is that, for any adversary interacting with @@ -2518,7 +2676,7 @@ nature of the Wrestlers identification protocol. However, Bob can work with the judge to bring him the evidence necessary to convict Alice. Here's how. Alice's public key is $A$, and Bob's public key is $B$. The judge chooses -some session-id $s$, and $r \inr \Nupto{q}$. He computes $R = r P$ and $c = +some session-id $s$, and $r \inr \gf{q}$. He computes $R = r P$ and $c = r \xor H_I(B, s, R, r A)$, and gives Bob the triple $(s, R, c)$, keeping $r$ secret. Bob can now persuade Alice to enter into a key-exchange with him, with session-id $s$. He uses $(R, c)$ as his challenge message. When Alice @@ -2553,45 +2711,36 @@ formal description is shown in figure~\ref{fig:wdkx-formal}. \begin{figure} \begin{description} - \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime. + \item[Setup] Group $G = \langle P \rangle$; $\#G = q$ is prime. $H_I(\cdot, \cdot, \cdot, \cdot, \cdot)$ and $H_K(cdot)$ are secure hashes. $\E = (\kappa, E, D)$ is an IND-CCA2 symmetric encryption scheme. \item[Parties] $U_i$ for $0 \le i < n$. - \item[Private keys] $x_i \inr \Nupto{q}$. + \item[Private keys] $x_i \inr \gf{q}$. \item[Public keys] $X_i = x_i P$. \end{description} - \[ \begin{graph} - !{0; <8cm, 0cm>: <0cm, 3cm>::} - *+[F]\dbox{$r_i \getsr I$; $R_i \gets r_i P$} ="i-1" - [d] - *+[F]\dbox{$c_i \gets r_i \xor H_I(R_j, X_i, s, R_i, r_i X_j)$} ="i0" - [d] - *+[F]\dbox{Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$ \\ - $Z \gets r_i R_j$; $K \gets H_K(0, Z)$ \\ - $\chi_i \gets E_K(x_i R_j)$} ="i1" - [d] - *+[F]\dbox{Check $D_K(\chi_j) = r_i X_j$ \\ - Shared key is $H_K(1, Z)$} ="i2" - "i-1" [r] - *+[F]\dbox{$r_j \getsr I$; $R_j \gets r_j P$} ="j-1" - [d] - *+[F]\dbox{$c_j \gets r_j \xor H_I(R_i, X_j, s, R_j, r_j X_i)$} ="j0" - [d] - *+[F]\dbox{Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$ \\ - $Z \gets r_j R_i$; $K \gets H_K(0, Z)$ \\ - $\chi_j \gets E_K(x_j R_i)$} ="j1" - [d] - *+[F]\dbox{Check $D_K(\chi_i) = r_j X_i$ \\ - Shared key is $H_K(1, Z)$} ="j2" - % - "i-1" : |(0)/3.25cm/*+{R_i} "j0" - "i0" : |(0)/3.25cm/*+{(R_i, c_i)} "j1" - "i1" : |(0)/3.25cm/*+{(R_i, \chi_i)} "j2" - "j-1" : |(0)/3.25cm/*+{R_j} "i0" - "j0" : |(0)/3.25cm/*+{(R_j, c_j)} "i1" - "j1" : |(0)/3.25cm/*+{(R_j, \chi_j)} "i2" - \end{graph} \] + + \begin{protocol} + $r_i \getsr I$; $R_i \gets r_i P$; & + $r_j \getsr I$; $R_j \gets r_j P$; \\ + \send{->}{R_i} + \send{<-}{R_j} + $c_i \gets r_i \xor H_I(R_j, X_i, s, R_i, r_i X_j)$; & + $c_j \gets r_j \xor H_I(R_i, X_j, s, R_j, r_j X_i)$; \\ + \send{->}{(R_i, c_i)} + \send{<-}{(R_j, c_j)} + Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$; & + Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$; \\ + $Z \gets r_i R_j$; $(K_0, K_1) \gets H_K(Z)$; & + $Z \gets r_j R_i$; $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi_i \gets E_{K_0}(x_i R_j)$; & + $\chi_j \gets E_{K_0}(x_j R_i)$; \\ + \send{->}{(R_i, \chi_i)} + \send{<-}{(R_j, \chi_j)} + Check $D_{K_0}(\chi_j) = r_i X_j$; & + Check $D_{K_0}(\chi_i) = r_j X_i$; \\ + Shared key is $K_1$. & Shared key is $K_1$. + \end{protocol} \caption{Summary of the Deniable Wrestlers Key Exchange protocol, $\Wdkx$} \label{fig:wdkx} @@ -2601,7 +2750,7 @@ formal description is shown in figure~\ref{fig:wdkx-formal}. \begin{program} Function $\id{init}(n)$: \+ \\ \FOR $i \in \Nupto{n}$ \DO \\ \ind - $x \getsr \Nupto{|G|}$; \\ + $x \getsr \gf{q}$; \\ $\mathbf{i}[i] \gets x$; \\ $\mathbf{p}[i] \gets x P$; \- \\ \RETURN $(\mathbf{p}, \mathbf{i})$; @@ -2611,7 +2760,7 @@ formal description is shown in figure~\ref{fig:wdkx-formal}. $X \gets \mathbf{p}[i]$; $X' \gets \mathbf{p}[j]$; $C \gets \emptyset$; \\ - $r \getsr \Nupto{|G|}$; + $r \getsr \gf{q}$; $R \gets r P$; $Y \gets r X'$; \\ \SEND $(\cookie{pre-challange}, R)$; @@ -2652,13 +2801,14 @@ formal description is shown in figure~\ref{fig:wdkx-formal}. \OUTPUT $K_1$; \STOP; \end{program} - + \caption{Deniable key-exchange: formalization of $\Wdkx$} \label{fig:wdkx-formal} \end{figure} The security of this variant is given by the following theorem, whose proof -is in appendix~\ref{sec:sk2-proof}. +is \ifshort given in the full version of this paper\else in +appendix~\ref{sec:sk2-proof}\fi. \begin{theorem}[SK-security of $\Wdkx$] \label{thm:sk2} Let $G$ be a cyclic group. Let $\E = (\kappa, E, D)$ be a symmetric @@ -2687,14 +2837,17 @@ deniability of our protocols. \frac{q_M}{2^{\ell_I}} \] and - \[ \InSec{sim}(W_{\Wdkx^{G, \E}}, I_{\Wdkx^{G, \E}}, S_{\Wdkx^{G, \E}}; - t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), n_C) \le - \frac{n_C q_S}{|G|} + + \iffancystyle\[\else\begin{spliteqn*}\fi + \InSec{sim}(W_{\Wdkx^{G, \E}}, I_{\Wdkx^{G, \E}}, S_{\Wdkx^{G, \E}}; + t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), n_C) \le + \iffancystyle\else\\\fi + \frac{n_C q_S}{\#G} + \frac{q_M}{2^{\ell_I}}. - \] + \iffancystyle\]\else\end{spliteqn*}\fi The running time of the simulators is $O(t_A) + O(\mathcal{Q}_A q_M)$. \end{theorem} -\begin{proof} +\begin{longproof}{The proof of this theorem can be found in the full version + of this paper.} The simulators $S_\Wkx$ and $S_\Wdkx$ are very similar. We describe both here. Both are fake-world simulators, working as follows. \begin{enumerate} @@ -2702,7 +2855,7 @@ deniability of our protocols. giving each the public key $X_i$ from the common input. \item Suppose the adversary requests creation of a new session $S = (P_i, P_j, s)$. Then the simulator creates a new session, including a random - value $r_S \inr \Nupto{|G|}$, and computes $R_S = r_S P$, and $Y_S = r_S + value $r_S \inr \gf{q}$, and computes $R_S = r_S P$, and $Y_S = r_S X_j$. For $\Wdkx$, it sends the message $(\cookie{pre-challenge}, R_S)$; for $\Wkx$, it additionally computes $h = H_I(X_i, s, R_S, Y_S)$ and sends $(\cookie{challenge}, R_S, r_S \xor h)$. @@ -2754,17 +2907,17 @@ deniability of our protocols. adversary's auxiliary input. In this case the simulator must fail. But $R_S = r_S P$, and $r_S$ was chosen uniformly at random. If there are at most $n_C$ challenge sets in the auxiliary input then this happens with - probability at most $n_C/|G|$ for any given session. + probability at most $n_C/\#G$ for any given session. \end{itemize} We conclude that the simulator fails with probability - \[ \frac{q_M}{2^{\ell_I}} + \frac{q_S n_C}{|G|}. \] + \[ \frac{q_M}{2^{\ell_I}} + \frac{q_S n_C}{\#G}. \] (Note that we only consider $n_C = 0$ for $\Wkx$.) No adversary can distinguish the simulator from a real interaction unless the simulator fails, and the simulator is a fake-world simulator. We therefore apply proposition~\ref{prop:fakesim}; the theorem follows. -\end{proof} - +\end{longproof} +\ifshort\else \subsection{Practical issues} \label{sec:practice} @@ -2780,11 +2933,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 @@ -2848,11 +3001,15 @@ 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. +schemes also provide integrity of plaintexts +\cite{bellare-namprempre-2000:authn-enc-notions} (e.g., the +encrypt-then-MAC generic composition approach +\cite{bellare-namprempre-2000:authn-enc-notions,% + krawczyk-2001:order-enc-authn}, +and the authenticated-encryption modes of +\cite{rogaway-2001:ocb,bellare-2004:eax,% + mcgrew-viega-2004:gcm-security-performance}), +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 @@ -2873,7 +3030,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 @@ -2908,11 +3065,11 @@ Wrestlers protocol over UDP. \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 -\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$. +\cite{bellare-namprempre-2000:authn-enc-notions} (or, alternatively, +is an AEAD scheme \cite{rogaway-2002:aead}. 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 @@ -2921,9 +3078,9 @@ 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}. +\fi %%%-------------------------------------------------------------------------- - \section{Conclusions} \label{sec:conc} @@ -2934,7 +3091,6 @@ Finally, we have shown how to modify the key-exchange protocol for practical use, and proven that this modification is still secure. %%%-------------------------------------------------------------------------- - \section{Acknowledgements} The Wrestlers Protocol is named after the Wrestlers pub in Cambridge where @@ -2942,10 +3098,10 @@ Clive Jones and I worked out the initial design. %%%-------------------------------------------------------------------------- -\bibliography{mdw-crypto,cryptography2000,cryptography,rfc,std} +\bibliography{mdw-crypto} %%%-------------------------------------------------------------------------- - +\ifshort\def\next{\end{document}}\expandafter\next\fi \appendix \section{Proofs} @@ -3000,11 +3156,11 @@ X_j$ where $0 \le i < j < n$), we stop the game immediately and without crediting the adversary with a win. This only happens when the corresponding private keys are equal, i.e., $x_i = x_j$, and since the initialization function chooses private keys uniformly at random, this happens with -probability at most $\binom{n}{2}/|G|$. Since if this doesn't happen, the +probability at most $\binom{n}{2}/\#G$. Since if this doesn't happen, the game is identical to $\G0$, we can apply lemma~\ref{lem:shoup}, and see that \begin{equation} \label{eq:sk-g0-g1} - \diff{0}{1} \le \frac{1}{|G|} \binom{n}{2} = \frac{n (n - 1)}{2 |G|}. + \diff{0}{1} \le \frac{1}{\#G} \binom{n}{2} = \frac{n (n - 1)}{2 \#G}. \end{equation} In game~$\G1$ and onwards, we can assume that public keys for distinct parties are themselves distinct. Note that the game now takes at most @@ -3102,14 +3258,15 @@ We conclude that, for any adversary $A$, \Pr[V_4] = 0 \qquad \text{and} \qquad \Pr[W_4] = \frac{1}{2}. \end{equation} Putting equations~\ref{eq:sk-g0-g1}--\ref{eq:sk-g4} together, we find +\begingroup \splitright=4em minus 4em \begin{spliteqn} \Adv{sk}{\Wident^{G, \E}}(A) \le 2 q_S \bigl(\InSec{ind-cca}(\E; t', q_M, q_M) + {} \\ \InSec{mcdh}(G; t', q_K) + n \,\InSec{mcdh}(G; t', q_M + q_I) \bigr) + {} - \frac{n (n - 1)}{|G|} + + \frac{n (n - 1)}{\#G} + \frac{2 q_M}{2^{\ell_I}}. -\end{spliteqn} +\end{spliteqn} \endgroup The theorem follows, since $A$ was chosen arbitrarily. @@ -3197,7 +3354,7 @@ The theorem follows, since $A$ was chosen arbitrarily. = \frac{1}{2^{\ell_I}} \sum_\Cid \Ccount(\Cid) \le \frac{q_M}{2^{\ell_I}} \] - as required. + as required. Now observe that, in $\G2$, sessions don't actually check incoming challenges in this way any more -- instead we run the extractor. So, to @@ -3374,7 +3531,7 @@ The theorem follows, since $A$ was chosen arbitrarily. choose a random $m \in \Nupto{n}$, and when the adversary creates the session $S = S_k = (P_i, P_j, s)$, we abort the game unless $j = m$. Clearly we have $\Pr[F_6] = n \Pr[F_7]$. - + Finally, we can explicitly bound $F_6$. In $\G6$, the adversary's view is independent of the correct response $Y_S = r_S X_S = x_j R_S$ to $S$'s challenge. Therefore, if $A$ manages to send any message $\mu \notin M_T$ @@ -3427,7 +3584,7 @@ The theorem follows, since $A$ was chosen arbitrarily. The proof is almost identical to the proof of theorem~\ref{thm:sk}, in appendix~\ref{sec:sk-proof}. Unfortunately a black-box reduction doesn't -seem possible. +seem possible. We use the games and notation of section~\ref{sec:sk-proof}. @@ -3466,15 +3623,15 @@ the encryption scheme $\E$, with the \emph{same} key $K = K_0$, still provides secure channels. \subsubsection{Secure channels definition} -We (very briefly!) recall the \cite{Canetti:2001:AKE} definition of a secure -channels protocol. We again play a game with the adversary. At the -beginning, we choose a bit $b^* \inr \{0, 1\}$ at random. We allow the -adversary the ability to establish \emph{secure channels} sessions within the -parties. Furthermore, for any running session $S = (P_i, P_j, s)$, we allow -the adversary to request $S$ to send a message~$\mu$ through its secure -channel. Finally, the adversary is allowed to choose one ripe -\emph{challenge} session, and ask for it to send of one of a \emph{pair} of -messages $(\mu_0, \mu_1)$, subject to the restriction that $|\mu_0| = +We (very briefly!) recall the \cite{canetti-krawczyk-2001:secure-channels} +definition of a secure channels protocol. We again play a game with the +adversary. At the beginning, we choose a bit $b^* \inr \{0, 1\}$ at random. +We allow the adversary the ability to establish \emph{secure channels} +sessions within the parties. Furthermore, for any running session $S = (P_i, +P_j, s)$, we allow the adversary to request $S$ to send a message~$\mu$ +through its secure channel. Finally, the adversary is allowed to choose one +ripe \emph{challenge} session, and ask for it to send of one of a \emph{pair} +of messages $(\mu_0, \mu_1)$, subject to the restriction that $|\mu_0| = |\mu_1|$; the session sends message $\mu_{b^*}$. The adversary may not expose the challenge session. @@ -3517,7 +3674,7 @@ that \end{equation} Finally, we can bound the adversary's advantage at guessing the hidden bit $b^*$. We isolate (we hope) the challenge session $S$ by choosing a target -session at random, as before. Let $K_* = H_K(Z_S)$ be the key agreed by the +session at random, as before. Let $K^* = H_K(Z_S)$ be the key agreed by the session (if it becomes ripe). We define an adversary $B$ against the IND-CCA security of $\E$. The adversary $B$ simulates the game. If the adversary exposes the target session, or doesn't choose it as the challenge session, @@ -3541,7 +3698,7 @@ the advantage of our IND-CCA distinguisher. Then \end{document} -%%% Local Variables: +%%% Local Variables: %%% mode: latex %%% TeX-master: t -%%% End: +%%% End: