# Deniable Key Establishment Resistance against eKCI Attacks

Authors: Łukasz Krzywiecki; Tomasz Wlisłocki
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Inextended Key Compromise Impersonation (eKCI)attack againstauthenticated key establishment (AKE) protocols the adversary impersonates one party, having the long term key and the ephemeral key of the other peer party. Such an attack can be mounted against variety of AKE protocols, including 3-pass HMQV. An intuitive countermeasure, based on BLS (Boneh–Lynn–Shacham) signatures, for strengthening HMQV was proposed in literature. The original HMQV protocol fulfills the deniability property: a party can deny its participation in the protocol execution, as the peer party can create a fake protocol transcript indistinguishable from the real one. Unfortunately, the modified BLS based version of HMQV is not deniable. In this paper we propose a method for converting HMQV (and similar AKE protocols) into a protocol resistant to eKCI attacks but without losing the original deniability property. For that purpose, instead of the undeniable BLS, we use a modification of Schnorr authentication protocol, which is deniable and immune to ephemeral key leakages.


---

## Body

## 1. Introduction

An authenticated key establishment (AKE) protocol enables two parties: the initiator (starting the protocol, usually called Alice) and the responder (usually called Bob) to mutually identify themselves and establish a secret shared session key, subsequently used to protect communication channel. Thedeniability property for AKE protocols [1, 2] guarantees that parties still can mutually verify their identities, but the transcript of the protocol cannot be regarded as a proof that the parties have executed the protocol together. We distinguish theinitiator deniability and theresponder deniability as the deniability feature can be achieved for each party independently. Deniability may be desirable in various privacy protecting scenarios where the proof of interaction should not be transferable; for example, clients of some Internet services might wish to have the right and real possibility of denying using the service.Many general AKE schemes have been proposed so far; see, for example, MQV [3], HMQV [4], SIGMA [5], KEA+ [6], NAXOS [7], CMQV [8], SMQV [9], E-NAXOS [10], Huang [11], or Kim et al. [12] with numerous additional modifications. Their security has been analyzed in many models, for example, CK [13], eCK [7], and seCK [9], under various attack scenarios. In Key Compromise Impersonation (KCI) attack scenario [14–16], an adversary, which obtained long term secrets of one party, say Alice, can execute AKE protocol with her, and impersonate her another party, say Bob, without using the long term secret of Bob. This attack is especially devastating when the correct identification is of the paramount importance. Imagine the attacker learning the long term key of a bank. Now, the attacker not only can play a role of the bank to any identity (which is obvious), but also can be authenticated as any identity in front of that bank, for example, can be authenticated to the account of some very rich person and subsequently order the money transfer from that logged-in account to his own.In [17] Tang and Chen proposed a new impersonation attack type on AKE protocols called extended KCI (eKCI). In this attack, the adversary has access not only to Alice’s long term secret, but also to her ephemeral secret, for example, the ephemeral Diffie-Hellman key. With the knowledge of both these keys it can impersonate any party to Alice. This new kind of attack can be mounted against protocols already proven to be secure for regular KCI attacks, for example, NAXOS secure in the extended Canetti-Krawczyk model. In [17] authors exemplified the eKCI attack against HMQV protocol [4]. Subsequently they proposed an intuitive and elegant countermeasure based on BLS signatures [18]: in the rest of the paper we refer to this solution by BLS-HMQV.From the design point of view BLS-HMQV is a composition of original HMQV with another layer of authentication, done by the BLS signature scheme. In BLS-HMQV, a party running the protocol sends to its peer an additional signature over some challenge depending on previous messages. The signature forms a proof of identity, since it can be produced only with the secret key corresponding to the certified public key of the signer. Unfortunately, there is one aspect of this solution which in some scenarios can be regarded as a serious drawback: signed messages in the protocol transcript may be used as undeniable proof for a third party where the communication with the signers took place. In this context the modification to HMQV proposed in [17] makes it resistant to eKCI, but at the same time the protocol loses itsdeniability property.Therefore to achieve the deniability property altogether with the eKCI resistance, we follow two-layer architecture of BLS-HMQV. However in our modified protocol (called mHMQV) we exchange the undeniable layer of BLS with the deniable layer of Schnorr-like protocol from [19]. Therefore our proposition mHMQV is deniable like original HMQV and is eKCI resistant like BLS-HMQV, with its two-layer composition.As a final remark we recall that secrecy and fairness of values generated by both parties rely on the internal implementation of pseudorandom number generator algorithm, which itself may utilize hardware based randomness or external environmental sources. One of the most comprehensive recommendations for such algorithms can be found in [20]. However note that even algorithms approved for scientific simulations [21], with super long periods, like [22], must be specially tuned for cryptographic purposes [23]. A practical construction for using external source of randomness in AKE protocol, resembling the common reference string model, is given in [24]. Secrecy of values gained in this way can be compromised if an adversary captures the measurements of the external source as well. An example countermeasure for that problem, which uses distributed leader election for selecting a random source of data, was proposed in [25]. As for the internal hardware sources of randomness, the promising approach of using physically unclonable functions is also considered, for example, [26, 27]. Such hardware functions rely on micro differences of the used material and characteristics of processes in production phase, which—as unpredictable and unrepeatable even for the device manufacturer—guarantee the uniqueness of the final results.


### 1.1. Contribution and Organization of the Paper

The contributions of the paper are the following.(i) Undeniability of BLS-HMQV. We show that BLS-HMQV protocol from [17], which is BLS based modification of HMQV, although resistant to eKCI is no longer deniable.(ii) Proposition of mHMQV-eKCI as Resistant and Deniable. This is the main contribution. We propose an extension to HMQV (applicable to similar 2-party protocols) which protects against the eKCI attack and which does not destroy the protocol deniability property: for the initiator and subsequently for the responder. We use for that purpose the modified Schnorr identification scheme [19], which is secure even if the ephemeral secrets of parties are compromised. To the best of our knowledge it is the first proposition of this kind for AKE protocols so far.(iii) Prototype Implementation. To compare the complexity overhead for deniability and eKCI resistance, we implemented prototypes of HMQV, the BLS based scheme (BLS-HMQV), and our deniable proposition mHMQV.


### 1.2. Previous Work

In Table1 we give the comparison showing the eKCI resistance and deniability feature of the majority of AKE protocols, alongside level of complexity (based on required computational effort for used operations) and number of rounds. Note that eKCI resistance in [11, 17, 31] is provided by undeniable signature scheme that is used to identify the parties to each other. In the case of [11, 17] BLS signatures are used: we call these protocols “without NAXOS” and “BLS-HMQV,” respectively. We observe and stress here that the scheme of [11] does not withstand repetition attack in the setup of eKCI. Namely, after the protocol execution between parties A and B (with the knowledge of the transcript), an adversary can later impersonate A in front of B if long term and ephemeral secrets of B are leaked during the new sessions (andvice versa). Therefore we put “!” instead of “✓” in the table. Finally we denote the protocols we proposed in this paper by “mHMQV.”Table 1
Protocol comparison.
[Paper] protocol
Complexity
Rounds
eKCI resistance
Deniability
[6] KEA+
3
2
—
✓
[6] KEA+C
3
3
—
✓
[7] NAXOS
4
2
—
✓
[28] NAXOS+
5
2
—
✓
[10] E-NAXOS
5
2
—
✓
[8] CMQV
3
2
—
✓
[9] SMQV
3
2
—
✓
[12] Prot.1
3
2
—
✓
[12] Prot.2
5
2
—
✓
[29] AMA
4
4
—
✓
[30] MRI
3
4
—
✓
[4] HMQV
3
3
—
✓
[2] Mod. Σ0
2 +RS + RV
3
—
Initiator
[2] Mod. Σ1
2 +RS + RV
4
Responder
[31] Σ0
2 +S + V
3
✓
—
[31] Σ1
2 +S + V
4
✓
—
[11] without NAXOS
3
2
!
—
[17] BLS-HMQV
4
3
✓
—
mHMQV-1
5
3
✓
Initiator
mHMQV-2
6
4
✓
✓Beside the typical protocols, securing the session key against the combinations of secrets leakages, comparable in terms of the exponentiation operations for Diffie-Hellman based key exchange and listed in Figure1, there are schemes that address additional requirements and adversarial assumptions. The AKE schemes in identity-based setup using elliptic curves were analyzed, for example, in [32, 33]. Those 2-round schemes are still vulnerable to eKCI attacks (actually the first one does not withstand the regular KCI as well). Authors of [34] proposed a ring signature based scheme, useful for vehicles key exchange and authentication. Note that they use idea close to one already presented in [2]. However, as it was signaled in [2], the ring signature based authentication makes the schemes vulnerable to KCI and eKCI-adversary knowing the peer long term key can impersonate other parties to that peer. In [35] the lattice based HMQV version for postquantum era was proposed. The proposition exchanges the cryptographic building blocks, preserving the construction design, but as the original version, it is still eKCI vulnerable. It is an interesting open question how this particular postquantum HMQV construction can be improved, as the modification based on [19] proposed in our paper is also vulnerable to quantum attacks. There are also approaches for a partial leakage of cryptographic material and bad randomness. The security model assuming partial leakage of bits of secret keys was analyzed in [36]; however the proposed solution is based on the signatures and as so is undeniable. The next solution from [37], addressing similar problem, results in 2-round protocol which still is not eKCI resistant. Another 2-round protocol from [38], addressing the “bad randomness” problem for pseudorandom number generators in user devices, is also not eKCI resistant. Another AKE construction, secure without ROM under the hardness of integer factorization problem, code-based problems, or learning with errors problems, was proposed in [39]. Note that this proposition also is not secure to aKCI attacks. In [40] the authors analyzed security model with the adversary registering arbitrary bit strings as keys. They showed generic results for protocols that achieve security even if some keys have been produced maliciously in this way. However this also does not solve the eKCI resistance for typical protocols; for example, the strengthened version of CMQV presented there is still eKCI vulnerable.Figure 1
3-pass HMQV.To the best of our knowledge the problem of construction of an AKE protocol, both deniable and withstanding eKCI, as stated in Section1.1, is still open in literature, since the original eKCI introduction in [17]. Please note, additionally, that in the context of immunizing AKE protocols to eKCI attacks, the construction [41], which follows up the paper [19] and is a modification of Okamoto identification scheme, can be also taken into consideration as the authentication layer: as it is deniable and resistant to ephemeral values leakage and setup.Organization of the Paper. The paper is organized in the following way. In Section 2.2 we recall the HMQV protocol and discuss its deniability property. In Section 3 we recall the eKCI attack on HMQV and the defense method proposed in [17]. We discuss how that approach breaks the deniability of the original HMQV. In Section 4 we propose a solution to the eKCI attack on HMQV based on the modified Schnorr authentication protocol from [19]. We recall the original Schnorr authentication protocol, discuss its deniability property, and show that it is inadequate in setups where the ephemeral keys can be leaked. Then we propose using its modified version to getinitiator deniability. Subsequently we show how the protocol can be modified further to achieve theresponder deniability. We prove the security of our claims. In Section 6 we discuss theproof-of-concept implementation of our protocols.


## 1.1. Contribution and Organization of the Paper

The contributions of the paper are the following.(i) Undeniability of BLS-HMQV. We show that BLS-HMQV protocol from [17], which is BLS based modification of HMQV, although resistant to eKCI is no longer deniable.(ii) Proposition of mHMQV-eKCI as Resistant and Deniable. This is the main contribution. We propose an extension to HMQV (applicable to similar 2-party protocols) which protects against the eKCI attack and which does not destroy the protocol deniability property: for the initiator and subsequently for the responder. We use for that purpose the modified Schnorr identification scheme [19], which is secure even if the ephemeral secrets of parties are compromised. To the best of our knowledge it is the first proposition of this kind for AKE protocols so far.(iii) Prototype Implementation. To compare the complexity overhead for deniability and eKCI resistance, we implemented prototypes of HMQV, the BLS based scheme (BLS-HMQV), and our deniable proposition mHMQV.


## 1.2. Previous Work

In Table1 we give the comparison showing the eKCI resistance and deniability feature of the majority of AKE protocols, alongside level of complexity (based on required computational effort for used operations) and number of rounds. Note that eKCI resistance in [11, 17, 31] is provided by undeniable signature scheme that is used to identify the parties to each other. In the case of [11, 17] BLS signatures are used: we call these protocols “without NAXOS” and “BLS-HMQV,” respectively. We observe and stress here that the scheme of [11] does not withstand repetition attack in the setup of eKCI. Namely, after the protocol execution between parties A and B (with the knowledge of the transcript), an adversary can later impersonate A in front of B if long term and ephemeral secrets of B are leaked during the new sessions (andvice versa). Therefore we put “!” instead of “✓” in the table. Finally we denote the protocols we proposed in this paper by “mHMQV.”Table 1
Protocol comparison.
[Paper] protocol
Complexity
Rounds
eKCI resistance
Deniability
[6] KEA+
3
2
—
✓
[6] KEA+C
3
3
—
✓
[7] NAXOS
4
2
—
✓
[28] NAXOS+
5
2
—
✓
[10] E-NAXOS
5
2
—
✓
[8] CMQV
3
2
—
✓
[9] SMQV
3
2
—
✓
[12] Prot.1
3
2
—
✓
[12] Prot.2
5
2
—
✓
[29] AMA
4
4
—
✓
[30] MRI
3
4
—
✓
[4] HMQV
3
3
—
✓
[2] Mod. Σ0
2 +RS + RV
3
—
Initiator
[2] Mod. Σ1
2 +RS + RV
4
Responder
[31] Σ0
2 +S + V
3
✓
—
[31] Σ1
2 +S + V
4
✓
—
[11] without NAXOS
3
2
!
—
[17] BLS-HMQV
4
3
✓
—
mHMQV-1
5
3
✓
Initiator
mHMQV-2
6
4
✓
✓Beside the typical protocols, securing the session key against the combinations of secrets leakages, comparable in terms of the exponentiation operations for Diffie-Hellman based key exchange and listed in Figure1, there are schemes that address additional requirements and adversarial assumptions. The AKE schemes in identity-based setup using elliptic curves were analyzed, for example, in [32, 33]. Those 2-round schemes are still vulnerable to eKCI attacks (actually the first one does not withstand the regular KCI as well). Authors of [34] proposed a ring signature based scheme, useful for vehicles key exchange and authentication. Note that they use idea close to one already presented in [2]. However, as it was signaled in [2], the ring signature based authentication makes the schemes vulnerable to KCI and eKCI-adversary knowing the peer long term key can impersonate other parties to that peer. In [35] the lattice based HMQV version for postquantum era was proposed. The proposition exchanges the cryptographic building blocks, preserving the construction design, but as the original version, it is still eKCI vulnerable. It is an interesting open question how this particular postquantum HMQV construction can be improved, as the modification based on [19] proposed in our paper is also vulnerable to quantum attacks. There are also approaches for a partial leakage of cryptographic material and bad randomness. The security model assuming partial leakage of bits of secret keys was analyzed in [36]; however the proposed solution is based on the signatures and as so is undeniable. The next solution from [37], addressing similar problem, results in 2-round protocol which still is not eKCI resistant. Another 2-round protocol from [38], addressing the “bad randomness” problem for pseudorandom number generators in user devices, is also not eKCI resistant. Another AKE construction, secure without ROM under the hardness of integer factorization problem, code-based problems, or learning with errors problems, was proposed in [39]. Note that this proposition also is not secure to aKCI attacks. In [40] the authors analyzed security model with the adversary registering arbitrary bit strings as keys. They showed generic results for protocols that achieve security even if some keys have been produced maliciously in this way. However this also does not solve the eKCI resistance for typical protocols; for example, the strengthened version of CMQV presented there is still eKCI vulnerable.Figure 1
3-pass HMQV.To the best of our knowledge the problem of construction of an AKE protocol, both deniable and withstanding eKCI, as stated in Section1.1, is still open in literature, since the original eKCI introduction in [17]. Please note, additionally, that in the context of immunizing AKE protocols to eKCI attacks, the construction [41], which follows up the paper [19] and is a modification of Okamoto identification scheme, can be also taken into consideration as the authentication layer: as it is deniable and resistant to ephemeral values leakage and setup.Organization of the Paper. The paper is organized in the following way. In Section 2.2 we recall the HMQV protocol and discuss its deniability property. In Section 3 we recall the eKCI attack on HMQV and the defense method proposed in [17]. We discuss how that approach breaks the deniability of the original HMQV. In Section 4 we propose a solution to the eKCI attack on HMQV based on the modified Schnorr authentication protocol from [19]. We recall the original Schnorr authentication protocol, discuss its deniability property, and show that it is inadequate in setups where the ephemeral keys can be leaked. Then we propose using its modified version to getinitiator deniability. Subsequently we show how the protocol can be modified further to achieve theresponder deniability. We prove the security of our claims. In Section 6 we discuss theproof-of-concept implementation of our protocols.


## 2. Preliminaries

### 2.1. Notation

Presented AKE protocols are based on Diffie-Hellman (DH) key exchange, so we assume that corresponding computations are done within a groupG=g of prime order q, where computational Diffie-Hellman assumption (CDH) holds.LetI (denotes initiator called Alice) and R (denotes responder called Bob) be two peer parties of the key exchange protocol π. Alice as initiator is the party which starts (sends the first message) the protocol π. Bob is the other party. Let a,A and b,B denote pairs of long term secret/public keys of Alice and Bob, respectively, randomly chosen according to the key generating algorithm. Usually, apart from the long term keys, each party in protocol π coins additional random secret key, called ephemeral key, used in computation during protocol execution. Let x, y denote ephemeral keys of Alice and Bob, respectively. Thus πIa,B,x,Rb,A,y denotes the protocol run between the initiator (Alice) having the secret key a, the ephemeral key x, and the public key B of Bob and the responder (Bob) having the secret key b, the ephemeral key y, and the public key A of Alice.Typical requirements after the authenticated key establishment protocolπ
I
a
,
B
,
x
,
R
b
,
A
,
y is completed (i.e., after both parties finished their computations successfully) are the following:(i)
Both parties mutually identified themselves. We denote thatπIa,B,x,Rb,A,y→IacceptsR initiator speaks with responder of identityBob.πIa,B,x,Rb,A,y→RacceptsI Bob knows he speaks with Alice.(ii)
Both parties have computed the same session key.(iii)
The session key is secret; that is, it is known only to the parties of the protocol.The eKCI attack proposed in [17] affects the first requirement. Intuitively we demand that each party should use its secret key to perform the protocol and be accepted by its peer party. In eKCI attack the adversary can use the peer party secret to impersonate another party.Definition 1.
One says that AKE protocolπ is eKCI vulnerable if there exists an efficient adversary algorithm A such that at least one of the probabilities (1)Pr⁡πIa,B,x,Aa,A,B,x,y⟶IacceptsAas  BobPr⁡πAb,B,A,x,y,Rb,A,y⟶RacceptsAas  Alice is nonnegligible.Remark 2.
In the first eventAa,B,A,x,y denotes the adversary which possesses Alice’s secrets but does not have Bob’s long term secret key b. It is identified falsely by Alice as Bob. Similarly in the second event Ab,B,A,x,y denotes the adversary which possesses Bob’s secrets but does not have Alice’s long term secret key a. It is identified falsely by Bob as Alice. Note that this reflects the scenario in which a hacker, knowing secrets of the bank, can impersonate any user in front of that bank, subsequently ordering malicious money transfers on behalf of this user.Deniability Model. In this point we recall the deniability model from [1], which is applicable to authenticated key establishment protocols.Definition 3.
One says thatKeyGen,I,R is a concurrently deniable key establishment protocol with respect to the class AUX of auxiliary inputs if, for any adversary M, for any input of public keys pk=pk1,…,pkl and any auxiliary input aux∈AUX, there exists a simulator SIMM that, running on the same inputs as M, produces a simulated view which is indistinguishable from the real view of M. That is, consider the following two probability distributions, where pk=(pk1,…,pkl) is the set of public keys of the honest parties:(2)Realn,aux=ski,pki⟵KeyGen1n;(aux,pk,ViewMpk,auxSimn,aux=ski,pki⟵KeyGen1n;(aux,pk,SIMMpk,aux; then for all probabilistic polytime machinesDist and all aux∈AUX(3)Prx∈Realn,aux⁡Distx=1-Prx∈Simn,aux⁡Distx=1≤negln.We say that the protocol isinitiator deniable if there exists the simulator SIMM, denoted as SIMMI, that running on the same inputs as Bob (and without Alice’s secret key) can provide Alice’s part of the protocol. That is when Bob can simulate the whole transcript itself. Conversely, we say that the protocol isresponder deniable if there exists the simulator SIMM, denoted as SIMMR, that running on the same inputs as Alice (and without Bob’s secret key) can provide Bob’s part of the protocol. That is when Alice can simulate the whole transcript itself.


### 2.2. Description of the 3-Pass HMQV

Let us recall the 3-pass protocol of the HMQV family from [4], which is proved to be secure against the standard KCI attacks. The two users Alice and Bob agree on a group G of prime order q, a generator g of G, a hash function H, and a message authentication code function MAC. Alice selects her long term private key at random a∈RZq∗ and lets the trusted third party (TTP) certify the public key A=ga. Similarly, Bob selects his long term private key b∈RZq∗ and lets the TTP certify the public key B=gb. The protocol is shown in Figure 1. The values σa and σb are defined as follows: (4)d=H-X∥“Bob”,e=H-Y∥“Alice”,σa=Ygbex+da,σb=Xgady+eb, where H- outputs the first l bits of the input of the hash function H, and l is a security parameter. Note that σa = Ygbex+da = gygbex+da = gx+day+eb = gxgday+eb = Xgday+eb = σb. Thus the values km and the secret session key sk computed independently on both sides are the same.


### 2.3. Deniability of HMQV

Theorem 4.
HMQV is initiator deniable.Proof.
We show that the protocol isinitiator deniable as Bob can produce the transcript of the protocol execution X,Y,Z,W alone, but with the same probability distribution as it would be produced altogether with Alice. Namely, the simulator SIMMI (run with Bob’s input) chooses x∈RZq∗ and computes X=gx and the rest of parameters Y, Z, W, which does not require Alice’s secret key a. Observe that for σa he does not apply the derivations from the protocol (the private key of Alice would be necessary). Instead, he makes use of the equality σa = σb.It follows that a transcript cannot be regarded as a proof that Alice participates in the protocol execution. Similarly we state the following.Theorem 5.
HMQV is responder deniable.Proof.
It is analogical to the proof of Theorem4. Alice can produce the transcript alone: SIMMR (run with Alice’s view and input) chooses Y∈RZq∗ and computes Y=gy and the rest of parameters Y, Z, W, which does not require Bob’s secret key b.


### 2.4. eKCI Attack on the 3-Pass HMQV

We recall the original eKCI attack on HMQV from [17]. Suppose that an adversary has access to x and a and mounts an attack against Alice. After obtaining the first message X the adversary computes σb′ = gx+ady·Bx+ade = gx+ady·gbx+ade. This equals gx+day+eb. Then it computes the rest of parameters on Bob’s side and sends them to Alice, impersonating in this way itself as Bob. Note the fact that the computation of σb does not require the knowledge of b. It is straightforward to verify that σb=σa, and the adversary always succeeds in the attack.


## 2.1. Notation

Presented AKE protocols are based on Diffie-Hellman (DH) key exchange, so we assume that corresponding computations are done within a groupG=g of prime order q, where computational Diffie-Hellman assumption (CDH) holds.LetI (denotes initiator called Alice) and R (denotes responder called Bob) be two peer parties of the key exchange protocol π. Alice as initiator is the party which starts (sends the first message) the protocol π. Bob is the other party. Let a,A and b,B denote pairs of long term secret/public keys of Alice and Bob, respectively, randomly chosen according to the key generating algorithm. Usually, apart from the long term keys, each party in protocol π coins additional random secret key, called ephemeral key, used in computation during protocol execution. Let x, y denote ephemeral keys of Alice and Bob, respectively. Thus πIa,B,x,Rb,A,y denotes the protocol run between the initiator (Alice) having the secret key a, the ephemeral key x, and the public key B of Bob and the responder (Bob) having the secret key b, the ephemeral key y, and the public key A of Alice.Typical requirements after the authenticated key establishment protocolπ
I
a
,
B
,
x
,
R
b
,
A
,
y is completed (i.e., after both parties finished their computations successfully) are the following:(i)
Both parties mutually identified themselves. We denote thatπIa,B,x,Rb,A,y→IacceptsR initiator speaks with responder of identityBob.πIa,B,x,Rb,A,y→RacceptsI Bob knows he speaks with Alice.(ii)
Both parties have computed the same session key.(iii)
The session key is secret; that is, it is known only to the parties of the protocol.The eKCI attack proposed in [17] affects the first requirement. Intuitively we demand that each party should use its secret key to perform the protocol and be accepted by its peer party. In eKCI attack the adversary can use the peer party secret to impersonate another party.Definition 1.
One says that AKE protocolπ is eKCI vulnerable if there exists an efficient adversary algorithm A such that at least one of the probabilities (1)Pr⁡πIa,B,x,Aa,A,B,x,y⟶IacceptsAas  BobPr⁡πAb,B,A,x,y,Rb,A,y⟶RacceptsAas  Alice is nonnegligible.Remark 2.
In the first eventAa,B,A,x,y denotes the adversary which possesses Alice’s secrets but does not have Bob’s long term secret key b. It is identified falsely by Alice as Bob. Similarly in the second event Ab,B,A,x,y denotes the adversary which possesses Bob’s secrets but does not have Alice’s long term secret key a. It is identified falsely by Bob as Alice. Note that this reflects the scenario in which a hacker, knowing secrets of the bank, can impersonate any user in front of that bank, subsequently ordering malicious money transfers on behalf of this user.Deniability Model. In this point we recall the deniability model from [1], which is applicable to authenticated key establishment protocols.Definition 3.
One says thatKeyGen,I,R is a concurrently deniable key establishment protocol with respect to the class AUX of auxiliary inputs if, for any adversary M, for any input of public keys pk=pk1,…,pkl and any auxiliary input aux∈AUX, there exists a simulator SIMM that, running on the same inputs as M, produces a simulated view which is indistinguishable from the real view of M. That is, consider the following two probability distributions, where pk=(pk1,…,pkl) is the set of public keys of the honest parties:(2)Realn,aux=ski,pki⟵KeyGen1n;(aux,pk,ViewMpk,auxSimn,aux=ski,pki⟵KeyGen1n;(aux,pk,SIMMpk,aux; then for all probabilistic polytime machinesDist and all aux∈AUX(3)Prx∈Realn,aux⁡Distx=1-Prx∈Simn,aux⁡Distx=1≤negln.We say that the protocol isinitiator deniable if there exists the simulator SIMM, denoted as SIMMI, that running on the same inputs as Bob (and without Alice’s secret key) can provide Alice’s part of the protocol. That is when Bob can simulate the whole transcript itself. Conversely, we say that the protocol isresponder deniable if there exists the simulator SIMM, denoted as SIMMR, that running on the same inputs as Alice (and without Bob’s secret key) can provide Bob’s part of the protocol. That is when Alice can simulate the whole transcript itself.


## 2.2. Description of the 3-Pass HMQV

Let us recall the 3-pass protocol of the HMQV family from [4], which is proved to be secure against the standard KCI attacks. The two users Alice and Bob agree on a group G of prime order q, a generator g of G, a hash function H, and a message authentication code function MAC. Alice selects her long term private key at random a∈RZq∗ and lets the trusted third party (TTP) certify the public key A=ga. Similarly, Bob selects his long term private key b∈RZq∗ and lets the TTP certify the public key B=gb. The protocol is shown in Figure 1. The values σa and σb are defined as follows: (4)d=H-X∥“Bob”,e=H-Y∥“Alice”,σa=Ygbex+da,σb=Xgady+eb, where H- outputs the first l bits of the input of the hash function H, and l is a security parameter. Note that σa = Ygbex+da = gygbex+da = gx+day+eb = gxgday+eb = Xgday+eb = σb. Thus the values km and the secret session key sk computed independently on both sides are the same.


## 2.3. Deniability of HMQV

Theorem 4.
HMQV is initiator deniable.Proof.
We show that the protocol isinitiator deniable as Bob can produce the transcript of the protocol execution X,Y,Z,W alone, but with the same probability distribution as it would be produced altogether with Alice. Namely, the simulator SIMMI (run with Bob’s input) chooses x∈RZq∗ and computes X=gx and the rest of parameters Y, Z, W, which does not require Alice’s secret key a. Observe that for σa he does not apply the derivations from the protocol (the private key of Alice would be necessary). Instead, he makes use of the equality σa = σb.It follows that a transcript cannot be regarded as a proof that Alice participates in the protocol execution. Similarly we state the following.Theorem 5.
HMQV is responder deniable.Proof.
It is analogical to the proof of Theorem4. Alice can produce the transcript alone: SIMMR (run with Alice’s view and input) chooses Y∈RZq∗ and computes Y=gy and the rest of parameters Y, Z, W, which does not require Bob’s secret key b.


## 2.4. eKCI Attack on the 3-Pass HMQV

We recall the original eKCI attack on HMQV from [17]. Suppose that an adversary has access to x and a and mounts an attack against Alice. After obtaining the first message X the adversary computes σb′ = gx+ady·Bx+ade = gx+ady·gbx+ade. This equals gx+day+eb. Then it computes the rest of parameters on Bob’s side and sends them to Alice, impersonating in this way itself as Bob. Note the fact that the computation of σb does not require the knowledge of b. It is straightforward to verify that σb=σa, and the adversary always succeeds in the attack.


## 3. Prevention of the Attack: Undeniable Version

Let us recall the method from [17] protecting against the eKCI attack. The idea is that the users (Alice and Bob) should mutually demonstrate the knowledge of their long term private key to each other. The authors propose the use of deterministic BLS signature scheme [18]. We denote the resulting protocol as BLS-HMQV. The construction of that protocol is very intuitive: It can be viewed as two-layer approach:(i)
The first layer is the original HMQV.(ii)
The second layer includes the BLS signatures over the parameters of the HMQV protocol (parties identifiers, messages). Indeed any adversary algorithm that would break eKCI resistance of BLS-HMQV, that is, would impersonate one party by means of anything but the long term secret key (e.g., the other party parameters) would be immediately used to break unforgeability of BLS signature scheme.


### 3.1. BLS-HMQV

First let us briefly recall the BLS scheme. LetG, GT be groups of a prime order q and g be a generator of G. Let H1:0,1∗→G. We assume that e^:G×G→GT is a bilinear map, and a signer holds a private/public key pair α,gα, where α∈RZq∗. For a message m∈0,1∗, the signature generation and verification procedures are as follows:(1)
The signer computes a signatureV, where V=H1mα∈G.(2)
The verifier checks whethere^V,g = e^H1m,gα. If so, the signature is accepted.The BLS-HMQV based solution to the eKCI attack on HMQV is depicted in Figure2. We follow the notation from [17]. The important part of the protocol extension computed on the responder side is boxed. Similarly respective computations on the initiator side are underlined.Figure 2
BLS-HMQV: BLS based prevention of the eKCI attack against HMQV.


### 3.2. Loosing Deniability

Although BLS-HMQV is resistant to eKCI attack, we observe that the protocol depicted in Figure2 isnot initiator deniable.Theorem 6.
The BLS-HMQV protocol depicted in Figure2 isnot initiator deniable.Proof.
Indeed, in order to produce a simulated transcript indistinguishable from the original one, a simulatorSIMMI (run with Bob’s input and without the knowledge of Alice’s secret key a) would have to create a verifiable signature V′. So it would be used as an efficient forger for the underlying BLS scheme, contradicting BLS security.Corollary 7.
The BLS-HMQV protocol innot responder deniable due to the similar reasoning.


## 3.1. BLS-HMQV

First let us briefly recall the BLS scheme. LetG, GT be groups of a prime order q and g be a generator of G. Let H1:0,1∗→G. We assume that e^:G×G→GT is a bilinear map, and a signer holds a private/public key pair α,gα, where α∈RZq∗. For a message m∈0,1∗, the signature generation and verification procedures are as follows:(1)
The signer computes a signatureV, where V=H1mα∈G.(2)
The verifier checks whethere^V,g = e^H1m,gα. If so, the signature is accepted.The BLS-HMQV based solution to the eKCI attack on HMQV is depicted in Figure2. We follow the notation from [17]. The important part of the protocol extension computed on the responder side is boxed. Similarly respective computations on the initiator side are underlined.Figure 2
BLS-HMQV: BLS based prevention of the eKCI attack against HMQV.


## 3.2. Loosing Deniability

Although BLS-HMQV is resistant to eKCI attack, we observe that the protocol depicted in Figure2 isnot initiator deniable.Theorem 6.
The BLS-HMQV protocol depicted in Figure2 isnot initiator deniable.Proof.
Indeed, in order to produce a simulated transcript indistinguishable from the original one, a simulatorSIMMI (run with Bob’s input and without the knowledge of Alice’s secret key a) would have to create a verifiable signature V′. So it would be used as an efficient forger for the underlying BLS scheme, contradicting BLS security.Corollary 7.
The BLS-HMQV protocol innot responder deniable due to the similar reasoning.


## 4. Our Proposition: Deniable Prevention to eKCI Attack

In this section we propose the deniable version of the solution to eKCI attack. It is based on exchanging the undeniable BLS layer from BLS-HMQV with the deniable identification (IS) scheme, for example, SchnorrIS. To illustrate the idea of the construction we first show theinitiator deniable solution based on the Schnorr identification protocol [42]. Next we observe that this particular solution is imperfect in systems where the ephemeral secrets may be leaked: the security of the long term key relies on the security of the ephemeral key; thus once the ephemeral secrets are leaked the long term secrets are also compromised.


### 4.1. The Basic Schnorr Based Imperfect Solution

Let us recall the Schnorr identification protocol from [42].Schnorr Identification Protocol. Let G be a group of prime order q and g be a generator of G. Suppose that an authenticator possesses the certified private/public key pair a,A=ga, and a verifier already knows the public key A=ga.(1)
The authenticator computesx∈RZq∗, X=gx and sends X to the verifier.(2)
The verifier chosesc∈RZq∗ and sends it to the authenticator.(3)
The authenticator computess=x+ac and sends s to the verifier.(4)
The verifier accepts the verification iffgs=XAc.Theinitiator deniable version of the protocol from Figure 2 augmented with the Schnorr identification protocol is presented in Figure 3. The hash function H2:0,1∗→Zq∗ effectively produces challenge c computed from mA, which itself contains Y coined at Bob’s side.Figure 3
Preventing eKCI-initiator deniable imperfect solution.Deniability of the Basic Schnorr Based Solution. To prove the deniability of the protocol (Figure 3) for Alice it suffices to show the construction of the efficient simulator that produces the protocol transcript without the knowledge of Alice’s secret a. Indeed such a simulator exists: Bob simulates the messages of Alice with the distribution indistinguishable from the original one:(1)
Bob chooses randomlys∈RZq∗.(2)
Bob computesgx=X≔gs/Ac. Thus s=x+ac, although Bob does not know the value x.(3)
HavingX and s Bob computes the rest of the parameters and protocol messages: Y, Z, V are computed by Bob alone from his secrets; W is computed as MAC“0”,km, where values km on both sides are equal; hence σa=σb. Thus he produces the transcript X,Y,Z,V,W,s which has the same distribution as the original transcript that would be produced altogether with Alice.Note that message mA computed on Alice’s side does not contain X. Otherwise it would be impossible to compute X=(gs)/Ac for c=H2mA. Indeed, this trick was used to provide deniability of PACE∣AA protocol from [43].Imperfection of the Basic Schnorr Based Solution. The solution is imperfect in scenarios where ephemeral keys can be leaked. If the ephemeral secret x is known to the adversary, it can compute Alice’s long term secret a≔s-x/c and impersonate her since then. Therefore in the next section we propose using the secure version from [19].


### 4.2. Prevention of the Attack: Secure Deniable Solution

Modified Schnorr Identification Protocol from [19]. The idea of that protocol is to perform response computation in the exponent using a new generator g^. Let s recall the steps:(1)
The authenticator computesx∈RZq∗, X=gx and sends X to the verifier.(2)
The verifier computes a challengec∈RZq∗ and sends it to the authenticator.(3)
The authenticator computesg^=H1(X∣c), S=g^xg^ac and sends S to the verifier.(4)
The verifier accepts the verification iffe^S,g=e^H1(X∣c),XAc.Note that we do not require the intermediate computation ofs. Such intermediate values can be leaked in some scenarios and together with the leaked ephemerals can be used to compromise the long term keys. The modified HMQV protocol which uses the above technique for initiator is depicted in Figure 4. We denote the protocol as mHMQV-1.Figure 4
mHMQV-1: preventing eKCI-initiator deniable version.Deniability of the Modified Schnorr Based Solution. Theinitiator deniability property is preserved. We state the following.Theorem 8.
ThemHMQV-1 protocol depicted in Figure 4 isinitiator deniable.Proof.
We have to show how the simulatorSIMMI (with Bob’s view) would produce the transcript X, Y, Z, V, W, S which has exactly the same distribution as the transcript produced by two parties Alice and Bob together. The simulator SIMMI computes values X, Y, Z, V, W, S, where S=H1(X∣c)s=H1(X∣c)x+ac in the following way: It computes everything in the generator g first. It takes s, and y randomly computes Y=gy, mA = “Alice”∥“Bob”∥A∥B∥Y, and c=H2mA. Afterwards it is able to compute the commitment of the first message X = gx = gs/Ac accordingly (as in the example from Section 4.1). Y, Z, V are computed by Bob alone from his secrets as in HMQV. W is computed as MAC“0”,km, because values km on both sides are equal as σa=σb. Then it computes S=H1(X∣c)s. Note that it does not need to compute H1(X∣c)a: this value is not a part of the transcript. Therefore the resulting transcript has exactly the same distribution as the transcript computed by Alice and Bob together.Proving of Interaction for Initiator. Note that in theinitiator deniable version of the protocol mHMQV-1 in Figure 4 the transcript could have been produced by Bob alone, or together by Alice and Bob really interacting with each other. Therefore the simple trick can be made by Alice to have a proof of interaction. She simply has to remember x=logg⁡X as the commitment to the value X she uses in the first message. Usually ephemeral values are deleted once they are not needed anymore. However Alice may record the ephemeral value x and produce it in front of the judge to prove that the transcript, and particularly X, was not computed by Bob’s simulation. Indeed if Bob is to present x he will have to break DLP problem for X=gs/Ac. Still, if Alice does not store x, then no algorithm can tell if the transcript was the result of the protocol interaction or Bob’s simulation.Achieving Responder Deniability. The deniability of the responder also can be achieved; however it requires a slight modification of the protocol. The mechanism is symmetrical. The procedures of Bob mimic/reflect the behavior of Alice: this also requires an additional message from Bob at the end (so 4 messages in total). Note that storing values x and y enables Alice and Bob to prove the interaction according to reasoning from Section 4.2.We state that the modified protocol depicted in the Figure5 provides deniability for both Alice and Bob:(i)
The transcript can be simulated by the responder alone (Alice deniability).(ii)
The transcript can be simulated by the initiator alone (Bob deniability). We call the protocol mHMQV-2. It is deniable for both the initiator and the responder.Figure 5
mHMQV-2: preventing eKCI-deniability for both the initiator and the responder.Theorem 9.
ThemHMQV-2 protocol depicted in Figure 5 is “initiator deniable.”Proof.
Essentially it is as the proof of Theorem8. The only difference is that the value V is computed by the simulator as H1(Y∣d)yH1(Y∣d)bd and included in the last fourth message (not in the second).Theorem 10.
The mHMQV-2 protocol depicted in Figure5 is “responder deniable.”Proof.
Analogically it is as above. The simulatorSIMMR for the responder, with Alice’s secrets, produces the transcript X, Y, Z, W, S, V, where V = H1Yv should be equal to H1(Y∣d)y+bd for c = H2mB: It starts with v and x uniformly at random, computes X = gx, and sets mB = “Alice”∥“Bob”∥A∥B∥X, and h = H2mB. Then it computes Y = gy as gv/Bd. Z is computed as MAC“1”,km, because values km on both sides are equal as σa=σb. The parameters W, S can be easily computable with the input of Alice. Subsequently it computes V = H1(Y∣h)v.


## 4.1. The Basic Schnorr Based Imperfect Solution

Let us recall the Schnorr identification protocol from [42].Schnorr Identification Protocol. Let G be a group of prime order q and g be a generator of G. Suppose that an authenticator possesses the certified private/public key pair a,A=ga, and a verifier already knows the public key A=ga.(1)
The authenticator computesx∈RZq∗, X=gx and sends X to the verifier.(2)
The verifier chosesc∈RZq∗ and sends it to the authenticator.(3)
The authenticator computess=x+ac and sends s to the verifier.(4)
The verifier accepts the verification iffgs=XAc.Theinitiator deniable version of the protocol from Figure 2 augmented with the Schnorr identification protocol is presented in Figure 3. The hash function H2:0,1∗→Zq∗ effectively produces challenge c computed from mA, which itself contains Y coined at Bob’s side.Figure 3
Preventing eKCI-initiator deniable imperfect solution.Deniability of the Basic Schnorr Based Solution. To prove the deniability of the protocol (Figure 3) for Alice it suffices to show the construction of the efficient simulator that produces the protocol transcript without the knowledge of Alice’s secret a. Indeed such a simulator exists: Bob simulates the messages of Alice with the distribution indistinguishable from the original one:(1)
Bob chooses randomlys∈RZq∗.(2)
Bob computesgx=X≔gs/Ac. Thus s=x+ac, although Bob does not know the value x.(3)
HavingX and s Bob computes the rest of the parameters and protocol messages: Y, Z, V are computed by Bob alone from his secrets; W is computed as MAC“0”,km, where values km on both sides are equal; hence σa=σb. Thus he produces the transcript X,Y,Z,V,W,s which has the same distribution as the original transcript that would be produced altogether with Alice.Note that message mA computed on Alice’s side does not contain X. Otherwise it would be impossible to compute X=(gs)/Ac for c=H2mA. Indeed, this trick was used to provide deniability of PACE∣AA protocol from [43].Imperfection of the Basic Schnorr Based Solution. The solution is imperfect in scenarios where ephemeral keys can be leaked. If the ephemeral secret x is known to the adversary, it can compute Alice’s long term secret a≔s-x/c and impersonate her since then. Therefore in the next section we propose using the secure version from [19].


## 4.2. Prevention of the Attack: Secure Deniable Solution

Modified Schnorr Identification Protocol from [19]. The idea of that protocol is to perform response computation in the exponent using a new generator g^. Let s recall the steps:(1)
The authenticator computesx∈RZq∗, X=gx and sends X to the verifier.(2)
The verifier computes a challengec∈RZq∗ and sends it to the authenticator.(3)
The authenticator computesg^=H1(X∣c), S=g^xg^ac and sends S to the verifier.(4)
The verifier accepts the verification iffe^S,g=e^H1(X∣c),XAc.Note that we do not require the intermediate computation ofs. Such intermediate values can be leaked in some scenarios and together with the leaked ephemerals can be used to compromise the long term keys. The modified HMQV protocol which uses the above technique for initiator is depicted in Figure 4. We denote the protocol as mHMQV-1.Figure 4
mHMQV-1: preventing eKCI-initiator deniable version.Deniability of the Modified Schnorr Based Solution. Theinitiator deniability property is preserved. We state the following.Theorem 8.
ThemHMQV-1 protocol depicted in Figure 4 isinitiator deniable.Proof.
We have to show how the simulatorSIMMI (with Bob’s view) would produce the transcript X, Y, Z, V, W, S which has exactly the same distribution as the transcript produced by two parties Alice and Bob together. The simulator SIMMI computes values X, Y, Z, V, W, S, where S=H1(X∣c)s=H1(X∣c)x+ac in the following way: It computes everything in the generator g first. It takes s, and y randomly computes Y=gy, mA = “Alice”∥“Bob”∥A∥B∥Y, and c=H2mA. Afterwards it is able to compute the commitment of the first message X = gx = gs/Ac accordingly (as in the example from Section 4.1). Y, Z, V are computed by Bob alone from his secrets as in HMQV. W is computed as MAC“0”,km, because values km on both sides are equal as σa=σb. Then it computes S=H1(X∣c)s. Note that it does not need to compute H1(X∣c)a: this value is not a part of the transcript. Therefore the resulting transcript has exactly the same distribution as the transcript computed by Alice and Bob together.Proving of Interaction for Initiator. Note that in theinitiator deniable version of the protocol mHMQV-1 in Figure 4 the transcript could have been produced by Bob alone, or together by Alice and Bob really interacting with each other. Therefore the simple trick can be made by Alice to have a proof of interaction. She simply has to remember x=logg⁡X as the commitment to the value X she uses in the first message. Usually ephemeral values are deleted once they are not needed anymore. However Alice may record the ephemeral value x and produce it in front of the judge to prove that the transcript, and particularly X, was not computed by Bob’s simulation. Indeed if Bob is to present x he will have to break DLP problem for X=gs/Ac. Still, if Alice does not store x, then no algorithm can tell if the transcript was the result of the protocol interaction or Bob’s simulation.Achieving Responder Deniability. The deniability of the responder also can be achieved; however it requires a slight modification of the protocol. The mechanism is symmetrical. The procedures of Bob mimic/reflect the behavior of Alice: this also requires an additional message from Bob at the end (so 4 messages in total). Note that storing values x and y enables Alice and Bob to prove the interaction according to reasoning from Section 4.2.We state that the modified protocol depicted in the Figure5 provides deniability for both Alice and Bob:(i)
The transcript can be simulated by the responder alone (Alice deniability).(ii)
The transcript can be simulated by the initiator alone (Bob deniability). We call the protocol mHMQV-2. It is deniable for both the initiator and the responder.Figure 5
mHMQV-2: preventing eKCI-deniability for both the initiator and the responder.Theorem 9.
ThemHMQV-2 protocol depicted in Figure 5 is “initiator deniable.”Proof.
Essentially it is as the proof of Theorem8. The only difference is that the value V is computed by the simulator as H1(Y∣d)yH1(Y∣d)bd and included in the last fourth message (not in the second).Theorem 10.
The mHMQV-2 protocol depicted in Figure5 is “responder deniable.”Proof.
Analogically it is as above. The simulatorSIMMR for the responder, with Alice’s secrets, produces the transcript X, Y, Z, W, S, V, where V = H1Yv should be equal to H1(Y∣d)y+bd for c = H2mB: It starts with v and x uniformly at random, computes X = gx, and sets mB = “Alice”∥“Bob”∥A∥B∥X, and h = H2mB. Then it computes Y = gy as gv/Bd. Z is computed as MAC“1”,km, because values km on both sides are equal as σa=σb. The parameters W, S can be easily computable with the input of Alice. Subsequently it computes V = H1(Y∣h)v.


## 5. Key Security and eKCI Resistance

In this point we discuss the security aspects of the proposed modification.(i) Ephemeral Key Leakage Does Not Compromise Long Term Keys. This addresses the problem with the regular Schnorr authentication signalized in Section 4.1.(ii) eKCI Resistance. The mHMQV protocols, extended with the proposed modification of Schnorr identification scheme, are resistant against eKCI attack, that is, are immune against impersonation attacks of the adversary authenticator which learns both the long term key and the ephemeral key of the verifier.(iii) Session Key Security. The resulting protocol mHMQV still fulfills the session key security of the original unmodified version. In other words, the proposed modifications do not affect and impair the original AKE security.The following theorem states that leakage of authenticator’s ephemeral secret gives no advantage to the adversary whose goal is to extract the long term key.Theorem 11.
No adversary can extract the long term secret key of the authenticator given public parameters, transcript of the protocol, and the ephemeral secret of the authenticator.Proof.
The proof is by contradiction. W.l.o.g. let the authenticator be Alice, whose ephemeral keyx is leaked. Now suppose that some algorithm A(A,B,X,Y,Z,V,W,S,x), when given the public parameters A,B, transcript of the protocol X, Y, Z, V, W, S, and the ephemeral secret of Alice x, outputs Alice’s long term secret a in nonnegligible probability. Then we can use it as a subprocedure to break the DLP problem for a given value, say U=gu, for unknown u. We have to prepare the input for A, including U as public key of Alice, and S, as it would be computed by corresponding Alice’s secret key u. We set up the system in which U is the public key of Alice and a random x is her ephemeral key. We simulate the transcript which would be indistinguishable from the real one. Hence we know x and we can compute X. Values Y, Z, V, W are also easily computable. The only problem here is to produce the suitable S. Indeed in ROM we program H1(X∣c) as gr for randomly chosen r. Then we compute S=grxUrc, which equals grxgurc = grxgruc = H1(X∣c)xH1(X∣c)uc. Then verification holds: e^S,g = e^H1(X∣c),XUc, and we obtain a perfect simulation in ROM. Now we treat the value output from A as the discrete logarithm of U.


### 5.1. eKCI Resistance of mHMQV-1 and mHMQV-2

The eKCI resistance requires that the attacker cannot launch the impersonation attack, even if(1)
the attacker knows the long term key of the verifier,(2)
the ephemeral key of the verifier, after it is coined, is also leaked to the attacker as soon as it is coined. The attacker is required to possess and use the secret key corresponding to the public key of the authenticator with identity ID, to be positively verified and accepted with this identity ID.Remark 12.
It is of the paramount importance, here, to strictly follow the protocol scheduled steps and implement the protocol in the designed order. Indeed, if the verifier carelessly changes the protocol schedule and prepares the challengeY=gy before the very first step of the protocol (before receiving the commitment message X) and if the ephemeral y is leaked to the attacker before the first message, then it possible to impersonate any ID, say with public key U, but without corresponding secret u. In this case the attacker follows the simulator SIMMI: it starts with random s and the leaked y computes Y=gy, mD = “Dorothy”∥“Bob”∥U∥B∥Y, and c=H2mU. Then it computes X = gx as gs/Uc. Subsequently it computes S=H1(X∣c)s. Then in the first message it sends to Bob precomputed X and later on after receiving Y it sends back precomputed S, impersonating itself in this way to Bob.Theorem 13.
No adversary can authenticate as Alice in front of responder without the knowledge of the secret key “a” corresponding to public A=ga in mHMQV-1 and mHMQV-2 protocols.Proof.
(
1) Reduction to Security of Mod-Schnorr [19]. The proof is an immediate consequence of the security of the mod-Schnorr identification scheme: any attacker that would impersonate Alice without her keys in mHMQV-1 and mHMQV-2 protocols would be used to break the underlying security of the mod-Schnorr identification scheme [19]. Conversely assume that there is an effective adversary A that impersonates Alice, without her secret key a, in front of Bob in mHMQV-1 protocol with nonnegligible probability. We use that adversary as a subprocedure to break mod-Schnorr in the following way: We play the role of Bob for A. After obtaining X from A we forward it to our challenger as the first message. Then after obtaining c from our challenger we compute the values on Bob’s side and send the second message to A. Now after the adversary A issues an oracle query H2mA we set H2mA←c in ROM table return value c. After A outputs S we forward it as the third message to our challenger. Note that if A is successfully accepted in mHMQV-1 then it is also accepted in mod-Schnorr.
(
2) Reduction to CDH. Below we show how that adversary can be used to break the instance g,gα,gβ of the underlying CDH problem, as in original paper [19]. Suppose the adversary A plays Alice in front of Bob without the knowledge of her secret key and is accepted. We give the adversary the secret key of Bob. Note that Bob’s ephemeral key y can only be given (leaked to the adversary only ASAP after it is created on Bob’s side). Since then y is another representation of the challenge Y=gy. We set up the system for A with A=gα as the public key of Alice. Then we use arewinding technique (as in regular Schnorr identification): we fix the random value x used in X=gx by the algorithm A and let A interact twice with Bob, choosing each time a different random y, say y1 and y2. These will result with mA1,c1,S1 and mA2,c2,S2 accordingly. Note that on A’s query to H1(X∣c) we answer with the value gβ. If Bob accepts both times we have S1=gβxgβαc1 and S2=gβxgβαc2. Thus we have S1/S2 = gβαc1-αc2, so we can compute gαβ = S1/S2c1-c2-1.Theorem 14.
No adversary can be authenticated as Bob in front of Alice without the knowledge of the secret keyb corresponding to public B=gb in mHMQV-2 protocol.Proof.
The proof is similar to the proof of Theorem13. We omit it to save the space.As a simple conclusion from Theorems13 and 14 we state the following.Corollary 15.
The protocols mHMQV-1 and mHMQV-2 are resistant to eKCI attacks.Now we address the security of the session key. This refers to the requirement that the session key established by the parties in the course of the protocol execution is known only to those parties. Usually the security model for the session key defines the so-calledsession key security game, in which the attacker is allowed to issue queries to various oracles, about the long term keys, and ephemeral keys of both parties. Usually the attacker is allowed to issue any combination of such queries, except those which would trivially reveal the session key. Eventually the attacker should not be able to distinguish whether thetest-key, it was given, is the real established session key or some unrelated random value. However if it does distinguish that, with nonnegligible probability, it wins the security game, and the protocol is considered broken.


### 5.2. Session Key Security

To show the session key security we follow the same approach as in [17]. It is based on the actual HMQV security proven in [44]. Now observe that extension from [17] that immunes HMQV against eKCI only adds BLS layer for authentication purposes and does not affect the underlying session key security of HMQV. We follow the same approach. We want to show that our modifications do not spoil the session key security of the original HMQV. Our modified version adds some additional computation on each side, providing extra deniable authentication steps, against eKCI attack. This extra computation does not affect the session key security of the original HMQV. We take for granted that HMQV is “session-key-secure”; that is, no adversary AHMQV can learn the session key for the completed session between uncorrupted parties (refer [45] for proof of that in Canetti-Krawczyk model). Note that these extra computations can be easily simulated in ROM. Thus the execution of original HMQV can be easily transformed in execution of our mod versions. Now any attacker breaking the session key security of mHMQV could be used to break the session key security of org HMQV. We state the following.Theorem 16.
If the original AKE protocol is “session-key-secure,” then the modified protocol, extended with the authentication method proposed in Section4.2, is also “session-key-secure” assuming programmable random oracle model.Proof.
The proof is by contradiction. Assume that there exists an efficient adversary algorithmAmod that breaks the security of the modified protocol. We can use it as a subprocedure, to build the adversary algorithm Aorg, which breaks the session key security of the original “unmodified” protocol. Observe that each oracle query from Amod can be served by Aorg via forwarding question and answers to/from corresponding oracles for org protocol. The only exception is queries concerning values S and V. These however can be easily simulated in ROM: for S we set H1(X∣c)←gr for some random r and compute S=H1(X∣c)xH1(X∣c)ac = grxgrac as XrArc (for V we simulate similarly). This way we transform the transcript of the original protocol “org” into the transcript of the modified protocol “mod.” Now any answer from Amod concerns the session key we output as the answer of Aorg. If Amod wins the session key security game for mod, then also Aorg wins the security game for org. This would contradict assumption about session key security of org protocol.


## 5.1. eKCI Resistance of mHMQV-1 and mHMQV-2

The eKCI resistance requires that the attacker cannot launch the impersonation attack, even if(1)
the attacker knows the long term key of the verifier,(2)
the ephemeral key of the verifier, after it is coined, is also leaked to the attacker as soon as it is coined. The attacker is required to possess and use the secret key corresponding to the public key of the authenticator with identity ID, to be positively verified and accepted with this identity ID.Remark 12.
It is of the paramount importance, here, to strictly follow the protocol scheduled steps and implement the protocol in the designed order. Indeed, if the verifier carelessly changes the protocol schedule and prepares the challengeY=gy before the very first step of the protocol (before receiving the commitment message X) and if the ephemeral y is leaked to the attacker before the first message, then it possible to impersonate any ID, say with public key U, but without corresponding secret u. In this case the attacker follows the simulator SIMMI: it starts with random s and the leaked y computes Y=gy, mD = “Dorothy”∥“Bob”∥U∥B∥Y, and c=H2mU. Then it computes X = gx as gs/Uc. Subsequently it computes S=H1(X∣c)s. Then in the first message it sends to Bob precomputed X and later on after receiving Y it sends back precomputed S, impersonating itself in this way to Bob.Theorem 13.
No adversary can authenticate as Alice in front of responder without the knowledge of the secret key “a” corresponding to public A=ga in mHMQV-1 and mHMQV-2 protocols.Proof.
(
1) Reduction to Security of Mod-Schnorr [19]. The proof is an immediate consequence of the security of the mod-Schnorr identification scheme: any attacker that would impersonate Alice without her keys in mHMQV-1 and mHMQV-2 protocols would be used to break the underlying security of the mod-Schnorr identification scheme [19]. Conversely assume that there is an effective adversary A that impersonates Alice, without her secret key a, in front of Bob in mHMQV-1 protocol with nonnegligible probability. We use that adversary as a subprocedure to break mod-Schnorr in the following way: We play the role of Bob for A. After obtaining X from A we forward it to our challenger as the first message. Then after obtaining c from our challenger we compute the values on Bob’s side and send the second message to A. Now after the adversary A issues an oracle query H2mA we set H2mA←c in ROM table return value c. After A outputs S we forward it as the third message to our challenger. Note that if A is successfully accepted in mHMQV-1 then it is also accepted in mod-Schnorr.
(
2) Reduction to CDH. Below we show how that adversary can be used to break the instance g,gα,gβ of the underlying CDH problem, as in original paper [19]. Suppose the adversary A plays Alice in front of Bob without the knowledge of her secret key and is accepted. We give the adversary the secret key of Bob. Note that Bob’s ephemeral key y can only be given (leaked to the adversary only ASAP after it is created on Bob’s side). Since then y is another representation of the challenge Y=gy. We set up the system for A with A=gα as the public key of Alice. Then we use arewinding technique (as in regular Schnorr identification): we fix the random value x used in X=gx by the algorithm A and let A interact twice with Bob, choosing each time a different random y, say y1 and y2. These will result with mA1,c1,S1 and mA2,c2,S2 accordingly. Note that on A’s query to H1(X∣c) we answer with the value gβ. If Bob accepts both times we have S1=gβxgβαc1 and S2=gβxgβαc2. Thus we have S1/S2 = gβαc1-αc2, so we can compute gαβ = S1/S2c1-c2-1.Theorem 14.
No adversary can be authenticated as Bob in front of Alice without the knowledge of the secret keyb corresponding to public B=gb in mHMQV-2 protocol.Proof.
The proof is similar to the proof of Theorem13. We omit it to save the space.As a simple conclusion from Theorems13 and 14 we state the following.Corollary 15.
The protocols mHMQV-1 and mHMQV-2 are resistant to eKCI attacks.Now we address the security of the session key. This refers to the requirement that the session key established by the parties in the course of the protocol execution is known only to those parties. Usually the security model for the session key defines the so-calledsession key security game, in which the attacker is allowed to issue queries to various oracles, about the long term keys, and ephemeral keys of both parties. Usually the attacker is allowed to issue any combination of such queries, except those which would trivially reveal the session key. Eventually the attacker should not be able to distinguish whether thetest-key, it was given, is the real established session key or some unrelated random value. However if it does distinguish that, with nonnegligible probability, it wins the security game, and the protocol is considered broken.


## 5.2. Session Key Security

To show the session key security we follow the same approach as in [17]. It is based on the actual HMQV security proven in [44]. Now observe that extension from [17] that immunes HMQV against eKCI only adds BLS layer for authentication purposes and does not affect the underlying session key security of HMQV. We follow the same approach. We want to show that our modifications do not spoil the session key security of the original HMQV. Our modified version adds some additional computation on each side, providing extra deniable authentication steps, against eKCI attack. This extra computation does not affect the session key security of the original HMQV. We take for granted that HMQV is “session-key-secure”; that is, no adversary AHMQV can learn the session key for the completed session between uncorrupted parties (refer [45] for proof of that in Canetti-Krawczyk model). Note that these extra computations can be easily simulated in ROM. Thus the execution of original HMQV can be easily transformed in execution of our mod versions. Now any attacker breaking the session key security of mHMQV could be used to break the session key security of org HMQV. We state the following.Theorem 16.
If the original AKE protocol is “session-key-secure,” then the modified protocol, extended with the authentication method proposed in Section4.2, is also “session-key-secure” assuming programmable random oracle model.Proof.
The proof is by contradiction. Assume that there exists an efficient adversary algorithmAmod that breaks the security of the modified protocol. We can use it as a subprocedure, to build the adversary algorithm Aorg, which breaks the session key security of the original “unmodified” protocol. Observe that each oracle query from Amod can be served by Aorg via forwarding question and answers to/from corresponding oracles for org protocol. The only exception is queries concerning values S and V. These however can be easily simulated in ROM: for S we set H1(X∣c)←gr for some random r and compute S=H1(X∣c)xH1(X∣c)ac = grxgrac as XrArc (for V we simulate similarly). This way we transform the transcript of the original protocol “org” into the transcript of the modified protocol “mod.” Now any answer from Amod concerns the session key we output as the answer of Aorg. If Amod wins the session key security game for mod, then also Aorg wins the security game for org. This would contradict assumption about session key security of org protocol.


## 6. Performance

Each of the proposed modifications of the scheme strengthens its security but requires performing certain amount of additional computations, which should be expected to affect the overall performance of the protocol. We implemented the basic scheme(3-pass HMQV), the BLS based scheme(BLS-HMQV), the basic Schnorr based imperfect modification(mHMQV-0), the modified Schnorr based initiator deniable version(mHMQV-1), and the modified Schnorr based fully deniable version(mHMQV-2) in order to measure how much do the proposed improvements extend the execution time of the protocol.


### 6.1. Implementation

Our implementations have been created usingPython 3 with theCharm Crypto library [46], a commonly used open-source cryptographic toolbox providing methods to perform operations on elliptic curves, including bilinear pairings and hashing and thetimeit for measuring the average execution times. All computations are performed on the same NIST-approved symmetric elliptic curve with a 512-bit base field [47]. In order to measure nothing but the time of computations strictly related to the schemes, each implementation is created as a single program, where the two parties are simulated by interweaving methods.


### 6.2. Results

Average execution time for each protocol has been measured by running 1000 full rounds of each version on aUbuntu 12 virtual machine withIntel i7 2.5 GHz and 8 GB RAM. The acquired results are presented in Table 2. As it was expected, each modified version of the protocol is 4 to 8 times slower than the original one. This is intuitively self-explained: each subsequent modification requires additional computing hashes and bilinear pairings.Table 2
Execution times for different protocol versions.
Protocol
1000 executions
Average time
3-pass HMQV
4,150.30 ms
4.15 ms
BLS-HMQV
16,565.33 ms
16.57 ms
mHMQV-0
18,505.76 ms
18.51 ms
mHMQV-1
27,336.94 ms
27.34 ms
mHMQV-2
33,992.05 ms
33.99 msAs a first step in assessing which modifications affect the execution time of the protocols, we had to measure the execution times for everybuilding block operation used in the protocol. The results can be seen in Table 3. It emerges that the bilinear pairing operation, crucial for our modifications, requires relatively much computational power. However, to better assess the protocols, we have measured how much time is taken for the most complexbuilding blocks, as it has to be noticed that each of them may be used multiple times in a single protocol round.Table 3
Average computation times for basic cryptographic building blocks used in the protocols.
Operation
Average time
Bilinear pairing
4.91 ms
Modular exponentiation
0.66 ms
Hash computing
0.14 ms
Multiplication
<0.01 ms
Addition
<0.01 msA detailed assessment of time complexity for every protocol version has been presented in Table4. It depicts how much time in the protocols is consumed by computing bilinear pairings, hashes, and modular exponents (ModPow operations). One can easily notice that the longer execution time in the modified versions resulted mostly from usage of bilinear pairings. One should take it into consideration while implementing these schemes, as some hardware enhancements could possibly improve the performance of the pairing routines and, as a result, the entire protocol.Table 4
Time complexity assessment for different protocol versions.
Protocol
ModPow
Hashing
Pairing
Other
Total
3-pass HMQV
1.74 ms
0.44 ms
0.00 ms
1.97 ms
4.15 ms
BLS-HMQV
3.29 ms
1.23 ms
9.71 ms
2.34 ms
16.57 ms
mHMQV-0
2.99 ms
1.07 ms
9.43 ms
5.02 ms
18.51 ms
mHMQV-1
5.20 ms
1.78 ms
15.41 ms
4.95 ms
27.34 ms
mHMQV-2
6.89 ms
1.21 ms
21.03 ms
4.86 ms
33.99 msNevertheless, it has to be pointed that the average execution time remains to be just several milliseconds in all the cases, making any of the proposed modification applicable to implementation in real-world usage.


## 6.1. Implementation

Our implementations have been created usingPython 3 with theCharm Crypto library [46], a commonly used open-source cryptographic toolbox providing methods to perform operations on elliptic curves, including bilinear pairings and hashing and thetimeit for measuring the average execution times. All computations are performed on the same NIST-approved symmetric elliptic curve with a 512-bit base field [47]. In order to measure nothing but the time of computations strictly related to the schemes, each implementation is created as a single program, where the two parties are simulated by interweaving methods.


## 6.2. Results

Average execution time for each protocol has been measured by running 1000 full rounds of each version on aUbuntu 12 virtual machine withIntel i7 2.5 GHz and 8 GB RAM. The acquired results are presented in Table 2. As it was expected, each modified version of the protocol is 4 to 8 times slower than the original one. This is intuitively self-explained: each subsequent modification requires additional computing hashes and bilinear pairings.Table 2
Execution times for different protocol versions.
Protocol
1000 executions
Average time
3-pass HMQV
4,150.30 ms
4.15 ms
BLS-HMQV
16,565.33 ms
16.57 ms
mHMQV-0
18,505.76 ms
18.51 ms
mHMQV-1
27,336.94 ms
27.34 ms
mHMQV-2
33,992.05 ms
33.99 msAs a first step in assessing which modifications affect the execution time of the protocols, we had to measure the execution times for everybuilding block operation used in the protocol. The results can be seen in Table 3. It emerges that the bilinear pairing operation, crucial for our modifications, requires relatively much computational power. However, to better assess the protocols, we have measured how much time is taken for the most complexbuilding blocks, as it has to be noticed that each of them may be used multiple times in a single protocol round.Table 3
Average computation times for basic cryptographic building blocks used in the protocols.
Operation
Average time
Bilinear pairing
4.91 ms
Modular exponentiation
0.66 ms
Hash computing
0.14 ms
Multiplication
<0.01 ms
Addition
<0.01 msA detailed assessment of time complexity for every protocol version has been presented in Table4. It depicts how much time in the protocols is consumed by computing bilinear pairings, hashes, and modular exponents (ModPow operations). One can easily notice that the longer execution time in the modified versions resulted mostly from usage of bilinear pairings. One should take it into consideration while implementing these schemes, as some hardware enhancements could possibly improve the performance of the pairing routines and, as a result, the entire protocol.Table 4
Time complexity assessment for different protocol versions.
Protocol
ModPow
Hashing
Pairing
Other
Total
3-pass HMQV
1.74 ms
0.44 ms
0.00 ms
1.97 ms
4.15 ms
BLS-HMQV
3.29 ms
1.23 ms
9.71 ms
2.34 ms
16.57 ms
mHMQV-0
2.99 ms
1.07 ms
9.43 ms
5.02 ms
18.51 ms
mHMQV-1
5.20 ms
1.78 ms
15.41 ms
4.95 ms
27.34 ms
mHMQV-2
6.89 ms
1.21 ms
21.03 ms
4.86 ms
33.99 msNevertheless, it has to be pointed that the average execution time remains to be just several milliseconds in all the cases, making any of the proposed modification applicable to implementation in real-world usage.


## 7. Conclusion

In this paper we extended the results from [17]. We observed that the solution from [17], protecting HMQV against the eKCI attack, destroys the deniability property of HMQV. Therefore, following the two-layer construction of [17], we exchange the undeniable BLS signatures layer, with the modified Schnorr identification scheme from [19] resistant to ephemeral key leakages. This way we immune HMQV against eKCI in such a way that the deniability property is preserved. Compared with the undeniable solution from [17], in ourinitiator deniable version of the protocol Alice needs to compute one more exponentiation. Theinitiator and responder deniable version requires two more exponentiations (one more per side) and the additional fourth message. The conducted experiments confirmed that, despite the additional computational effort, the newly proposed protocols remain efficient enough to be implemented in real-world applications.



---

*Source: 7810352-2017-09-24.xml*