Breaking provably secure SAKE-C authenticated key exchange protocol with Extended Key Compromise Impersonation (E-KCI) Attack

Authenticated Key Exchange (AKE) protocols are those protocols that allow two or more entities to concur with a common session key in an authentic manner in which this key isused to encrypt the proceeding communications.

By Ali Mackvndai& Mansour Naddafiun;Pishgaman International Enterprise Maryam Saeed Iran University of Science & Technology

In 2010, Zhao etal. proposed Provably Secure Authenticated Key Exchange
Protocol under the CDH Assumption (referred to as SAKE and SAKE-C). Despite the fact that the security of the proposeprotocol is proved in the formal model, due to not considering all the prerequisite queries in defining and designing formal security model, in this paper it is shown that the so-called secure protocol is vulnerable to Extended Key Compromise Impersonation (E-KCI) attack so that this attack is a practicable flaw that was
signaled by Tang et al. for the first time in 2011.

It is furthermore worth mentioning that Tang et al. applied E-KCI attack to the
famous 3-pass HMQV protocol. It is also noteworthy that the E-
KCI attack is verified by D. Pointcheval in Tang et al.’s paper.


THE indispensable need for maintaining the security,privacy, and reliability of transmitting data over the Internetmade many researchers propose and devise different methodsbased on the cryptographic approaches.

To the best of ourknowledge, the first practical step in preserving the privacyand security of the vital transmitting data is to establish acommon symmetric encryption session key in a secure mannerbetween two or more intended entities.

Another burning issueis key authentication that should be achieved between thecorresponding parties in an authentic way.

In other words, keyauthentication is achieved successfully when communicatingparties assure that they are the only ones who are cognizant ofthe fresh agreed-upon session key.

If a KE protocol providesmutual authentication, it is called authenticated Key Exchange(AKE) protocol.

Consequently, numerous Key Exchangeprotocols (KE) have been proposed and studied over the pastyears to provide a diversity of security needs, the most secureand efficient of which are surveyed in [1,2].

Also, the mostrecent studies on KE protocols can be referred to the seminalwork of Diffie-Hellman and Needham-Schroeder in [3,4].Furthermore, the standardization associations including IEEE and ISO have proposed several key establishment standards inthe literature [5,6,7].

While we are encountering with new attacks and threatson the Internet day in and day out, it is perspicuous thatdesigning and proposing a secure protocol, being able to resistthese ongoing vulnerabilities, is not a trivial task.

Consequently, it is incumbent on the protocol designers totake into consideration all the imperative security attributesthroughout designing their protocols since, in case of anynegligence in designing such protocols, ineluctable andirreparable losses will be brought about.It is also worth mentioning that analyzing the security ofthe proposed protocols is commonly achieved in the formalmodels, but defining a proper model is not a inconsequentialtask, because not taking account of some types of queries, e.g.the Corrupt Query [8,9], or malapropos defining theadversarial game [10 ] may prompt a security proof that failsto capture valid attacks, and this matter disproves the beliefthat a security proof in the Random Oracle Model means thatthere are no structural flaws in the scheme [11]. It is essential for AKEs to provide the following desirablesecurity attributes [13,15,16,17,18]:

  • Forward secrecy: The forward secrecy is provided if thesecrecy of previously established session keys is notdivulged by compromising any entity’s password or long-term private keys.
  •  Known session key security: Compromising the one sessionkey should  not jeopardize the security of other session keys.
  •  Resilience to Unknown Key Share attack (UKS): User should not be compelled into sharing a session key with anadversary E after the completion of a protocol run, whilefalsely thinks that his/her key is shared with user B.
  •  Resilience to password compromise impersonation attack: Disclosure of any user 's password should notallow an adversary to share any session key withbymasquerading him- or herself as any other entity.
  • Resilience to ephemeral key compromise impersonation attacks: Some protocols deploy some random parameters asthe ephemeral keys. Disclosure of any user 's ephemera key should not enable an adversary to establish a session keywithby impersonating him- or herself as any otherparticipant.


  •  Resilience to extended Key Compromise Impersonation (KCI) attack: Exposure of any participant's long-termand ephemeral secrets should not allow an adversary to shareany session key withby masquerading him- or herself asany other entity. In 2010, Zhao et al. [12] proposed Provably SecureAuthenticated Key Exchange Protocol under the CDHAssumption (referred to as SAKE-C). In spite of the fact thatthe security and efficiency of the SAKE-C protocol is provedin the formal model and that it is asserted that one of theexpected and desirable security attributes of a secure AKEprotocol is resistance to KCI attack, but the designers of [12]did not take into consideration all the fundamental securityfeatures in defining their formal security model, causing theirproposed protocol to be vulnerable to the Extended KCIattack.

    The E-KCI attack is a feasible threat in the real worldsince an adversary can easily gain access to the confidentialinformation of users by exploiting different malwares whichcan be installed on the victim’s system platform or theadversary can utilize the imperfectness of the pseudo-randomnumber generator in practice [13]. It is also notable that the E-KCI attack is upheld by D. Pointcheval in [13]. The rest of the paper is organized as follows. Section 2explicates the notation used hereinafter and reviews theSAKE-C protocol [12] in brief, while its security vulnerabilityis elucidated in Section 3. Finally, the conclusion is drawn in section 4


PROTOCOLIn this section, in concise, we scrutinize SAKE-C protocol[12] in Fig.1. It is noteworthy that SAKE protocols consist oftwo versions, namely SAKE and SAKE-C.

There is a slightdifference between these two proposed versions in which theformer requires two communication rounds without providingPerfect forward Secrecy(PFS) and key confirmation whereasthe latter requires three rounds of communications thatsatisfies PFS and key confirmation. For the sake of simplicity,we will zero in on the SAKE-C protocol, since it is assertedthat this version is more secure and robust in comparison withthe other one.

The notations applied in this protocol are listedin Table1.The running steps of the SAKE-C protocol, which is depictedin Fig.1, proceed as follows:(1) The participantselects an ephemeral keyandcomputes , ,,, ,.) , , respectively and sends, to .(2) Upon receiving, from , verifies the validationofby computing.and, .If, it means.Then, chooses an ephemeral key and calculates, ,, ),,,,, , , ,1, , , ,, ,respectively, and sends, ,to .

Table 1. Deployed NotationsNotationDefinition IDA, IDB Identities of users and , respectively. P, q, g Two large primes p and q with q|(p−1), anda generator g of group G with order q. A, a Long-term key pair of , in which A = ga modp. B, b Long-term key pair of , in which B = gb modp. , Ephemeral keys of and , respectively. H1,H2 : {0, 1}* → Two collision-free one-way hashfunctions modeled as random oracles. H:{0,1}*→ 0,1 Collision-free one-way hash functionmodeled as a random oracle, where is asecurity parameter. SK Session key established by the users. (3) Likewise, upon receiving , ,from , also verifies the authenticity ofby computing .and, . If , it means.Then,computes, , , , ,,0, , , ,,and . Also, checks the validity of =. If it holds, thensendsto .(4) As soon asrevieves , s/he checks if =. If the equality holds,assures ofthe legitimacy of .At this stage, both entities share their common session keyand verify the validity of the exchanged key SK.


Vulnerability to Extended Key Compromise Impersonation (E-KCI) attack:In this section, it is shown that the proposed protocol [12] issubject to E-KCI attack. As it is mentioned, the E-KCI attackis demonstrated for the first time by [13] and they proved thatthis attack is a feasible threat in the real world, because anadversary can easily gain access to the confidentialinformation of users by exploiting different malwares whichcan be installed on victim’s system platform or the adversarycan misuse of the imperfectness of the pseudo-random numbergenerator in use [13]. Into the bargain, it is noteworthy that theE-KCI attack is confirmed by D. Pointcheval in Tang et al.’spaper.The E-KCI attack is reasonably straightforward and canproceed as follows:(1) The adversary initiates the E-KCI attack against Alice bycompromising Alice’s long-term private key and the Diffie-Hellman ephemeral key x , respectively. Then, s/he can posehimself/herself as the opposite party, Bob, and carry on theprotocol steps.(2) Upon receiving ,from Alice, the adversarysequentiallyselects, and computes , ,,, ,. ),,,,, , , , 1, , , ,, and. Then, the adversary sends, ,toAlice.(3) After receiving , ,, Alice first verified thevalidity ofby computing .and, . If , it means. Then, computes , , , , ,and 0, , , ,. Finally, Alice computes for verification and sends it to the adversary.At this moment in time, the adversary is succeeded toimpersonate him-or herself as and shares a valid session keywith the participant .


In this paper, the provably secure SAKE-C protocol isanalyzed. Notwithstanding the fact that the security of theanalyzed protocol is evinced and proved in the formal model,we demonstrated that how easy the adversary can apply E-KCIattack which is introduced for the first time by Tang et al. onthis protocol by installing some Trojans on the victim’s systemor the adversary can employ the imperfectness of the pseudo-random number generator and breaks the protocol.Unfortunately, it goes without saying that most of the PAKEand AKE protocols are vulnerable to E-KCI attack which is anew-introduced flaw in this field, because even one of themost famous PAKE protocols such as the 3-pass HMQVprotocol suffers from this vulnerability. As a countermeasure, it is suggested that a deterministic EU-CMA secure signature can be employed in the protocols.Through a deterministic signature, we mean that a signature isa function of the private signing key and a signed message,and does not require any ephemeral secret, since we presumethat our resolution works in the environment where theephemeral secret might be in jeopardy. For instance, we selectthe BLS signature for a reasonably good functioning [14], inspite of the fact that other secure deterministic signatureschemes should also be adequate.

Published by:

siavash's picture