Authenticated key exchange protocol based on two hard problems - Do Viet Binh

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 147 AUTHENTICATED KEY EXCHANGE PROTOCOL BASED ON TWO HARD PROBLEMS Do Viet Binh* Abstract: Arazi was the first author to propose the integration of a key exchange protocol with a digital signature algorithm. Other authors have subsequently proposed methods to increase the level of security and achieve the necessary properties of authenticated key exchange protocols. However, these proposals exhibit several weaknesses and the majority of these protocols are based only on a single hard problem. In this paper, we propose a new secured key exchange protocol which is based on two hard problems. The security proofs for the new protocol confirm their novelty and security. Key words: Authentication, Hard problem, Key exchange. 1. INTRODUCTION The Diffie-Hellman key exchange protocol does not guarantee authentication between the two parties of the protocol [1]. Based on this fact, it is possible to develop a new key exchange protocol by integrating the Diffie-Hellman key exchange protocol (DH) into a digital signature scheme (DSA). This inherits the advantages of DH and DSA when they are deployed in practice. In paper [2], Arazi proposed improving the security of a key exchange protocol by integrating DH and DSA. However, later research [3], [4], [8] has highlighted several drawbacks to this method. Thus, other authors investigated ways to further improve the level of security and to achieve the required properties of authenticated key exchange (AKE) protocols [4-6], [9-11]. Nevertheless, several limitations remain, and the majority of these proposals are based only on a hard problem [2-6], [8-11]. This paper proposes a new secured authenticated key exchange protocol based on two hard problems. The structure of the rest of the paper is as follows. Section 2 presents an overview of related work in this area of study. Section 3 briefly describes the digital signature scheme [7], which is the foundation for the new secure key exchange protocol based on two hard problems (DH-MM-KE) and provides security proofs for the proposed protocol. The performance result of new protocol is reported in Section 4. Section 5 summarizes the paper. 2. RELATED WORK In 1993, Arazi designed a key exchange protocol with the idea of integrating the DH protocol into the DSA scheme [2]. However, some other authors [3], [4], [8] have pointed out several weaknesses in Arazi’s scheme, such as small subgroup attacks, known key attacks, unknown key attacks, and key replay attacks. Therefore, L.Harn [4] extended Arazi’s scheme to securely integrate the DH protocol into the DSA scheme. Harn suggested three protocol alternatives for different types of application. The key exchange protocols proposed by Harn hadthree important features: known-key security, unknown key-share security, and key replay security. These three security properties are standard requirements for any authenticated key exchange protocol. However, these protocols fail to provide the other two security properties: forward secrecy and key freshness [9]. In 2005, Phan [9] proposed a new protocol that had forward secrecy. In this protocol, even if the long-term private key of one side is exposed, the previous session key cannot be determined. In 2010, J. Liu and J. Li [6] suggested another protocol that overcomes the weaknesses of Phan’s key exchange protocol. Liu and Li's protocol was more secure than Phan's protocol while still maintaining its advantages. In 2014, D. Sow et al. [10], pointed Công nghệ thông tin & Cơ sở toán học cho tin học Do Viet Binh, “Authenticated key exchange protocol based on two hard problems.” 148 out weaknesses in the protocol suggested by Jeong et al. [5] and presented their improvement. However, all of these key exchange protocols are only based on one hard problem (the discrete logarithm problem – DLP). 3. DESIGN OF THE DH-MM-KE PROTOCOL 3.1. Signature scheme based on two hard problems This section provides an overview of a digital signature scheme based on two hard problems [11] (called the MM scheme). This scheme uses a prime modulo p with the special structure = 2 + 1, where = ′, ′ and are large prime numbers of at least 1024 bits. The value is a primitive element in of order satisfying ≡ 1 . The values and are the private key and the public key, respectively, and are generated as in the RSA cryptosystem [26]. is selected to be a small number (with a size between 16 and 32 bits) that is relatively prime to () = ( − 1)( − 1), while is computed as = (). is a secure one-way hash function. 1) Key generation: - Randomly select integer ∈ such that (, ) = 1. - Computed such that ≡ 1 (). - Randomly select private key with ∈ ∗ and compute = . The public key is (, , ). The private key is (, ). 2) Signature generation: - Select secret random number , ∈ [1, − 1]. - Compute = . - Compute = (||). - Compute the value , such that = ( − ) . i.e., = ( − ) such that = . The signature is the pair (, ). 3) Signature verification: - Compute ∗ = and ∗ = (||∗). - Comparethe values ∗ and . If ∗ = , then the signature is valid. Otherwise, the signature is rejected as invalid. 3.2. DH-MM-KE protocol This section proposes a new protocol, the Diffie Hellman–MM–Key Exchange protocol (DH-MM-KEP). 3.2.1. DH-MM-KEP design The domain parameters are (, , , ) as defined for the MM scheme. User A: = 2 + 1, where = and , are large prime numbers of at least 1024 bits. A's key parameters are a public key (, ) and a private key (, ). User B: = 2 + 1, where = and , are large prime numbers of at least 1024 bits. B's key parameters are a public key (, ) and a private key (, ). Compute such that it is a generator in ∗ and ∗ . With a certain probability (roughly equal to 1/4), a random value for is a generator in ∗ and ∗ . Therefore try several values of and check if it is a generator in both groups. We denote {} = {0, 1, , − 1} and {} = {0, 1, , − 1}. Compute the intersection ∩ of the two sets and to create a set = ∩ . Therefore, the value is also a generator of ∗ . Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 149 We assume that user A wants to share the secret session key with user B. Then: 1) A does the following: - Select ∈ [1, − 1] - Compute = and = . - Send (, ) to B. 2) B does the following: - Select ∈ [1, − 1]. - Compute = - Select ∈ [1, − 1]. - Compute = = - Compute the shared secret key = (||) - Compute = and = - Compute = (||||||||||) and = ( − ) - Send (, , , , ) to A. 3) A does the following: - Compute = - Compute = = - Compute the shared secret key = (||) - Verify (, ). - Compute = (||||||||||). - Compute = ( − ) - Send (, ) to B. 4) B does the following: - Verify (, ). A scenario for DH-MM-KEP is depicted in Figure 1. User A (, , , , ) User B (, , ) 1 Select ∈ [1, − 1] = and = 2 Select ∈ [1, − 1] = Select ∈ [1, − 1] = = = (||) = and = = (||||||||||) = ( − ) (, ) (, , , , ) Công nghệ thông tin & Cơ sở toán học cho tin học Do Viet Binh, “Authenticated key exchange protocol based on two hard problems.” 150 3 = = = = (||) Verify (, ) = (||||||||||) = ( − ) 4 Verify (, ) Fig. 1. DH-MM-KE protocol. 3.2.2. Security of the DH-MM-KE protocol Property 1. DH-MM-KE has perfect forward secrecy. Proof. The session key for the direction A to B is computed by A as = (||) = (|| ) (1) while it is computed by B as = (||) = (|| ) (2) Therefore, when the long-term private keys (, ) and (, ) of A and B are leaked, an attacker cannot compute previously established session keys and using equations (1) and (2). This is because the values and also depend on the secret values and . Therefore, this protocol has perfect forward secrecy. Property 2. DH-MM-KE has key independency. Proof. In DH-MM-KE, A and B compute = (|| ) and = (| which depend on the private keys (, ) and the random numbers (, ). It means that the session key is independently computed. Property 3. DH-MM-KE is secure against session state reveal (SSR) attacks. Proof. If an attacker acquires the random numbers used by user A and user B, the attacker cannot compute the session keys and . In DH-MM-KE, and are computed as follows: = (|| ) and = (|| ) where and are random values selected by users A and B. If the attacker gets and , he cannot compute and because the attacker cannot compute () and . Thus, DH-MM-KE is secure against session state reveal attacks. Property 4. DH-MM-KE is secure against key-compromise impersonation attacks. Proof. This protocol uses the mutual authentication between two entities A and B. Thus, authentication fails if the attacker is active and does not simultaneously know and (, ) or and (, ). Therefore, the only avenue open to the attacker is to try to compute the session key directly, assuming that he knows the long-term private key of A (, ) and the session’s ephemeral key of B (), because the session key is = (|| ) and the attacker can compute . However, the attacker cannot compute . Thus, DH-MM-KE is secure against key-compromise impersonation attacks. Property 5. DH-MM-KE is secure against unknown key-share attacks. Proof. Key confirmation can prevent unknown key-share attacks. User B confirms the receipt of the shared secret key with user A by signing this key along with (, ) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 50, 08 - 2017 151 (, , , , ). Because this shared secret key is a one-way hash function of random values (, ) that was computed by user A, user A is convinced that the message is not replay and knows that it is indeed from user B. B could also do something similar with as A. Property 6. DH-MM-KE is secure based on two hard problems. Proof. In DH-MM-KE, A and B compute = (|| ) and = (|| ) which depend on the values (, or ). Therefore, it is possible to compute (or ), but it is necessary to compute the values of and (or ). To compute , IFP should be solved and the value of (or ) is DLP. Therefore, DH-MM-KE is secure which based on two hard problems. 4. EXPERIMENT The time consumption of the proposed protocol is strongly depends on length of choosen . Therefore, we operate proposed protocol with several length of . The PC that we use to test running jdk1.8 and having two cores of Intel CPU with processing speed of 1.6 GHz and primary memory capacity of 8GB operating with Windows 10. Table 1. Experiment result. Length of (bit) Time performance (ms) 256 7 512 20 1024 114 5. CONCLUSION We have proposed a authenticated key exchange protocol based on two hard problems. Therefore, they have a higher level of security than existing protocols. The security of these protocols have been verified, and the existence of all the necessary properties required for a general security protocol has been proven. This protocol can also be applied in practice. REFERENCES [1]. Diffie W, Hellman M. (1976), “New Directions in Cryptography.IEEE Transactions on Information Theory”; 22: 644-654. [2]. Arazi B. (1993), “Integrating a key distribution procedure into the digital signature standard”. Electronics Letters; 29: 966-967. [3]. Brown D, Menezes A. (2001), “A Small Subgroup Attack on Arazi's Key Agreement Protocol”. Bulletin of the ICA;37: 45-50. [4]. Harn L, Mehta M, Hsin WJ. (2004), “Integrating Diffie-Hellman key exchange into the digital signature algorithm (DSA)”. IEEE Communications Letters; 8: 198-200. [5]. Jeong IR, Kwon JO, Lee DH. (2007), “Strong Diffie-Hellman DSA Key Exchange”. IEEE Communications Letters; 11: 432-433. [6]. Liu J, Li J. (2010), “A Better Improvement on the Integrated Diffie-Hellman - DSA Key Agreement Protocol”. IEEE Communications Letters; 11: 114-117. [7]. Minh NH, Binh DV, Giang NT, Moldovyan NA. (2012), “Blind signature protocol based on difficulty of simultaneous solving two difficult problems”. Applied Mathematical Sciences; 6: 6903 – 6910. [8]. Nyberg K, Rueppel R. (1994), “Weaknesses in some recent key agreement protocols”. Electronics Letters; 30: 26-27. Công nghệ thông tin & Cơ sở toán học cho tin học Do Viet Binh, “Authenticated key exchange protocol based on two hard problems.” 152 [9]. Phan RCW. (2005), “Fixing the integrated Diffie-Hellman DSA key exchange protocol”. IEEE Communications Letters; 9: 570-572. [10]. Sow D, Camara1 MG, Sow D. (2014), “Attack on “Strong Diffie-Hellman-DSA KE” and Improvement”. Journal of Mathematics Research; 6: 70-75. [11]. Viet HV, Minh NH, Truyen BT, Nga NT. (2013), “Improving on the integrated Diffie-Hellman-DSA key agreement protocol”. In: 2013 Third World Congress on Information and Communication Technologies (WICT 2013); 15-18 December 2013; Hanoi, Vietnam: pp. 106-110. TÓM TẮT PHÁT TRIỂN GIAO THỨC TRAO ĐỔI KHÓA CÓ XÁC THỰC DỰA TRÊN HAI BÀI TOÁN KHÓ Arazi là người đầu tiên đề xuất tích hợp chữ ký số và giao thức trao đổi khóa. Các tác giả khác cũng đề xuất các giao thức nhằm nâng cao tính bảo mật và đạt được các tính chất an toàn cần thiết của giao thức trao đổi khóa có xác thực. Tuy nhiên, các giao thức này tồn tại nhiều điểm yếu và đa phần chỉ dựa trên một bài toán khó. Trong bài báo này, xin được đề xuất một giao thức trao đổi khóa an toàn dựa trên hai bài toán khó và chứng minh tính bảo mật của giao thức mới này. Từ khóa: Xác thực, Bài toán khó, Trao đổi khóa. Nhận bài ngày 28 tháng 6 năm 2017 Hoàn thiện ngày 28 tháng 7 năm 2017 Chấp nhận đăng ngày 18 tháng 8 năm 2017 Địa chỉ: Military Information Technology Institute, Hanoi, Vietnam; *Email: binhdv@gmail.com