A Modular Approach to the Design and Analysis of Authentication

and Key Exchange Protocols

(Extended Abstract)

MIHIR BELLARE* RAN CANETTI~ HUGO KFLAWCZYK*

Abstract mand for Internet security solutions- it is important to

keep practical issues in mind from the start. This means
We prcscnt a general framework for constructing and analyz- that one cannot afford a significant sacrifice of simplicity
ing authentication protocols in realistic models of communi- and performance in order to achieve provability. Similarly,
cation networks. This framework provides a sound formal- one cannot afford definitions which are an “overkill” of the
ization for the authentication problem and suggests simple problem. It also requires a careful definition of the adver-
and attractive design principles for general authentication sarial model in order to capture the real threats of today’s
and key exchange protocols. The key element in our ap- global communications scenarios. Elements such as the con-
pronch io a modular treatment of the authentication problem current execution of many instances of the same protocol by
in cryptographic protocols; thii applies to the definition of different parties, the inherent asynchrony of actual message-
accurity, to the design of the protocols, and to their analysis. driven network protocols, and the scale of today’s networks
In particulnr, following this modular approach, we show how and applications must be considered.
to systematically transform solutions that work in a model of
idaalizcd authenticated communications into solutions that 1.1 The problems
are secure in the realistic setting of communication channels
controlled by an active adversary. The problem of “secure communications” is very broad, and
Using these principles we construct and prove the secu- encompassesa variety of sub-problems and goals. The fo-
rity of simple and practical authentication and key-exchange cus of this paper is authentication in communications, with
protocols. In particular, we provide a security analysis of special emphasis on the related problem of key exchange.
aomowell-known key exchange protocols (e.g. authenticated AUTHENTICATED COMMUNICATIONS. In a nutshell, the au-
Dlfllc-Hcllman key exchange), and of some of the techniques thentication problem deals with curbing adversaries that ac-
underlying the design of several authentication protocols tively control the communication lii used by the legit-
that are currently being deployed on a large scale for the imate parties. They may modify and delete messagesin
Intornot Protocol and other applications. transit, and even inject false ones; they also control the de-
lays of messages. (These adversaries may have additional
1 Introduction capabilities, for instance corrupting parties.) Our goal is to
guarantee authenticity of the communicated data; that is,
A major tssk in cryptographic research is to define, and pro- make sure that the system behaves (as much as possible) as
vide sound and efficient solutions for, the problem of secure if the links were ‘physically authenticated” and no message
communicntions, We need models and tools that enable was modified en-route or its origin misrepresented. Clearly,
the analysis of existing protocols as well as the development solving this problem is an essential step towards enabling
and analysis of new, improved solutions, Purthermore, in secure communications in a realistic network environment.
today’s cnvlronment -we are seeing a rapidly growing de- The authentication problem has received less attention
* Dopnrtmont of Computor Science & Engineering, Mail than secrecy and privacy issues, especially in the context of
E$icc 0114, UnivoreltyAof 9;.i;ornIa at San Drego, 9500 Gilman cryptographic protocols. Many of the fundamental works
La Jolla, Email: nihir9co.ucrtd.edu. and techniques for the design of cryptographic protocols
httpr~/vuv-cco.ucod.odu/uoerc/n~hfr. Supported in part by NSF were developed under the idealized assumption of ‘(authen-
CiAI’tEER Award CCR-002443Dnnd a 1090 Packard Foundation Fel- ticated links” between the communicating parties. Prime
lowahlp In Scloncoand EnSincorIng.
t IBM T.J. Watnon Ftcccarch Center, PO Box 704, Yorktown examples are the Diflle-Helhnan key exchange protocol [DHl
Hoirthta. Now York 10GDS.Email: cMcttiQuatson.ibn.ccn. as well as much of the work on secure distributed function
r Dcpnrtmcnt of Electrical En3inoorin3, Technion, Haifa 32000,Is- evaluation (eg, [y, GMW, BGW, CCD]). Thii abstraction
raol, and IBM T,J, Watson Rccoarch Center, Now York, USA. Email: of the authentication problem is of great value when devel-
oping higher level protocols. However, implementing these
uauthenticated links” in realistic environments is far less
trivial than one would have initially imagined. In partic-
ular, networks are often asynchronous in nature, and proto-
cols are often message-dtiuen. Here authentication cannot
be achieved by simply applying signatures or message au-

419
thentication codes to the transmitted data (although these an authenticator. We formalize this notion and show several
primitives are useful tools in 6he design of complete solu- constructions of authenticators.
tions). In particular, we shonehow the construction of aut1~ent.L
Several facets of the authentication problem have re- caters is greatly simplified by reducing their design to that
ceived a rigorous treat,ment, most notably entity authen- of much simpler protocols, called hlT-authenticators, whose
tication betnveen two parties [BRl] and authenticated mes- goal is limited to authenticate a simple eschange of mcs-
sage t,ransmission [Ra]. Hov;ever there are basic and gen- sages between the parties. (Here hlT stands for “messago
eral quest.ions t.hat still remain umreated. The first pxt of transmission” .) These protocols have a very limited scope
our effort will go into properly formulating and then solving and are significant,ly easier to build and analyze than gon-
these. The tools that emerge are not only useful in their eral authentication protocols. We show constructions of hlT-
own right, but enable us to treat a more popular but notori- aut.henticators based on standard cryptographic funct,ions
ously difficult problem, namely authenticated key exchange, such as messageauthentication codes, digital signatures and
in effective nays. public key encrypt.ion.
Following our methodology, a protocol intended to work
KEY EXCHANGE. An aut,henticated key eschange protocol in an unauthenticated network can be designed (or ana-
enables two parties to end up with a shared secret key in lyzed) in two independent stages: first design and prove the
3 secure and aut,henticated manner. That is, no (computa- protocol in the authenticated model; then apply a Iparticu-
tionally limited) adversary can impersonate any party dur- lar authenticator. It is now guaranteed that the L’compilcd”
ing the protocol or learn any information about the value of protocol maintains, in the unauthent,icated environment, the
the exchanged secret,. Such protocols are an essential piece same behavior that the original one has in an ideally au-
in the process of providing authenticated communication. thenticated environment. The analysis of t,hese two picccs
On the ot,her hand, they are themselves esamples of prob- is independent of each other and each piece can bc “lie-used”
lems in t,he domain of authenticated communications. separately to get different protocols with different flavors of
Authent,icated key eschange has been estensively stud- authentication. For esample, one can use any of the ba-
ied (wo survey some of thii work at the end of this section). sic authenticators proven in this paper in new authentira-
Esperience indicates bhat,it is far more subtle and harder to tion protocols without the need to m-prow the properbies
achieve than may appear at first glance. A very large num- of these authenticators. In particular, one gets the security
ber of proposed protocols succumb to attacks not envisioned of the authenticated protocol solely based on the sbrength
by their designers. of the cryptographic functions underlying the design of t.ho
The first works to provide formal foundations in thii area (IT-) authenticators. This modular approach has important
were those of Bellare and Rogavray [BRl, BR’J]. They ad- practical consequences: it simplifies the design ancl analy-
dressed t.he problems of ent,ity authentication and key es- sis work, and helps building t.he protocol in ways that arc
change in the tv;o party, shared key model, and the problem easier to implement and maintain in practice. It also pro-
of three party key dist,ribution (Needham Schroeder [NS], or vides a “debugging tool” for the protocol designer and may
Kerberos [SNS] model). Generalizations are possible in or- help cleaning protocols from unnecessary elements. WC CS-
der to accommodate other tasks and models of interest. But emplify these aspect,sthrough our construction and analysis
these formalizations are not always easy to work with. They of key eschange protocols as discussed below.
also regard key-exchange as a stand-alone problem without
putting it in a t,he wider contest of authentication. Most THE DEFINITIONAL APPROACH. The definition of nuthenti-
importantly, each new key eschange protocol must be re- caters involves a formal treatment of the authenbicnted and
analyzed from scratch, and a proof provided that it meets the unauthenticated models, as well as defining the notion
one of t,he definibions. of equivalence between protocols running in thesc different
models. A basic ingredient in our formalization work is the
1.2 Our approach and contributions notion of emulation of one protocol by another. This cap-
tures the idea of ‘*equivalent behavior” of protocols running
We present. definitions and analysis techniques that provide in different models of communication. (Below WCillust.mto
a unified treatment. of the different aspects of the authen- this notion by sketching how it is used to define BXIW@IiCy-
tication problem, t.hus leading us to to simplify the process eschange protocols.) The notion draws from general defini-
of designing and analyzing authentication protocols. The tions of secure multi-party protocols [MR, Bea, Cal].
key element is our modular treatment of the aut,hentication This definitional approach has several important propcr-
problem. We start wit,h solutions that work in a model of ties which distinguish our work from previous treatment of
idealized aut.henticated communications and then transform the authentication problem: it makes the intuit.ion behind
these solutions, via automatic techniques (or Vompilers”), the definitions clearer, it provides with uniform definitions
into solutions that work in the realistic unauthenticated set- for the diierent models of communication, and, very im-
ting. portantly, it enables our constructive methodology of trans-
AUTHENTICATORS. The core component in our modul:ar ap- forming secure protocols from the idealized models to t.he
proach is t,he construction of “universal compilers” C that realistic ones. In particular, this uniform treatment helps
transform (or emulate) any protocol r in an ideally authen- positioning key eschange in the broader contest of t.he DU-
ticated model into a protocol x’ = C(n) that achieves es- thentication problem.
sentially the same task as TT(in a well defined sense) but KEY EXCHANGE.A main beneficiary of the above approach
withstands a much stronger and realistic adversary; not only is the kegsezchengeproblem. We define this problem and its
can this adversary corrupt a subset of the parties, but it also security requirements in a way that can fit both the nuthon-
has total control over t,he communication links connecting ticated and unauthenticated models. We do that by first
all t,he parties (corrupted or not). We call such a compiler C defining an ideal key es&urge process, where a fully honest
and trusted party provides other parties, upon request, with

420
 nharcd secret keys. A secure key exchange protocol, in either proved secure some simple protocols. Various works address
the authenticated or unauthenticated model, is then defined extending their framework to other settings and problems;
as ono where tho result of the actions of the adversary can be for example, Shoup and Rubm to smart card settings [SRI;
ofl’lciantly simulated (or emulated, using our terminology) in Lucks to consider dictionary attacks [Luc]; Blake-Wilson,
tho idonl modal. In particular this means that “bad events” Johnson and Menezes PIMe, BJM] and Bellare, Petrank,
(such as secrecy compromise, replay of exchanges, imper- Rackoff and Rogaway [BPRR] for the public key setting. See
sonation, etc.) can happen in the actual protocols only if [MW, Chapter 121for general background and information
they could have happened in the ideal model. In order to on the subject of authenticated key exchange.
achieve menningful results, we carefully define the attacker A d&rent approach to the analysis of authentication
in the idea1 model to capture some of the unavoidable capa- and key exchange protocols is provided through the use of
bilities of a realistic attacker such as the ability to control logic tools. The best known example is the BAN logic of
the scheduling of key exchanges, and to corrupt all, or parts, [BAN]. This approach, however, abstracts out the crypto-
of the information kept by the communicating parties. graphic mechanisms and replace them with ideal primitives,
Thio approach has as a prime advantage that it is appli- thus liiting the signi&mce of a successful analysis of a
cable to different flavors of key exchange protocols, such as given protocol (on the other hand, these tools have proven
public key and shared key protocols, and can accommodate useful to ‘debug” some weaknessesfrom certain authentica-
particular variants (e.g., identity protection, perfect forward tion protocols).
accrccy, ctc,) without requiring a complete m-definition of ORGANIZATION. In Section 2 we present our communication
tho problem. models and formulate the central notion of an authenticator,
Once the problem of key exchange is formally defined, we i.e. a compiler for authenticated networks. We show how
une the above modular authentication techniques to build to build such an authenticator out of a much simpler proto-
and analyze specific key exchange protocols: we start with col (an hiT-authenticator) intended to authenticate a simple
a key-oxchange protocol that is proven secure in the sim- exchange of messages. In Section 3 we present two simple
pler authenticated model, and then apply to it an authen- such hlT-authenticators based on pubhc key techniques. In
ticntor that transforms it into a key exchange protocol se- Section 4 we define key exchange protocols and show how
cure in the unauthenticated model. We exemplify thii pro- to use such protocols to construct authenticators which in
cc33 using the basic Diffie-Hellman protocol for idealized
turn form the basis for authentication of bulk data over typ-
authenticated links [DH] and transforming it into several ical communication networks. In Section 5 we show the
flavors of “authenticated Diffie-Hellman” through different application of the tools developed in previous sections to
MT-authenticators. A3 said before this reduces to only prov- the construction of specific secure key exchange protocols.
ing tha basic Diffie-Hellman protocol in the much simpler Thii is exempliEed through several important variants of the
nuthonticatcd model. Remarkably, we are able to provide in authenticated DiEe-Helhnan protocol. Proofs are omitted
this way with analysis of several of the underlying key ex- throughout, for lack of space. They appear in [BCK].
chnngo mechanisms used in some well known practical key
distribution protocols (see [DOW, Kra, ISO, HC]).
As another demonstration of the power of these tools, 2 Authenticators
and as a significant result by itself, we prove validity of the
following common approach to authenticating bulk commu- We introduce authenticators, i.e. compilers for unauthen-
nications: the parties first exchange a key using a particular ticated networks, and show how to build them from sim-
key oxchangc protocol and then use this key to compute a ple protocols. Informally, an authenticator takes a proto-
MAC (messageauthentication code) function on the trans- col for (ideally) authenticated networks and turns it into a
mittcd information. Using our methodology we show that protocol that has similar input-output characteristics in an
any sccuro key exchange combined with a secure MAC func- unauthenticated network. Here we formalize thii notion and
tion in this way represents a good authenticator. present a general methodology for building authenticators.
In existing unauthenticated networks (such as the Inter-
RELATED WORK, A3 indicated above, the design of these net) an adversary may have control over the deley and order-
protocols has a long history in which many protocols are ing of messages. This control gives the adversary consider-
proposed and broken. The works of Bird et al. [BGH+] able powers, and in particular allows a host of attacks called
nnd Diflla ot al. [DOW], the first in the model of shared man-in-the-middle attacks. In addition, protocols that do
accreta and the second in the public key model, exposed not depend on timings of messagesare typically preferable
aevernl of the subtleties involved. This included issues like in practice. In order to captnre these concerns we allow our
denling with interleaving of different runs (or sessions) of a adversaries total control over the scheduling of messages.
protocol and the importance of binding identities of sender Formally, this modeling is reminiscent of the esynchmnous
and receiver to the exchanged information. These works also model used in the theory of secure distributed computing
mado clear the fact that no satisfactory definitions existed in (see [BCG] for instance). Yet, it is stressed that the notion
the iitcrnture for this kind of protocols (in particuhu, they of asynchrony there is different from the one here in several
point out thnt previous extensive work in formalization of respects; in addition the motivations are different.
cryptographic primitives and protocols did not cover these In Section 2.1 we present basic definitions that are cen-
bscic authentication protocols). tral for our formalization and techniques. These include a
Tho above-mentioned works of Bellare and Rogaway [BRl, formalization of (message-driven) protocols and of the ad-
BRZ] provided formalizations for certain cases. They intro- versarial model for authenticated and unauthenticated net-
duccd the model of an adversary in charge of all communica- works, as well as the definition of protocol emulation and
tlona, modeled sessions and session key reveal attacks, and of authenticators. In Section 2.2 we present a refinement
suggested that the session key should be strongly secure, of these definitions aimed at capturing the peculiarities of
in tho sense of semantic security. They also provided and protocols that involve different sessions. In Section 2.3 we

421
present. a general approach for designing and analyzing au- current state of the corrupted party Pie3 In addit,ion, from
thenticators. The approach regards an-authentic&or-as a this point on A can add to the set M any (fake) messages,
‘lower layer’ communication protocol; this considerably fa- as long as pi is specified as the sender of these messages.
cilitates designing and proving security of authenticators. In The corrupted party appends a special symbol to its out-
the rest of this work we concentrate on authenticators built put, specifying that it is corrupted. From this point on t,hc
using t,his approach. corrupted party is no longer activat,ed (a~ its actions can
be taken by the adversary itself), thus its output does not
2.1 Basic definitions gr~nr.~ We refer to an adversary as described here as an
Ahl-adversary.
&,rESSAGE-DRIVEN PROTOCOLS. A message-driven protocol The global output of running a protocol is the concatc-
is an iterative process described as follows. The protocol nation of the cumulative output,s of all the parties, together
is invoked by a party with some initial state that includes with the output of the adversary. The output of the advcr-
the protocol’s input, random input, and the party’s identity. sary is a function, specific to each adversary, of the adversary
Once invoked, t,he protocol waits for an activation. An acti- view. The adversary view is all t,he informat.ion seen (and
vation can be caused by two types of events: the arrival of a derived) by the adversary throughout the comput,ation, to-
messagefrom the network, or an external request. (Ester- gether with its random input. Recall that t.he output of the
nal requests model information coming from other processes parties includes registration of important events that oc-
run by the party). Upon activat,ion, the protocol processes curred during the esecution (such as corruption of parties),
the incoming data together with its current internal state, This provision ensures that these events are considrred in
generating a new internal state, as well as generating outgo- the security requirement (Definition 1 below).
ing messagesto the network and external requests to other We use the following notation. Let ADVn,d(z, 3 denote
protocols (or processes) run by the party. In addition, an the output of adversary d when interacting wibh partics
output value is generated. We regard the output as cumu- running protocol r on input P = 21. . . x,, and random input
lative. That is, initially the output is empt.y; in each acti- r’= TO.. . T,, as described above (TO for .& Zi and Ti for party
vation the current. output is appended to the previous one. Pi, i > 0). Let AUTHn,d(Z,;T3i denote the cumulabive output
Once bhe activation is completed, bhe protocol waits for the of party Pi after running protocol A on input 5 and random
nest activation. Formally, a protocol x is captured by a input ?, and with an Ahf-adversary A. Let AUTHn,d(z, ?) =
(probabilistic) function:
Let AuT&.,d(5) denote the random variable describing
n(current state, incoming message,esternal request) = AUTH,,d@, q when T’is uniformly chosen.
(new state, outgoing messages,outgoing requests, output)
THE UNAUTHENTICATED-LINKS hlODEL (Uhl). BaGcallS: dlC!
unauthenticated-links model of computation is similar to the
THE AUTHENTICATED-LINKS hlODEL (Ahf). There are 71par- authenticated-links one, with the esception that here the
ties, Pl...P,,, each running a copy of a message-driven pro- adversary li, referred to as a uhf-adversary, is not limited
tocol x. The comput,ation consists of a sequence of acti- to deliver messagesthat are in M. Instead, it can activate
vations of ‘ITwithin diierent parties. The activations are parties with arbitrary incoming messages (even with fake
controlled and scheduled bv an adversary A.’ That is, ini- messagesthat were never sent).
tially and upon the compleiion of each activation A decides In addition, here we augment the protocol z with an
which part.y to activate nest; A also decides which incoming initialization function I that models an init,ial phase of out-
messageor external request the activated party is to receive. of-band and authenticated information eschange between
The outgoing messages,outgoing external requests and the the parties. (This function models the necessary boot&rap-
output generated by the protocol become known to d. The ping of the cryptographic authentication functions, e.g. by
new internal state remains unknown to A. letting the parties choose private and public keye for some
In the aut.hent.icated-links model, A is restricted to de- asymmetric cryptosystem and trustfully eschange the public
livering messagesfaithfully. That. is, we assume that each keys.) Function I takes only a random input T, and out.puts
outgoing messagecarries the identities of the sender P, and a vector I(T) = I(T)o....~(T),. The component I(T)o is the
of the intended recipient Pj. When a messageis sent by a public information and becomes known to all parrties and to
part.y (ie, when the messageappears in the list of outgoing the adversary. For i > 0, I( becomes known only to 8.’
messagesin an activation of x within the party), the message
is added to a set lli of undelivered messages. Whenever A 3By limiting the adversary to learn only the current ntnto of the
corrupted party we allow protocols that erosc dota. An nitcrnntivo,
activates a party Pj on some incoming messagem it must be more conservative formalization (which we do not ndopt) niiowo tho
that m is in the set Af and t.hat Pj is the intended recipient adversary to learn ail the past internal states of the party, thus mnk-
in m. Furt.hermore, m is now deleted from JV.~ We stress ing erasures pointless. This more conservative formniizntion capturc~
that A is not required to maintain the order of the messages, the reluctance of parties to base their security on the good will of
nor is it bound by any fairness requirement on the activation other parties to locally erase data. See [CFGN] for n dincuc~ion. In
this work, the distinction between the two formaiizations mill becomc
of parties, nor is it required to deliver all messages. There apparent in Section 6.
are also no limitations on the cztemal requests that A issues. ‘We do not limit the number of parties that the ndvernnry can
In addit,ion to actiwting parties, the adversary .4 can corrupt. This reflects our goal of providing nuthcnticity agninnt ad-
corrupt parties at wish. Upon corruption A learns the entire versaries that corrupt any number of parties.
‘The initialization function I models a ‘perfectly nccuro’ initial
‘Ail the adversaries in this paper are probabilistic polynomial exchange where the private information of ail parties is chonon ac-
time. cording to the protocol, and ail pnrties learn tho nuthentic public
2Hcre we assume that no messarre armears twice. Alternatively, information pertaining to ail othor partios. Aitornntiveiy, the initial
one can add message-ID’s to messa& to-make them unique. information exchange among the parties can bo modoied vin an es-
piicit in-band communication phase where the ndvorsary in restricted

422
 We define UNAUT&,U(~!, fl and UNAUTH~,U@) analogously 2.2 Incorporating sessions
to AUTlln,~(#, 3 and AUTH,,A@), where here the computa-
tion is carried out in the unauthenticated-links model. The Definitions 1 and 2 treat each party as a monolythic en-
initialization function I is part of the description of protocol tity: either a party is totally corrupted or it is totally se-
Tr. cure. However, communication protocol5 often have addi-
tional structure that allonrs a party to have, at the same
EMULATION OP PROTOCOLS. We define what it mean5 for time, several “independent conversations” with other par-
a protocol 7~’in the unauthenticated-links model to emulate ties. (Two parties may even have several parallel “conversa-
a protocol qr in the authenticated-links model. We want tions” running between them.) These conversations, often
to capture the idea that ‘running n’ in an unauthenticated called sessions, may be very different fFom each other, and
network has the same effect,as running 7~in an authenticated in particular may have different security requirements. It
network’. This is done following a general approach used for is thus convenient to let each session have its own cryp-
doflning secure multi-party protocols [MR, Bea, Cal]. That tographic protection mechanisms, and to ensure that ses-
in: sions are “cryptographically independent” from each other
Doflnition 1 Let ‘IFand I? be message-driven protocols for as much as possible. That is, we want to make sure that
n parties, We sau that T? emulates A in unauthenticated net-
compromising the security of one session will have as little
worko iffor aag UM-UdversaflJu there exists an AM-adversary
effect as possible on the security of other session run by the
same party.
Jt ouch that for all input vectors 2,
To accomodate the session structure, we refine defini-
AUTll,&?) & UNAUTH,IJ&) (1) tions 1 and 2 as follows. First we refine our formalization
of message-driven protocols. One or more subroutine5 (or
where & denotes ‘computationally indistinguishable’.’ sub-protocols) can be defined within the code of a protocol.
Rcquiromont (1) incorporates many conditions. In particu- The synta of each sub-protocol is similar to the syntax of a
lar, the combined distributions of the outputs of the parties, (message-driven) protocol described in Section 2.1. During a
the advcrsnry’s output, and the identities of corrupted par- run of the protocol several invocation5 of these sub-protocols
tics, ohould be indistinguishable on the two sides of (1). In may occur. A protocol may classify some of these invoca-
general, this condition captures the required notion of “se- tions as sessions.’ Typically, the local state of a session is
curity cquivalencc” between the protocols in the sense that mostly independent of local state of other sessions. (Yet,
any conscqucnccs of the actions of the strong UM-adversary often sessions do share some limited amount of state, e.g.
ngainst oxccutions of the protocol 7r’ can be imitated or the public and private keys of the party.) Each session is
achiovcd by tho weaker Ah+adversary against the runs of identified by a unique session ID. Notice that a messagesent
protocol 7~without requiring the corruption of more (or dif- from a sender to an intended recipient is part of the sender’s
ferent) parties. session and the recipient’s session. We assume that such a
An authenticator is a ‘compiler’ that take5 for input pro- messagecarries, iu addition to the identities of the sender
tocola designed for authenticated networks, and turns them and receiver, also the ID corresponding to the sender’s ses-
into ‘cquivalcnt’ protocols for unauthenticated networks: sion and the ID corresponding to the recipient’s session.
Upon activation of the protocol with au incoming mes-
Daflnition 2 A compiler C is an algorithm that takes for sage m, a special code called a session manager is executed.
input deocriptions of protocols and outputs descriptions of Typically, the sessionmanager activates the session specified
protocols. Aa authenticator is a compiler C where for any in m with incoming messagem. (Alternatively, the session
protocol ST,the protocol C(n) emulates 7~in unauthenticated manager can decide to activate several sessions, to invoke a
networks, new session, or to discard the incoming messagewithout in-
In particular, authenticators translate secure (in some well voking any session.) In addition, if an activated session gen-
defined sense) protocols in the authenticated-links model erates outgoing requests t&k that are addressed to other
Lnto accure protocols in the unauthenticated-links model. In sessions PI..& within the party, then sessions p1...& are
the following sections we show constructions of authentica- activated, one by one, each pi with incoming request ti. Fi-
tors nnd their applications (e.g., we show how to transform nally, the session manager outputs all the outgoing messages
the bwic Dific-Hellman protocol that runs securely in the from all the activated sessions.
authonticatcd-links model into a secure key exchange proto- Although all sessionsare run by the same party, we would
col in the unauthenticated-links model). like to think of the different sessionsas of independent mod-
ules to a large esteut. In particular, we want to allow
to bo nutbcntlcntod (lo to deliver only messages in M) and perhaps the adversary to compromise the security of only some of
alflo synchronous. This nltornntive npproach has the advantage that it
captures posslblo wonkncssos of methods for inltial key exchange (es, the sessions within some party. In thii case we want the
al’ protocols for certification nuthorlties). In particular, this approach uncompromised sessions to proceed uninterrupted. In or-
allown tho advorsnry to corrupt partles during the initial phase. In der to capture these additional requirements, the definitions
thlo work v/o ‘abstract out’ tho initial cxchango phase and stick to the of the authenticated-links and unauthenticated-links model5
Inltlnllzntlon function formallzntion.
Alao noto that The lnitlallzntlon function I allows for other type-s of are enriched as follows. Recall that a protocol may specify
lnltlnl oxcbnngcs, other tbnn exchanging public keys of an asymmetric distinct sessions(at run-time). A well-defined part of the lo-
cryptosyatom. For lnetnnco, I can contain shared secret keys betvzeen cal state is associated with each session. In both models we
OIWII pair of pnrtlcs. Conocquontly, thls same model can be used to
nnnlyzo also obnrod-key based authontlcntlon protocols. In this work ‘Although the previous paragraph follows the common interpretn-
wo concontrnto on lnltlallzation functions where the parties do not tion of a session as an object that involves two (conversing) parties,
ahnro aocrot dntn. here we define a session as a syntactic object that is local to a party.
‘TWO dlstrlbutlon ensembles arc computationally indistinguish- This greatly simplifies the presentation. In fact, a conversation be-
able If no polytlmo adversary can dlstlngtdsh them with more than tween two parties is now a pair of sessions - one session wSthin each
nagllglbla probnblllty. Hero the asymptotics is over a security param- of the involved parties.
otcr tlmt la lmpliclt In the descrlptlon.

423
allow the adversary an additional type of corruption, called
a session corruption. In a session corruption the adversary A m : B
learns only t.he internal state associated with a particular
session. In addition, a special value is added to the party’s m. NR
output specifying that the particular session (identified by
its session ID) has been corrupted. Once the adversary cor- m, SICXb.(m,NB,B)
rupts a session, it can add any (fake) messagesto the set
fif of undelivered messages,as long as the specified origin of
these messagesis t.he corrupted session. The rest of Defini-
tions 1 and 2 remains unchanged. Figure 1: Signature based hlT-authenticator
We maintain t,he convention that all corruption requests
made by the adversary are registered in the parties’ outputs,
thus they become part of t,he global output of the compu- all parties.) Now, authenticate each message indcpendentl~
tation. Thii convention ensures that if protocol X’ emulates from all other messages. That is, the hlT-authenticator in-
?r then ?r’ must preserve the partitioning of protocol ‘ITinto vokes an independent copy of some simple protocol for each
sub-protocols, and have similar session structure and session message of the original protocol. One may think of such
numbers. hlT-authenticator as ones that consider each sending of a
message as a session, and authenticate each session sepa-
rately.
2.3 hlT-authenticators Applying Theorem 3, the two hfT-authenticators can be
We present the following general technique for designing au- made into full-fledged authenticators. In particular, they
t,henticators. First design a ‘lower layer’ protocol X that play a central role in our constructions of key-exchange pro-
takes external requests for sending messagesand sends these tocols in Section 5.
messagesin au authenticated way. Next, given some proto-
col x (designed to work in the authenticated-links model), 3.1 A signature-based hlT-authenticator
the aut,henticator will output a protocol 7r’ that is identical
to protocol n wit.h the exception that messagesare deliv- We construct an hlT-authenticator, &, based on public key
ered t,hrough X. That is, instead of sending messagesto the signatures. The initialization function I tist invokes, once
for each party, the key generation algorithm of a signature
network, X is activated for delivery of these messages,and
instead of receiving incoming messagesfrom the network, scheme secure against chosen messageattack with security
parameter k. Let SIGNand VER denote the signing and ver-
t.he messagesare taken from X’s output. We prove that this
ification algorithms. Let si and vi denote the signing and
technique yields valid authenticators. verification keys associated with party Pi. The public infor-
More precisely, consider the following simple protocol,
called the message transmission (hIT) protocol, and designed mation is all public keys: 10 = vl...v,. Pi’s private informa-
for authenticated networks. The protocol take-sempty input. tion is Ii = Sic
Upon activation within Pi on external request (Pi, m), party Next, when activated, within party pi and with external
Pi sends bhe message (pi, PJ,m) to p&y Pj, and outputs
request to send messagem to party Pj, protocol .&o invokes
‘Pi sent m t0 Pj’a Upon receipt of amessage (Pi, Pj,m), a two-party protocol jSIG that proceeds as follows. (Since
PJ OUtpUtS ‘Pj received m from Pi’. &IO involves only two parties, we use A and B instead of Pi
Let X be a protocol that emulates hlT in unauthenticated and Pj. Also, in the following description we alternate bc-
networks. (We call such protocols hfT-authenticators.) Then, tween instructions for the sender A and for the recipient B.)
define a compiler CAas follows. Given a protocol r, the gen- First, A sends ‘message:m’ to B. (A also outputs ‘14 sont
erated protocol ‘IT’ = CA(~), running within party Pi, first message m to B’.) Upon receipt of ‘message:m’ from ti,
invokes A, Next, for each messagethat n sends, ?r’ activates party B chooses a random value NB ER (0, l}‘“, and sends
X wiith external request for sending t,hat messageto the spec- ‘challenge: m, NB a to A. Upon receipt of ( challongo: m, Nn
ified recipient. Whenever 7r’ is activated with some incoming from B, party A sends ‘signature:m,SIGN,A(m,Ng,B)’
message,it activates X wit.h this incoming message.When X to B. Upon receipt of ‘signature:m, SIGNS,, (m, Na, B)‘,
oubputs ‘Pi received m from Pj’, protocol R is activated party B accepts m (ie, it output,s ‘B rocoivod m from
with incoming messagem from Pj. We call authenticators A’) if the signature is successfully verified. Pictorially, the
t,hat follow thii design layered authenticators. This name is exchange for a single messagecan be described as in Figure 1.
justified by the following theorem.
Proposition 4 Assume that the signature scheme in use is
Theorem 3 Let A be an hlT-authenticator (i.e. A emulates secure chosen message attacks. Then protocol &la
against
hlT in unauthenticated networks), and let C,J be a compiler emulates protocol hlT in unauthenticated networks,
constructed based on X as described above. Then CA is an
authenticator. Proof: See [BCK]. cl
cl REMARKS. 1. Protocol Xslo can be modified to roplnce
Proof: See [BCK].
the challenge NB in the second flow with a counter that
makes sure that no value appears twice. The proof rc-
3 Two simple hiT-authenticators mains unchanged. Yet, now Xslc has to ‘maintain common
state’ among the different ‘sessions’ (i-e, among the activa-
We present two simple AiT-authenticators. These hlT-authent- tions pertaining to different n-messages). Maintaining state
icators adopt the following approach. Assume that the par- across sessionsis problematic and inadvisable in actual BYE-
ties have set up keys of an asymmetric cryptosystem. (That terns.
is, each party has its private key as well as the public keys of

424
 2. Another possible modification of &lo is to avoid the sec-
A m : B
ond flow altogether, and collapse the first and thud flows to
a single flow where A signs (m, B). To avoid replay of mes-
sagesby the adversary, each party will maintain a database
of all the messagesreceived in the past and will accept only
new mcnsagcs, Yet, this protocol too requires the party to m , hfACivB (m, B)
maintain (a lot of) state across sessions, to the point of im- b
practicality,
3. Ono does not need to send the messagem in each of the
flows of the protocol. A can send it in the first flow only or Figure 2: Encryption based hlT-authenticator
oven in the last flow only (in the latter case the first flow
can just carry a notice that there is a message “waiting for
dolivcry’,). The flow from B to A does not need to carry [RS’, and that the MAC scheme in use is secure. Then pro-
the messagebut needs some unique “identifier’, (similar to tocol &SC ernulates protocol MT in unauthenticated networks.
a session-ID) that bounds the particular value of the chal- Proof: See [BCK]. 0
ionge No to the messagebeing transmitted.
4, All the thrco elements signed by A in the third flow REMARKS. 1. Proposition 5 needs only a considerably
nro necessary, Omitting any one of these elements makes weaker property than m&fledged security against chosen ci-
our proof fail and actual attacks against the security of the phertext attacks of the encryption scheme. That is, forger
scheme are possible, This includes the less obvious case in 3 (m the proof of Proposition 5), as well as distinguisher
which a’s identity is omitted. An attack in this case was ‘D, do not need a full-fledged decryption oracle. Instead,
dcncribcd by Diffio et al [DOW]. they only need to know, given ENC~- (N’) and a value v, the
appropriate MAC (ie, MACpp (v)).
3.2 An encryption-based m-authenticator 2. An alternative MT-authenticator, based on encryption
schemes that are non-malleable against chosen cipher&t
We construct a MT-authenticator, XENC,based on public key attacks, is described in [DDN]. Their construction does not
encryption, In addition, &NC uses a messageauthentication use MAC schemes; instead it uses the ‘full power’ of the
(MAC) scheme. This protocol is based on the authentica- decryption oracle.
tion technique underlying the key exchange mechanisms in
[Kra], (It is also reminiscent of the [DDN] messageauthenti- 4 Key exchange protocols: Definitions and usage
cation protocol.) The initialization function I flrst invokes,
once for oath party, the key generation algorithm of a public In Section 3 we presented authenticators that treated each
key encryption schemesemantically secure against chosen ci- messageseparately. Such authenticators are not suited for
phortoxt attack in the senseof [BS], with security parameter authentication of a large number of messagesexchanged be-
k,” Lot 6NcJand DIE denote the encrypting and decrypting tween two parties since they involve a costly public-key oper-
algorithms, and let MAC denote the MAC schemein use. Let ation (ie, encryption, decryption, signature or verification)
et and dl denote the signing and verification keys associated per message. When transmitting many messagesbetween
with party Pi. The public information is all the public keys: two parties the following approach is usually taken: first
lo = cr.,,c,,, Pi’s private information is li = di. have the parties engage in a key exchange protocol, where
Next, when activated within party A, and with exter- they obtain a common key known only to the two parties.
nnl rcqucst to send message m to party B, protocol XENc Next, authenticate each messagebetween the parties using
invokes a two-party protocol A,,, that proceeds as follows. a standard symmetric key message authentication (MAC)
First, A sends ‘moooage:m, to B. (A also outputs ‘A sent algorithm under the exchanged key. MAC performance is
mooongo m to B,.) Upon receipt of ‘message:m, from usually several orders of magnitude faster than the public
A, party B chooses a random value NE ~a {O,l}“, and key related operations. (In addition, some extra measure is
sends ‘challengo:m, ENC~,., (Ns), to A. Upon receipt of needed in order to avoid replay of messages. Thii can be
’ challongo:m, ENC~,, (NO), from B, party A obtains Ns done through a shared state between the parties.)
by decrypting the value in the last field in the incoming Typically, several invocations of a key exchange proto-
me33age,nnd sends ‘mac:m, MAON, (m, B) J to B. Upon col may occur between each two parties during the lifetime
receipt of ‘mac:m, v,, party B proceeds as follows. If v = of the system. It is natural to consider each invocation of
MAWa (m, B) then B accepts m (ie, it outputs ‘B received the key exchange protocol (together with the invocation of
m from A,). Otherwise, B rejects this messageand termi- the code pertaining to the incoming and outgoing messages
nates this invocation of A,,. (Terminating the session in that are authenticated with the obtained key) as a separate
case of a bad MAC is not essential for the security; however, session. In this and the following section we concentrate on
considerably simplifies the analysis.) Pictorially, the ex- this meaning of the term session. As usual, we would like to
chnngo for a single messagecan be described as in Figure 2. consider each session as an independent entity, as much as
possible (see Section 2.2).
Proposition 5 Assume that the encryption scheme in use Below we define key-exchange protocols (Section 4.1),
ta aeculre againat chooen cipher-text attacks in the sense of and show that the above approach to constructing authen-
ticators is indeed secure (Section 4.2).
‘The ndvoroary is given a ciphertoxt and is allowed to ask for
dccryptlon of any vnluo othor than tho value &on. It must eventually
dcclde whothor tho &on ciphortext is an encryption of a given value. 4.1 Key-exchange protocols: a definition
IIoro wo use a vroak version of [RS] security (see remark after the
proof of Proposition G). Tho Rrst encryption scheme secure in this We present a definition of a secure key exchange (KE) pro-
aonao apponra in (DDN]. tocol. We use the following standard paradigm for defining

425
secure protocols: First we specify an ideal KE process. Thii the set I and s = (pi, Pi, C, I) for some pi and C. The effect
ideal processcaptures our intuitive notion of ‘the best we can is that the value ‘Pj established key (6,;) with Pi’ is
espect’ from a KE protocol. Nest we say that a KE protocol added to Pi’s output, where )i is the same value that appears
(either in t.he authenticated or in the unauthenticated-links in the corresponding output of Pi, and 9^= (Pi, Pi, c, R),
model) is secure if it emulates to the ideal KE process, as Here the f{mbol R specifies that Pj is a responder in this
formalized in Definition 1. eschange. (Also here, we envision that the value t; ia
Using t.hii definitional approach we obtain, ‘in one blow’, handed to Pj by the trusted party.) In addition, tho value
definitions for secure KE protocols both in the authenticated s is deleted from the set I of incomplete sessions.
and t,he unaut,henticated-links models. It may seemthat KE
III. Corrupt session s. This activation is of course valid
protocols in the authenticated-links model are of theoretical
interest only. Yet, it will follow as an immediate corollary only ifs is a session ID that was in I at some point (or is cur-
rently in I). The effect is that the adversary learns the. key /t
that if ‘ITis a secure KE protocol in the authenticated-links
that corresponds to s. In addition, the value ‘Soooion s in
model, and C is an authenticator, t,hen C(n) is a secure KE
corrupted’ is appended to the output of the initiator. If 3
protocol in t.he unauthenticated-links model. This points to is no longer in I then the value ‘Session d is corruptad’
a very attractive design principle for secure KE protocols. is appended also to the output of the responder. We stress
See Section 5 for further details. that s is not deleted from I (in case that s is currently in
Although each eschange of a key involves only two par-
ties, we model a KE protocol as an on-going multi-party I)*
process that involves all parties in the system. This cap- IV. Corrupt party Pi. The effect is that all the Iroys
tures the realistic (and often subtle) threats against a, key known to Pi become known to the adversary. In addition n
exchange protocol where an attacker can use a corrupted value ‘Pi is corrupted’ is appended to Pi’s out,put.
party in order to attack an exchange between two other un- We allow the adversary to keep activating corrupted par-
corrupted par&s. In addition, we allow pairs of parties to ties (in order to allow corrupted parties to eschange keys
have multiple keys eschanged between them. Each eschange with uncorrupted ones.) Yet, we stick to the convention
of a key induces a separate session within each participating that the output of a corrupted party does not grow (ie, the
party.’ We want t.he different sessionsto be as independent last value in a corrupted party’s output is the corruption
of each other as possible. In part.icular, the compromi;e of notice).
a key eschanged and used in one session should not 1ez.dto As in Section 2.1, the global output of the ideal KE pro-
the compromise of keys exchanged in other sessions. These cess is the concatenation of the cumulative output:; of all
and other characteristics (such as the ability of an attacker the parties, together with the output of the adversary. (Thti
to dest,roy messagessent from one party to another) are output of the adversary is a function of the information seen
captured in t.he ideal KE process, described below. by the adversary throughout the computation, together with
its random input.)
THE IDEAL KE PROCESS. There are 7~parties Pl...Pnr and We use the following notation. Let ADVS(TS, OPT)denoto
an ideal KE adversary S. We also imagine participation of the output of ideal KE adversary S of a run on random
a trusted party T. The computation consists of a series of input rs and when the keys are chosen (b.v the trusted
activations of parties, made by S. There are four types of p&y T ) using random input TT. Let IDE&(TS~?‘T)i de-
activat.ions: note the cumulative outout of nartv pi after an interaction
I. Invoke Pi to establish a new key with Pj. The effect with ideal KE adversari S ani r&dom inputs TS,T’T. Let
is t,hat t,he Mlue ‘Pi established key (K, s) with Pj' is IDEALs(Ts, TT) =
added to Pi’s output, where fi is a key chosen according to ADVS(TS,TT),IDEALS(TS,TT)I . ..IDEALs(Ts.TT), .
some predefined distribution. lo The value s is a session ID
that consists of a tuple (Pi, Pj, c, I), where c is the numeral Let IDEALSO denote the random variable describing
IDEALs(Ts, TT) when TS, TT are uniformly chosen.
of the session among all sessions established by Pi with Pj,
and I is a symbol specifying t,hat Pi is an initiator in this Let AUT&,d() and UNAUTHn,u() be defined as in Section
eschange. The adversary learns only the value s, and does 2. As there, we use the convention that whenever a party
not learn the value K. (We envision that the value K is is corrupted, or a session within a party is corrupted, or a
handed to Pi by the trusted party.) In addition, the value s request to exchange a key is issued, an appropriate note is
is added to a global set I of incomplete sessions. appended to the party’s output.”
If an uncorrupted party establishes a key with a cor-
Definition 6 Let r be a message-driven protocol for n par-
rupted party (see item IV below), then we let the adver-
ties. We say that 7~is a secure KE protocol in unauthenticated
sary choose the value of the key. Thii provision reflects the networks if for any Uhl-adversa9-y U there exhts an ideal 1iE
fact that we do not have security requirements from keys
eschanges with corrupted parties. In addition it will be adversary 8 such that UNAUTHa,~() & IDEALS&
important for proving validity of known KE protocols (see We say that ‘IF is a secure KE protocol in authenticated
Section 5). networks if for any Ahf-adversary A there exists an ideal ICE

II. Invoke Pj to establish key of session s with Pi. “We adopt the convention that in the Ideal model tho ncaqion 1Do
Thii activation is allowed only if the value s is currently in of the initiating and responding parties are idonticni, oscopt for tho
I/R field. In particular, the initiator of the cschnngo niwayo appcnro
“Typically, all the sessions are invocations of a single ‘exchange first.
subroutine’. (This subroutine is invoked whenever a party is ‘*This recording of “Important events” is crucial for our notion of
prompted to exchange a key with another party.) Set, me do not ex- emulation. In particular, it forces a secure KE protocol to nctuniiy
clude protocols that invoke different subroutines for different sessions. exchange keys if the adversary delivers all messages faithfully; it aioo
‘“The distribution of the established key is a parameter of the sys- makes sure that a secure KE protocol mnintnins a session otructura
tem. For instance, it may be that is ER (0.1)” where k is a security similar to the ideal KE process (ie, each exchanged koy 10 asnocintad
parameter. with a separate session).

426
a&w&a~ 8 such that AUT&,A() & IDEALso. Corollary 8 Let KE be a secure KE protocol in authenti-
cated networks, and let C be an authenticator. Then C(KE)
is a secure KE protocol in unauthenticated networks. cl
~&MARI<. The ideal KE process does not take any input.
Definition 6 to consider only the empty input.
Thie 0110~~s We consider two well-known KE protocols in the authenti-
cated-links model: the Difhe-Hellman protocol [DH], de-
4.2 From key-exchangeprotocols to authenticators noted DH, aud an encryption-based protocol, denoted EB.
Wo show an MT-authenticator that exchanges a single key ENCRYPTION-BASEDKE. First the parties choose private
(ia, maintains a single session) for the entire communica- and public keys of any semantically secure encryption scheme
tion between each pair of parties. This can be generalized with security parameter k. (We stress that here, in the
straightforwardly to the case of multiple keys (ie, multiple authenticated-links model, simple semantic security against
scesions) between each pair of parties. passive eavesdroppers is sufficient.) Let ep, wp denote party
Lot KE bo a key cxchangc protocol in the unauthenticated- P’s encryption and decryption keys. Next, upon activation
links model. Then the MT-authenticator XIteproceeds as fol- for exchanging a key with party B, party A invokes the fol-
lows, First each party A invokes a copy of KE with each other lowing two-party protocol $B. A chooses a key ICEu (0, l}&
party, Next, when invoked to send a messagem to party B, sends EN&,(K) to B, and lets K be the established key. It
party A increments a local counter (associated with party is crucial that A immediately erase the random coins used
B), and sends m, i, MACQ, (m, i) to party B, where i is to encrypt K.Is Upon receipt of ENQ, (K), party B lets IEbe
the current reading of the counter and KAB is the obtained the established key.”
key for authenticating messagesfrom A to B.13 Upon acti-
vation with incoming message(m, j, u), from B, verify that Proposition 9 Protocol EB is a secure KE protocol in au-
w = hIAC~~~~(rn,j) and that no messagewith counter j thenticated networks.
or higher was received from B. If both verifications succeed
then output ‘A received m from B’. Proof: See [BCK]. cl
DIFFIE-HELLMAN KE. It is assumed that a large safe prime
Thoorom 7 Assume that KE is a key exchange protocol in
p and an element g of multiplicative order (p - 1)/2 mod
lhc u4lauthenticated.link8 model, and that MAC is a secure
p are known to all parties. 0, is safe if (p - 1)/2 is a
MAO ocheme. Then protocol &Z described above is a secure
prime). Upon activation for exchanging a key with party
MT-authticator.
B, party A invokes the following twc+party protocol Dir.
Proof: Sco[BCK]. cl (Confusingly, this protocol is often called “unauthenticated
DH?.) A chooses an element z & ZZSand sends g2(mod p)
to B. Upon receipt of g2 from A, party B chooses y ER
6 Key exchange protocols: Constructions Z$, sends g*(modp) to A and lets the established key be
(gz)u(mod p). Upon receipt of gV from B, party A lets the
In this section WCpresent some constructions of KE proto- established key be (g*)Z(modp). It is crucial that both A
cola, Here we finally put our new machinery in use. In fact, and B erase the secret exponents x, y once the keys are es-
wo use our machinery with the following ‘twist’. In Section tablished, otherwise the protocol is not known to be secure
4 wo considered KE protocols as a tool for obtaining authen- against adversaries that choose the corrupted parties in an
ticators, Here we use authenticators (and, in particular, the adaptive way.
authenticators constructed in Section 3) to construct KE
protocols, That is, we first perform the much easier task of Proposition 10 Protocol DH is a secure KE protocol in au-
designing a KE protocol KE in the authenticated-links model. thenticated networks.
Next, we use any authenticator C to obtain a full-fledged au-
thenticator C(Kn) in the unauthenticated-links model. Proof: See [BCK]. 0
An important observation is that using thii method with Let Cslcand Cehcbe the layered authenticators based on
the layarcd authenticators of Section 3 we are able to obtain hlT-authenticators & and xmc, respectively (see Section
KE protocols that underlie important practical key distribu- 3). Then, it follows from Corollary 8 that both C&D@
tion protocols. This exposes a design principle that implic- and &c(DH) are secure KE protocols in unauthenticated
itly underlies those KE protocols, namely, the %eparability” networks. Protocol &(DH) is very similar to a signature-
of the authentication mechanisms from the underlying basic based KE protocol used in an IS0 standard PSO, MW].
key cxchango mcchanism,14 C&D@ is very similar to the SKEME KE protocol pra].
Substnntinting this design principle, we note the follow-
ing onsy (but central) corollary: REMARKS. 1. Naive application of &C and &XC to proto-
CO~DH results in a 6-move protocol. Yet it is straightforward
“‘An lmmcdiato optlmlzation is to let party A invoke the key- to see that the 6 moves can be ‘collapsed’ to 3 moves by
cxchnn~o protocol with party 33 only when it need5 to send the first ‘piggybacking messagesof one protocol on the other. Thii
moaonge to R,
Also, ono can use tho abovo protocol to have one key for the com- lbIf the parties do not trust each other to properly erase their ran-
munication from A to B and n second key for the communication dom inputs then standard semantically secure encryption does not
from B to A, Altornatlvely, ono can havo the same key for the com- suffice. In some cases non-committing (ie, adaptively secure) encryp
municntiono in both wnys. Both vnriants aro secure. tion will suffice [CFGN]. See details there.
14Wo otroao thnt not all aroaosed kev exchanrre orotocols in the ‘%‘ypically in practice, the exchange is bi-directional. That is, both
lltornturo follow this modular approach-(see [M\TVjj. However, our A and B send encrypted values to each other, and the established key
work domonatratoa a clonr advnntago of “separable” protocol8 where is some function (say, the bitwise exclusive or) of the two dues. This
tho do&n nnd onaiy5is of tho protocol aro mado possiblo, and greatly is done so that parties do not have to trust each other to properly
nimpliflod, by this property. choose their keys. For simplicity vie concentrate here on the single-
sided protocol.

427
is done as follows. Let X be either one of Xslc or ,&sc, let A, [CFGN] R. CANETTI, U. FEIGE, 0. GOLDREIOH AND Hal NAon,
be the invocation of X that authenticates the initiator’s mes- “Adaptively SecureComputation”, Proc. of tire 28th
sage, and let Ax be t,he invocation of X that authenticates ACM STOC, ACM, 1996.Fuller version MIT-LCS-TR
the responder’s message. Then, in the first messageof the #682, 1996.
combined protocol the initiator sends the f&t messageof XI WW D. CHAU~I, C. CFU?PEAU, AND I. DABIOARD,“Multiparty
together with the second messageof )LR.(The first message unconditionally secure protocols”, Proc. of the 20th
of Xn is not sent. It. is implicit. in the next step.) In the ACM STOC, ACM, 19S8.
second step of the combined protocol the responder sends PHI W. DIFFIE AND M. HELLAIAN, “New directions in cryp-
the second messageof A, toget,her with the third messageof tography,” IEEE !lkans. Info. Theoq IT-22, November
1976, pp. 644-654.
.& In the t,hiid step of the combined protocol the initiator
sends the t.hird messageof AI. POW] W. DIFFIE, P. VAN OORSCHOTAND M. WIENER, “Au-
2. In a full version of thii work we will estend the anal- thentication and authenticated key eschanecdl, Dc-
signs, Codes and CqrptographS; 2, 1992, pp. 107-12.X
ysis of the DH exchange to deal with issues like perfect-
forward-secrecy and anonymity. WNI D. DOLEV, C. DWORK AND M. NAOR, L’Non-maiicablc
cryptography”, TR CS95-27,Weizmann Institute. Prc-
iiminaxy version in Proc. of the 23rd ACM STOC,
References ACAI, 1991.
[hi] D. BE;\\%zR, ‘LFoundationsof SecureInteractive Com- WYl 0. GOLDREICH,S. MICALI AND A. WIGDGRSON,“How
puting”, CRYPT0 ‘91.
to play any mental game, or A completenesst,hcorom
for protocols with honest majority,” Proc. of the 19th
[BCK] AI. BELLARE, R. CXNETTI AND H. K~~CZYK, ‘<A ACh4 STOC, ACM, 1987.
Bloclular Approach to the Design and Analysis of Au- [GMR] S. GOLD~VASSER, S. MICALI AND R. RIVEST, ‘IA dig-
thentication and Kev Escbanne Protocols”, Available ital signature scheme secure against adaptive choscn-
at http://--cse.;csd.edu/;sers/mihir and at the message attacks,” SIAM Journal of Cornput&, Vol. 17,
Theory of CwrWwhy Li- No. 2, April 1988,pp. 281-308.
brary, http://theory.lcs.nit.edu/‘tcryptol, hiarch
1993. PSOI ISO/IEC IS 9793-3, ‘<Entity authentication mechaniomo
-Part 3: Entity authentication using asymmetric tcch-
[BPRR] h1. BELLARE, E. PEELANK, C. RACKOFFAND P. ROG- niques”, 1993.
~ww, “Authenticated key eschangein the public key
model,” 1995-96. PC1 D. HARKINS AND D. CARREL, ed., “The reso-
lution of ISAKMP with Oakley,” Internet draft,
PfaU I& BELLME AND P. ROGA~AY, uEntity authentication draft-ietf-ipeec-imkmp-oeltley-OS.txt, Nov. 1097.
and key distribution”, CRYPT0 ‘93. [Kral H. KRA~VCZYK,“SKEME: A Versatile Secure Key Es-
[BR2] XI. BELLARE AND P. ROGAIVA~‘,“Provably secureses- change AiIechanism for Internet,“, Proceedings of the
sion key distribution- the three party case,” Proc. of 1996 Internet Society SJrmposium on Netrrwk and Dk-
the 27th ACM STOC, ACM, 1995. tributed S.wtem Security; Feb. 1996, pp. 114-127.
[Blhle]S. BLXE-WILSON? AND A. A~ENEZES,“Entity authenti- PC1 S. LUCKS, “Open key eschange: How to defcnt dictio-
cation and authenticated key transport protocols em- nary attacks without encrypting public keys,” Procccd-
ploying asymmetric techniques”, Proceeding of the in@ of the 1997 Security Protocols librkshop, 1997.
1997 Security Protocol; Workshop, 1997. [h,fw] A. MENEZES, P. VAN OORS~HOTAND S. VA~STOND,
[BJAI] S. BLAKE-WILSO;I, D. JOHNSONAND A. A~ENEZES, “Key ‘LHandbookof Applied Cryptography,” CRC PrcsJ,
exchange protocols and their security analysis,” Pro- 1996.
ceedings of the sisth IAlA International Conference on [MR] S. MICALI AND P. ROGA~VAY,‘Secure Computation”,
Cr~pto,rrapig~ and Coding, 1997. Manuscript., 1992. Preliminary version in CRYPT0 ‘91.
WJGI h1. BEN-OR, R. CANETTI AND 0. GOLDREICN, LLAsyn- WI M. NAOR AND 0. REINGOLD, “Efficient cryptographic
chronous Secure Comwtations”. Proc. of the 25th primitives based on the decisional Diffic-Heiiman as-
ACM STOC, ACAI, 19-93. . sumption”, Proc. of the 38th IEEE FOCS, IEEE, 1997.
[BGW] Bl. BEN-OR, S. GOLD~YASSER,AND A. WIGDERSON, WI M. NAOR AND M. YUNG, “Public key cryptosystomo
Completeness theorems for non-cryptographic fauit- provably secure against chosen ciphertest attacks”,
tolerant distributed computations, Proc. of the 20th Proc. of the 22nd ACM STOC, ACM, 1990.
ACM STOC, ACM, 195% iNSI R. NEEDHAAIAND M. SCIIROEDER,“Ueine encryption
for authentication in large networks of computers,”
[BGH+]R. BIRD, I. GOPAL, A. HERZBERG,P. JANSON,S. KUT- Communications of the ACM, Vol. 21, No. 12, Dccem-
TEN, R. hfo~m AND Al. YUNG, ‘Systematic design of ber 1978, pp. 993-999.
tv;o-party authentication protocols,” CRYPT0 ‘91.
[BAN] AI. Buruxov~s, Al. AB.$DI AND R. NEEDHA~I,“A lo.& for bl C. RACKOFF, “Some definitions, protocoio and proofil
about secure authentication,” IBM CASCON 02.
authentication,” DEC Systems Research Center Tech-
nical Report 39, February 1990. Earlier versions in Pro- [SRI V. SHOUPAND A. RUBIN. Session key distribution using
ceedincs of the Second Conference on Theoretical As- smart cards. EUROCRYPT ‘96.
pects of Reasoning about Knowledge, 19SS, and Pro- WI C. RACKOFF AND D. SIMON, “Non-interactive zcro-
ceedincs of the Twelfth ACM Svmaosium on Ooeratinr knowledge proof of knowledge and chosen ciphertest
Systen% Principles, 1989. . - attack” CRYPT0 ‘91.
WI R. CANETTI, Woduiar Composition of Secure Bluiti- PNSI J. STE&R C. NEWAIAN AND J. SCIZILLER ‘%erberox
party Protocols”, Available at the Theory of Cryptogra- an authentication service for open netwo& syutemo,”
phy Library,http://theory.lcs.mit.edu/ tcryptol, Proceedings of the USENIX Winter Conferencq 1988,
199x. pp. 191-202.
[C32] R. CANETTI, “Tovzards realizing random oracles: Hash M A. \‘AO, Protocols for Secure Computation, In Proc.
functions that hide ail martial information”. CRYPT0 23th Annual Symp. on Foundations of Computer Sci-
ence, pages 160-164. IEEE, 1982.

428