Cryptanalysis of an Authentication Key Exchange Protocol

INTRODUCTION

---

In 1976, the key agreement protocol was introduced by Diffie and Hellman^[1]. The two parties were able to establish a secret session key over an insecure channel, such that the confidential information was transmitted securely. However, the Diffie and Hellman protocol could not provide authentication of the two parties. In other words, the two parties could not authenticate each other.

To solve this problem, there are two ways to integrate authentication into a key agreement protocol. One approach uses a pre-shared password^[2]. With this pre-shared password, the session key can be established with user authentication. The other approach uses certificates (e.g. digital signatures), which provides authentication of the session key in key agreement protocols.

In 1995, the MQV key agreement protocol was proposed by Menezes et al.^[3] The MQV key agreement protocol was the first key agreement protocol to use a digital signature to sign the Diffie-Hellman public keys without using one-way hash functions. Moreover, the MQV key agreement protocol was adopted as a standard by the IEEE P1363 committee^[4].

In 1998, based on the MQV protocol, Harn and Lin^[5] proposed an authenticated key agreement protocol without using one-way functions. Summarily, Harn and Lin’s protocol contain the authentication for the Diffie-Hellman protocol. The two communication entities can establish multiple session keys in one round of interaction and use simple key computations.

Unfortunately, Yen and Joye^[6] pointed out that Harn and Lin’s protocol had a security flaw; it suffered from forgery attacks. If a valid short-term public key pair is given, an attacker can forge a new short-term public key pair and pass the verification procedure. In 2001, Harn and Lin^[7] further proposed an improved protocol to avoid forgery attacks by modifying the signature signing equation. However, there was still a weakness in Harn and Lin’s improved protocol. The common session keys generated by two parties were limited to the use of if two parties send n Diffie-Hellman public keys at a time. The purpose of this limit was to prevent the known-key attacks.

Recently, Hwang et al.^[8] modified Harn and Lin’s protocol using the XOR operation to decrease computational time and to use n²-1 to provide perfect forward secrecy. In this study, we will show that Hwang et al.’s protocol suffers from forgery attacks. An attacker can fool one communication part into believing the forged short-term public keys and share session keys with him.

Review of Hwang et al.’s protocol: In the Diffie-Hellman scheme, the system publishes two values p and g, where, p is a large prime and g is a generator with order p-1 in GF(p). Each user in the system selects a long-term secret key κ ∈ GF and computes a corresponding long-term public key y=g^κ mod p. Assume the two communication parties are Alice and Bob. The long-term secret key and the long-term public key for Alice is (κ_A and y_A) and for Bob, it is (κ_B and y_B), respectively. The following are the steps needed to establish multiple common session keys.

Step 1: Alice privately selects two random integers k_A1 and k_A2 to be short-term secret keys and computes short-term public keys r_A1= _g^kA1 mod p and r_A2= _g^kA2mod p. The signature value s_A can be obtained by computing the following equation:

Alice then sends the authenticated message {r_A1, r_A2, s_A, cert(y_A)} where, cert(y_A) is the certificate of Y_A to Bob.

Step 2: Bob follows the same procedure as Alice. He chooses two integers, k_B1 and k_B2 and computes {r_B1, r_B2, s_B}. Then Bob sends {r_B1, r_B2, s_B, cert(y_B)} to Alice.

Step 3: After receiving the message {r_B1, r_B2, s_B, cert(y_B)} sent from Bob, Alice checks the following verification equation:

Once the verification is valid, Alice uses r_B1 and r_B2 to compute four common session keys.
-pjas

Step 4: Bob still uses the same procedure as Alice. After receiving the message{r_A1, r_A2, s_A, cert(y_A)}, he checks the following verification equation:

If the verification equation holds, Bob also uses r_A1 and r_A2 to compute four common session keys using the following equation:

The four common session keys have been established successfully by Alice and Bob.

Forgery attack by an attacker
Step 1: An attacker intercepts the message {r_A1,r_A2, s_A, cert(y_A)} from Alice. The attacker chooses a random integer k_C1 and the corresponding and computes ‘r_A2 as follows:

Step 2: The attacker impersonates Alice in order to share keys with Bob. He/she sends {r_A1, r_A2', r_C1, s_A, cert(y_A)} to Bob. When Bob receives the message, he thinks that Alice wants to share 9 keys with him and verifies {r_A1, r_A2', r_C1} by checking

In fact,

The attacker can then successfully share with Bob.

With this attack, since Alice’s short term public key can be forged, the attacker can fool Bob into believing that he has shared 9 keys with Alice. However, Alice has actually only shared 4 keys with Bob. The attacker can therefore use forged short term public keys to compute 3 session keys and share them with Bob.