Zhao와 Gu가 제안한 키 교환 프로토콜의 안전성 분석
남 정 현*, 백 주 련**, 이 영 숙***, 원 동 호**
A Security Analysis of Zhao and Gu's Key Exchange Protocol
Junghyun Nam
*
, Juryon Paik **, Youngsook Lee ***, Dongho Won**요 약
키 교환 프로토콜은 공개 네트워크상에서 안전한 통신 채널을 구축하는데 필수적인 요소이다. 특히, 패스워드 기반 키 교환 프로토콜에서는 패스워드를 이용하여 사용자 인증이 이루어지며 이를 바탕으로 안전하게 키 교환이 이루어지도록 설계되어야 한다. 그러나 패스워드는 인간이 쉽게 기억할 수 있는 반면에 엔트로피가 낮고 따라서 사 전공격에 쉽게 노출될 수 있다. 최근, Zhao와 Gu가 서버의 도움을 필요로 하는 새로운 패스워드 기반 키 교환 프 로토콜을 제안하였다. Zhao와 Gu가 제안한 프로토콜은 일회성 비밀키의 노출 상황을 고려하는 공격자 모델에서도 안전성이 증명가능하다고 주장하였다. 본 논문에서는 Zhao와 Gu의 프로토콜에 대한 재전송 공격을 통하여 이 프 로토콜이 저자들의 주장과 달리 일회성 비밀키의 노출 시에 안전하지 않다는 것을 보일 것이다. 본 연구 결과는 Zhao와 Gu가 제시한 안전성 증명이 성립하지 않음을 의미한다.
▸ Keywords : 안전성, 키 교환 프로토콜, 패스워드, 공격
Abstract
Key exchange protocols are essential for building a secure communication channel over an insecure open network. In particular, password-based key exchange protocols are designed to work when user authentication is done via the use of passwords. But, passwords are easy for human beings to remember, but are low entropy and thus are subject to dictionary attacks. Recently, Zhao
∙제1저자 : 남정현 ∙교신저자 : 원동호
∙투고일 : 2012. 07. 05, 심사일 : 2012. 08. 02, 게재확정일 : 2012. 09. 03.
* 건국대학교 컴퓨터공학과(Dept. of Computer Engineering, Konkuk University)
** 성균관대학교 컴퓨터공학과(Dept. of Computer Engineering, Sungkyunkwan University)
*** 호원대학교 사이버수사 경찰학부(Dept. of Cyber Investigation Police, Howon University)
※ This paper was written as part of Konkuk University's research support program for its faculty on sabbatical leave in 2012.
and Gu proposed a new server-aided protocol for password-based key exchange. Zhao and Gu’s protocol was claimed to be provably secure in a formal adversarial model which captures the notion of leakage of ephemeral secret keys. In this paper, we mount a replay attack on Zhao and Gu’s protocol and thereby show that unlike the claim of provable security, the protocol is not secure against leakage of ephemeral secret keys. Our result implies that Zhao and Gu’s proof of security for the protocol is invalid.
▸ Keywords : Security, Key exchange protocol, Password, Attack
I. Introduction
Key exchange protocols are designed to allow two or more parties to establish a common secret key over a public network. This secret key, commonly called a session key, is then typically used to build confidential or integrity-protected communication channel between the parties. The highest priority in designing a key exchange protocol is placed on ensuring the security of session keys to be established by the protocol. Roughly speaking, establishing a session key securely means that the key is being known only to the intended parties at the end of the protocol run. But unfortunately, the experience has shown that the design of secure key exchange protocols is notoriously difficult. Thus, key exchange protocols must be subjected to a thorough and systematic scrutiny before they are deployed into a public network, which might be controlled by an adversary.
Secure session-key generation requires an authentication mechanism to be integrated into key exchange protocols. In turn, achieving any form of authentication inevitably requires some secret information to be established between users in advance of the authentication stage. Cryptographic keys, either secret keys for symmetric cryptography or private/public keys for asymmetric cryptography, may be one form of the underlying secret information pre-established between users. However, these high-entropy cryptographic keys are random in
appearance and thus are difficult for humans to remember, entailing a significant amount of administrative work and costs. Eventually, it is this drawback that password-based authentication has come to be widely used in reality. Passwords are drawn from a relatively small space like a dictionary, and are easier for humans to remember than cryptographic keys with high entropy.
Bellovin and Merritt [1] was the first to consider how two parties, who only share a weak, low-entropy password, and who are communicating over a public network, authenticate each other and agree on a high-entropy cryptographic key to be used for protecting their subsequent communication.
Their protocol, known as encrypted key exchange, or EKE, was a great success in showing how one can exchange password authenticated information while protecting poorly-chosen passwords from the notorious password guessing attacks. Due in large part to the practical significance of password-based authentication, this initial work has been followed by a number of two-party protocols (e.g., [2][3][4][5]
[6][7]) offering various levels of security and complexity.
While two-party protocols for password-authenticated
key exchange (PAKE) are well suited for client-server
architectures, they are inconvenient and costly for
use in large scale peer-to-peer systems. Since two-party
PAKE protocols require each pair of potential
communication parties to share a password, a large
number of parties result in an even larger number of
passwords to be shared. It is due to this problem
that three-party models have been often used in
Fig. 1. Zhao and Gu’s Three-Party PAKE Protocol
designing PAKE protocols (e.g., [8][9][10][11][12]).
In a typical three-party setting, each party (often called client) does not need to remember and manage multiple passwords, but shares only a single password with a trusted server who then assists clients in establishing a session key by providing authentication services to them. However, this convenience comes at the price of clients’ trust in the server. Despite this drawback, the three-party model offers an effective, realistic solution to the problem of session key exchange in large peer-to-peer systems, and in fact is assumed by the popular Kerberos authentication system [13].
Recently, Zhao and Gu [14] proposed a three-party PAKE protocol making use of the trapdoor test technique introduced by Cash, Kiltz, and Shoup [15]. Zhao and Gu’s protocol was claimed to be provably secure under the assumption that the hash functions used in the protocol are random oracles. The adversarial model, where security of the protocol is proven, captures the notion of strong corruption by allowing the adversary to ask EphemeralKeyReveal queries. An EphemeralKeyReveal query against a user instance outputs all the ephemeral secrets used by the instance during the protocol execution. Allowing an adversary to ask EphemeralKeyReveal queries models the adversary’s capability to embed a Trojan horse or other form of malicious code into a user’s machine and then obtain all the session-specific information of the victim.
Since Zhao and Gu’s protocol is proven secure in a model that allows EphemeralKeyReveal queries, it should be secure against strong corruption. But what we found is the opposite: Zhao and Gu’s protocol does not exhibit resistance against strong corruption. Indeed, Zhao and Gu’s protocol is vulnerable to a replay attack where the adversary asks an EphemeralKeyReveal query in its attack.
We here reveal this security vulnerability of Zhao and Gu’s protocol. Our result invalidates the claimed proof of security for the protocol.
II. Review of Zhao and Gu’s Protocol
This section describes the three-party PAKE protocol proposed by Zhao and Gu [14]. The protocol participants consist of a single server and two clients and . The clients and wish to establish a session key between them while the server exists to provide the clients with authentication services. We denote by ,
and the identities of , and , respectively.
Let and be the passwords of and
, respectively. Each client’s password is assumed to be shared with the authentication server via a secure channel. The followings are the public system parameters used in the protocol.
Two large primes and with , and a generator of group of order .
A pair of symmetric encryption/decryption algorithms ( , ) modeled as an ideal cipher [2].
Three hash functions , and modeled as random oracles [16]. and map
to
while maps
to
, where is a security parameter representing the length of session keys.
Once , and are fixed, the server
generates its long-term private/public keys
such that ∈ and . A high-level depiction of the protocol is given in Fig. 1, and a more detailed description follows:
Client chooses random ∈ and computes
and
. Then verifies if lies in . If not, aborts. Otherwise, computes
, ,
, and
,
where is a random value. Finally, deletes the
ephemeral secret and sends 〈
〉 to .
Similarly, chooses random ∈ and computes
and
. Then verifies if lies in . If not, aborts. Otherwise,
computes , ,
and
, where is a random value. Finally, deletes and sends
〈 〉 to . Upon receiving and , the server
verifies if all of , , , , and lie in
. If not, aborts. Otherwise, computes
′ and
′ by using its private key . Then performs the decryptions
′
′
′
and
′
′
′
and verifies that ′ and
′ . If ′ ≠ or
′ ≠ , then aborts. Otherwise,
computes
′
and sends 〈 〉 to
, where is a random value chosen by . Similarly,
computes
′
and sends 〈 〉 to
, where is a random value chosen by . At last, deletes the session-specific information:
′ ′ ′ ′ .
After receiving , checks if (1) ,
and lie in and (2)
. If any of these are untrue,
aborts. Otherwise, computes
, , ,
and
. Finally, defines the session ID
and computes the session key
.
Similarly, on receiving , checks if (1) ,
and lie in and (2)
. If
any of these are untrue, aborts. Otherwise,
computes ,
,
, and . Finally, defines the session ID
and computes the session key .
III. Adversarial Model
Zhao and Gu’s protocol comes along with a claimed proof of its security in a formal model of adversarial capabilities. The adversarial model that they used is the one of Yoneyama [12] and captures security against strong corruption [2][17][18]. Here we provide an overview of the adversarial model as a preliminary step towards mounting an ephemeral- key reveal attack against the protocol.
1. Participants
Each participant in a three-party key exchange is either a client or the trusted server
. Each may run the protocol multiple times
either serially or concurrently, with possibly
different participants. Thus, at a given time, there
could be many instances of a single client and the
server. denotes instance of a participant .
An instance is said to accept when it computes
a valid session key . During the initialization
phase of the protocol, the server generates its
long-term private/public key pair ( , ) and
each client chooses a password as their
long-term secret key and shares it with .
Passwords are drawn from a dictionary .
2. Adversary
The adversary is in complete control of every aspect of all communications between participants, and may ask, at any time, them to open up access to their long-term secret keys. These capabilities and others of the adversary are modeled via various oracles to which the adversary is allowed to make queries.
Execute( , ′ , ): This query prompts an honest execution of the protocol among the client instances and ′ and the server instance
. The transcript of the honest execution is returned to the adversary as the output of the query. This oracle call represents passive eavesdropping of a protocol execution.
SendClient( , ): This query sends message to the client instance . The instance proceeds as it would in the protocol upon receiving . The response message generated by , if any, is the output of this query and is returned to the adversary. A query of the form SendClient( , start: ′ ) prompts to initiate the protocol with a client ′ ( ≠ ).
SendServer( , ): This query sends message to the server instance . The instance proceeds as it would in the protocol upon receiving . The response message generated by , if any, is the output of this query and is returned to the adversary.
Long-termKeyReveal( ): This query outputs the long-term secret key of . This oracle call captures the idea that damage due to loss of ’s long-term key should be restricted to those sessions where
will participate in the future.
EphemeralKeyReveal( ): This query returns all short-term secrets used by instance . This models the adversary’s capability to embed a Trojan horse or other form of malicious code into a user’s machine and then obtain all the session-specific information of the victim.
SessionKeyReveal( ): This query returns the session key held by instance , modeling leakage of session keys. This oracle call captures the idea that exposure of some session keys should not affect the security of other session keys.
EstablishParty( , , ): This query models the adversary to register a password on behalf of a client . In this way the adversary totally controls that client. Clients against whom the adversary did not issue this query are called honest.
Test( ): This query provides a means of defining security of session keys. The output of this query depends on the hidden bit chosen uniformly at random from
. The Test oracle returns the real session key held by if , or returns a random key drawn from the session-key space if
. The adversary is allowed to access the Test oracle only once.
TestPassword( , ′ ): This query provides a means of defining security of passwords. If the password guess ′ is the same as the client
’s real password , then return 1. Otherwise, return 0. The adversary can make TestPassword query only once.
3. Partnership
Loosely stated, two instances are partners of each
other if they participate together in a protocol
execution and share a session key as a result of the
execution. The notion of partners is used in the
definition of security to disallow the adversary to
ask the Test query against an instance whose partner instance has already been asked for the session key (with a SessionKeyReveal query), ephemeral keys (with an EphemeralKeyReveal query), or long-term keys (with a Long-termKeyReveal query). It is thus important to define partnership correctly. An error in the partnership definition may render a protocol insecure (in the proof model used) when there is no known attack on the protocol (for a concrete example, see the work by Choo et al. [19]).
Let the session identifier ( ) of an instance be a function of the messages sent and received by the instance during its execution. Zhao and Gu follow the recent practice of relying on the notion of s to define partnership between instances. According to their definition of partnership, two instances
and ′ (with ≠ ′ ) are said to be partnered if the following conditions hold: (1) both and
′ have accepted, (2) and ′ have computed the same , (3) the partner identifier for is ′ and vice versa, and (4) no instance besides and ′ has accepted with a partner identifier equal to and ′ . When an instance
accepts, it holds a session key, a session identifier, and a partner identifier.
4. Security Definition
Definition of security is based on the notion of freshness. Intuitively, a fresh instance is an instance which holds a session key about which the adversary should not know. More precisely:
Definition 1 (freshness). Let be an instance who has accepted and let ′ be ’s partner instance (if it exists). An instance is considered fresh if none of the following conditions hold:
The adversary reveals the session key of the instance or its partner instance ′ .
The adversary asks neither SendClient( ,
) nor SendClient( ′ , ′ ) query. Then the adversary either makes queries:
EphemeralKeyReveal( ) or EphemeralKeyReveal( ′ )
The adversary asks SendClient( ′ , ′ ) query. Then the adversary either makes queries:
Long-termKeyReveal( ), Long-termKeyReveal( ),
EphemeralKeyReveal( ) for any session or EphemeralKeyReveal( ′ ).
The adversary asks SendClient( , ) query. Then the adversary either makes queries:
Long-termKeyReveal( ′ ), Long-termKeyReveal( ), EphemeralKeyReveal( ) or
EphemeralKeyReveal( ′ ) for any session . In this definition of freshness, all the queries for
′ are defined if ′ exists.
The security of a protocol against an adversary
is defined in terms of the probability that
succeeds in distinguishing a real session key established in an execution of from a random session key. That is, the adversary is considered successful in attacking if it breaks the semantic security of session keys generated by . More precisely, the security is defined in the following context. The adversary executes the protocol exploiting as much parallelism as possible and asking any queries allowed in the adversarial model.
During executions of the protocol, the adversary ,
at any time, asks a Test query to a fresh instance,
gets back a key as the response to this query, and at
some later point in time, outputs a bit ′ as a guess
for the value of the hidden bit used by the Test
oracle. Then the advantage of in attacking protocol
Query Response 1 Execute( , , ) Transcript: , , ,
2 EphemeralKeyReveal( ) 〈 〉
3 SendClient( , start: ) ′ 〈 ′′ ′ ′ ′ 〉
4 SendServer( , ′ )
5 SendServer( , ) 〈 ′ ′ 〉
〈 ′′ ′ ′ ′ 〉
6 SendClient( , ) (accept)
7 Test( ) or a random key
Table 1. The Sequence of Oracle Queries
is denoted by , and is defined as
′ .
Let denote the maximum value of
over all with time complexity at most
and asking at most queries. Then, protocol is said to be AKE-secure if is only negligibly larger than , where is a constant and is the number of SendClient/
SendServer queries. This notion of security is commonly termed as “AKE security”.
IV. Breaking AKE Security
In this section, we break the AKE security of Zhao and Gu’s key exchange protocol. The security model described in the previous section allows the adversary to ask EphemeralKeyReveal queries. The EphemeralKeyReveal oracle is allowed to check that the protocol is secure against strong corruption. In
other words, the EphemeralKeyReveal oracle call captures the idea that exposure of ephemeral secrets of a session should not affect the security of other sessions. Hence, a key exchange protocol proven secure in a model that allows EphemeralKeyReveal queries ought to be secure against an adversary who
tries to break the security of a session by exploiting ephemeral secrets obtained from some other sessions. Zhao and Gu’s protocol carries a claimed proof of its AKE security, but as we will see below, it does not provide security against strong corruption. This implies that their security proof is flawed.
The vulnerability of Zhao and Gu’s protocol against strong corruption is attributed to the fact that clients’ messages 〈
〉and
〈
〉can replayed without being detected by the server.
Our attack starts from this observation. Let
be an honest protocol session where and
established a session key as per protocol specification. Suppose now that a malicious adversary eavesdropped the message sent by to in the protocol session . Suppose also that the adversary obtained the ephemeral secrets - , and - which used in the
session . As also stated in the definition
of EphemeralKeyReveal oracle, this leakage of
the ephemeral secrets can be justified under
the assumption that has the capability to
embed a Trojan horse or other form of
malicious code into ’s machine and then log
all the session-specific information of . With ,
and in hand, can easily impersonate
to as follows:
initiates a new session with as if the initiation message is from .
Next, sends the message
〈
〉 (eavesdropped in the previous session ) to alleging that the message is from .
then intercepts the message sent by to
for this new session.
Finally, using , and , the adversary
computes the same session key as that of . This allows to impersonate to .
The above attack on Zhao and Gu’s protocol is well captured in the adversarial model. Let again
and denote two registered clients and also be any registered client other than and . Table 1 shows the sequence of oracle queries corresponding to the attack scenario described above. The goal of the adversary is to break the AKE security of Zhao and Gu’s protocol. begins by letting and
execute the protocol together by asking Execute ( , , ). As a result, obtains the message
〈
〉 from to
. Then asks EphemeralKeyReveal( ) to obtain all the ephemeral secrets 〈 〉
used by instance . Now asks SendClient ( , start: ) which prompts instance to initiate the protocol with client . In response to this query, will output the message
′ 〈 ′′ ′ ′ ′ 〉 . The next queries makes correspond to an honest execution of the protocol among ,
(impersonated by ) and . Hence, the rest of the queries are straightforward: asks
SendServer( ,
〈
′
′
′
′
′
〉 )
and SendServer( , 〈
〉 ), and then, as responds to the queries, asks SendClient(
,
〈
′
′
〉).
Notice that replays the message obtained from . When is sent the query SendClient ( , 〈 ′ ′ 〉 ), it accepts with the session key being computed as
, where
′ ,
′ , ′ ′
and
′ ′
. It can be easily verified that the instance is fresh under Definition 1; (1) no one in { , , } has been sent a Corrupt query, (2) no Reveal query has been made against any instance, and (3) the query EphemeralKeyReveal( ) has been asked before the SendClient queries to have been asked.
Thus, may test (i.e., ask the Test query against) the instance . is able to compute on its own since it knows the values of the exponents
, , used to compute , and . This means that ′ and hence
. Therefore, achieves its goal of breaking the AKE security of Zhao and Gu’s protocol.
Generally speaking, it is desirable that ephemeral
secrets exposed in a session should not jeopardize
the session-key secrecy of any other sessions. For
this reason, key exchange protocols proven
AKE-secure in a model that allows strong corruption
ought to be resistant against any attacks similar to
ours. Our attack shows that the proof of security for
Zhao and Gu’s protocol is invalid. The problem with
the proof is that the result of EphemeralKeyReveal
queries was not adequately considered in the
simulation.
V. Conclusion
This work has considered the security of Zhao and Gu’s three-party protocol [14] for password authenticated key exchange. Although Zhao and Gu’s protocol comes along with a claimed proof of its security, we have shown that the protocol is not secure against strong corruption in the context of the proof model. This vulnerability, however, is not just a failure of Zhao and Gu’s protocol but it is an inherent limitation of all three-party protocols that do not require the server to verify the freshness of incoming messages. Thus, there is no quick tweak we can apply to make Zhao and Gu’s protocol resistant to strong corruption. Moreover, it is not clear how to make the protocol achieve any form of provable security.
참고문헌
