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.
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 g^{ai} to a responder, where g is a generator of a group and α_{i} is the random value selected by the initiator. After receiving g^{ai}, the responder sends g^{aj} to the initiator. Then the initiator and the responder calculate a session key, sk = g^{aiaj}. 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:
P_{i} (initiator)
P_{j} (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 P_{i} initiate a run of a protocol between P_{i} and P_{j} and receives g^{ai} from P_{i}, (b) A makes P_{j} initiate another run of a protocol between P_{i} and P_{j} and receives g^{aj} from P_{j}, (c) A sends g^{ai} to P_{j} in the latter run and g^{aj} to P_{i} in the former run. As a result of the behavior of A, P_{i} and P_{j} obtain the same protocol messages g^{ai} and g^{aj} in the two runs, and thus generate the same session key sk = g^{aiaj}. In addition, P_{i} thinks that they are the initiator and P_{j} thinks that they are the initiator. This situation is depicted as follows:
Pi’s view:
P_{i} (initiator)
P_{j} (responder)
Round 1
g^{αi}
Round 2
g^{αj}
Pj’s view:
P_{i} (responder)
P_{j} (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, P_{i} and P_{j} have the notion of being partnered in the KR model, whereas P_{i} and P_{j} 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:
P_{i}
P_{j}
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 g^{ai}; while, at the same time, the other sends g^{aj} 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 P_{i} 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 kth instance of party P_{i} is denoted by Π_{i,k}. If a key-establishment protocol terminates, then Π_{i,k} generates a session key sk_{i,k}.A session identifier of an instance Π_{i,k}, denoted sid_{i,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 P_{i}. The partner of this instance is the party P_{j} (≠ P_{i}) with whom P_{i} 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: sid_{i,k} = sid_{j,k'}, P_{j} is the partner of Π_{i,k}, and P_{i} 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 (x_{k}, y_{k} = g^{x}k) be a pair of private/public keys of P_{i}. Let H be a collision-resistant hash function and Mac a strongly unforgeable MAC-generation function. Then HMQV is defined as follows [2]:
P_{i} (initiator)
P_{j} (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} || y_{j}) and e = H(g^{αj} || y_{i}).KAM is defined as follows [22]:
P_{i}’s message
P_{j}’s message
Round 1
g^{αi}
g^{αj}
Round 2
τ_{i}
τ_{j}
The MAC keys are calculated as k_{i,j} = H(g^{αjxi}) and k_{j,i} = H(g^{αixj}). Note that k_{i,j} ≠ k_{j,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(g^{xixj}) ⊕ 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)
P_{i} (initiator)
P_{j} (responder)
Round 1
g^{αi}
Round 2
g^{αj}
The first session (Πj,1’s view)
P_{i} (responder)
P_{j} (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 P_{i} is going to establish a session key with P_{j} (≠ P_{i}). Assume that P_{i} is an initiator and that P_{j} is a responder. Person P_{j} behaves as similarly as P_{i}, so we describe the protocol on behalf of P_{i}.Round messages. In the lth round of KE_{D}, P_{i} and P_{j} may send their lth-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 P_{i} first sends its message of the lth round of KE_{D} in a given round, and then responder P_{j} sends its message of the lth round of KE_{D} in the next round. So, if KE_{D} is an n-round protocol, then KE_{W} is at most a 2n-round protocol.Computation of session keys. Person P_{i} 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 P_{i} is going to establish a session key with P_{j}(≠P_{i}). Assume that P_{i} is an initiator and P_{j} is a responder. Person P_{j} behaves as similarly as P_{i}, so we describe the protocol on behalf of P_{i}.Round messages. KE_{S}’s round messages are the same as those of KE_{W}.Computation of session keys.P_{i} calculates sk_{KEW} in the same way as a session key of KE_{W} is calculated in the KR model. Person P_{i} makes the session identifier sid = strTIME and session key sk_{KES} = Fsk_{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 P_{j}. 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:
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:
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}θ.
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:
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:
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:
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:
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:
P_{i} (initiator)
P_{j} (responder)
Round 1
g^{αi}
Round 2
g^{αj}
A session identifier is sid = g^{αi}||g^{αj} and a session key is sk = Fsk_{HMQV} (ℏ(sid)), where d = H(g^{αi}||y_{j}), e = H(g^{αj}||y_{j}), 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:
P_{i} (initiator)
P_{j} (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 = Fsk_{KAM} (ℏ(sid)), where sk_{KAM} =H(g^{xixj})⊕(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
HMQV_{S}
2 rounds
3.5 exp. + 1 PRF
BR model
KAM_{S}
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 P_{i} precedes P_{j} in the lexicographic ordering as P_{i} ＜ P_{j}.
We name the parties that are not insider attacker honest parties.
Π_{i,k} and Π_{j,k'} are partnered.
BIO
jeongokkwon@gmail.comJeong 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 Authorirjeong@korea.ac.krIk 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.
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
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
2001
American National Standard (ANSI) X9.42-2001, Public Key Cryptography for the Financial Services Industry: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography
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
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
Citing 'Relations among Security Models for Authenticated Key Exchange
'
@article{ HJTODO_2014_v36n5_856}
,title={Relations among Security Models for Authenticated Key Exchange}
,volume={5}
, url={http://dx.doi.org/10.4218/etrij.14.0113.1071}, DOI={10.4218/etrij.14.0113.1071}
, number= {5}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Kwon, Jeong Ok
and
Jeong, Ik Rae}
, year={2014}
, month={Oct}
TY - JOUR
T2 - ETRI Journal
AU - Kwon, Jeong Ok
AU - Jeong, Ik Rae
SN - 1225-6463
TI - Relations among Security Models for Authenticated Key Exchange
VL - 36
PB - Electronics and Telecommunications Research Institute
DO - 10.4218/etrij.14.0113.1071
PY - 2014
UR - http://dx.doi.org/10.4218/etrij.14.0113.1071
ER -
Kwon, J. O.
,
&
Jeong, I. R.
( 2014).
Relations among Security Models for Authenticated Key Exchange.
ETRI Journal,
36
(5)
Electronics and Telecommunications Research Institute.
doi:10.4218/etrij.14.0113.1071
Kwon, JO
,
&
Jeong, IR
2014,
Relations among Security Models for Authenticated Key Exchange,
ETRI Journal,
vol. 5,
no. 5,
Retrieved from http://dx.doi.org/10.4218/etrij.14.0113.1071
[1]
JO Kwon
,
and
IR Jeong
,
“Relations among Security Models for Authenticated Key Exchange”,
ETRI Journal,
vol. 5,
no. 5,
Oct
2014.
Kwon, Jeong Ok
and
,
Jeong, Ik Rae
and
,
“Relations among Security Models for Authenticated Key Exchange”
ETRI Journal,
5.
5
2014:
Kwon, JO
,
Jeong, IR
Relations among Security Models for Authenticated Key Exchange.
ETRI Journal
[Internet].
2014.
Oct ;
5
(5)
Available from http://dx.doi.org/10.4218/etrij.14.0113.1071
Kwon, Jeong Ok
,
and
Jeong, Ik Rae
,
“Relations among Security Models for Authenticated Key Exchange.”
ETRI Journal
5
no.5
()
Oct,
2014):
http://dx.doi.org/10.4218/etrij.14.0113.1071