# Password-Only Authenticated Three-Party Key Exchange Proven Secure against Insider Dictionary Attacks

Authors: Junghyun Nam; Kim-Kwang Raymond Choo; Juryon Paik; Dongho Won
Journal: The Scientific World Journal
 (2014)

---

## Abstract

While a number of protocols for password-only authenticated key exchange (PAKE) in the 3-party setting have been proposed, it still remains a challenging task to prove the security of a 3-party PAKE protocol against insider dictionary attacks. To the best of our knowledge, there is no 3-party PAKE protocol that carries a formal proof, or even definition, of security against insider dictionary attacks. In this paper, we present the first 3-party PAKE protocol proven secure against both online and offline dictionary attacks as well as insider and outsider dictionary attacks. Our construct can be viewed as a protocol compiler that transforms any 2-party PAKE protocol into a 3-party PAKE protocol with 2 additional rounds of communication. We also present a simple and intuitive approach of formally modelling dictionary attacks in the password-only 3-party setting, which significantly reduces the complexity of proving the security of 3-party PAKE protocols against dictionary attacks. In addition, we investigate the security of the well-known 3-party PAKE protocol, called GPAKE, due to Abdalla et al. (2005, 2006), and demonstrate that the security of GPAKE against online dictionary attacks depends heavily on the composition of its two building blocks, namely a 2-party PAKE protocol and a 3-party key distribution protocol.


---

## Body

## 1. Introduction

Key exchange protocols (also known as key establishment protocols) enable two or more parties communicating over a public network to establish a shared secret key. This secret key, called asession key, is then used for building a confidential or integrity-preserving communication channel between the involved parties. Typically, a key exchange protocol is integrated with an authentication mechanism so that each party can ensure that the session key is in fact shared with the intended parties and not with an impostor. Achieving authenticated key exchange (AKE) inevitably requires some secret information to be preestablished between the parties during an initialization phase. Password-only authenticated key exchange (PAKE) protocols, for example, are designed to work when the preestablished secret information for authentication is only a human-memorable password.The design of secure PAKE protocols continues to be a subject of active research. A major challenge in designing a PAKE protocol is to prevent dictionary attacks, in which an attacker exhaustively enumerates all possible passwords to find out the correct password. The difficulty of designing PAKE protocols secure against dictionary attacks is compounded in the 3-party setting, in which two clients wishing to establish a session key share their individual passwords only with an authentication server but not with any other client. A 3-party PAKE protocol must prevent potential dictionary attacks by a malicious client, who is registered with the server and thus is able to set up normal protocol sessions with other clients. (Throughout the paper, we will use the term “insider attacks” to refer to attacks mounted by a registered (malicious) client and use the term “outsider attacks” to refer to attacks mounted by a nonregistered party.) Indeed, a cursory review of the literature suggests that the majority of attacks mounted against 3-party PAKE protocols fall into the category of insider dictionary attacks; see, for example, Section2 as well as [1–6].The difficulties of obtaining a high level of assurance in the security of almost any new, or even existing, protocol are well illustrated with examples of errors found in many such protocols years after they were published. A widely accepted approach is to use a deductive reasoning process whereby the emphasis is placed on a proven reduction from the problem of breaking the protocol to another problem believed to be hard. Such an approach for key exchange protocols was made popular by Bellare and Rogaway [7] who provide the first formal definition for a model of adversary capabilities with an associated definition of the indistinguishability-based security. This model has been further revised several times, and one of the more recent revisions is the real-or-random (ROR) model proposed by Abdalla et al. [8, 9] for PAKE protocols. They also proposed a generic construction of a 3-party PAKE protocol that allows existing provably secure 2-party password-based key exchange and 3-party symmetric key distribution protocols to beplugged and played in a modular approach and yet remain secure [8, 9].To date, a number of 3-party PAKE protocols have been presented with a formal proof of security [1, 8–17]. Most of these protocols were proven secure only in a restricted model, in which the adversary is not allowed to corrupt protocol participants [1, 8–10, 12–14]. In other words, these protocols were not proven secure against insider attacks including dictionary attacks conducted by insiders. Some protocols [11, 13] were subsequently found to be flawed [6, 18] and several protocols [15, 16] were proven secure only in a model that cannot capture (both insider and outsider) online dictionary attacks. Although protocols such as those of [19, 20] claimed to be provably secure against dictionary attacks of any kind, these protocols assume a “hybrid” 3-party setting where a server’s public key is required in addition to passwords (see [21–27] for other protocols designed to work in a hybrid setting). To the best of our knowledge, no 3-party PAKE protocol has been proven secure against insider dictionary attacks.We regard the contributions of this paper to be threefold.Contribution 1. We presentthe first 3-party PAKE protocol, a hashed variant of the protocol of  [1], whose indistinguishability-based security as well as password security against all classes of dictionary attacks are formally proved in a well-defined communication model. Similar to the protocols of [1, 8, 9], our proposed protocol is generic in the sense that it can be constructed from any 2-party AKE protocol. Our construct can be viewed as a protocol compiler that transforms any 2-party AKE protocol into a 3-party AKE protocol with 2 more rounds of communication. If the given 2-party protocol is password-only authenticated, then the 3-party protocol output by the compiler will also be password-only authenticated. We prove the security of our construct in the random oracle model under the gap Diffie-Hellman (GDH) assumption; see Section 4.Contribution 2. We offera simple and intuitive approach of capturing dictionary attacks in the widely accepted model of Bellare et al. [28]. First, we clarify the relationship between the indistinguishability-based security of session keys and the password security against dictionary attacks.(i)
The indistinguishability-based security property in the Bellare-Pointcheval-Rogaway model implies security against (both insider and outsider) offline dictionary attacks. We demonstrate this by showing that a protocol cannot achieve the indistinguishability-based security if it is not secure against an offline dictionary attack (see Section3.3).(ii)
The indistinguishability-based security property does not imply security against undetectable online dictionary attacks (referred to as “UD online dictionary attacks” in the remainder of this paper). It is important to note that a protocol may be insecure against a UD online dictionary attack but it can still achieve the indistinguishability-based security (see Section3.3). This observation allows us to exclude offline dictionary attacks from our consideration once we have proved the indistinguishability-based security. We then introduce a new security definition to capture UD online dictionary attacks. We claim that our approach, when compared to those of [19, 20] (where a separate security definition is introduced to capture both UD online and offline dictionary attacks), provides a more intuitive and simpler way of proving security against dictionary attacks (see Section 3).Contribution 3. We revisit the generic protocol GPAKE of Abdalla et al. [8, 9] to provide a detailed analysis of its security against UD online dictionary attacks. (We note that the work of Wang and Hu [1] has only provided a sketch of an insider UD online dictionary attack against GPAKE.) GPAKE is parameterized with a 2-party PAKE protocol 2PAKE and a 3-party key distribution protocol 3KD. We found that the security of GPAKE against both insider and outsider UD online dictionary attacks depends heavily on the security properties provided by 2PAKE and 3KD. For example, we can launch an insider UD online dictionary attack against the protocol GPAKE if neither 2PAKE nor 3KD provides client-to-server authentication. An outsider UD online dictionary attack can also be mounted under the same condition in addition to the condition that 2PAKE provides server-to-client authentication (see Section 2 for details).


## 2. Undetectable Online Dictionary Attacks against GPAKE

This section presents a comprehensive analysis of the security of the GPAKE protocol [8, 9] against UD online dictionary attacks. Our analysis shows that (1) GPAKE relies its security against UD online dictionary attacks on how its building blocks are instantiated and (2) the attacks could be mounted not only by a registered client (an insider) but also by a nonregistered party (an outsider). After conducting the security analysis, we suggest possible combinations of the instantiations that allow the GPAKE protocol to avoid the attacks.


### 2.1. A Review of GPAKE

The GPAKE protocol is constructed using a combination of three building blocks: (1) a 2-party PAKE protocol 2PAKE, (2) a 3-party key distribution protocol 3KD, and (3) a message authentication code- (MAC-) based Diffie-Hellman key exchange protocol MDH. LetG be a finite cyclic group generated by an element g; and let Σ= (Mac, Ver) be a MAC scheme where Mac and Ver are the MAC generation and MAC verification algorithms, respectively. The security of MDH relies on the hardness of the decisional Diffie-Hellman (DDH) problem in G and on the security of the underlying MAC scheme Σ against chosen message attacks. S represents a trusted server which registers clients and, during the registration, each client shares their individual password secretly with S. Suppose that A and B are two registered clients who wish to establish a session key and pwA and pwB are the passwords of A and B, respectively.


#### 2.1.1. Description

A high-level depiction of GPAKE is given in Figure1 and its brief description follows. First, A (and B) and S establish a shared high-entropy key, kAS (and kBS, resp.), by running the 2-party PAKE protocol, 2PAKE. Then, S generates a MAC key, kAB, and distributes kAB to both A and B by running the 3-party key distribution protocol 3KD which takes kAS and kBS as input. A session key, sk=gab, will be established between A and B after running the MAC-based Diffie-Hellman key exchange protocol MDH which takes kAB as an input.Figure 1
GPAKE: Abdalla et al.’s generic 3-party PAKE protocol [8, 9].


#### 2.1.2. Instantiations

Abdalla et al. [8, 9] suggested several practical and provably secure protocols that can be used in the instantiation of the 2-party protocol 2PAKE. Among them are the KOY protocol [29, 30] and its generalization [31], the PAK suite [32], and other protocols based on encrypted key exchange (EKE) of Bellovin and Merritt [33] (e.g., Bresson et al.’s OMDHKE protocol [34]). For the instantiation of 3KD, any particular choice that is secure with respect to a single session will do since the symmetric keys given as input to 3KD differ from session to session. Bellare and Rogaway’s 3PKD protocol [35], for example, was suggested as a possible choice. The MAC scheme used in MDH can be instantiated with the HMAC [36] and the CBC MAC.


### 2.2. An Insider Attack

Let us consider, for example, the case where 2PAKE and 3KD are instantiated with the PPK protocol [32] and with the 3PKD protocol [35], respectively. In this case, a malicious client B who is registered with the server, S, can mount a UD online dictionary attack against any other client, for example, A. It is important to note that we do not require either of the protocols, PPK (see Figure 2) and 3PKD (see Figure 3), to be insecure and, in fact, we assume that both protocols are secure.Figure 2
The PPK protocol [32].Figure 3
The 3PKD protocol [35].


#### 2.2.1. The PPK Protocol

LetG be a finite cyclic group of order q, and let g be a generator of G. The three hash functions used are G1:{0,1}*→G, G2:{0,1}*→G, and H:{0,1}*→{0,1}l, where l is the length of the session key. pwA denotes A’s password known only to A and (v-A,wA)=((G1(pwA))-1,G2(pwA)) denotes the password verifiers held by S. The functionacceptable  (*) returns true, if and only if *∈G (or, *∈G^ when G is defined as a (proper) subgroup of a group G^). The session key kAS is computed as kAS=H(A∥S∥X~∥Z~∥K∥v-A). We observe that two messages 〈A,X~〉 and 〈S,Z~〉 are independent and thus the protocol can be easily modified to run in a single round.


#### 2.2.2. The 3PKD Protocol

The cryptographic tools used in 3PKD include (1) a symmetric encryption scheme consisting of a pair of encryption/decryption algorithms (Enc, Dec) and (2) a MAC scheme consisting of a pair of MAC generation/verification algorithms (Mac, Ver). The protocol runs between a trusted server, S, and two clients, A and B. A (and B) and S are assumed to have preestablished a 2κ-bit secret kAS=kASenc∥kASmac (resp., kBS=kBSenc∥kBSmac). The protocol, depicted in Figure 3, begins by having A choosing a random κ-bit challenge rA and sending it to client B. B also chooses a random κ-bit challenge rB and sends 〈rA,rB〉 to S. Upon receiving 〈rA,rB〉, S generates a session key kAB which he will distribute. S then encrypts kAB under A’s encryption key kASenc (resp., B’s encryption key kBSenc) to get ciphertext αA (resp., αB). Then, S computes μA (resp., μB), the MAC under key kASmac (resp., kBSmac) of the string A∥B∥rA∥αA (resp. A∥B∥rB∥αB). Then, S sends 〈αA,μA〉 and 〈αB,μB〉 to A and B, respectively. A and B accept the session key kAB if and only if their received MAC is valid.In order for PPK and 3PKD to be used together, the session keys generated by PPK need to be at least2κ-bit long.


#### 2.2.3. One Possible Attack Scenario

The malicious client,B, can mount the following UD online dictionary attack against another client, A.Step 1 (running PPK).
Bbegins by initiating two concurrent runs, R1 & R2, of the PPK protocol. (i)
In the (dishonest) run R1,B impersonating A makes a guess (denoted by pwA′) on A’s actual password, pwA, selects a random x∈Zq, computes X~′=gx·G1(pwA′), and sends the server S a fabricated message 〈A,X~′〉. Since X~′∈G, S will respond with the message 〈S,Z~〉. After obtaining 〈S,Z~〉, B computes a key kAS′=H(A∥S∥X~′∥Z~∥K′∥v-A′), where K′=(Z~·(G2(pwA′))-1)x and v-A′=(G1(pwA′))-1. We let kAS′=k′ASenc∥k′ASmac.(ii)
In the (honest) run R2,B honestly performs all the operations as per protocol specification and establishes the key, kBS=kBSenc∥kBSmac.Step 2 (running 3PKD).
Once R1 & R2 are completed,B proceeds to run the protocol 3PKD by sending the server S two random challenges rA and rB (selected as specified by the protocol). S will respond to the random challenges with two messages 〈αA,μA〉 and 〈αB,μB〉. After obtaining these two messages, B recovers the keys  kAB′=Deck′ASenc(αA) and  kAB=DeckBSenc(αB).Step 3 (verifying the password guess).
B verifies the correctness of pwA′ by checking that kAB′ is equal to kAB. If they are equal, pwA′ is the correct password with an overwhelming probability. Otherwise, it means that pwA′≠pwA.


### 2.3. An Outsider Attack

We now consider the case where 2PAKE and 3KD are instantiated with the OMDHKE protocol [34] and with the 3PKD protocol [35], respectively. Although OMDHKE (see Figure 4) is largely similar to PPK, there is a marked difference between the two. OMDHKE provides server-to-client authentication while PPK focuses on implicit key authentication.Figure 4
The OMDHKE protocol [34].


#### 2.3.1. The OMDHKE Protocol

LetG be a finite cyclic group generated by an element g of prime order q. The hash functions used are G:{0,1}*→G, H:{0,1}*→{0,1}l, and F:{0,1}*→{0,1}f, where l is the length of the session key and f is the length of the authenticator AuthSA. Unlike the PPK protocol described in Figure 2, both A and S have a shared password, pwA. The protocol starts when A chooses a random x∈Zq, computes X=gx, PWA=G(pwA), and X~=X·PWA, and sends 〈A,X~〉 to S. Upon receiving the message from A, S computes PWA=G(pwA) and X=X~/PWA, chooses a random z∈Zq, and computes Z=gz, K=Xz, and AuthSA=F(A∥S∥X~∥Z∥PWA∥K). Then S sends 〈S,Z,AuthSA〉 to A and computes the session key, kAS=H(A∥S∥X~∥Z∥PWA∥K). A computes K=Zx, verifies AuthSA, and computes the session key kAS=H(A∥S∥X~∥Z∥PWA∥K) if the verification succeeds.Note that, in OMDHKE, server-to-client authentication is achieved via the authenticatorAuthSA sent by S to A.


#### 2.3.2. One Possible Attack Scenario

We now demonstrate howC, a malicious adversary who is not registered with the server, can mount a UD online dictionary attack against two registered clients, A and B.Step 4 (running OMDHKE).
C initiates two concurrent runs, R1 & R2, of the protocol OMDHKE. (i)
In the (dishonest) run R1,C impersonating A makes a guess (denoted by pwA′) on A’s password, pwA, chooses a random x∈Zq, computes PWA′=G(pwA′) and X~′=gx·PWA′, and sends the fabricated message 〈A,X~′〉 to S. C will then receive the response, 〈S,Z,AuthSA〉, from S as per protocol specification.(ii)
In the (dishonest) run R2,C proceeds as per R1 but impersonating B (instead of A) and making a guess (denoted as pwB′) on B’s password, pwB. Let AuthSB denote the authenticator received (in response) from  S.Step 5 (running 3PKD).
After R1 & R2 are completed,C runs the 3PKD protocol with S while impersonating both A and B. (This step provides no useful information to C but is required for the attack to go undetected.)Step 6 (verifying the password guess).
C can then verify the correctness of pwA′ by computing AuthSA′=F(A∥S∥X~′∥Z∥PWA′∥Zx) and then checking if AuthSA′ is equal to AuthSA. If they are equal, pwA′ is the correct password (with an overwhelming probability). Otherwise, C knows that pwA′≠pwA. Similarly, the correctness of pwB′ can be verified using the received AuthSB.


### 2.4. Discussion

The insider attack described in Section2.2 works because neither PPK nor 3PKD provides client-to-server authentication. Indeed, the same attack also works if we replace the PPK protocol with the OMDHKE protocol [34], the EKE2 protocol [28], or the SPAKE protocol [37]. In other words, the GPAKE protocol becomes vulnerable to the insider attack when both 2PAKE and 3KD are instantiated with a protocol that does not provide client-to-server authentication. The outsider attack described in Section 2.3 works under the same circumstance but additionally exploits the fact that the OMDHKE protocol provides server-to-client authentication.Informally, both attacks can be prevented if one of the two protocols, 2PAKE or 3KD, is instantiated with a protocol that provides client-to-server authentication. We observe that a typical 3-party key distribution protocol is not expected to provide client-to-server authentication, and hence, we suggest that the countermeasure targets the instantiation of 2PAKE. While some might also suggest that a round-optimal protocol (i.e., a protocol that runs in a single round) should be used in the instantiation of 2PAKE to achieve better efficiency, we caution against this as no round-optimal 2-party PAKE protocol is known to provide client-to-server authentication and achieve security against offline dictionary attacks.


## 2.1. A Review of GPAKE

The GPAKE protocol is constructed using a combination of three building blocks: (1) a 2-party PAKE protocol 2PAKE, (2) a 3-party key distribution protocol 3KD, and (3) a message authentication code- (MAC-) based Diffie-Hellman key exchange protocol MDH. LetG be a finite cyclic group generated by an element g; and let Σ= (Mac, Ver) be a MAC scheme where Mac and Ver are the MAC generation and MAC verification algorithms, respectively. The security of MDH relies on the hardness of the decisional Diffie-Hellman (DDH) problem in G and on the security of the underlying MAC scheme Σ against chosen message attacks. S represents a trusted server which registers clients and, during the registration, each client shares their individual password secretly with S. Suppose that A and B are two registered clients who wish to establish a session key and pwA and pwB are the passwords of A and B, respectively.


### 2.1.1. Description

A high-level depiction of GPAKE is given in Figure1 and its brief description follows. First, A (and B) and S establish a shared high-entropy key, kAS (and kBS, resp.), by running the 2-party PAKE protocol, 2PAKE. Then, S generates a MAC key, kAB, and distributes kAB to both A and B by running the 3-party key distribution protocol 3KD which takes kAS and kBS as input. A session key, sk=gab, will be established between A and B after running the MAC-based Diffie-Hellman key exchange protocol MDH which takes kAB as an input.Figure 1
GPAKE: Abdalla et al.’s generic 3-party PAKE protocol [8, 9].


### 2.1.2. Instantiations

Abdalla et al. [8, 9] suggested several practical and provably secure protocols that can be used in the instantiation of the 2-party protocol 2PAKE. Among them are the KOY protocol [29, 30] and its generalization [31], the PAK suite [32], and other protocols based on encrypted key exchange (EKE) of Bellovin and Merritt [33] (e.g., Bresson et al.’s OMDHKE protocol [34]). For the instantiation of 3KD, any particular choice that is secure with respect to a single session will do since the symmetric keys given as input to 3KD differ from session to session. Bellare and Rogaway’s 3PKD protocol [35], for example, was suggested as a possible choice. The MAC scheme used in MDH can be instantiated with the HMAC [36] and the CBC MAC.


## 2.1.1. Description

A high-level depiction of GPAKE is given in Figure1 and its brief description follows. First, A (and B) and S establish a shared high-entropy key, kAS (and kBS, resp.), by running the 2-party PAKE protocol, 2PAKE. Then, S generates a MAC key, kAB, and distributes kAB to both A and B by running the 3-party key distribution protocol 3KD which takes kAS and kBS as input. A session key, sk=gab, will be established between A and B after running the MAC-based Diffie-Hellman key exchange protocol MDH which takes kAB as an input.Figure 1
GPAKE: Abdalla et al.’s generic 3-party PAKE protocol [8, 9].


## 2.1.2. Instantiations

Abdalla et al. [8, 9] suggested several practical and provably secure protocols that can be used in the instantiation of the 2-party protocol 2PAKE. Among them are the KOY protocol [29, 30] and its generalization [31], the PAK suite [32], and other protocols based on encrypted key exchange (EKE) of Bellovin and Merritt [33] (e.g., Bresson et al.’s OMDHKE protocol [34]). For the instantiation of 3KD, any particular choice that is secure with respect to a single session will do since the symmetric keys given as input to 3KD differ from session to session. Bellare and Rogaway’s 3PKD protocol [35], for example, was suggested as a possible choice. The MAC scheme used in MDH can be instantiated with the HMAC [36] and the CBC MAC.


## 2.2. An Insider Attack

Let us consider, for example, the case where 2PAKE and 3KD are instantiated with the PPK protocol [32] and with the 3PKD protocol [35], respectively. In this case, a malicious client B who is registered with the server, S, can mount a UD online dictionary attack against any other client, for example, A. It is important to note that we do not require either of the protocols, PPK (see Figure 2) and 3PKD (see Figure 3), to be insecure and, in fact, we assume that both protocols are secure.Figure 2
The PPK protocol [32].Figure 3
The 3PKD protocol [35].


### 2.2.1. The PPK Protocol

LetG be a finite cyclic group of order q, and let g be a generator of G. The three hash functions used are G1:{0,1}*→G, G2:{0,1}*→G, and H:{0,1}*→{0,1}l, where l is the length of the session key. pwA denotes A’s password known only to A and (v-A,wA)=((G1(pwA))-1,G2(pwA)) denotes the password verifiers held by S. The functionacceptable  (*) returns true, if and only if *∈G (or, *∈G^ when G is defined as a (proper) subgroup of a group G^). The session key kAS is computed as kAS=H(A∥S∥X~∥Z~∥K∥v-A). We observe that two messages 〈A,X~〉 and 〈S,Z~〉 are independent and thus the protocol can be easily modified to run in a single round.


### 2.2.2. The 3PKD Protocol

The cryptographic tools used in 3PKD include (1) a symmetric encryption scheme consisting of a pair of encryption/decryption algorithms (Enc, Dec) and (2) a MAC scheme consisting of a pair of MAC generation/verification algorithms (Mac, Ver). The protocol runs between a trusted server, S, and two clients, A and B. A (and B) and S are assumed to have preestablished a 2κ-bit secret kAS=kASenc∥kASmac (resp., kBS=kBSenc∥kBSmac). The protocol, depicted in Figure 3, begins by having A choosing a random κ-bit challenge rA and sending it to client B. B also chooses a random κ-bit challenge rB and sends 〈rA,rB〉 to S. Upon receiving 〈rA,rB〉, S generates a session key kAB which he will distribute. S then encrypts kAB under A’s encryption key kASenc (resp., B’s encryption key kBSenc) to get ciphertext αA (resp., αB). Then, S computes μA (resp., μB), the MAC under key kASmac (resp., kBSmac) of the string A∥B∥rA∥αA (resp. A∥B∥rB∥αB). Then, S sends 〈αA,μA〉 and 〈αB,μB〉 to A and B, respectively. A and B accept the session key kAB if and only if their received MAC is valid.In order for PPK and 3PKD to be used together, the session keys generated by PPK need to be at least2κ-bit long.


### 2.2.3. One Possible Attack Scenario

The malicious client,B, can mount the following UD online dictionary attack against another client, A.Step 1 (running PPK).
Bbegins by initiating two concurrent runs, R1 & R2, of the PPK protocol. (i)
In the (dishonest) run R1,B impersonating A makes a guess (denoted by pwA′) on A’s actual password, pwA, selects a random x∈Zq, computes X~′=gx·G1(pwA′), and sends the server S a fabricated message 〈A,X~′〉. Since X~′∈G, S will respond with the message 〈S,Z~〉. After obtaining 〈S,Z~〉, B computes a key kAS′=H(A∥S∥X~′∥Z~∥K′∥v-A′), where K′=(Z~·(G2(pwA′))-1)x and v-A′=(G1(pwA′))-1. We let kAS′=k′ASenc∥k′ASmac.(ii)
In the (honest) run R2,B honestly performs all the operations as per protocol specification and establishes the key, kBS=kBSenc∥kBSmac.Step 2 (running 3PKD).
Once R1 & R2 are completed,B proceeds to run the protocol 3PKD by sending the server S two random challenges rA and rB (selected as specified by the protocol). S will respond to the random challenges with two messages 〈αA,μA〉 and 〈αB,μB〉. After obtaining these two messages, B recovers the keys  kAB′=Deck′ASenc(αA) and  kAB=DeckBSenc(αB).Step 3 (verifying the password guess).
B verifies the correctness of pwA′ by checking that kAB′ is equal to kAB. If they are equal, pwA′ is the correct password with an overwhelming probability. Otherwise, it means that pwA′≠pwA.


## 2.2.1. The PPK Protocol

LetG be a finite cyclic group of order q, and let g be a generator of G. The three hash functions used are G1:{0,1}*→G, G2:{0,1}*→G, and H:{0,1}*→{0,1}l, where l is the length of the session key. pwA denotes A’s password known only to A and (v-A,wA)=((G1(pwA))-1,G2(pwA)) denotes the password verifiers held by S. The functionacceptable  (*) returns true, if and only if *∈G (or, *∈G^ when G is defined as a (proper) subgroup of a group G^). The session key kAS is computed as kAS=H(A∥S∥X~∥Z~∥K∥v-A). We observe that two messages 〈A,X~〉 and 〈S,Z~〉 are independent and thus the protocol can be easily modified to run in a single round.


## 2.2.2. The 3PKD Protocol

The cryptographic tools used in 3PKD include (1) a symmetric encryption scheme consisting of a pair of encryption/decryption algorithms (Enc, Dec) and (2) a MAC scheme consisting of a pair of MAC generation/verification algorithms (Mac, Ver). The protocol runs between a trusted server, S, and two clients, A and B. A (and B) and S are assumed to have preestablished a 2κ-bit secret kAS=kASenc∥kASmac (resp., kBS=kBSenc∥kBSmac). The protocol, depicted in Figure 3, begins by having A choosing a random κ-bit challenge rA and sending it to client B. B also chooses a random κ-bit challenge rB and sends 〈rA,rB〉 to S. Upon receiving 〈rA,rB〉, S generates a session key kAB which he will distribute. S then encrypts kAB under A’s encryption key kASenc (resp., B’s encryption key kBSenc) to get ciphertext αA (resp., αB). Then, S computes μA (resp., μB), the MAC under key kASmac (resp., kBSmac) of the string A∥B∥rA∥αA (resp. A∥B∥rB∥αB). Then, S sends 〈αA,μA〉 and 〈αB,μB〉 to A and B, respectively. A and B accept the session key kAB if and only if their received MAC is valid.In order for PPK and 3PKD to be used together, the session keys generated by PPK need to be at least2κ-bit long.


## 2.2.3. One Possible Attack Scenario

The malicious client,B, can mount the following UD online dictionary attack against another client, A.Step 1 (running PPK).
Bbegins by initiating two concurrent runs, R1 & R2, of the PPK protocol. (i)
In the (dishonest) run R1,B impersonating A makes a guess (denoted by pwA′) on A’s actual password, pwA, selects a random x∈Zq, computes X~′=gx·G1(pwA′), and sends the server S a fabricated message 〈A,X~′〉. Since X~′∈G, S will respond with the message 〈S,Z~〉. After obtaining 〈S,Z~〉, B computes a key kAS′=H(A∥S∥X~′∥Z~∥K′∥v-A′), where K′=(Z~·(G2(pwA′))-1)x and v-A′=(G1(pwA′))-1. We let kAS′=k′ASenc∥k′ASmac.(ii)
In the (honest) run R2,B honestly performs all the operations as per protocol specification and establishes the key, kBS=kBSenc∥kBSmac.Step 2 (running 3PKD).
Once R1 & R2 are completed,B proceeds to run the protocol 3PKD by sending the server S two random challenges rA and rB (selected as specified by the protocol). S will respond to the random challenges with two messages 〈αA,μA〉 and 〈αB,μB〉. After obtaining these two messages, B recovers the keys  kAB′=Deck′ASenc(αA) and  kAB=DeckBSenc(αB).Step 3 (verifying the password guess).
B verifies the correctness of pwA′ by checking that kAB′ is equal to kAB. If they are equal, pwA′ is the correct password with an overwhelming probability. Otherwise, it means that pwA′≠pwA.


## 2.3. An Outsider Attack

We now consider the case where 2PAKE and 3KD are instantiated with the OMDHKE protocol [34] and with the 3PKD protocol [35], respectively. Although OMDHKE (see Figure 4) is largely similar to PPK, there is a marked difference between the two. OMDHKE provides server-to-client authentication while PPK focuses on implicit key authentication.Figure 4
The OMDHKE protocol [34].


### 2.3.1. The OMDHKE Protocol

LetG be a finite cyclic group generated by an element g of prime order q. The hash functions used are G:{0,1}*→G, H:{0,1}*→{0,1}l, and F:{0,1}*→{0,1}f, where l is the length of the session key and f is the length of the authenticator AuthSA. Unlike the PPK protocol described in Figure 2, both A and S have a shared password, pwA. The protocol starts when A chooses a random x∈Zq, computes X=gx, PWA=G(pwA), and X~=X·PWA, and sends 〈A,X~〉 to S. Upon receiving the message from A, S computes PWA=G(pwA) and X=X~/PWA, chooses a random z∈Zq, and computes Z=gz, K=Xz, and AuthSA=F(A∥S∥X~∥Z∥PWA∥K). Then S sends 〈S,Z,AuthSA〉 to A and computes the session key, kAS=H(A∥S∥X~∥Z∥PWA∥K). A computes K=Zx, verifies AuthSA, and computes the session key kAS=H(A∥S∥X~∥Z∥PWA∥K) if the verification succeeds.Note that, in OMDHKE, server-to-client authentication is achieved via the authenticatorAuthSA sent by S to A.


### 2.3.2. One Possible Attack Scenario

We now demonstrate howC, a malicious adversary who is not registered with the server, can mount a UD online dictionary attack against two registered clients, A and B.Step 4 (running OMDHKE).
C initiates two concurrent runs, R1 & R2, of the protocol OMDHKE. (i)
In the (dishonest) run R1,C impersonating A makes a guess (denoted by pwA′) on A’s password, pwA, chooses a random x∈Zq, computes PWA′=G(pwA′) and X~′=gx·PWA′, and sends the fabricated message 〈A,X~′〉 to S. C will then receive the response, 〈S,Z,AuthSA〉, from S as per protocol specification.(ii)
In the (dishonest) run R2,C proceeds as per R1 but impersonating B (instead of A) and making a guess (denoted as pwB′) on B’s password, pwB. Let AuthSB denote the authenticator received (in response) from  S.Step 5 (running 3PKD).
After R1 & R2 are completed,C runs the 3PKD protocol with S while impersonating both A and B. (This step provides no useful information to C but is required for the attack to go undetected.)Step 6 (verifying the password guess).
C can then verify the correctness of pwA′ by computing AuthSA′=F(A∥S∥X~′∥Z∥PWA′∥Zx) and then checking if AuthSA′ is equal to AuthSA. If they are equal, pwA′ is the correct password (with an overwhelming probability). Otherwise, C knows that pwA′≠pwA. Similarly, the correctness of pwB′ can be verified using the received AuthSB.


## 2.3.1. The OMDHKE Protocol

LetG be a finite cyclic group generated by an element g of prime order q. The hash functions used are G:{0,1}*→G, H:{0,1}*→{0,1}l, and F:{0,1}*→{0,1}f, where l is the length of the session key and f is the length of the authenticator AuthSA. Unlike the PPK protocol described in Figure 2, both A and S have a shared password, pwA. The protocol starts when A chooses a random x∈Zq, computes X=gx, PWA=G(pwA), and X~=X·PWA, and sends 〈A,X~〉 to S. Upon receiving the message from A, S computes PWA=G(pwA) and X=X~/PWA, chooses a random z∈Zq, and computes Z=gz, K=Xz, and AuthSA=F(A∥S∥X~∥Z∥PWA∥K). Then S sends 〈S,Z,AuthSA〉 to A and computes the session key, kAS=H(A∥S∥X~∥Z∥PWA∥K). A computes K=Zx, verifies AuthSA, and computes the session key kAS=H(A∥S∥X~∥Z∥PWA∥K) if the verification succeeds.Note that, in OMDHKE, server-to-client authentication is achieved via the authenticatorAuthSA sent by S to A.


## 2.3.2. One Possible Attack Scenario

We now demonstrate howC, a malicious adversary who is not registered with the server, can mount a UD online dictionary attack against two registered clients, A and B.Step 4 (running OMDHKE).
C initiates two concurrent runs, R1 & R2, of the protocol OMDHKE. (i)
In the (dishonest) run R1,C impersonating A makes a guess (denoted by pwA′) on A’s password, pwA, chooses a random x∈Zq, computes PWA′=G(pwA′) and X~′=gx·PWA′, and sends the fabricated message 〈A,X~′〉 to S. C will then receive the response, 〈S,Z,AuthSA〉, from S as per protocol specification.(ii)
In the (dishonest) run R2,C proceeds as per R1 but impersonating B (instead of A) and making a guess (denoted as pwB′) on B’s password, pwB. Let AuthSB denote the authenticator received (in response) from  S.Step 5 (running 3PKD).
After R1 & R2 are completed,C runs the 3PKD protocol with S while impersonating both A and B. (This step provides no useful information to C but is required for the attack to go undetected.)Step 6 (verifying the password guess).
C can then verify the correctness of pwA′ by computing AuthSA′=F(A∥S∥X~′∥Z∥PWA′∥Zx) and then checking if AuthSA′ is equal to AuthSA. If they are equal, pwA′ is the correct password (with an overwhelming probability). Otherwise, C knows that pwA′≠pwA. Similarly, the correctness of pwB′ can be verified using the received AuthSB.


## 2.4. Discussion

The insider attack described in Section2.2 works because neither PPK nor 3PKD provides client-to-server authentication. Indeed, the same attack also works if we replace the PPK protocol with the OMDHKE protocol [34], the EKE2 protocol [28], or the SPAKE protocol [37]. In other words, the GPAKE protocol becomes vulnerable to the insider attack when both 2PAKE and 3KD are instantiated with a protocol that does not provide client-to-server authentication. The outsider attack described in Section 2.3 works under the same circumstance but additionally exploits the fact that the OMDHKE protocol provides server-to-client authentication.Informally, both attacks can be prevented if one of the two protocols, 2PAKE or 3KD, is instantiated with a protocol that provides client-to-server authentication. We observe that a typical 3-party key distribution protocol is not expected to provide client-to-server authentication, and hence, we suggest that the countermeasure targets the instantiation of 2PAKE. While some might also suggest that a round-optimal protocol (i.e., a protocol that runs in a single round) should be used in the instantiation of 2PAKE to achieve better efficiency, we caution against this as no round-optimal 2-party PAKE protocol is known to provide client-to-server authentication and achieve security against offline dictionary attacks.


## 3. Modelling Dictionary Attacks in the Password-Only 3-Party Setting

TheROR model used for security analysis of GPAKE [8, 9] does not allow the adversary to access the Corrupt oracle and thus cannot capture any kind of insider attacks, in particular, (UD) online and offline dictionary attacks by a malicious insider. The security definition associated with the ROR model intends to capture indistinguishability of session keys and does not consider mounting an online dictionary attack against a protocol to be a violation of the security of the protocol (see Section 3.3). Consequently, none of the online dictionary attacks presented in Section 2 can be captured in the model.We begin this section by presenting a communication model adapted from the Bellare-Pointcheval-Rogaway 2000 model [28] to support key exchange in the password-only 3-party setting. Our communication model allows the adversary to ask Corrupt queries and thereby captures insider attacks (as well as forward secrecy and unknown key share attacks). We then define a typical indistinguishability-based security of session keys, which we call theSK security. As we demonstrate in Section 3.3, the SK security implies security against offline dictionary attacks but does not imply security against UD online dictionary attacks. We then introduce a separate security definition to capture UD online dictionary attacks. Unlike the approach of [19, 20] where a separate security definition is introduced to capture both online and offline dictionary attacks, we only need to prove the protocol secure against UD online dictionary attacks once we have proved that it is SK-secure.


### 3.1. The Communication Model

#### 3.1.1. Participants and Long-Term Keys

We denoteS by a trusted authentication server and C by the set of all clients registered with S. During registration, each client C∈C selects a password, pwC, from a dictionary, D, and shares pwC with S via a secure channel. pwC is used as the long-term secret key shared between C and S. Any two clients, C,C′∈C, may run a 3-party PAKE protocol P with S at any point in time to establish a session key. Let U=C∪{S}. A user, U∈U, may participate in multiple protocol sessions running, either serially or concurrently, with the same or different participants. Thus, at any given time, there could be multiple instances of a single user. ΠUi denotes instance i of user U. We say that a client instance, ΠCi,accepts when it computes its session key, skCi, in an execution of the protocol.


#### 3.1.2. Partnering

We say, informally, that two instances arepartners if they participate in a protocol execution and establish a (shared) session key. Formally, partnering between instances is defined in terms of the notions of session and partner identifiers (See [38] on the role and the possible construct of session and partner identifiers as a form of partnering mechanism that enables the right session key to be identified in concurrent protocol executions.) Session identifier (sid) is a unique identifier of a protocol session and is usually defined as a function of the messages transmitted in the session (although this may not be possible in a multiparty protocol where not all participants have the same view).  sidUi denotes the sid of instance ΠUi. A partner identifier (pid) is a sequence of identities of participants of a specific protocol session. Instances are given as input a pid before they can run the protocol.  pidUi denotes the pid given to instance ΠUi.  Note that  pidCi=〈C,C′,S〉, where C′ is another client with whom ΠCi believes it runs the protocol. We say that two instances, ΠCi and ΠC′j, are partners if the following holds: (1) both ΠCi and ΠC′j have accepted, (2)  sidCi=sidC′j, and (3)  pidCi=pidC′j.


#### 3.1.3. Adversary Capabilities

The probabilistic polynomial-time (ppt) adversary A is in complete control of all communications between users, and its capabilities are modeled via a predefined set of oracle queries described below.(i)
Execute  (ΠCi,ΠC′j,ΠSk): this query models passive attacks against the protocol. It prompts an execution of the protocol between the instances ΠCi, ΠC′j and ΠSk and returns the transcript of the protocol execution to A.(ii)
Send  (ΠUi,m): this query sends message m to instance ΠUi, modelling active attacks against the protocol. Upon receiving m, the instance ΠUi proceeds according to the protocol specification. The message output by ΠUi, if any, is returned to A. A query of the form Send (ΠCi, start: 〈C,C′,S〉) prompts ΠCi to initiate the protocol with pidCi=〈C,C′,S〉.(iii)
Reveal  (ΠCi): this query captures the notion of known key security (it is often reasonable to assume that the adversary will be able to obtain session keys from any session different from the one under attack). The instance ΠCi, upon receiving the query and if it has accepted, returns the session key, skCi, back to A.(iv)
Corrupt  (U): this query returns the password pwU of U. If U=S (i.e., the server is corrupted), all clients’ passwords stored by the server are returned. This query captures not only the notion of forward secrecy but also unknown key share attacks and insider attacks.(v)
Test  (ΠCi): this query is used to define the indistinguishability-based security of the protocol. If ΠCi has accepted, then, depending on a randomly chosen bit b, A is given either the real session key skCi (when b=1) or a random key drawn from the session-key space (when b=0). Following the ROR model [8, 9], we allow A to ask as many Test queries as it wishes. All Test queries are answered using the same value of the hidden bit b. Namely, the keys output by the Test oracle are either all real or all random. But, we require that, for each different set of partners, A should access the Test oracle only once.We describe the number of queries asked by an adversary as thequery complexity of the adversary. The query complexity is represented as an ordered sequence of five nonnegative integers, Q=〈qexec, qsend, qreve, qcorr, qtest〉, where qexec, qsend, qreve, qcorr, and qtest refer to the numbers of queries that the adversary asked, respectively, to the Execute, Send, Reveal, Corrupt, and Test oracles.


### 3.2. Session Key (SK) Security

We now proceed to define the basic security, called the SK security, of a 3-party PAKE protocol. The notion offreshness is a key element in defining the SK security. Intuitively, a fresh instance is one that holds a session key which should not be known to the adversary A, and an unfresh instance is one whose session key (or some information about the key) can be known by trivial means. A formal definition of freshness follows.Definition 11.
An instanceΠCi is fresh unless one of the following occurs: (1) A queries Reveal  (ΠCi) or Reveal  (ΠC′j), where ΠC′j is the partner of ΠCi; or (2) A queries Corrupt  (U), for some  U∈pidCi, before ΠCi or its partner ΠC′j accepts.
The SK security of a 3-party PAKE protocolP is defined in the context of Box 1.
LetSucc0 be the event that A succeeds in the experiment Exp0. Let  AdvP(A) denote the advantage of A in attacking protocol P and be defined as  AdvP(A)=2·Pr⁡P,A[Succ0]-1.Box 1
ExperimentExp0:
Phase  1.  A makes any oracle queries at will as many times as it wishes, except that:
(1)A is not allowed to ask the Test(ΠCi) query if the instance ΠCi is unfresh.
(2)A is not allowed to ask the Reveal(ΠCi) query if it has already made a Test query to
ΠCi or ΠC′j, where ΠC′j is the partner of ΠCi.
Phase  2. Once A decides that Phase 1 is over, it outputs a bit b′ as a guess on the hidden bit
b chosen by the Test oracle. A is said to succeed if b=b′.Definition 12.
A 3-party PAKE protocolP isSK-secure if, for anyppt adversary A asking at most qsend   Send queries,  AdvP(A) is only negligibly larger than c·qsend/|D|, where c is a very small constant (usually around 2 or 4) when compared with |D|.To quantify the security of protocolP in terms of the amount of resources expended by adversaries, we let AdvP(t,Q) denote the maximum value of  AdvP(A) over allppt adversaries A with time complexity at most t and query complexity at most Q.


### 3.3. Password Security

#### 3.3.1. Capturing Offline Dictionary Attacks

The SK security described in Definition12 implies security against offline dictionary attacks. In other words, a 3-party PAKE protocol P is not SK-secure if it is not secure against an offline dictionary attack. To demonstrate this, suppose that the protocol P is not secure against an offline dictionary attack whereby an attacker B can derive the password of any registered client A. Then we can construct an adversary Aoff⁡ who breaks the SK security of protocol P as follows.Corruption. If B is a malicious insider, Aoff⁡ queries Corrupt  (B) to obtain the password pwB. Otherwise, Aoff⁡ skips this step.Dictionary Attack. Next, Aoff⁡ runs the protocol P exactly in the way that B conducts its offline dictionary attack against client A. Note that Aoff⁡ can perfectly simulate B’s attack by using the disclosed password pwB and by asking oracle queries appropriately. At the end of this step, Aoff⁡ will obtain the password pwA of client A as a result of the attack.Impersonation. Now, Aoff⁡ initiates a new protocol session by querying Send  (ΠCi, start: 〈A,C,S〉), where ΠCi is an unused instance of an uncorrupted client C. Aoff⁡ runs this session as per the protocol specification, but simulating by itself all the actions of A (by using pwA). At the end of the session, the instance ΠCi will accept with its session key skCi.Test. Clearly the instance ΠCi is fresh, since (1) no Reveal query has been made on ΠCi or its partner (which does not exist in this case) and (2) no Corrupt query has been made against any of A, C, and S. Thus, Aoff⁡ may ask the Test  (ΠCi) query. Since Aoff⁡ can compute the same session key as skCi, the probability that Aoff⁡ correctly guesses the bit b chosen by the Test   oracle is 1 and so is the advantage of Aoff⁡ in attacking the protocol. Then, by Definition 12, the protocol P is not SK-secure since the number of Send queries asked by Aoff⁡ is much smaller (i.e., nonnegligibly smaller) than |D|/c.


#### 3.3.2. Capturing Undetectable Online Dictionary Attacks

Unfortunately, the SK security does not imply security against UD online dictionary attacks. In other words, a 3-party PAKE protocol that is not secure against a UD online dictionary attack may be rendered SK-secure. Let us assume a 3-party PAKE protocolP that is susceptible to a UD online dictionary attack (e.g., the GPAKE protocol in Section 2). Then, we can construct an adversary Aon⁡ who attacks protocol P with advantage 1. The construction of Aon⁡ is the same as that of Aoff⁡, except that to correctly determine the password pwA, Aon⁡ may have to ask Send queries as many times as d·|D| for some integer d≥1. Note that verifying the correctness of a password guess may require more than one Send query to be asked. Even if  AdvP(Aon⁡)=1, the protocol P is still rendered SK-secure by Definition 12, as the following holds for some c≥1:
(1)AdvP(Aon⁡)≤cd|D||D|.
This result is not surprising since we call a protocol SK-secure if mounting an online dictionary attack by asking Send queries is the best an adversary can do. However, we want to be able to distinguish UD online dictionary attacks from detectable online dictionary attacks and ensure that the best an adversary can do is to mount a detectable online dictionary attack. The following new definitions together provide a simple and intuitive way of capturing security against UD online dictionary attacks.Definition 13 (an online dictionary attack).
TheSend  (ΠSk,m) query models anonline dictionary attack if both the following are true at the time of the termination of instance ΠSk: (1) m was not output by a previous Send query asked to an instance of C by which ΠSk believes m was sent and (2) the adversary A queried neither Corrupt  (S) nor Corrupt  (C).In Definition13, the first condition implies that a straightforward delivery of a message between instances is not considered as an online dictionary attack while the second condition implies that when C′ is the (assumed) peer of client C, the adversary A can corrupt the peer client C′ to mount an (insider) online dictionary attack. Note that our definition of an online dictionary attack does not impose any restriction on asking  Reveal queries.LetUndet be the event that, in experiment Exp0, a server instance terminates normally when an online dictionary attack was mounted against the instance. We say that the adversary A succeeds in mounting an UD online dictionary attack if the event Undet occurs. Formally, we define protocol’s security against UD online dictionary attacks as follows:Definition 14.
A 3-party PAKE protocolP is secure against a UD online dictionary attack if, for anyppt adversary A asking at most qsend  Send queries,  Pr⁡P,A[Undet] is only negligibly larger than c·qsend/|D|, where c is as defined in Definition 12.


## 3.1. The Communication Model

### 3.1.1. Participants and Long-Term Keys

We denoteS by a trusted authentication server and C by the set of all clients registered with S. During registration, each client C∈C selects a password, pwC, from a dictionary, D, and shares pwC with S via a secure channel. pwC is used as the long-term secret key shared between C and S. Any two clients, C,C′∈C, may run a 3-party PAKE protocol P with S at any point in time to establish a session key. Let U=C∪{S}. A user, U∈U, may participate in multiple protocol sessions running, either serially or concurrently, with the same or different participants. Thus, at any given time, there could be multiple instances of a single user. ΠUi denotes instance i of user U. We say that a client instance, ΠCi,accepts when it computes its session key, skCi, in an execution of the protocol.


### 3.1.2. Partnering

We say, informally, that two instances arepartners if they participate in a protocol execution and establish a (shared) session key. Formally, partnering between instances is defined in terms of the notions of session and partner identifiers (See [38] on the role and the possible construct of session and partner identifiers as a form of partnering mechanism that enables the right session key to be identified in concurrent protocol executions.) Session identifier (sid) is a unique identifier of a protocol session and is usually defined as a function of the messages transmitted in the session (although this may not be possible in a multiparty protocol where not all participants have the same view).  sidUi denotes the sid of instance ΠUi. A partner identifier (pid) is a sequence of identities of participants of a specific protocol session. Instances are given as input a pid before they can run the protocol.  pidUi denotes the pid given to instance ΠUi.  Note that  pidCi=〈C,C′,S〉, where C′ is another client with whom ΠCi believes it runs the protocol. We say that two instances, ΠCi and ΠC′j, are partners if the following holds: (1) both ΠCi and ΠC′j have accepted, (2)  sidCi=sidC′j, and (3)  pidCi=pidC′j.


### 3.1.3. Adversary Capabilities

The probabilistic polynomial-time (ppt) adversary A is in complete control of all communications between users, and its capabilities are modeled via a predefined set of oracle queries described below.(i)
Execute  (ΠCi,ΠC′j,ΠSk): this query models passive attacks against the protocol. It prompts an execution of the protocol between the instances ΠCi, ΠC′j and ΠSk and returns the transcript of the protocol execution to A.(ii)
Send  (ΠUi,m): this query sends message m to instance ΠUi, modelling active attacks against the protocol. Upon receiving m, the instance ΠUi proceeds according to the protocol specification. The message output by ΠUi, if any, is returned to A. A query of the form Send (ΠCi, start: 〈C,C′,S〉) prompts ΠCi to initiate the protocol with pidCi=〈C,C′,S〉.(iii)
Reveal  (ΠCi): this query captures the notion of known key security (it is often reasonable to assume that the adversary will be able to obtain session keys from any session different from the one under attack). The instance ΠCi, upon receiving the query and if it has accepted, returns the session key, skCi, back to A.(iv)
Corrupt  (U): this query returns the password pwU of U. If U=S (i.e., the server is corrupted), all clients’ passwords stored by the server are returned. This query captures not only the notion of forward secrecy but also unknown key share attacks and insider attacks.(v)
Test  (ΠCi): this query is used to define the indistinguishability-based security of the protocol. If ΠCi has accepted, then, depending on a randomly chosen bit b, A is given either the real session key skCi (when b=1) or a random key drawn from the session-key space (when b=0). Following the ROR model [8, 9], we allow A to ask as many Test queries as it wishes. All Test queries are answered using the same value of the hidden bit b. Namely, the keys output by the Test oracle are either all real or all random. But, we require that, for each different set of partners, A should access the Test oracle only once.We describe the number of queries asked by an adversary as thequery complexity of the adversary. The query complexity is represented as an ordered sequence of five nonnegative integers, Q=〈qexec, qsend, qreve, qcorr, qtest〉, where qexec, qsend, qreve, qcorr, and qtest refer to the numbers of queries that the adversary asked, respectively, to the Execute, Send, Reveal, Corrupt, and Test oracles.


## 3.1.1. Participants and Long-Term Keys

We denoteS by a trusted authentication server and C by the set of all clients registered with S. During registration, each client C∈C selects a password, pwC, from a dictionary, D, and shares pwC with S via a secure channel. pwC is used as the long-term secret key shared between C and S. Any two clients, C,C′∈C, may run a 3-party PAKE protocol P with S at any point in time to establish a session key. Let U=C∪{S}. A user, U∈U, may participate in multiple protocol sessions running, either serially or concurrently, with the same or different participants. Thus, at any given time, there could be multiple instances of a single user. ΠUi denotes instance i of user U. We say that a client instance, ΠCi,accepts when it computes its session key, skCi, in an execution of the protocol.


## 3.1.2. Partnering

We say, informally, that two instances arepartners if they participate in a protocol execution and establish a (shared) session key. Formally, partnering between instances is defined in terms of the notions of session and partner identifiers (See [38] on the role and the possible construct of session and partner identifiers as a form of partnering mechanism that enables the right session key to be identified in concurrent protocol executions.) Session identifier (sid) is a unique identifier of a protocol session and is usually defined as a function of the messages transmitted in the session (although this may not be possible in a multiparty protocol where not all participants have the same view).  sidUi denotes the sid of instance ΠUi. A partner identifier (pid) is a sequence of identities of participants of a specific protocol session. Instances are given as input a pid before they can run the protocol.  pidUi denotes the pid given to instance ΠUi.  Note that  pidCi=〈C,C′,S〉, where C′ is another client with whom ΠCi believes it runs the protocol. We say that two instances, ΠCi and ΠC′j, are partners if the following holds: (1) both ΠCi and ΠC′j have accepted, (2)  sidCi=sidC′j, and (3)  pidCi=pidC′j.


## 3.1.3. Adversary Capabilities

The probabilistic polynomial-time (ppt) adversary A is in complete control of all communications between users, and its capabilities are modeled via a predefined set of oracle queries described below.(i)
Execute  (ΠCi,ΠC′j,ΠSk): this query models passive attacks against the protocol. It prompts an execution of the protocol between the instances ΠCi, ΠC′j and ΠSk and returns the transcript of the protocol execution to A.(ii)
Send  (ΠUi,m): this query sends message m to instance ΠUi, modelling active attacks against the protocol. Upon receiving m, the instance ΠUi proceeds according to the protocol specification. The message output by ΠUi, if any, is returned to A. A query of the form Send (ΠCi, start: 〈C,C′,S〉) prompts ΠCi to initiate the protocol with pidCi=〈C,C′,S〉.(iii)
Reveal  (ΠCi): this query captures the notion of known key security (it is often reasonable to assume that the adversary will be able to obtain session keys from any session different from the one under attack). The instance ΠCi, upon receiving the query and if it has accepted, returns the session key, skCi, back to A.(iv)
Corrupt  (U): this query returns the password pwU of U. If U=S (i.e., the server is corrupted), all clients’ passwords stored by the server are returned. This query captures not only the notion of forward secrecy but also unknown key share attacks and insider attacks.(v)
Test  (ΠCi): this query is used to define the indistinguishability-based security of the protocol. If ΠCi has accepted, then, depending on a randomly chosen bit b, A is given either the real session key skCi (when b=1) or a random key drawn from the session-key space (when b=0). Following the ROR model [8, 9], we allow A to ask as many Test queries as it wishes. All Test queries are answered using the same value of the hidden bit b. Namely, the keys output by the Test oracle are either all real or all random. But, we require that, for each different set of partners, A should access the Test oracle only once.We describe the number of queries asked by an adversary as thequery complexity of the adversary. The query complexity is represented as an ordered sequence of five nonnegative integers, Q=〈qexec, qsend, qreve, qcorr, qtest〉, where qexec, qsend, qreve, qcorr, and qtest refer to the numbers of queries that the adversary asked, respectively, to the Execute, Send, Reveal, Corrupt, and Test oracles.


## 3.2. Session Key (SK) Security

We now proceed to define the basic security, called the SK security, of a 3-party PAKE protocol. The notion offreshness is a key element in defining the SK security. Intuitively, a fresh instance is one that holds a session key which should not be known to the adversary A, and an unfresh instance is one whose session key (or some information about the key) can be known by trivial means. A formal definition of freshness follows.Definition 11.
An instanceΠCi is fresh unless one of the following occurs: (1) A queries Reveal  (ΠCi) or Reveal  (ΠC′j), where ΠC′j is the partner of ΠCi; or (2) A queries Corrupt  (U), for some  U∈pidCi, before ΠCi or its partner ΠC′j accepts.
The SK security of a 3-party PAKE protocolP is defined in the context of Box 1.
LetSucc0 be the event that A succeeds in the experiment Exp0. Let  AdvP(A) denote the advantage of A in attacking protocol P and be defined as  AdvP(A)=2·Pr⁡P,A[Succ0]-1.Box 1
ExperimentExp0:
Phase  1.  A makes any oracle queries at will as many times as it wishes, except that:
(1)A is not allowed to ask the Test(ΠCi) query if the instance ΠCi is unfresh.
(2)A is not allowed to ask the Reveal(ΠCi) query if it has already made a Test query to
ΠCi or ΠC′j, where ΠC′j is the partner of ΠCi.
Phase  2. Once A decides that Phase 1 is over, it outputs a bit b′ as a guess on the hidden bit
b chosen by the Test oracle. A is said to succeed if b=b′.Definition 12.
A 3-party PAKE protocolP isSK-secure if, for anyppt adversary A asking at most qsend   Send queries,  AdvP(A) is only negligibly larger than c·qsend/|D|, where c is a very small constant (usually around 2 or 4) when compared with |D|.To quantify the security of protocolP in terms of the amount of resources expended by adversaries, we let AdvP(t,Q) denote the maximum value of  AdvP(A) over allppt adversaries A with time complexity at most t and query complexity at most Q.


## 3.3. Password Security

### 3.3.1. Capturing Offline Dictionary Attacks

The SK security described in Definition12 implies security against offline dictionary attacks. In other words, a 3-party PAKE protocol P is not SK-secure if it is not secure against an offline dictionary attack. To demonstrate this, suppose that the protocol P is not secure against an offline dictionary attack whereby an attacker B can derive the password of any registered client A. Then we can construct an adversary Aoff⁡ who breaks the SK security of protocol P as follows.Corruption. If B is a malicious insider, Aoff⁡ queries Corrupt  (B) to obtain the password pwB. Otherwise, Aoff⁡ skips this step.Dictionary Attack. Next, Aoff⁡ runs the protocol P exactly in the way that B conducts its offline dictionary attack against client A. Note that Aoff⁡ can perfectly simulate B’s attack by using the disclosed password pwB and by asking oracle queries appropriately. At the end of this step, Aoff⁡ will obtain the password pwA of client A as a result of the attack.Impersonation. Now, Aoff⁡ initiates a new protocol session by querying Send  (ΠCi, start: 〈A,C,S〉), where ΠCi is an unused instance of an uncorrupted client C. Aoff⁡ runs this session as per the protocol specification, but simulating by itself all the actions of A (by using pwA). At the end of the session, the instance ΠCi will accept with its session key skCi.Test. Clearly the instance ΠCi is fresh, since (1) no Reveal query has been made on ΠCi or its partner (which does not exist in this case) and (2) no Corrupt query has been made against any of A, C, and S. Thus, Aoff⁡ may ask the Test  (ΠCi) query. Since Aoff⁡ can compute the same session key as skCi, the probability that Aoff⁡ correctly guesses the bit b chosen by the Test   oracle is 1 and so is the advantage of Aoff⁡ in attacking the protocol. Then, by Definition 12, the protocol P is not SK-secure since the number of Send queries asked by Aoff⁡ is much smaller (i.e., nonnegligibly smaller) than |D|/c.


### 3.3.2. Capturing Undetectable Online Dictionary Attacks

Unfortunately, the SK security does not imply security against UD online dictionary attacks. In other words, a 3-party PAKE protocol that is not secure against a UD online dictionary attack may be rendered SK-secure. Let us assume a 3-party PAKE protocolP that is susceptible to a UD online dictionary attack (e.g., the GPAKE protocol in Section 2). Then, we can construct an adversary Aon⁡ who attacks protocol P with advantage 1. The construction of Aon⁡ is the same as that of Aoff⁡, except that to correctly determine the password pwA, Aon⁡ may have to ask Send queries as many times as d·|D| for some integer d≥1. Note that verifying the correctness of a password guess may require more than one Send query to be asked. Even if  AdvP(Aon⁡)=1, the protocol P is still rendered SK-secure by Definition 12, as the following holds for some c≥1:
(1)AdvP(Aon⁡)≤cd|D||D|.
This result is not surprising since we call a protocol SK-secure if mounting an online dictionary attack by asking Send queries is the best an adversary can do. However, we want to be able to distinguish UD online dictionary attacks from detectable online dictionary attacks and ensure that the best an adversary can do is to mount a detectable online dictionary attack. The following new definitions together provide a simple and intuitive way of capturing security against UD online dictionary attacks.Definition 13 (an online dictionary attack).
TheSend  (ΠSk,m) query models anonline dictionary attack if both the following are true at the time of the termination of instance ΠSk: (1) m was not output by a previous Send query asked to an instance of C by which ΠSk believes m was sent and (2) the adversary A queried neither Corrupt  (S) nor Corrupt  (C).In Definition13, the first condition implies that a straightforward delivery of a message between instances is not considered as an online dictionary attack while the second condition implies that when C′ is the (assumed) peer of client C, the adversary A can corrupt the peer client C′ to mount an (insider) online dictionary attack. Note that our definition of an online dictionary attack does not impose any restriction on asking  Reveal queries.LetUndet be the event that, in experiment Exp0, a server instance terminates normally when an online dictionary attack was mounted against the instance. We say that the adversary A succeeds in mounting an UD online dictionary attack if the event Undet occurs. Formally, we define protocol’s security against UD online dictionary attacks as follows:Definition 14.
A 3-party PAKE protocolP is secure against a UD online dictionary attack if, for anyppt adversary A asking at most qsend  Send queries,  Pr⁡P,A[Undet] is only negligibly larger than c·qsend/|D|, where c is as defined in Definition 12.


## 3.3.1. Capturing Offline Dictionary Attacks

The SK security described in Definition12 implies security against offline dictionary attacks. In other words, a 3-party PAKE protocol P is not SK-secure if it is not secure against an offline dictionary attack. To demonstrate this, suppose that the protocol P is not secure against an offline dictionary attack whereby an attacker B can derive the password of any registered client A. Then we can construct an adversary Aoff⁡ who breaks the SK security of protocol P as follows.Corruption. If B is a malicious insider, Aoff⁡ queries Corrupt  (B) to obtain the password pwB. Otherwise, Aoff⁡ skips this step.Dictionary Attack. Next, Aoff⁡ runs the protocol P exactly in the way that B conducts its offline dictionary attack against client A. Note that Aoff⁡ can perfectly simulate B’s attack by using the disclosed password pwB and by asking oracle queries appropriately. At the end of this step, Aoff⁡ will obtain the password pwA of client A as a result of the attack.Impersonation. Now, Aoff⁡ initiates a new protocol session by querying Send  (ΠCi, start: 〈A,C,S〉), where ΠCi is an unused instance of an uncorrupted client C. Aoff⁡ runs this session as per the protocol specification, but simulating by itself all the actions of A (by using pwA). At the end of the session, the instance ΠCi will accept with its session key skCi.Test. Clearly the instance ΠCi is fresh, since (1) no Reveal query has been made on ΠCi or its partner (which does not exist in this case) and (2) no Corrupt query has been made against any of A, C, and S. Thus, Aoff⁡ may ask the Test  (ΠCi) query. Since Aoff⁡ can compute the same session key as skCi, the probability that Aoff⁡ correctly guesses the bit b chosen by the Test   oracle is 1 and so is the advantage of Aoff⁡ in attacking the protocol. Then, by Definition 12, the protocol P is not SK-secure since the number of Send queries asked by Aoff⁡ is much smaller (i.e., nonnegligibly smaller) than |D|/c.


## 3.3.2. Capturing Undetectable Online Dictionary Attacks

Unfortunately, the SK security does not imply security against UD online dictionary attacks. In other words, a 3-party PAKE protocol that is not secure against a UD online dictionary attack may be rendered SK-secure. Let us assume a 3-party PAKE protocolP that is susceptible to a UD online dictionary attack (e.g., the GPAKE protocol in Section 2). Then, we can construct an adversary Aon⁡ who attacks protocol P with advantage 1. The construction of Aon⁡ is the same as that of Aoff⁡, except that to correctly determine the password pwA, Aon⁡ may have to ask Send queries as many times as d·|D| for some integer d≥1. Note that verifying the correctness of a password guess may require more than one Send query to be asked. Even if  AdvP(Aon⁡)=1, the protocol P is still rendered SK-secure by Definition 12, as the following holds for some c≥1:
(1)AdvP(Aon⁡)≤cd|D||D|.
This result is not surprising since we call a protocol SK-secure if mounting an online dictionary attack by asking Send queries is the best an adversary can do. However, we want to be able to distinguish UD online dictionary attacks from detectable online dictionary attacks and ensure that the best an adversary can do is to mount a detectable online dictionary attack. The following new definitions together provide a simple and intuitive way of capturing security against UD online dictionary attacks.Definition 13 (an online dictionary attack).
TheSend  (ΠSk,m) query models anonline dictionary attack if both the following are true at the time of the termination of instance ΠSk: (1) m was not output by a previous Send query asked to an instance of C by which ΠSk believes m was sent and (2) the adversary A queried neither Corrupt  (S) nor Corrupt  (C).In Definition13, the first condition implies that a straightforward delivery of a message between instances is not considered as an online dictionary attack while the second condition implies that when C′ is the (assumed) peer of client C, the adversary A can corrupt the peer client C′ to mount an (insider) online dictionary attack. Note that our definition of an online dictionary attack does not impose any restriction on asking  Reveal queries.LetUndet be the event that, in experiment Exp0, a server instance terminates normally when an online dictionary attack was mounted against the instance. We say that the adversary A succeeds in mounting an UD online dictionary attack if the event Undet occurs. Formally, we define protocol’s security against UD online dictionary attacks as follows:Definition 14.
A 3-party PAKE protocolP is secure against a UD online dictionary attack if, for anyppt adversary A asking at most qsend  Send queries,  Pr⁡P,A[Undet] is only negligibly larger than c·qsend/|D|, where c is as defined in Definition 12.


## 4. A Compiler for 3-Party PAKE Protocols

We now present a protocol compiler that transforms any 2-party PAKE protocol into a 3-party PAKE protocol. If the given 2-party protocol is SK-secure, then the 3-party protocol output by the compiler is not only SK-secure but also secure against both insider and outsider UD online dictionary attacks. (We stress again that the SK security implies resistance against both insider and outsider offline dictionary attacks.) This is the case regardless of whether the underlying 2-party protocol provides client-to-server authentication or not. Our transformation does not require the use of a 3-party key distribution protocol and always takes only two additional rounds of communication. Hence, applying the compiler to a round-optimal 2-party PAKE protocol immediately yields a 3-party PAKE protocol running in three communication rounds.Our generic construction, which we call H3PAKE (“H” for “hashed”), is a variant of NGPAKE that is the generic construction of Wang and Hu [1]. The key difference between H3PAKE and NGPAKE is in the computation of the session key. NGPAKE defines the session key simply as the Diffie-Hellman key gxy, whilst H3PAKE defines the session key as  H(pid∥sid∥gxy) where H is a cryptographic hash function. The difference in how session key is computed, together with a minor modification in the specifications of the protocol messages, results in a significant improvement on the security of the constructions. More specifically, we are now able to prove that H3PAKE is secure against insider dictionary attacks, unlike NGPAKE where it is unclear whether it can be proven secure against insider dictionary attacks. Note that the security of NGPAKE was proved in the ROR model that does not allow the adversary to ask Corrupt queries; and as shown in Section 3.3, protocols proven secure in such a model cannot claim provable security against insider attacks of any kind.


### 4.1. Preliminaries

We begin with the cryptographic primitives on which the security of our construction relies.Gap Diffie-Hellman (GDH) Assumption. Consider a finite cyclic group G of prime order q where the operation is denoted multiplicatively. Since the order of G is prime, all the elements of G, except 1, are generators of G. Let g be a random generator of G. The GDH problem in G is to solve the computational Diffie-Hellman (CDH) problem in G when given an oracle O(·,·,·) that solves the decisional Diffie-Hellman (DDH) problem in G. The DDH oracle O(·,·,·), on input a triple (ga,gb,C) for a,b∈Zq, outputs 1 if and only if C=gab. We define the advantage of appt algorithm A in solving the GDH problem in G as  AdvGGDH(A)=Pr⁡[AO(·,·,·)(G,q,g,gx,gy)=gxy: x,y∈RZq]. We say that the GDH assumption holds in G if  AdvGGDH(A) is negligible for allppt algorithms A. We denote by  AdvGGDH(t) the maximum value of  AdvGGDH(A) over all algorithms A running in time at most t.Message Authentication Codes. A message authentication code (MAC) scheme Σ is a triple of efficient algorithms (Gen, Mac, Ver) where (1) the key generation algorithm Gen takes as input a security parameter 1l and outputs a key k chosen uniformly at random from {0,1}l; (2) the MAC generation algorithm Mac  takes as input a key k and a message m and outputs a MAC (also known as a tag) σ; and (3) the MAC verification algorithm Ver takes as input a key k, a message m, and a MAC σ and outputs 1 if σ is valid for m under k or outputs 0 if σ is invalid. Let AdvΣ(A) be the advantage of an adversary A in violating the strong existential unforgeability of Σ  under adaptive chosen message attacks. More precisely,  AdvΣ(A) is the probability that an adversary A, who mounts an adaptive chosen message attack against Σ with oracle access to  Mack(·) and  Verk(·), outputs a message/tag pair (m,σ) such that (1) Verk(m,σ)=1 and (2) σ was not previously output by the oracle  Mack(·) as a MAC on the message m. We say that the MAC scheme Σ is secure if  AdvΣ(A) is negligible for everyppt adversary A. We use  AdvΣ(t,qmac,qver) to denote the maximum value of  AdvΣ(A) over allppt adversaries A running in time at most t and asking at most qmac and qver queries to  Mack(·) and  Verk(·), respectively.2-Party PAKE Protocols. H3PAKE takes as input a 2-party PAKE protocol 2PAKE. We assume that the given 2-party protocol 2PAKE outputs session keys distributed in {0,1}l and is SK-secure against an adversary who is given access to all the oracles: Send, Execute, Reveal, Corrupt, and Test. Let  Adv2PAKE(A) be the advantage of an adversary A in breaking the SK security of 2PAKE. We require that, for anyppt adversary A asking at most qsend   Send queries,  Adv2PAKE(A) is only negligibly larger than qsend/|D|.  Adv2PAKE(t,Q) denotes the maximum value of  Adv2PAKE(A) over allppt adversaries A with time complexity at most t and query complexity at most Q.Additionally, H3PAKE uses a cryptographic hash functionH mapping {0,1}* to {0,1}κ, where κ is a security parameter representing the length of session keys. H is modelled as a random oracle in our proof of security for H3PAKE.


### 4.2. Description of H3PAKE

We assume that the following information has been preestablished and is known to all users in the network: (1) a cyclic groupG of prime order q and a generator g of G, (2) a MAC scheme  Σ=(Gen,Mac,Ver), (3) a 2-party PAKE protocol 2PAKE, and (4) a cryptographic hash function H. These public parameters can be determined by the server and be broadcast to all its registered clients. Let A and B be two clients who wish to establish a session key, and let S be the trusted server with which A and B have registered their passwords pwA and pwB, respectively. We denote the partner identifier pid given as input to (an instance of) A (resp., B and S) by  pidA (resp.,  pidB  and  pidS). Recall that pid is a sequence of identities of protocol participants. The order of identities that appears in pid is of critical importance for the correctness of our construction and its security proof. For simplicity, we assume that  pidA=pidB=pidS=〈A,B,S〉. Figure 5 depicts how the generic 3-party PAKE protocol, H3PAKE, is constructed from any given 2-party protocol, 2PAKE. More specifically, H3PAKE is constructed as follows.Figure 5
H3PAKE: our proposed generic 3-party PAKE protocol.P
h
a
s
e
1. A and S establish a shared high-entropy key kAS by running the 2-party protocol 2PAKE. Likewise, B and S establish a shared high-entropy key kBS.P
h
a
s
e
2. A and B establish their session key by running a MAC-based Diffie-Hellman key exchange protocol with assistance of S.Step 1. A chooses a random x∈Zq, computes X=gx and  σAS=MackAS(A∥X∥pidA), and sends 〈A,X,σAS〉 to S. Meanwhile, B chooses a random y∈Zq, computes Y=gy and σBS=MackBS(B∥Y∥pidB), and sends 〈B,Y,σBS〉 to S.Step 2. S checks that  VerkAS(A∥X∥pidS,σAS)=1 and   VerkBS(B∥Y∥pidS,σBS)=1. If either verification fails, S aborts the protocol. Otherwise, S computes  σSA=MackAS(S∥Y∥pidS) and  σSB=MackBS(S∥X∥pidS) and sends 〈S,Y,σSA〉 and 〈S,X,σSB〉 to A and B, respectively.Step 3. A verifies that  VerkAS(S∥Y∥pidA,σSA)=1. If the verification fails, A aborts the protocol. Otherwise, A sets the session identifier,  sidA=A∥X∥B∥Y, and computes the Diffie-Hellman key,  KA=Yx, and the session key,  skA=H(pidA∥sidA∥KA). Meanwhile, B checks if  VerkBS(S∥X∥pidB,σSB)=1 and aborts if the check fails. Otherwise, B sets  sidB=A∥X∥B∥Y and computes KB=Xy and  skB=H(pidB∥sidB∥KB).At the end of the protocol execution,A and B will compute the same session key sk if they both hold the same sets of pid and sid and thus compute the same Diffie-Hellman key K=gxy.We do not require 2PAKE to be instantiated with a protocol that provides either unilateral or mutual authentication, as H3PAKE already provides mutual authentication between the server and the clients (via the MAC values exchanged inPhase 2). Hence, any 2-party protocol that provides implicit key authentication, including one-round protocols, will be suitable candidates to instantiate 2PAKE.


### 4.3. Proof of SK Security

We claim that the generic construction H3PAKE described in Figure5 is SK-secure in the random oracle model under the GDH assumption in G and the security of the MAC scheme Σ.Theorem 15.
LetH be a random oracle. Then, for any adversary with time complexity at most t and query complexity at most Q=〈qexec, qsend, qreve, qcorr, qtest〉, its advantage in breaking the SK security of H3PAKE is bounded by
(2)AdvH3PAKE(t,Q)≤2·Adv2PAKE(t′,Q′)+2·qsend·AdvΣ(t′,2,2)+2·AdvGGDH(t′),
where Q′=〈2qexec, qsend, qsend, qcorr, 2qexec+qsend〉 and t′ is the maximum time required to perform the experiment Exp0 involving an adversary who attacks H3PAKE with time complexity t.Proof. Assume appt adversary A who attacks H3PAKE with time complexity t and query complexity Q=〈qexec, qsend, qreve, qcorr, qtest〉. We prove the theorem by making a series of modifications to the experiment Exp0, bounding the difference in A’s advantage between two consecutive experiments, and ending up with an experiment in which A’s advantage is negligible. By  Succi, we denote the event that A correctly guesses the hidden bit b (chosen by the Test oracle) in experiment Expi.Before presenting the first modified experiment, we define the notion of aclean instance.Definition 16.
We say an instanceΠUi is unclean if A has queried Corrupt  (U′) for some U′∈pidUi. Otherwise, we say it is clean.Experiment
E
x
p
1
.This experiment is different from Exp0 only in that we replace each different MAC key with a random key drawn uniformly from {0,1}l for all clean instances. The difference in A’s advantage between Exp0 and Exp1 is bounded by the following lemma.Lemma 17.
|
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
1
]
-
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
0
]
| ≤ Adv2PAKE(t′,Q′), where t′ and Q′ are as defined in Theorem 15.Proof.
We prove the lemma by constructing an adversaryA' attacking protocol 2PAKE from the adversary A whose advantage in attacking H3PAKE is different between Exp0 and Exp1. A' begins by choosing a bit b uniformly at random. Then, A' runs A as a subroutine while simulating the oracles as follows.
E
x
e
c
u
t
e
Queries. When A makes an Execute  (ΠAi, ΠBj, ΠSk) query, A' first checks if any of A, B, and S was previously corrupted. (i)
If so,A' answers the Execute query as in experiment Exp0.(ii)
Otherwise,A' answers the query using its own oracles. A' first asks two queries Execute  (ΠAi, ΠSk) and Execute  (ΠBj, ΠSk′). Let  T2PAKE and  T2PAKE′ be two transcripts returned in response to the Execute queries. Next, A' makes the queries Test  (ΠAi) and Test  (ΠBj) and receives in return two keys k¯AS and k¯BS (either real or random). A' then generates the rest of the protocol transcript (i.e., the messages to be sent in Phase 2), using k¯AS and k¯BS as the MAC keys. Finally, A' returns these messages together with T2PAKE and  T2PAKE′ after ordering them properly.
S
e
n
d
Queries. Whenever A makes a Send  (ΠUi, m) query, A' checks if m is a message for initiating a new session (of H3PAKE) or the Send query belongs to an execution of 2PAKE.(1)
If both conditions are untrue,A′ responds to the query as in experiment Exp0.(2)
Otherwise,A′ answers it by making the same query to its own Send oracle. If the query prompts ΠUi to accept, then A′ checks if anyone in  pidUi was previously corrupted.
(a)
If so,A′ makes a Reveal  (ΠUi) query and uses the output of this Reveal query as the MAC key of ΠUi.(b)
Otherwise,A′ makes a Test  (ΠUi) query (unless the partner of ΠUi has already been tested) and uses the output of this Test query as the MAC key of ΠUi.
R
e
v
e
a
l
Queries. These queries are handled as in experiment Exp0.
C
o
r
r
u
p
t
Queries. A′ answers these queries in the straightforward way using its own Corrupt oracle.
T
e
s
t Queries. A′ answers these queries according to the bit b that it has chosen at the beginning of the simulation. That is, A′ returns real session keys, which it has computed on its own, if b=1, and otherwise returns random keys chosen uniformly at random from {0,1}κ.
At some point in time,A will terminate and output its guess b′. When this happens, A′ outputs 1, if b=b′, and 0 otherwise.
From the simulation, it is obvious that(i)
the probability thatA′ outputs 1 when its Test   oracle returns real session keys is equal to the probability that A correctly guesses the bit b in experiment Exp0;(ii)
the probability thatA′ outputs 1 when its Test  oracle returns random keys is equal to the probability that A correctly guesses the bit b in experiment Exp1. This means that  Adv2PAKE(A′)  =  |Pr⁡H3PAKE,A[Succ1] − Pr⁡H3PAKE,A[Succ0]|.  Since A′ has at most time complexity t′ and query complexity   Q′=〈2qexec,qsend, qsend, qcorr, 2qexec+qsend〉, we obtain Lemma 17.Experiment
E
x
p
2. Let Forge be the event that the adversary A makes a Send query of the form Send  (ΠUi, V∥*∥σ) before querying Corrupt  (U) and Corrupt  (V), where σ is a valid tag on  V∥*∥pidUi and was not output by a previous oracle query as a tag on  V∥*∥pidUi. Then Exp2 is different from Exp1 only in that, if Forge occurs, the experiment is aborted and the adversary does not succeed. We claim the following lemma.Lemma 18.
|
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
2
]
-
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
1
]
| ≤ qsend·AdvΣ(t′,2,2), where t′ is as defined in Theorem 15.Proof.
Given the adversaryA attacking H3PAKE and assuming that the event Forge occurs, we construct an algorithm F that outputs, with a nonnegligible probability, a forgery against the MAC scheme Σ. The algorithm F is given oracle access to  Mack(·) and  Verk(·). The goal of F is to produce a message/tag pair (m,σ) such that (1)  Verk(m,σ)=1 and (2) σ was not previously output by the   Mack(·) oracle on input m.
Letn be the number of all different MAC keys that are established via a Send query of A. Clearly, n≤qsend. F begins by choosing a random α∈{1,…,n}. Let kα denote the αth key among all the n MAC keys, and let Sendα be a Send query that should be answered and/or verified using kα. F invokes A as a subroutine and handles the oracle calls of A as in experiment Exp1 except that it answers all  Sendα queries by accessing its MAC generation and verification oracles. As a result, theαth MAC key kα is never used during the simulation. If Forge occurs against an instance that holds kα, F halts and outputs the message/tag pair generated by A as its forgery. Otherwise, F halts and outputs a failure indication.
If the guessα is correct, then the simulation is perfect and F achieves its goal. Namely,  AdvΣ(F)=Pr⁡[Forge]/n. Since n≤qsend, we get  Pr⁡[Forge]≤qsend·AdvΣ(F). Then, Lemma 18 follows by noticing that F has at most time complexity t′ and makes at most two queries to  Mack(·) and  Verk(·).Experiment
E
x
p
3. This experiment is different from experiment Exp2 only in that the Execute and Send oracles are simulated as in “the Exp3 modification” described in Box 2.Box 2
TheExp3 Modification
WhenA asks an Execute or Send query, the simulator answers it exactly as in experiment Exp2,
except that it modifies the way of generating the public Diffie-Hellman values (denoted asX and
Y in the protocol) as follows:
(i) The simulator chooses two randomv1,v2∈Zq and computes V1=gv1 and V2=gv2.
(ii) For each instanceΠCi, the simulator chooses a random r∈Zq, computes
R={V1rifCappears first inpidCiV2rifCappears second inpidCi,
and usesR as the public Diffie-Hellman value (i.e., as X or Y) of ΠCi.Since the view ofA is identical between Exp2 and Exp3, following Lemma 19 is clear.Lemma 19.
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
3
]
=
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
2
].In experimentExp3, the advantage of A in attacking H3PAKE is bounded by the following lemma.Lemma 20.
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
3
]
≤
(
1
/
2
)
+
A
d
v
G
G
D
H
(
t
′
) where t′ is as defined in Theorem 15.Proof.
The proof is via a reduction from the GDH problem which is believed to be hard. Assume that the advantage ofA in attacking H3PAKE is nonnegligible. Then we can construct an algorithm AGDH that has a nonnegligible advantage in solving the GDH problem in G. The goal of AGDH is to compute and output the value W3=gw1w2∈G when given a CDH-problem instance (W1=gw1,W2=gw2)∈G as well as an oracle O(·,·,·) that solves the DDH problem in G. AGDH runs A as a subroutine while simulating all the oracles on its own.
WhenA asks an Execute and Send query, AGDH answers it as specified in the Exp3 modification but using W1 and W2 instead of V1 and V2. In this way, AGDH can embed the CDH-problem instance (W1,W2) into all protocol sessions. Accordingly, AGDH can compute no session keys but can still correctly answer Reveal queries by storing all the keying materials associated with each instance. For each instance ΠCi whose only remaining work is to compute its session key, AGDH checks if the instance ΠCi is clean or unclean. If it is clean, AGDH stores a tuple  (pidCi,sidCi,R,r,R′,r′) into a list, which we denote as CDHList, where R=W1r and R′=W2r′. Here, the exponent r (resp., r′) is the one chosen for the instance whose user identity comes first (resp., second) in  pidCi. If it is unclean, AGDH stores a tuple  (pidCi,sidCi,R,r,R′,⊥) if C comes first in  pidCi or a tuple  (pidCi,sidCi,R,⊥,R′,r′) if C comes second in  pidCi. Here, ⊥ indicates that the exponent of the received public Diffie-Hellman value may have been chosen by A.
While imbedding the CDH-problem instance as above,AGDH has to provide A with the same view as in experiment Exp3. To this end, let kds be akey derivation string from which a session key is computed by applying the random oracle H. Let kdsCi denote the kds of instance ΠCi. Then,  kdsCi=pidCi∥sidCi∥KCi. As is clear from the above simulation, AGDH cannot compute any kds on its own. But, given a string m, AGDH can determine whether m is the kds of some instance ΠCi or not by repeatedly performing the deciding operation for the tuples in CDHList as in Box 3.
The simulation of other oracles is provided as follows.
H Queries. AGDH uses a list, HList, to maintain input-output pairs of H. For each H query on a string m, AGDH first checks if an entry of the form (m,h) is in HList. If it is, AGDH returns h to A. Otherwise, AGDH checks if m is the kds of some instance ΠCi by repeatedly performing the deciding operation above until a match is found. (i)
If a match is found and the corresponding tuple is of the form(pidCi,  sidCi,  R, r, R′, r′), AGDH computes W3=(mG)1/rr′ and terminates outputting W3. In this case, AGDH succeeds in solving the GDH problem.(ii)
If a match is found and the corresponding tuple is of the form(pidCi,  sidCi,   R, r, R′, ⊥) or  (pidCi,   sidCi,   R, ⊥, R′, r′), AGDH checks if a tuple of the form  (pidCi,  sidCi,  R, R′, sk) is in the RList which is maintained by AGDH to store revealed session keys. If it is, AGDH returns sk to A and adds (m,sk) to HList. Otherwise, AGDH returns a random κ-bit string str to A and adds (m,str) to HList.(iii)
Otherwise,AGDH returns a random κ-bit string str to A and adds (m,str) to HList.RevealQueries. When A asks a Reveal  (ΠCi) query, AGDH finds a tuple of the form  (pidCi,   sidCi,R,*,R′, *) in CDHList and checks if a tuple of the form  (pidCi,  sidCi, R, R′, sk) is in the RList. If it is, AGDH returns sk to A. Otherwise, AGDH checks if HList contains an entry (m,h) such that m=kdsCi. Given the tuple  (pidCi,  sidCi,R,*,R′,*), this check can be done by performing the deciding operation for all entries in HList. If such entry (m,h) exists in HList, AGDH returns h in response to the query and adds the tuple (pidCi,  sidCi,  R, R′, h) into RList. Otherwise, AGDH returns a random κ-bit string str to A and adds the tuple (pidCi,   sidCi, R, R′, str) into RList.
C
o
r
r
u
p
t
Queries. AGDH answers these queries in the obvious way.
T
e
s
t
Queries. For each of these queries, AGDH responses with a random κ-bit string.
LetAsk be the event that A makes an H query on a string m that is the kds of some fresh instance. From the simulation of H, it can be easily seen that as soon as Ask occurs, AGDH outputs the desired result W3=gw1w2 and thus succeeds in solving the GDH problem in G. But, since H is a random oracle, A gains no advantage in distinguishing the test keys from random if the event Ask does not occur. This implies the assertion of Lemma 20.
This result combined with Lemmas17–19 concludes the proof for Theorem 15.Box 3
Decidingm=?kdsCi
Given a stringm and a tuple (pidCi,sidCi,R,*,R′,*), AGDH first checks if the bit-length of m is
equal to the bit-length of key derivation strings. If it is, thenAGDH checks that (1) pidCi∥sidCi is
a prefix ofm and (2) O(R,R′,mG)=1 where mG is a |G|-bit string that is a suffix of m. If both
are true, thenm=kdsCi.


### 4.4. Proof of Resistance to Undetectable Online Dictionary Attacks

We now claim that H3PAKE is secure against a UD online dictionary attack as long as the given 2-party protocol 2PAKE is SK-secure.Theorem 21.
Assume that, for anyppt adversary A′ asking at most qsend   Send queries,  Adv2PAKE(A′) is only negligibly larger than qsend/|D|. Then, for anyppt adversary A asking at most qsend  Send queries,  Pr⁡H3PAKE,A[Undet] is only negligibly larger than qsend/|D|, where Undet is as defined in Section 3.3.Proof.
LetA be an adversary who asks qsend  Send queries in attacking the protocol H3PAKE. Assume that  Pr⁡H3PAKE,A[Undet] is nonnegligibly larger than qsend/|D|. Given the adversary A, we prove the theorem by constructing an adversary A′ against 2PAKE who asks at most qsend  Send queries but has an advantage nonnegligibly larger than qsend/|D|.
A
′ invokes A as a subroutine and answers the oracle queries of A as follows.
E
x
e
c
u
t
e
Queries. When A makes an Execute  (ΠAi, ΠBj, ΠSk) query, A′ answers the query using its own Execute and Reveal oracles. A′ first queries Execute  (ΠAi, ΠSk) and Execute  (ΠBj, ΠSk′). Let  T2PAKE and  T2PAKE′ be two transcripts returned in response to the Execute queries. Next, A′ obtains two keys kAS and kBS by querying Reveal  (ΠAi) and Reveal  (ΠBj). A′ then generates the rest of the protocol transcript, using kAS and kBS as the MAC keys. Finally, A′ returns these messages together with  T2PAKE and  T2PAKE′ after ordering them properly.
S
e
n
d
Queries. When A makes a Send  (ΠUi, m) query, A′ checks if m is a message for initiating a new session (of H3PAKE) or the Send query belongs to an execution of 2PAKE. (1)
If both conditions are untrue,A′ responds to the query as that in the original experiment Exp0.(2)
Otherwise,A′ answers it by making the same query to its own Send oracle. If the query prompts ΠUi to accept,  A′ checks if ΠUi is a server instance against which A has mounted an online dictionary attack. If not, A′ makes a Reveal (ΠUi) query (and later uses the output of this Reveal query as the MAC key of ΠUi). (How to handle the other case will be explained below.)CorruptQueries. A′ answers these queries using its own Corrupt oracle.
R
e
v
e
a
l/Test Querise. A′ answers these queries as in the original experiment Exp0.
LetΠSt be any server instance against which A has mounted an online dictionary attack. Let  kSt be the session key that the instance ΠSt has computed in its execution of 2PAKE. In order for the instance ΠSt to terminate normally, the adversary A has to make a query of the form Send  (ΠSt, C∥*∥σCS) such that  VerkSt(C∥*∥pidSt,σCS)=1. When A makes such a Send query (i.e., when the event Undet occurs), A' makes a Test query against the instance ΠSt. Note that the instance ΠSt is fresh as (1) it is partnered with no instance and (2) S and C must have not been corrupted. Let k-St be the key returned in response to the Test query. A′ outputs 1, if  Verk-St(C∥*∥pidSt,σCS)=1, and outputs 0, otherwise. If Undet does not occur, A′ outputs a random bit.
From the simulation above, it is clear to see that(3)Adv2PAKE(A′)=2·Pr2PAKE,A′[Succ]-1=2·(PrH3PAKE,A[Undet]12iiiiiiiiiiiiiii+12(1-PrH3PAKE,A[Undet]))-1=PrH3PAKE,A[Undet].
Then, Theorem 21 immediately follows since the number of Send queries asked by A′ against 2PAKE is at most qsend.


## 4.1. Preliminaries

We begin with the cryptographic primitives on which the security of our construction relies.Gap Diffie-Hellman (GDH) Assumption. Consider a finite cyclic group G of prime order q where the operation is denoted multiplicatively. Since the order of G is prime, all the elements of G, except 1, are generators of G. Let g be a random generator of G. The GDH problem in G is to solve the computational Diffie-Hellman (CDH) problem in G when given an oracle O(·,·,·) that solves the decisional Diffie-Hellman (DDH) problem in G. The DDH oracle O(·,·,·), on input a triple (ga,gb,C) for a,b∈Zq, outputs 1 if and only if C=gab. We define the advantage of appt algorithm A in solving the GDH problem in G as  AdvGGDH(A)=Pr⁡[AO(·,·,·)(G,q,g,gx,gy)=gxy: x,y∈RZq]. We say that the GDH assumption holds in G if  AdvGGDH(A) is negligible for allppt algorithms A. We denote by  AdvGGDH(t) the maximum value of  AdvGGDH(A) over all algorithms A running in time at most t.Message Authentication Codes. A message authentication code (MAC) scheme Σ is a triple of efficient algorithms (Gen, Mac, Ver) where (1) the key generation algorithm Gen takes as input a security parameter 1l and outputs a key k chosen uniformly at random from {0,1}l; (2) the MAC generation algorithm Mac  takes as input a key k and a message m and outputs a MAC (also known as a tag) σ; and (3) the MAC verification algorithm Ver takes as input a key k, a message m, and a MAC σ and outputs 1 if σ is valid for m under k or outputs 0 if σ is invalid. Let AdvΣ(A) be the advantage of an adversary A in violating the strong existential unforgeability of Σ  under adaptive chosen message attacks. More precisely,  AdvΣ(A) is the probability that an adversary A, who mounts an adaptive chosen message attack against Σ with oracle access to  Mack(·) and  Verk(·), outputs a message/tag pair (m,σ) such that (1) Verk(m,σ)=1 and (2) σ was not previously output by the oracle  Mack(·) as a MAC on the message m. We say that the MAC scheme Σ is secure if  AdvΣ(A) is negligible for everyppt adversary A. We use  AdvΣ(t,qmac,qver) to denote the maximum value of  AdvΣ(A) over allppt adversaries A running in time at most t and asking at most qmac and qver queries to  Mack(·) and  Verk(·), respectively.2-Party PAKE Protocols. H3PAKE takes as input a 2-party PAKE protocol 2PAKE. We assume that the given 2-party protocol 2PAKE outputs session keys distributed in {0,1}l and is SK-secure against an adversary who is given access to all the oracles: Send, Execute, Reveal, Corrupt, and Test. Let  Adv2PAKE(A) be the advantage of an adversary A in breaking the SK security of 2PAKE. We require that, for anyppt adversary A asking at most qsend   Send queries,  Adv2PAKE(A) is only negligibly larger than qsend/|D|.  Adv2PAKE(t,Q) denotes the maximum value of  Adv2PAKE(A) over allppt adversaries A with time complexity at most t and query complexity at most Q.Additionally, H3PAKE uses a cryptographic hash functionH mapping {0,1}* to {0,1}κ, where κ is a security parameter representing the length of session keys. H is modelled as a random oracle in our proof of security for H3PAKE.


## 4.2. Description of H3PAKE

We assume that the following information has been preestablished and is known to all users in the network: (1) a cyclic groupG of prime order q and a generator g of G, (2) a MAC scheme  Σ=(Gen,Mac,Ver), (3) a 2-party PAKE protocol 2PAKE, and (4) a cryptographic hash function H. These public parameters can be determined by the server and be broadcast to all its registered clients. Let A and B be two clients who wish to establish a session key, and let S be the trusted server with which A and B have registered their passwords pwA and pwB, respectively. We denote the partner identifier pid given as input to (an instance of) A (resp., B and S) by  pidA (resp.,  pidB  and  pidS). Recall that pid is a sequence of identities of protocol participants. The order of identities that appears in pid is of critical importance for the correctness of our construction and its security proof. For simplicity, we assume that  pidA=pidB=pidS=〈A,B,S〉. Figure 5 depicts how the generic 3-party PAKE protocol, H3PAKE, is constructed from any given 2-party protocol, 2PAKE. More specifically, H3PAKE is constructed as follows.Figure 5
H3PAKE: our proposed generic 3-party PAKE protocol.P
h
a
s
e
1. A and S establish a shared high-entropy key kAS by running the 2-party protocol 2PAKE. Likewise, B and S establish a shared high-entropy key kBS.P
h
a
s
e
2. A and B establish their session key by running a MAC-based Diffie-Hellman key exchange protocol with assistance of S.Step 1. A chooses a random x∈Zq, computes X=gx and  σAS=MackAS(A∥X∥pidA), and sends 〈A,X,σAS〉 to S. Meanwhile, B chooses a random y∈Zq, computes Y=gy and σBS=MackBS(B∥Y∥pidB), and sends 〈B,Y,σBS〉 to S.Step 2. S checks that  VerkAS(A∥X∥pidS,σAS)=1 and   VerkBS(B∥Y∥pidS,σBS)=1. If either verification fails, S aborts the protocol. Otherwise, S computes  σSA=MackAS(S∥Y∥pidS) and  σSB=MackBS(S∥X∥pidS) and sends 〈S,Y,σSA〉 and 〈S,X,σSB〉 to A and B, respectively.Step 3. A verifies that  VerkAS(S∥Y∥pidA,σSA)=1. If the verification fails, A aborts the protocol. Otherwise, A sets the session identifier,  sidA=A∥X∥B∥Y, and computes the Diffie-Hellman key,  KA=Yx, and the session key,  skA=H(pidA∥sidA∥KA). Meanwhile, B checks if  VerkBS(S∥X∥pidB,σSB)=1 and aborts if the check fails. Otherwise, B sets  sidB=A∥X∥B∥Y and computes KB=Xy and  skB=H(pidB∥sidB∥KB).At the end of the protocol execution,A and B will compute the same session key sk if they both hold the same sets of pid and sid and thus compute the same Diffie-Hellman key K=gxy.We do not require 2PAKE to be instantiated with a protocol that provides either unilateral or mutual authentication, as H3PAKE already provides mutual authentication between the server and the clients (via the MAC values exchanged inPhase 2). Hence, any 2-party protocol that provides implicit key authentication, including one-round protocols, will be suitable candidates to instantiate 2PAKE.


## 4.3. Proof of SK Security

We claim that the generic construction H3PAKE described in Figure5 is SK-secure in the random oracle model under the GDH assumption in G and the security of the MAC scheme Σ.Theorem 15.
LetH be a random oracle. Then, for any adversary with time complexity at most t and query complexity at most Q=〈qexec, qsend, qreve, qcorr, qtest〉, its advantage in breaking the SK security of H3PAKE is bounded by
(2)AdvH3PAKE(t,Q)≤2·Adv2PAKE(t′,Q′)+2·qsend·AdvΣ(t′,2,2)+2·AdvGGDH(t′),
where Q′=〈2qexec, qsend, qsend, qcorr, 2qexec+qsend〉 and t′ is the maximum time required to perform the experiment Exp0 involving an adversary who attacks H3PAKE with time complexity t.Proof. Assume appt adversary A who attacks H3PAKE with time complexity t and query complexity Q=〈qexec, qsend, qreve, qcorr, qtest〉. We prove the theorem by making a series of modifications to the experiment Exp0, bounding the difference in A’s advantage between two consecutive experiments, and ending up with an experiment in which A’s advantage is negligible. By  Succi, we denote the event that A correctly guesses the hidden bit b (chosen by the Test oracle) in experiment Expi.Before presenting the first modified experiment, we define the notion of aclean instance.Definition 16.
We say an instanceΠUi is unclean if A has queried Corrupt  (U′) for some U′∈pidUi. Otherwise, we say it is clean.Experiment
E
x
p
1
.This experiment is different from Exp0 only in that we replace each different MAC key with a random key drawn uniformly from {0,1}l for all clean instances. The difference in A’s advantage between Exp0 and Exp1 is bounded by the following lemma.Lemma 17.
|
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
1
]
-
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
0
]
| ≤ Adv2PAKE(t′,Q′), where t′ and Q′ are as defined in Theorem 15.Proof.
We prove the lemma by constructing an adversaryA' attacking protocol 2PAKE from the adversary A whose advantage in attacking H3PAKE is different between Exp0 and Exp1. A' begins by choosing a bit b uniformly at random. Then, A' runs A as a subroutine while simulating the oracles as follows.
E
x
e
c
u
t
e
Queries. When A makes an Execute  (ΠAi, ΠBj, ΠSk) query, A' first checks if any of A, B, and S was previously corrupted. (i)
If so,A' answers the Execute query as in experiment Exp0.(ii)
Otherwise,A' answers the query using its own oracles. A' first asks two queries Execute  (ΠAi, ΠSk) and Execute  (ΠBj, ΠSk′). Let  T2PAKE and  T2PAKE′ be two transcripts returned in response to the Execute queries. Next, A' makes the queries Test  (ΠAi) and Test  (ΠBj) and receives in return two keys k¯AS and k¯BS (either real or random). A' then generates the rest of the protocol transcript (i.e., the messages to be sent in Phase 2), using k¯AS and k¯BS as the MAC keys. Finally, A' returns these messages together with T2PAKE and  T2PAKE′ after ordering them properly.
S
e
n
d
Queries. Whenever A makes a Send  (ΠUi, m) query, A' checks if m is a message for initiating a new session (of H3PAKE) or the Send query belongs to an execution of 2PAKE.(1)
If both conditions are untrue,A′ responds to the query as in experiment Exp0.(2)
Otherwise,A′ answers it by making the same query to its own Send oracle. If the query prompts ΠUi to accept, then A′ checks if anyone in  pidUi was previously corrupted.
(a)
If so,A′ makes a Reveal  (ΠUi) query and uses the output of this Reveal query as the MAC key of ΠUi.(b)
Otherwise,A′ makes a Test  (ΠUi) query (unless the partner of ΠUi has already been tested) and uses the output of this Test query as the MAC key of ΠUi.
R
e
v
e
a
l
Queries. These queries are handled as in experiment Exp0.
C
o
r
r
u
p
t
Queries. A′ answers these queries in the straightforward way using its own Corrupt oracle.
T
e
s
t Queries. A′ answers these queries according to the bit b that it has chosen at the beginning of the simulation. That is, A′ returns real session keys, which it has computed on its own, if b=1, and otherwise returns random keys chosen uniformly at random from {0,1}κ.
At some point in time,A will terminate and output its guess b′. When this happens, A′ outputs 1, if b=b′, and 0 otherwise.
From the simulation, it is obvious that(i)
the probability thatA′ outputs 1 when its Test   oracle returns real session keys is equal to the probability that A correctly guesses the bit b in experiment Exp0;(ii)
the probability thatA′ outputs 1 when its Test  oracle returns random keys is equal to the probability that A correctly guesses the bit b in experiment Exp1. This means that  Adv2PAKE(A′)  =  |Pr⁡H3PAKE,A[Succ1] − Pr⁡H3PAKE,A[Succ0]|.  Since A′ has at most time complexity t′ and query complexity   Q′=〈2qexec,qsend, qsend, qcorr, 2qexec+qsend〉, we obtain Lemma 17.Experiment
E
x
p
2. Let Forge be the event that the adversary A makes a Send query of the form Send  (ΠUi, V∥*∥σ) before querying Corrupt  (U) and Corrupt  (V), where σ is a valid tag on  V∥*∥pidUi and was not output by a previous oracle query as a tag on  V∥*∥pidUi. Then Exp2 is different from Exp1 only in that, if Forge occurs, the experiment is aborted and the adversary does not succeed. We claim the following lemma.Lemma 18.
|
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
2
]
-
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
1
]
| ≤ qsend·AdvΣ(t′,2,2), where t′ is as defined in Theorem 15.Proof.
Given the adversaryA attacking H3PAKE and assuming that the event Forge occurs, we construct an algorithm F that outputs, with a nonnegligible probability, a forgery against the MAC scheme Σ. The algorithm F is given oracle access to  Mack(·) and  Verk(·). The goal of F is to produce a message/tag pair (m,σ) such that (1)  Verk(m,σ)=1 and (2) σ was not previously output by the   Mack(·) oracle on input m.
Letn be the number of all different MAC keys that are established via a Send query of A. Clearly, n≤qsend. F begins by choosing a random α∈{1,…,n}. Let kα denote the αth key among all the n MAC keys, and let Sendα be a Send query that should be answered and/or verified using kα. F invokes A as a subroutine and handles the oracle calls of A as in experiment Exp1 except that it answers all  Sendα queries by accessing its MAC generation and verification oracles. As a result, theαth MAC key kα is never used during the simulation. If Forge occurs against an instance that holds kα, F halts and outputs the message/tag pair generated by A as its forgery. Otherwise, F halts and outputs a failure indication.
If the guessα is correct, then the simulation is perfect and F achieves its goal. Namely,  AdvΣ(F)=Pr⁡[Forge]/n. Since n≤qsend, we get  Pr⁡[Forge]≤qsend·AdvΣ(F). Then, Lemma 18 follows by noticing that F has at most time complexity t′ and makes at most two queries to  Mack(·) and  Verk(·).Experiment
E
x
p
3. This experiment is different from experiment Exp2 only in that the Execute and Send oracles are simulated as in “the Exp3 modification” described in Box 2.Box 2
TheExp3 Modification
WhenA asks an Execute or Send query, the simulator answers it exactly as in experiment Exp2,
except that it modifies the way of generating the public Diffie-Hellman values (denoted asX and
Y in the protocol) as follows:
(i) The simulator chooses two randomv1,v2∈Zq and computes V1=gv1 and V2=gv2.
(ii) For each instanceΠCi, the simulator chooses a random r∈Zq, computes
R={V1rifCappears first inpidCiV2rifCappears second inpidCi,
and usesR as the public Diffie-Hellman value (i.e., as X or Y) of ΠCi.Since the view ofA is identical between Exp2 and Exp3, following Lemma 19 is clear.Lemma 19.
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
3
]
=
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
2
].In experimentExp3, the advantage of A in attacking H3PAKE is bounded by the following lemma.Lemma 20.
Pr
⁡
H
3
P
A
K
E
,
A
[
S
u
c
c
3
]
≤
(
1
/
2
)
+
A
d
v
G
G
D
H
(
t
′
) where t′ is as defined in Theorem 15.Proof.
The proof is via a reduction from the GDH problem which is believed to be hard. Assume that the advantage ofA in attacking H3PAKE is nonnegligible. Then we can construct an algorithm AGDH that has a nonnegligible advantage in solving the GDH problem in G. The goal of AGDH is to compute and output the value W3=gw1w2∈G when given a CDH-problem instance (W1=gw1,W2=gw2)∈G as well as an oracle O(·,·,·) that solves the DDH problem in G. AGDH runs A as a subroutine while simulating all the oracles on its own.
WhenA asks an Execute and Send query, AGDH answers it as specified in the Exp3 modification but using W1 and W2 instead of V1 and V2. In this way, AGDH can embed the CDH-problem instance (W1,W2) into all protocol sessions. Accordingly, AGDH can compute no session keys but can still correctly answer Reveal queries by storing all the keying materials associated with each instance. For each instance ΠCi whose only remaining work is to compute its session key, AGDH checks if the instance ΠCi is clean or unclean. If it is clean, AGDH stores a tuple  (pidCi,sidCi,R,r,R′,r′) into a list, which we denote as CDHList, where R=W1r and R′=W2r′. Here, the exponent r (resp., r′) is the one chosen for the instance whose user identity comes first (resp., second) in  pidCi. If it is unclean, AGDH stores a tuple  (pidCi,sidCi,R,r,R′,⊥) if C comes first in  pidCi or a tuple  (pidCi,sidCi,R,⊥,R′,r′) if C comes second in  pidCi. Here, ⊥ indicates that the exponent of the received public Diffie-Hellman value may have been chosen by A.
While imbedding the CDH-problem instance as above,AGDH has to provide A with the same view as in experiment Exp3. To this end, let kds be akey derivation string from which a session key is computed by applying the random oracle H. Let kdsCi denote the kds of instance ΠCi. Then,  kdsCi=pidCi∥sidCi∥KCi. As is clear from the above simulation, AGDH cannot compute any kds on its own. But, given a string m, AGDH can determine whether m is the kds of some instance ΠCi or not by repeatedly performing the deciding operation for the tuples in CDHList as in Box 3.
The simulation of other oracles is provided as follows.
H Queries. AGDH uses a list, HList, to maintain input-output pairs of H. For each H query on a string m, AGDH first checks if an entry of the form (m,h) is in HList. If it is, AGDH returns h to A. Otherwise, AGDH checks if m is the kds of some instance ΠCi by repeatedly performing the deciding operation above until a match is found. (i)
If a match is found and the corresponding tuple is of the form(pidCi,  sidCi,  R, r, R′, r′), AGDH computes W3=(mG)1/rr′ and terminates outputting W3. In this case, AGDH succeeds in solving the GDH problem.(ii)
If a match is found and the corresponding tuple is of the form(pidCi,  sidCi,   R, r, R′, ⊥) or  (pidCi,   sidCi,   R, ⊥, R′, r′), AGDH checks if a tuple of the form  (pidCi,  sidCi,  R, R′, sk) is in the RList which is maintained by AGDH to store revealed session keys. If it is, AGDH returns sk to A and adds (m,sk) to HList. Otherwise, AGDH returns a random κ-bit string str to A and adds (m,str) to HList.(iii)
Otherwise,AGDH returns a random κ-bit string str to A and adds (m,str) to HList.RevealQueries. When A asks a Reveal  (ΠCi) query, AGDH finds a tuple of the form  (pidCi,   sidCi,R,*,R′, *) in CDHList and checks if a tuple of the form  (pidCi,  sidCi, R, R′, sk) is in the RList. If it is, AGDH returns sk to A. Otherwise, AGDH checks if HList contains an entry (m,h) such that m=kdsCi. Given the tuple  (pidCi,  sidCi,R,*,R′,*), this check can be done by performing the deciding operation for all entries in HList. If such entry (m,h) exists in HList, AGDH returns h in response to the query and adds the tuple (pidCi,  sidCi,  R, R′, h) into RList. Otherwise, AGDH returns a random κ-bit string str to A and adds the tuple (pidCi,   sidCi, R, R′, str) into RList.
C
o
r
r
u
p
t
Queries. AGDH answers these queries in the obvious way.
T
e
s
t
Queries. For each of these queries, AGDH responses with a random κ-bit string.
LetAsk be the event that A makes an H query on a string m that is the kds of some fresh instance. From the simulation of H, it can be easily seen that as soon as Ask occurs, AGDH outputs the desired result W3=gw1w2 and thus succeeds in solving the GDH problem in G. But, since H is a random oracle, A gains no advantage in distinguishing the test keys from random if the event Ask does not occur. This implies the assertion of Lemma 20.
This result combined with Lemmas17–19 concludes the proof for Theorem 15.Box 3
Decidingm=?kdsCi
Given a stringm and a tuple (pidCi,sidCi,R,*,R′,*), AGDH first checks if the bit-length of m is
equal to the bit-length of key derivation strings. If it is, thenAGDH checks that (1) pidCi∥sidCi is
a prefix ofm and (2) O(R,R′,mG)=1 where mG is a |G|-bit string that is a suffix of m. If both
are true, thenm=kdsCi.


## 4.4. Proof of Resistance to Undetectable Online Dictionary Attacks

We now claim that H3PAKE is secure against a UD online dictionary attack as long as the given 2-party protocol 2PAKE is SK-secure.Theorem 21.
Assume that, for anyppt adversary A′ asking at most qsend   Send queries,  Adv2PAKE(A′) is only negligibly larger than qsend/|D|. Then, for anyppt adversary A asking at most qsend  Send queries,  Pr⁡H3PAKE,A[Undet] is only negligibly larger than qsend/|D|, where Undet is as defined in Section 3.3.Proof.
LetA be an adversary who asks qsend  Send queries in attacking the protocol H3PAKE. Assume that  Pr⁡H3PAKE,A[Undet] is nonnegligibly larger than qsend/|D|. Given the adversary A, we prove the theorem by constructing an adversary A′ against 2PAKE who asks at most qsend  Send queries but has an advantage nonnegligibly larger than qsend/|D|.
A
′ invokes A as a subroutine and answers the oracle queries of A as follows.
E
x
e
c
u
t
e
Queries. When A makes an Execute  (ΠAi, ΠBj, ΠSk) query, A′ answers the query using its own Execute and Reveal oracles. A′ first queries Execute  (ΠAi, ΠSk) and Execute  (ΠBj, ΠSk′). Let  T2PAKE and  T2PAKE′ be two transcripts returned in response to the Execute queries. Next, A′ obtains two keys kAS and kBS by querying Reveal  (ΠAi) and Reveal  (ΠBj). A′ then generates the rest of the protocol transcript, using kAS and kBS as the MAC keys. Finally, A′ returns these messages together with  T2PAKE and  T2PAKE′ after ordering them properly.
S
e
n
d
Queries. When A makes a Send  (ΠUi, m) query, A′ checks if m is a message for initiating a new session (of H3PAKE) or the Send query belongs to an execution of 2PAKE. (1)
If both conditions are untrue,A′ responds to the query as that in the original experiment Exp0.(2)
Otherwise,A′ answers it by making the same query to its own Send oracle. If the query prompts ΠUi to accept,  A′ checks if ΠUi is a server instance against which A has mounted an online dictionary attack. If not, A′ makes a Reveal (ΠUi) query (and later uses the output of this Reveal query as the MAC key of ΠUi). (How to handle the other case will be explained below.)CorruptQueries. A′ answers these queries using its own Corrupt oracle.
R
e
v
e
a
l/Test Querise. A′ answers these queries as in the original experiment Exp0.
LetΠSt be any server instance against which A has mounted an online dictionary attack. Let  kSt be the session key that the instance ΠSt has computed in its execution of 2PAKE. In order for the instance ΠSt to terminate normally, the adversary A has to make a query of the form Send  (ΠSt, C∥*∥σCS) such that  VerkSt(C∥*∥pidSt,σCS)=1. When A makes such a Send query (i.e., when the event Undet occurs), A' makes a Test query against the instance ΠSt. Note that the instance ΠSt is fresh as (1) it is partnered with no instance and (2) S and C must have not been corrupted. Let k-St be the key returned in response to the Test query. A′ outputs 1, if  Verk-St(C∥*∥pidSt,σCS)=1, and outputs 0, otherwise. If Undet does not occur, A′ outputs a random bit.
From the simulation above, it is clear to see that(3)Adv2PAKE(A′)=2·Pr2PAKE,A′[Succ]-1=2·(PrH3PAKE,A[Undet]12iiiiiiiiiiiiiii+12(1-PrH3PAKE,A[Undet]))-1=PrH3PAKE,A[Undet].
Then, Theorem 21 immediately follows since the number of Send queries asked by A′ against 2PAKE is at most qsend.


## 5. Concluding Remarks

The undetectable online dictionary attacks we presented against the widely studied GPAKE protocol of Abdalla et al. [8, 9] are a reminder of the difficulty of designing a secure yet efficient 3-party PAKE protocol. The GPAKE protocol was proven secure in a model that does not capture undetectable online dictionary attacks, and thus, our attacks do not invalidate the proof of security for GPAKE.We also presented a simple and intuitive approach of capturing all classes of dictionary attacks in the framework of the widely accepted Bellare-Pointcheval-Rogaway model. What motivated our approach is the observation that no prior work has provided a rigorous formal treatment of insider (online/offline) dictionary attacks in the password-only 3-party setting and as a consequence 3-party PAKE protocols insecure against such attacks have proliferated. We believe that our approach provides protocol designers with an easier and more accessible way of proving security of their protocols against dictionary attacks.Finally, we presented a generic 3-party PAKE protocol (H3PAKE) and proved its security in the random oracle model under the gap Diffie-Hellman assumption. To the best of our knowledge, H3PAKE is the first 3-party PAKE protocol proven secure against both insider and outsider dictionary attacks as well as offline and online dictionary attacks. Future work includes coming up with a 3-party PAKE protocol that achieves the same (or even better) level of security and efficiency as H3PAKE but does not rely its security proof on the random oracle model.



---

*Source: 802359-2014-09-18.xml*