Analysis And Design Of Authentication And Key Exchange Protocols

With the rapid development of modern computer communication techniques and the wide applications of Internet, how to ensure the security of information has been the concern of the whole society. A vital problem in information security and cryptography is to enable parties to communicate secretly and reliably in the presence of an adversary. This is often achieved by authentication and key exchange protocols where the parties authenticate the identity with each other and generate a mutual and secret session key. Then the session key can be involved in secure communications using known techniques (e.g., applying encryption, signature and message authentication codes to all communications). Moreover, authentication and key exchange protocols are fundamental building blocks and theoretical guaranty to realize both secure electronic commerce and electronic government. The analysis and design of authentication and key exchange protocols have been hot topics of researches on information security.The key exchange protocol was initially studied by Diffie and Hellman in 1976. Until now, many efficient and secure key exchange protocols have been presented. It is fair to regard the paper of Needham and Schroeder published in 1978 Communications of the ACM as the starting point for the modern research on protocols for authentication. Since then, many authentication protocols have been proposed.In most cases, both authentication and key exchange are important, then authenticated key exchange (AKE) protocol is proposed. Authenticated key ex- change protocols allow parities to not only compute the shared key but also ensure authenticity among the parties.By now there are three different methods for the study of authentication and key exchange protocols, which are computational complexity approach, ad-hoc approach (heuristic approach) and formal approach, respectively.In this dissertation, we make some researches on authentication and key exchange protocols using computational complexity approach and ad-hoc approach. Our researches focus on the following directions of authenticated key exchange protocols:1. Secure Password-based Authenticated Key Exchange Protocol in Standard ModelThe setting in which users are only capable of storing human-memorable passwords (password-based authenticated key exchange) arises most often in practice and gains more and more attentions recently.Formal models of security for the password-based setting were first presented by Halevi and Krawczyk, where a secure public key infrastructure (PKI) is required. This is a too strong requirement and we hope to avoid it. Goldreich and Lindell presented the first protocol to achieve security without any additional setup. Their protocol is based on the existence of trapdoor permutations. Unfortunately, the protocol is not very efficient and thus cannot be adopted in practice.Recently, Katz, Ostrovsky and Yung proposed an efficient and practical password-based authenticated key exchange protocol (KOY) which was subsequently improved by Gennaro and Lindell (GL). Furthermore, Gennaro improved both the KOY and the GL protocols by reducing the communication bandwidth required by the protocols.In Chapter 4, we propose a new password-based authenticated key exchange protocol. The new protocol is based on twin decisional Diffie-Hellman assumption which is proposed by Cash, Kiltz and Shoup in EuroCrypt'08. In their paper, they also proposed a password-based authenticated key exchange protocol. Their protocol was proved to be secure in random oracle model. The common interpretation of such results is that security is likely to hold even if the random oracle is replaced by a concrete function known explicitly to all parties (e.g., SHA-1). However, Canetti, Goldreich and Halevi pointed out that it is impossible to replace the random oracle in a generic manner with any concrete function. Thus, the security proofs of these protocols are actually heuristic.The security of our proposed protocol is proved in standard model. As far as we know, the new protocol is the first provably secure password-based authenticated key exchange protocol under the twin DDH assumption in standard model.In addition, the new protocol has comparable efficiency with previous password-based AKE protocols in standard model. More precisely, using the algorithms for simultaneous multiple exponentiation, the number of exponentiations for per party is close to 7. Moreover, some values can be precomputed and stored so as to further improve the efficiency of the protocol.2. Secure and Efficient Authenticated Key Exchange Protocol in Random Oracle ModelIn 2001, Canetti and Krawzcyk proposed a well-known security model, denoted by CK model. Krawzcyk improved CK model to achieve weak perfect forward secrecy (wPFS). However, the stronger security model does not include attacks such as revaluation of both ephemeral private keys or both static private keys. Recently, LaMacchia, Lauter and Mityagin proposed the extended CK model (eCK) that could capture all these security properties. The eCK model is currently regarded as the strongest security model.The NAXOS protocol is the first authenticated key exchange protocol whose security is established in the eCK model. One shortcoming of the protocol is that it requires 4 exponentiations per party. Recently, Ustaoglu presented the CMQV protocol that achieves both efficiency and security. However, the security proof of CMQV protocol is not tight. In Chapter 3, we propose a modified version CMQV+ of the CMQV protocol. The new protocol is also a Diffie-Hellman based authenticated key exchange protocol, and has the following properties.(i) The CMQV+ protocol is more efficient than NAXOS protocol. Because CMQV+ protocol's computations can be speedup using Shamir's algorithm which results in reducing the costs by 0.75 exponentiations on average, the CMQV+ protocol requires only 3.25 exponentiations per party at every execution. However, NAXOS protocol requires 4 exponentiations per party.(ii) Compared to the CMQV protocol, the CMQV+ protocol has a tight security proof under extended Canetti-Krawzcyk model. In CMQV protocol, the simulator can not give answer to CDH oracle from one run with the adversary, therefore the simulator must interactive with the adversary again on the same input, the same coin flips and some carefully modifications. Following the approach of the Forking Lemma, the simulator answers to CDH oracle. The forking lemma results in a highly non-tight reduction. We modify the CMQV protocol to satisfy that the simulator answers the CDH oracle from one run. Therefore, the proof of security avoids using the forking lemma and gets a tight reduction.To our knowledge, CMQV+ protocol is the most efficient authenticated key exchange protocol with a tight security proof in extended Canetti-Krawczyk model under random oracle assumption.3. Analysis and Design of Remote User Authentication and Key Exchange ProtocolRecently, remote user authentication and key exchange protocol also becomes an important security mechanism. The server can authenticate user's identity over insure channel, and then guarantee that only the legal users have access to the resources provided by the remote servers.In this part, we analyze a remote user authentication protocol using ad-hoc approach. We show that the scheme is totally broken. Furthermore, we improve the scheme and analysis the security of the improved scheme. In 1981, Lamport proposed the first well-known password-based remote authentication scheme and then several schemes have been proposed to improve the security, the cost or the efficiency. Subsequently, Hwang and Li pointed that the above scheme will be partially or totally broken if the password table is stolen by the adversary. Further, they also proposed a remote user authentication scheme using smart cards to solve the problems of Lamport's scheme. Soon afterwards, Chan-Cheng, Shen-Lin-Hwang, Chang-Hwang and Leung et al. proposed many similar schemes to increase the security and improve the efficiency. In 2004, Kumar proposed a new remote user authentication scheme based on Shen-Lin-Hwang's scheme. The new scheme is secure against both Chan-Cheng's attack and Shen-Lin-Hwang's attack.In 2000, Boneh and Franklin proposed a practical ID-based encryption system based on bilinear pairings. Afterwards, large amounts of ID-based cryptographic schemes based on bilinear pairings have been proposed such as signature schemes and authenticated key exchange protocols. In 2006, Wang and Chai also presented a remote user authentication scheme using bilinear pairings.In Chapter 5, we first review Wang-Chai's remote user authentication scheme using bilinear pairings and demonstrate that their scheme is vulnerable to impersonation attack. Namely, after obtaining a previous valid login message (e.g., by wiretapping), an attacker can easily forge another valid login message to pass the remote server's authentication, and then impersonates a legal user to access the resources at the remote server.We also propose an improvement of Wang-Chai's remote user authentication scheme based on bilinear pairings. The proposed scheme is composed of four phases: initialization phase, registration phase, login phase and authentication & session key agreement phase. Furthermore, we prove that the scheme not only keeps the merits of Wang-Chai's scheme but also repairs the security flaws of its scheme. In addition, the new scheme provides both mutual authentication and session key agreement.