Advanced
Relations among Security Models for Authenticated Key Exchange
Relations among Security Models for Authenticated Key Exchange
ETRI Journal. 2014. Aug, 36(5): 856-864
Copyright © 2014, Electronics and Telecommunications Research Institute(ETRI)
  • Received : October 25, 2013
  • Accepted : May 29, 2014
  • Published : August 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Jeong Ok Kwon
Ik Rae Jeong

Abstract
Usually, key-establishment protocols are suggested in a security model. However, there exist several different security models in the literature defined by their respective security notions. In this paper, we study the relations between the security models of key establishment. For the chosen security models, we first show that some proven key-establishment protocols are not secure in the more restricted security models. We then suggest two compilers by which we can convert a key-establishment protocol that is secure in a specific security model into a key-establishment protocol that is still secure in a more restricted security model.
Keywords
I. Introduction
When we design a cryptographic protocol, we should prove the security of the protocol in a security model. A security model is designed to reflect attacks in the real world.
In the field of key establishment, there are many security requirements, and there are many key-establishment protocols that are trying to achieve some of these security requirements. However, there are only a few key-establishment protocols achieving most of these security requirements (strong key-establishment protocols). Unfortunately, these strong key-establishment protocols were proven only in newer security models. Therefore, we do not know whether such strong key-establishment protocols are also secure in more traditional security models.
Bellare and Rogaway suggested the first formal security model for key exchange — a security model called the BR model [1] . The BR model assumes the network communication channel to be a half-duplex channel. In a half-duplex channel, the two communicating parties have to send their messages alternatively. A less restricted security model, one that perhaps makes it easier to construct a strong key-establishment protocol, for a half-duplex channel is suggested by Krawczyk, which we call the KR model [2] . In a duplex channel, the two communicating parties can send their messages at the same time. For such a channel, it is necessary to create new security models since those for the half-duplex channel are not transferable; one such model is defined by Jeong and others, which we call the JKL model [3] .
- 1. BR Model
In this paper, we consider only key-establishment protocols that are for use with two parties — namely, two-party key-establishment protocols. In [1] , Bellare and Rogaway suggested the BR model for two-party key-establishment protocols that are used in a half-duplex channel. In a two-party key-establishment protocol, two parties establish a common session key between them. One of the most basic two-party key-establishment protocols is the Diffie–Hellman key-establishment protocol [4] . In the basic unauthenticated Diffie–Hellman key-establishment protocol, an initiator of the protocol first sends gai to a responder, where g is a generator of a group and αi is the random value selected by the initiator. After receiving gai , the responder sends gaj to the initiator. Then the initiator and the responder calculate a session key, sk = gaiaj . In the basic Diffie–Hellman key-establishment protocol, an initiator and a responder alternatively send their messages through their network communication channel. In a half-duplex channel, the communicating parties cannot send their messages at the same time. Most two-party key-establishment protocols are constructed for use in a half-duplex channel. The basic unauthenticated Diffie–Hellman key-establishment protocol for a half-duplex channel is depicted as follows:
Pi (initiator) Pj (responder)
Round 1 gαi
Round 2 gαj
The session key is sk = gαiαj
- 2. KR Model
In [2] , Krawczyk suggested the KR model for a half-duplex channel. In this model, an initiator and a responder exchange their messages alternatively, as in the BR model. However, in the KR model, it does not matter which of the two communicating parties is the initiator. That is, we can ignore the roles of initiator and responder in the KR model. To see the difference between the two models, consider an adversary A who behaves as follows on the above unauthenticated Diffie–Hellman protocol: (a) A makes Pi initiate a run of a protocol between Pi and Pj and receives gai from Pi , (b) A makes Pj initiate another run of a protocol between Pi and Pj and receives gaj from Pj , (c) A sends gai to Pj in the latter run and gaj to Pi in the former run. As a result of the behavior of A , Pi and Pj obtain the same protocol messages gai and gaj in the two runs, and thus generate the same session key sk = gaiaj . In addition, Pi thinks that they are the initiator and Pj thinks that they are the initiator. This situation is depicted as follows:
Pi’s view:
Pi (initiator) Pj (responder)
Round 1 gαi
Round 2 gαj
Pj’s view:
Pi (responder) Pj (initiator)
Round 1 gαj
Round 2 gαi
The BR model considers the above attack as dangerous; hence, for a key-establishment protocol to be secure, it must be able to prevent such an attack. In contrast, the KR model does not consider the above attack to be dangerous; consequently, the key-establishment protocol is not required to prevent such an attack. In other words, the above run of a protocol is considered as an “intact” run in the KR model, while it is not considered intact in the BR model. The intact run is defined using a notion, partnered (or matched), in the formal security model. For the above run of a protocol, Pi and Pj have the notion of being partnered in the KR model, whereas Pi and Pj do not in the BR model.
- 3. JKL Model
In [3] , Jeong and others suggested the JKL model for a duplex channel. In a duplex channel, the two communicating parties can send their messages simultaneously. The basic unauthenticated Diffie–Hellman key-establishment protocol in a duplex channel is depicted as follows:
Pi Pj
Round 1 gαi gαj
The session key is sk = gαiαj
In the above key-establishment protocol, one of the two communicating parties sends gai ; while, at the same time, the other sends gaj without waiting for the communicating partner’s message. Note that the basic Diffie–Hellman key-establishment protocol requires two rounds in a half-duplex channel but only one round in a duplex channel. Thus, conducting a key-establishment protocol in a duplex channel is more efficient.
- 4. Authenticated Key Establishment
The basic Diffie–Hellman key-establishment protocol does not provide authentication of the session keys. That is, an adversary can impersonate the communicating party and send messages of its choice to the target party. As a result, the adversary can generate the same session key as the target party. There are many schemes (called authenticated key-establishment protocols) that provide authentication of session keys. Authentication of a session key simply means that no party, besides those involved in the communication, can obtain the session key information. Authenticated key-establishment protocols serve as basic building blocks for constructing secure, complex, and higher-level cryptographic protocols. In this paper, we consider only authenticated key-establishment protocols where each party holds a pair of private/public keys.
A party typically uses its private key and randomly generated numbers to establish a session key. It is easy to observe that without the use of the randomly generated numbers, all session keys would be identical. For secure subsequent use of a session key, most applications require that each session key be unique. Hence, to establish a new session key, it is necessary to use uniquely different randomly generated numbers along with the same private key each time. A private key is also used to authenticate a session key.
Several security notions pertinent to key establishment have been defined based on considerations of how to minimize the damage caused by an adversary acquiring either of the private keys, the random numbers used, or the session keys. One of the security notions considered most often in the literature is that of known-key security (KKS). Protocols providing KKS are secure against Denning–Sacco attacks [5] that aim at trying to compromise multiple session keys (for sessions other than those that require a guarantee of secrecy).
Forward secrecy considers scenarios in which an adversary is able to obtain the private keys of some parties. There are two kinds of forward secrecy: weak and strong. Protocols achieving weak forward secrecy (w-FS) maintain the secrecy of a session key that is shared through an execution of the protocol without any interference by an adversary. Protocols achieving strong forward secrecy (s-FS) maintain the secrecy of a session key, even if the session key has been established with the interference of an adversary.
Besides the above security notions, there are others, such as key compromise impersonation (KCI) and unknown key-share (UKS) [6] [8] . Security against session-state reveal (SSR) is formally considered in [2] and [9] .
- 5. Our works
Most authenticated key-establishment protocols are constructed in the BR model [1] , [6] , [10] [13] . The standardization of key establishment has been done in the BR model [14] [18] . We note that a comparison of the original BR model and subsequent variants of it have been analyzed in [19] .
Some key-establishment schemes are proved in the KR model [2] , [20] . There exist a few key-establishment schemes in the JKL model [3] , [21] [22] . We note that a multiparty authenticated key-establishment protocol can be used as a two-party authenticated key-establishment protocol. Thus, a multiparty key-establishment protocol in a broadcasting channel model, such as that in [21] and [23] [24] , can be used as a two-party key-establishment protocol in the JKL model.
The strong key-establishment protocols FS, KCI, and SSR, achieving most of the known security notions, are known respectively as HMQV [2] , Okamoto’s scheme [20] , and KAM [22] . HMQV and Okamoto’ s scheme are secure in the KR model, and KAM is secure in the JKL model. HMQV is proven in the random oracle model, whereas Okamoto’s scheme and KAM are proven in the standard model. HMQV is more efficient than both KAM and Okamoto’s scheme.
We will show that a key-establishment protocol, secure in a security model, might not be secure in a more restricted security model. That is, we cannot simply use a key-establishment protocol that is secure in the KR model or in the JKL model as a key-establishment protocol in the BR model. For example, we will show that both HMQV and KAM are not secure in the BR model.
We will then suggest a compiler that converts a secure key-establishment protocol in the JKL model into a secure key-establishment protocol in the KR model and another compiler that converts a secure key-establishment protocol in the KR model into a secure key-establishment protocol in the BR model. Our compilers do not modify any protocol messages of the underlying key-establishment scheme. Moreover, our compilers do not increase any computational complexity except adding only one pseudorandom function evaluation. Using compilers, we can convert both HMQV and KAM into HMQVS and KAMS, respectively, both of which are secure in the BR model.
In Section II, we review the primitives used in the paper. In Section III, we define the BR model, the KR model, and the JKL model. In Section IV, we show that HMQV and KAM are not secure in the BR model. In Section V, we suggest compilers by which we can convert a key-establishment protocol secure in a specific security model into a key-establishment protocol secure in a more restricted model. In Section VI, we conclude the paper.
II. Preliminaries
We use the following notations: (a) [ a , b ] denotes a set of integers from a to b , (b) c S denotes that c is randomly selected from a set S , (c) a concatenation of two strings a and b is denoted by a || b and (d) if evt is an event, then Pr[ evt ] is used to denote the probability of it occurring.
Let θ be a security parameter. We use a secure pseudorandom function F whose domain and range are {0, 1} θ [24] . Let F K : {0, 1} θ → {0, 1} θ be a function selected from a function family F, where F = {F K | K is in the space of θ -bit strings}.
III. Security Model for Key Establishment
We will explain the BR model, KR model, and JKL model in a unified way. We assume that each party’s identity is denoted as Pi and that each party holds a pair of private/public keys.
We consider key-establishment protocols in which two parties want to exchange a session key using their public keys to provide key authentication [25] . The k th instance of party Pi is denoted by Π i,k . If a key-establishment protocol terminates, then Π i,k generates a session key ski,k .
A session identifier of an instance Π i,k , denoted sidi,k , is a string that has a high probability of being different from those of all other sessions in the system. We first define strID i,k and strTIME i,k . The concatenation of all messages sent and received by a particular instance Π i,k , where the order of these messages is determined by the lexicographic ordering of the two parties’ identities, is given by strID i,k . The concatenation of all messages sent and received by a particular instance Π i,k , where the order of these messages is determined by the time they were sent or received, is given by strTIME i,k .
We note that an adversary can delay or reorder messages. The session identifiers are used to define partnered (or matched) instances in the security models and are appropriately defined as follows:
  • ▪ A session identifier in the BR model has been defined assidi,k= strTIMEi,k[1],[26].
  • ▪ session identifier in the KR model has been defined assidi,k= strIDi,k[2].
  • ▪ A session identifier in the JKL model has been defined assidi,k= strIDi,k[3],[22]. (Note that strTIMEi,kcannot be used as a session identifier in the JKL model, because the two parties may send their messages simultaneously.)
We note that the security models are different according to how the notion of being “partnered” is defined. As a consequence, the security models are different according to the way the session identifier is defined.
Consider instance Π i,k of party Pi . The partner of this instance is the party Pj (≠ Pi ) with whom Pi believes it is interacting. We say that the two instances Π i,k and Π j,k' are partnered (or matching), if the following conditions are true: sidi,k = sidj,k' , Pj is the partner of Π i,k , and Pi is the partner of Π j,k' .
Note that if two instances are partnered in the BR model, the two instances are also partnered in the KR model.
For a concrete definition of the KKS/w-FS/s-FS/KCI/SSR-security through an experiment, refer to [1] [3] .
IV. Security Analysis of HMQV
It is obvious that a key-establishment protocol secure in the BR model is also secure in the KR model, and a key-establishment protocol secure in the KR model is also secure in the JKL model. In this section, we show that we cannot simply use a key-establishment protocol that is secure in the KR model or in the JKL model as a key-establishment protocol in the BR model.
Let ( xk , yk = gxk ) be a pair of private/public keys of Pi . Let H be a collision-resistant hash function and Mac a strongly unforgeable MAC-generation function. Then HMQV is defined as follows [2] :
Pi (initiator) Pj (responder)
Round 1 gαi
Round 2 gαj
The subsequent session key is calculated as sk = H ( g (αi+dxi) (αj+exj) ), where d = H ( gαi || yj ) and e = H ( gαj || yi ).
KAM is defined as follows [22] :
Pi’s message Pj’s message
Round 1 gαi gαj
Round 2 τi τj
The MAC keys are calculated as ki,j = H ( gαjxi ) and kj,i = H ( gαixj ). Note that ki,j kj,i . τ i and τ j are MAC values, where τ i ← Mack i,j ( i || j || gαi ) and τ j ← Mack j,i ( j || i || gαj ). The session key is calculated as sk = H ( gxixj ) ⊕ H ( gαiαj ).
  • Theorem 1.HMQV is w-FS/KCI/SSR-secure in the KR model[2].
  • Theorem 2.HMQV is insecure against known-key attacks in the BR model. That is, HMQV does not provide KKS in the BR model.
  • Proof of Theorem 2.Consider an adversaryAthat creates two sessions among two partiesPiandPj. In the first session,Piinitiates a protocol such thatPisendsgαiIn the second session,Pjinitiates a protocol such thatPjsendsgαj. ThenAinterleaves protocol messages such thatAsendsgαjtoPiin the first session andgαitoPjin the second session, as follows:
The first session (Πi,1’s view)
Pi (initiator) Pj (responder)
Round 1 gαi
Round 2 gαj
The first session (Πj,1’s view)
Pi (responder) Pj (initiator)
Round 1 gαj
Round 2 gαi
  • AdversaryAobtainsskj,1, a session key ofPjin the second session, through the Reveal(j, 1) query. ThenAknowsski,1, a session key ofPiin the first session, and thus breaks KKS. We can easily determine whenski,1andskj,1are the same. Note that strTIMEi,1=gαi||gαjand strTIMEj,1=gαj||gαi. If we assume that (Pi
V. Compilers among Security Models
In this section, we suggest two compilers: compiler1 and compiler2. Compiler1 converts a key-establishment protocol in the JKL model into a key-establishment protocol in the KR model. Compiler2 converts a key-establishment protocol in the KR model into a key-establishment protocol in the BR model.
Let KE D be a secure key-establishment protocol in the JKL model. Then compiler1 converts KE D into a new key-establishment protocol, KE W , which is secure in the KR model. This procedure is explained below.
Setup. Let KE D be a secure key-establishment protocol in the JKL model. Person Pi is going to establish a session key with Pj (≠ Pi ). Assume that Pi is an initiator and that Pj is a responder. Person Pj behaves as similarly as Pi , so we describe the protocol on behalf of Pi .
Round messages. In the l th round of KE D , Pi and Pj may send their l th-round messages simultaneously in the JKL model. But in the KR model, only one of the two can send its message in any given round. So, we break the symmetry of KE D in such a way that initiator Pi first sends its message of the l th round of KE D in a given round, and then responder Pj sends its message of the l th round of KE D in the next round. So, if KE D is an n -round protocol, then KE W is at most a 2 n -round protocol.
Computation of session keys. Person Pi calculates a session key for KE W in the same way as a session key for KE D is calculated in the JKL model.
  • Theorem 3.If KEDis XX-secure in the JKL model, then KEWconverted by compiler1, is XX-secure in the KR model, whereXXis either KKS, w-FS, s-FS, KCI, or SSR.
  • Proof of Theorem 3.LetAWbe an adversary against KEWin the KR model. Then we can construct an adversaryADagainst KEDusingAWin the JKL model, such that the advantages ofADandAWare the same. AdversaryADreceives queries fromAW, gets answers from its own oracles, and returns the answers toAW. Note thatADperfectly simulates KEWtoAW, since the two instances are partnered in the JKL model if and only if the two instances are partnered in the KR model.                            ■
In [22] , Jeong and others suggested a key-establishment protocol, KAM, in the duplex channel and proved its security in the JKL model.
  • Theorem 4.KAM is s-FS/KCI/SSR-secure without random oracles in the JKL model[22].
Let KAM W be the converted protocol from KAM using compiler1 for the KR model.
  • Corollary 1.KAMWis s-FS/KCI/SSR-secure without random oracles in the KR model.
  • Proof of Corollary 1.From Theorem 3 and Theorem 4, Corollary 1 follows.                            ■
Even though KAM W is secure in the KR model, KAM W is insecure against know-key attacks in the BR model.
  • Theorem 5.KAMWis insecure against known-key attacks in the BR model. That is, KAMWdoes not provide KKS in the BR model.
  • Proof of Theorem 5.We can easily see that the same attack in the proof of Theorem 2 also applies for KAMW.                             ■
To make a secure key-establishment protocol in the BR model from a secure key-establishment protocol in the KR model, we construct another conversion method; namely, then compiler2. If KE W is a secure key-establishment protocol in the KR model, compiler2 converts KE W into KE S . This procedure is explained below.
Setup. Let KE W be a secure key-establishment protocol in the KR model, and let F be a secure pseudorandom function. Let ℏ be a collision-resistant hash function such that ℏ : {0, 1}*→{0, 1} θ . We assume that the session key space of KE W and the pseudorandom function key space of F are a space of θ -bit strings. Person Pi is going to establish a session key with Pj (≠ Pi ). Assume that Pi is an initiator and Pj is a responder. Person Pj behaves as similarly as Pi , so we describe the protocol on behalf of Pi .
Round messages. KE S ’s round messages are the same as those of KE W .
Computation of session keys. Pi calculates sk KEW in the same way as a session key of KE W is calculated in the KR model. Person Pi makes the session identifier sid = strTIME and session key sk KES = F sk KEW (ℏ( sid )) for KE S .
  • Theorem 6.If F is a secure pseudorandom function and KEWis XX-secure in the KR model, then KESconverted by compiler2 is XX-secure in the BR model, where XX is either KKS, w-FS, s-FS, KCI, or SSR. More concretely, AdvXXKES(θ, t) ≤ (2+2(Nqs)2) × AdvXXKEW(θ, t) + 4AdvRRFF(θ, t, 2), wheretis the maximum total experiment time including an adversary’s execution time. Here,Nis an upper bound on the number of honest2)parties, andqsis an upper bound on the number of the sessions an adversary creates.
  • Proof of Theorem 6.The intuition is as follows. For an adversaryAto get a non-negligible advantage for KES, the adversary has to break the underlying key-establishment scheme KEWor a pseudorandom function F. We show that usingA, we can make either an adversaryDthat breaks KEWor anEthat breaks F. Some difficulties arise when we construct aDthat simulates KEStoA. This is because in some casesAis allowed to make a Reveal query against KESbutDis not allowed to make a Reveal query against KEW. We solve this difficulty using the fact that if there exists oracle Πj,k'partnered with tested oracle Πi,k, the advantage of an adversary is the same as in the case when it asks a Test query to Πj,k'. The details of which are as follows.
Assume that A makes a Test( i, k ) query and that Π i,k ’s partner is Pj . The advantage of A then occurs in the following two cases:
  • ▪ Case 1. There exists an oracle Πj,k'such that strTIMEj,k'= strTIMEi,k3)∨there exists no oracle Πj,k'such that strIDj,k'= strIDi,k.
  • ▪ Case 2. There exists an oracle Πj,k'such that strIDj,k'= strIDj,kand strTIMEj,k'≠ strTIMEj,k.
We restrict the advantages from the above two cases in the following claims:
  • ▪ Claim 1. AdvCase(1)KES≤ 2AdvKEW+ 2AdvPRFF.
  • ▪ Claim 2. AdvCase(2)KES≤ 2(Nqs)2× AdvKEW+ 2AdvPRFF.
From Claim 1 and Claim 2, Theorem 6 follows. Next, we prove the claims.
  • Proof of Claim 1.Consider an adversaryAattacking KESwith the advantage from Case 1 in the sense of XX-security. We define the following three games:
  • ▪ In Game0, a session key for the test query is calculated and returned to the adversary as follows: ifb= 1,sk= FskKEW(ℏ (sid)). Ifb= 0,sk← {0,1}θ.
  • ▪ In Game1, a session key for the test query is calculated and returned to the adversary as follows: ifb= 1,sk= FR(ℏ(sid)), whereR← {0, 1}θ. Ifb= 0,sk← {0, 1}θ.
  • ▪ In Game2, a session key for the test query is calculated and returned to the adversary as follows: ifb= 1,sk=h(ℏ(sid)), whereh← Rand{0, 1}θ→{0, 1}θ. Ifb= 0,sk← {0, 1}θ.
The difference of the advantage of A from Case 1 in the aforementioned games is restricted as follows:
  • ▪ Claim 1.1. AdvGame0KES,A− AdvGame1KES,A≤ 2AdvKEW.
  • ▪ Claim 1.2. AdvGame1KES,A− AdvGame2KES,A≤ 2AdvPRFF.
  • It is obvious that the advantage of any adversary is 0 in Game2. Thus, from Claim 1.1 and Claim 1.2, Claim 1 follows.                        ■
Now, we proceed to prove Claim 1.1 and Claim 1.2.
  • Proof of Claim 1.1.Consider the following algorithmDthat tries to break KEWusingAthat tries to break KES. AlgorithmDreceives all oracle queries fromAand answers them using its own oracle queries to KEW. A more concrete description ofDis as follows:
  • 1) For each oracle query ofA, AlgorithmDanswers it using its own oracle query to KEWas follows:
  • • For Send(i, k) query:Djust asks Send(i, k) query in its own experiment.• For Corrupt(i) query:Djust asks Corrupt(i) query in its own experiment, receives the private key ofPi, and returns the private key toA.• For State(i, k) query:Djust asks State(i, k) query in its own experiment, receives the random values of Πi,k, and returns the random values toA.• For Reveal(i, k) query:DgetsskKEWthrough its own Reveal query and returnsskKES= FskKEW(ℏ(sidi,k)) toA.• For Test(i, k) query:Dgets τ through its own Test query and flips a coinb. Ifbis equal to 1,Dreturnssk= Fτ(ℏ(sidi,k)) toA. Otherwise,Dreturns a random value selected from {0,1}θ.
  • 2) Assume thatAoutputsb'then quits. Ifb=b',Doutputs 1. Otherwise,Doutputs 0.
  • AlgorithmDsimulates Game0or Game1depending on whether τ is a real session key of KEWor not. So, the following inequality holds:
  • AdvD, KEW= Pr[D() = 1|τ =skKEW] – Pr[D() = 1|τ ← {0, 1}θ]
  •                    = PrA[b=b'|sk= FskKEW(ℏ(sid))] − PrA[b=b'|sk= FR(ℏ(sid));R← {0, 1}θ]
  •                    = 1/2(AdvGame0A− AdvGame1A).                             ■
  • Proof of Claim 1.2.If the difference of advanatages of adversaryAbetween Game1and Game2is non-negligible, we can construct an algorithmEthat breaks the pseudorandomness of F with a non-negligible probability usingA. Consider a distinguisherEto break the pseudorandomness of a pseudorandom function family F. DistinguisherEis given an oracle functionf(·) in the experiment of pseudorandomness of the function family F. DistinguisherEusesf(·) to generate a session key for the test oracle. A more concrete description ofEis as follows:
  • 1) DistinguisherEis given an oracle functionf(·).Esimulates Game1.2) For each oracle query ofA,Eanswers it as in Game1, except in the case of Test(i, k) query wherebyEflips a coinb. Ifbis equal to 1,Ereturnsf(ℏ(sidi,k)). Otherwise,Ereturns a random value selected from {0,1}θ.3) Assume thatAoutputsb'then quits. Ifb=b',Eoutputs 1. Otherwise,Eoutputs 0.
  • DistinguisherEsimulates Game1or Game2depending on whetherf(·) is a function from F. So, the following inequality holds:
  • AdvPRFE= Pr[Ef(·)= 1|K← {0, 1}θ;f= FK] − Pr[Ef(·)= 1|h← Rand{0,1}θ→{0,1}θ;f=h]                    = PrA[b=b'|K← {0, 1}θ;f= FK] − PrA[b=b'|h← Rand{0,1}θ→{0,1}θ;f=h]                    =1/2 (AdvGame1A− AdvGame2A).                            ■
  • Proof of Claim 2.Consider an adversaryAattacking KESwith the advantage from Case 2 in the sense of XX-security. Let Πi*,t1be the tested oracle. Then there exists an oracle Πj*,t2such that strIDj*,t2= strIDi*,t1and strTIMEj*,t2≠ strTIMEi*,t1. We define the following three games:
  • ▪ Game0• A session key for Reveal query is calculated and returned to the adversary according to the protocol.• A session key for Test query is calculated and returned to the adversary as follows: Ifb= 1,sk= FskKEW(ℏ(sidi*,t1)). Ifb= 0,sk←{0,1}θ.
  • ▪ Game1• A session key of Πj*,t2for Reveal query is asked,sk= FR(ℏ(sidj*,t2)) is returned, whereR←{0,1}θ. A session key of Πi,k(≠Πj*,t2) for Reveal query is calculated and returned to the adversary as in Game0.• A session key for Test query is calculated and returned to the adversary as follows: Ifb= 1,sk= FR(ℏ(sidi*,t1)). whereR←{0,1}θ. Ifb= 0,sk←{0,1}θ.
  • ▪ Game2• A session key for Reveal query is calculated and returned to the adversary as in Game1.• A session key for Test query is calculated and returned to the adversary as follows: Ifb= 1,sk=h(ℏ(sidi*,t1)). whereh←Rand{0,1}θ→{0,1}θ. Ifb= 0,sk←{0,1}θ.
  • The difference of the advantage ofAfrom Case 2 in the aforementioned games is restricted as follows:
  • ▪ Claim 2.1. AdvGame0KES,A− AdvGame1KES,A≤ 2(Nqs)2· AdvKEW.▪ Claim 2.2. AdvGame1KES,A− AdvGame2KES,A≤ 2AdvPRFF.
It is obvious that the advantage of any adversary is 0 in Game 2 . Thus, from Claim 2.1 and Claim 2.2, Claim 2 follows.                             ■
Now, we proceed to prove Claim 2.1 and Claim 2.2.
  • Proof of Claim 2.1.Consider the following algorithmDthat tries to break KEWusingAthat tries to break KES. AlgorithmDreceives all oracle queries fromAand answers them using its own oracle queries to KEW. AlgorithmDfirst guesses the tested oracle Πi,kand an oracle Πj,k'such that strIDj,k'= strIDi,kand strTIMEj,k'≠ strTIMEi,k. A more concrete description ofDis as follows:
  • 1) AlgorithmDrandomly selectsi*andj*from [1,N], andt1,t2from [1,qs]. AlgorithmDsets two flags — namely,reveal-then-test= 0 andtest-then-reveal= 0.2) For each oracle query ofA,Danswers it using its own oracle query to KEWas follows:• For Send(i, k) query:Djust asks Send(i,k) query in its own experiment.• For Corrupt(i) query:Djust asks Corrupt(i) query in its own experiment, receives the private key ofPi, and returns the private key toA.• For State(i, k) query:Djust asks State(i,k) query in its own experiment, receives the random values of Πi,k, and returns the random values toA.• For Reveal(i,k) query.- Ifj=j*∧k=t2andtest-then-reveal= 0:Dgets τrthrough its own Test(j*,t2) query, and setsreveal-then-test= 1.Dreturnssk= Fτr(ℏ(sidj*,t2)) toA.- Else ifi=j*∧k=t2andtest-then-reveal= 1:Dreturnssk= Fτt(ℏ(sidj*,t2)) toA, where τtwas already obtained in Test query.- ElseDgetsskKEWthrough its own Reveal(i,k) query and returnssk= FskKEW(ℏ(sidi.k)) toA.• For Test(i,k) query.- Ifi≠i*∨k≠t1,Dfails and stops.- ifreveal-then-test= 0:Dgets τtthrough its own Test(i*,t1) query and setstest-then-reveal= 1.Dflips a coinb. Ifbis equal to 1,Dreturnssk= Fτt(ℏ(sidi*,t1)) toA, Otherwise,Dreturns a random value selected from {0,1}θ.- Else ifreveal-then-test= 1.Dflips a coinb. Ifbis equal to 1,Dreturnssk= Fτr(ℏ(sidi*,t1)) toA, where τrwas already obtained in Reveal query. Otherwise,Dreturns a random value selected from {0, 1}θ.3) Assume thatAoutputsb'then and quits. If there exists no oracle Πj*,t2such that strIDj*,t2= strIDi*,t1and strTIMEj*,t2≠ strTIMEi*,t1,Dfails and stops. Ifb=b',Doutputs 1. Otherwise,Doutputs 0.
If D guesses i * , j * , t 1 , and t 2 correctly, then D exactly simulates Game 0 or Game 1 depending on whether τ ∈{τ t , τ r } is a real session key of KE W . So, the probability of success of D depends on whether D guesses i' , j' , t 1 , and t 2 correctly as follows:
  • AdvD,KEW= Pr[D() = 1|τ ←skKEW] − Pr[D() = 1|τ ← {0,1}θ]
  •                       =1/(Nqs)2× (PrA[b=b'|sk= FskKEW(ℏ(sid))] − PrA[b=b'|sk= FR(ℏ(sid));R← {0,1}θ])
  •                       = 1/2(Nqs)2×(AdvGame0A− AdvGame1A).                             ■
  • Proof of Claim 2.2.If the difference of advanatages of adversaryAbetween Game1and Game2is non-negligible, then we can construct an algorithmEthat breaks the pseudorandomness of F with a non-negligible probability usingA. Consider a distinguisherEto break the pseudorandomness of a pseudorandom function family F. DistinguisherEis given an oracle functionf(·) in the experiment of pseudorandomness of the function family F. It then usesf(·) to generate a session key for the test oracle. A more concrete description ofEis as follows:
  • 1) DistinguisherEis given an oracle functionf(·).Esimulates Game1.2) For each oracle query ofA,Eanswers it as in Game1except in the case of Test(i, k) query wherebyEflips a coinb. Ifbis equal to 1,Ereturnsf(ℏ(sidi,k)). Otherwise,Ereturns a random value selected from {0,1}θ.3) Assume thatAoutputsb'then and quits. If Test(i,k) was queried but there exists no oracle Πj,k'such that strIDj,k'= strIDi,kand strTIMEj,k'≠ strTIMEi,k, thenEfails and stops. Ifb=b',Eoutputs 1. Otherwise thenEoutputs 0.
  • DistinguisherEsimulates Game1or Game2depending on whetherf(·) is a function from F. So, the following inequality holds:
  • AdvPRFE= Pr[Ef(·)= 1|K← {0, 1}θ;f= FK] − Pr[Ef(·)= 1|h← Rand{0,1}θ→{0,1}θ;f=h]                    = PrA[b=b'|K← {0, 1}θ;f= FK] − PrA[b=b'|h← Rand{0,1}θ→{0,1}θ;f=h]                    = 1/2 (AdvGame1A− AdvGame2A).                            ■
If we convert HMQV in the KR model into HMQV S in the BR model, then the converted HMQV S protocol in the BR model is as follows:
Pi (initiator) Pj (responder)
Round 1 gαi
Round 2 gαj
A session identifier is sid = gαi || gαj and a session key is sk = F sk HMQV (ℏ( sid )), where d = H ( gαi || yj ), e = H ( gαj || yj ), and sk HMQV = H ( g (αi+dxi)(αj+exj) ).
  • Corollary 2.If F is a secure pseudorandom function, then HMQVS is w-FS/KCI/SSR-secure in the BR model.
  • Proof of Corollary 2.From Theorem 1 and Theorem 6, Corollary 2 follows.                             ■
If we convert KAM in the JKL model into KAM S in the BR model, then the converted KAM S protocol in the BR model is as follows:
Pi (initiator) Pj (responder)
Round 1 gαi
Round 2 gαj
Round 3 τi
Round 4 τj
A session identifier is sid = gαi || gαj ||τ i ||τ j , and a session key is sk = F sk KAM (ℏ( sid )), where sk KAM = H ( gxixj )⊕( gαiαj ).
  • Corollary 3.If F is a secure pseudorandom function, then KAMS is s-FS/KCI/SSR-secure without random oracles in the BR model.
  • Proof of Corollary 3.From Theorem 3, Theorem 4, and Theorem 6, Corollary 3 follows.                            ■
Table 1 shows the comparison of complexities between the original schemes and the converted schemes.
Detailed comparison of original and converted schemes.
Communication complexity Computational complexity Security model
HMQV [2] 2 rounds 3.5 exp. KR model
KAM [22] 2 rounds 6 exp. JKL model
HMQVS 2 rounds 3.5 exp. + 1 PRF BR model
KAMS 4 rounds 6 exp. + 1 PRF BR model
†The basic HMQV requires 2.5 exponentiations. But, the group membership tests of static and ephemeral Diffie-Hellman messages are required for SSR security, as noted in [2].
VI. Conclusion
We have shown that a key-establishment protocol secure in a specific security model might not be secure in a more restricted security model. For example, we have shown that HMQV is not secure in the Bellare–Rogaway security model. We have suggested compilers by which we can convert a key-establishment protocol secure in a specific security model into a key-establishment protocol secure in a more restricted security model.
This work was supported by Basic Science Research Programs through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2013R1A2A2A01068200)
We denote Pi precedes Pj in the lexicographic ordering as PiPj.
We name the parties that are not insider attacker honest parties.
Πi,k and Πj,k' are partnered.
BIO
jeongokkwon@gmail.com
Jeong Ok Kwon received her BS degree in computer science from Dongduk Women’s University, Seoul, Rep. of Korea, in 2000. She received her MS and PhD degrees in information security from Korea University, Seoul, Rep. of Korea, in 2003 and 2007, respectively. In 2007, she began work at Korea University as a post doctor. Then in 2008 she became a research professor; a position that she held until 2009. Currently, she is a senior engineer working for Integrated Security Consulting Group, Samsung SDS, Seoul, Rep. of Korea. Her current research interests include cryptography and information security
Corresponding Author  irjeong@korea.ac.kr
Ik Rae Jeong received his BS and MS degrees in computer science and his PhD degree in information security from Korea University, Seoul, Rep. of Korea, in 1998, 2000, and 2004, respectively. From 2006 to 2008, he was a senior engineer at the Electronics and Telecommunications Research Institute, Daejeon, Rep. of Korea. Currently, he is a faculty at the Graduate School of Information Security, Korea University, Seoul, Rep. of Korea. His current research areas include cryptography and theoretical computer science.
References
Bellare M. , Rogaway P. “Entity Authentication and Key Distribution,” CRYPTO Santa Barbara, CA, USA Aug. 22–26, 1994 773 232 - 249    DOI : 10.1007/3-540-48329-2_21
Krawczyk H. “HMQV: A High-Performance Secure Diffie–Hellman Protocol,” CRYPTO Santa Barbara, CA, USA Aug. 14–18, 2005 3621 546 - 566    DOI : 10.1007/11535218_33
Jeong I.R. , Katz J. , Lee D.H. “One-Round Protocols for Two-Party Authenticated Key Exchange,” ACNS Yellow Mountain, China June 8–11, 2004 3089 220 - 232    DOI : 10.1007/978-3-540-24852-1_16
Diffie W. , Hellman M. 1976 “New Directions in Cryptography,” IEEE Trans. Inf. Theory 22 (6) 644 - 654    DOI : 10.1109/TIT.1976.1055638
Denning D. , Sacco G. 1981 “Timestamps in Key Distribution Protocols,” Commun. ACM 24 (8) 533 - 536    DOI : 10.1145/358722.358740
“Authenticated Diffie–Hellman Key Agreement Protocols,” SAC 339 - 361    DOI : 10.1007/3-540-48892-8_26
Law L. 2003 “An Efficient Protocol for Authenticated Key Agreement,” Des. Codes Cryptography 28 (2) 119 - 134    DOI : 10.1023/A:1022595222606
Menezes A. , Qu M. , Vanstone S. “Some New Key Agreement Protocols Providing Mutual Implicit Authentication,” SAC Ottawa, Ontario, Canada May 18–19, 1995 22 - 32
Canetti R. , Krawczyk H. “Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels,” EUROCRYPT Innsbruck, Austria May 6–10, 2001 453 - 474    DOI : 10.1007/3-540-44987-6_28
Diffie W. , Oorschot P. , Wiener M. 1992 “Authentication and Authenticated Key Exchanges,” Des. Codes, Cryptography 2 (2) 107 - 125    DOI : 10.1007/BF00124891
Bellare M. , Canetti R. , Krawczyk H. “A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols,” STOC Dallas, TX, USA May 23–26, 1998 419 - 428    DOI : 10.1145/276698.276854
Blake-Wilson S. , Johnson D. , Menezes A. “Key Agreement Protocols and their Security Analysis,” IMA Int. Conf. Cryptography Coding Cirencester, UK Dec. 17–19,1997 1355 30 - 45    DOI : 10.1007/BFb0024447
Canetti R. , Krawczyk H. “Universally Composable Notions of Key Exchange and Secure Channels,” EUROCRYPT Amsterdam, Netherlands Apr. 28–May 2 2332 337 - 351    DOI : 10.1007/3-540-46035-7_22
2001 American National Standard (ANSI) X9.42-2001, Public Key Cryptography for the Financial Services Industry: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography
2000 IEEE 1363-2000, Standard Specifications for Public Key Cryptography
2002 ISO/IEC IS 15946-3, Information Technology - Security Techniques Cryptographic Techniques Based on Elliptic Curves – Part 3: Key Establishment
2003 NIST Special Publication 800-56 (DRAFT), Recommendation on Key Establishment Schemes
Stasak J. 2004 “NSAs Elliptic Curve Licensing Agreement,” IETF’ s Security Area Advisory Group https://www.ietf.org/proceedings/61/slides/saag-2/saag3.ppt
Choo K. , Boyd C. , Hitchcock Y. “Examining Indistinguishability-Based Proof Models for Key Establishment Protocols,” ASIACRYPT Chennai, India Dec. 4–8, 2005 3788 585 - 604    DOI : 10.1007/11593447_32
Okamoto T. “Authenticated Key Exchange and Key Encapsulation in the Standard Model,” ASIACRYPT Kuching, Sarawak, Malaysia Dec. 2–6, 2007 4833 474 - 484    DOI : 10.1007/978-3-540-76900-2_29
Katz J. , Yung M. “Scalable Protocols for Authenticated Group Key Exchange,” CRYPTO Santa Barbara, CA, USA Aug. 17–21, 2003 110 - 125    DOI : 10.1007/978-3-540-45146-4_7
Jeong I.R. , Kwon J.O. , Lee D.H. “A Diffie–Hellman Key Exchange Protocol without Random Oracles,” CANS Suzhou, China Dec. 8–10, 2006 4301 37 - 54    DOI : 10.1007/11935070_3
Jeong I.R. , Lee D.H. 2007 “Key Agreement for Key Hypergraph,” Comput. Sec. 26 (7-8) 452 - 458    DOI : 10.1016/j.cose.2007.08.001
Jeong I.R. , Lee D.H. 2008 “Parallel Key Exchange,” J. Univ. Comput. Sci. 14 (3) 377 - 396
Menezes A. , Oorschot P. , Vanstone S. 1996 Handbook of Applied Cryptography CRC Press Boca Raton, USA 490 - 497    DOI : 10.1201/9781439821916
Bellare M. , Pointcheval D. , Rogaway P. “Authenticated Key Exchange Secure against Dictionary Attacks,” EUROCRYPT Bruges, Belgium May 14–18, 2000 139 - 155    DOI : 10.1007/3-540-45539-6_11