網路安全一直是網路應用普及後眾所關心的課題，在解決網路安全問題的機制中，使用者身份驗證通常是最基本的第一步，透過使用者驗證，系統可以據以決定是否提供服務或允許怎樣的權限，並得以依此來做帳務計算等。而在驗證過使用者之後，接下來的問題就是如何保護通訊雙方所互相傳遞的資料，目前解決這個問題最有效的方式就是為通訊的雙方分配一把共有的秘密金鑰，然後以此秘密金鑰來加密傳送的資料以防止竊聽，並產生訊息驗證碼以防止篡改。因此，一個能同時提供使用者驗證及秘密金鑰分配的安全協定，方能滿足上述的安全需求，這一類的安全協定通常稱之為「驗證金鑰交換協定」(Authenticated Key Exchange - AKE)。而在驗證使用者的技術中，又以允許使用者自行選取「通行碼」(Password)的方式，最方便使用者記憶且成本最低。這種以使用者自選通行碼為基礎的使用者驗證及秘密金鑰分配協定則稱之為「通行碼驗證金鑰交換協定」(Password Authenticated Key Exchange - PAKE)，而這就是本論文要探討的主題。

　　在通行碼驗證金鑰交換協定的安全威脅中，通行碼猜測攻擊(Password Guessing Attack)是最特別的，這是因為使用者通常會選擇容易記憶的字串來當做通行碼，這意味著通行碼的選擇空間是相對小到攻擊者可以在很短的時間內就全部搜尋過，而此一攻擊的不易防範已經使得一些過去發表的通行碼驗證金鑰交換協定後來被發現是不安全的。

　　在過去有很長的一段時間，對於網路安全協定最重要的安全分析與評估，一直停留在所謂的探索式安全分析(Heuristic Security Analysis)，也就是一個新的安全協定被提出時，設計者會說明其之所以安全的原因，在經過一段長時間之後(可能十年或更久)，若此協定仍未被破解，則其安全性將廣被接受。然而過去的發展經驗顯示出：這樣的安全分析方式常常造成有些一直被認為是安全的協定，在經過一段時間後被發現是不安全的；這樣的情況，使得所謂的「可證明安全」(Provable Security)被期待能提供明確的安全保證。而最近幾年，針對通行碼驗證金鑰交換協定的正規安全證明已逐漸發展出不錯的成果，因此，對新設計的通行碼驗證金鑰交換協定做正規的安全證明，已經是不可或缺的。

　　自從1992年Bellovin與Merritt提出兩方(Two-Party，也就是user與server)通行碼驗證金鑰交換協定以來，不斷有新的協定在安全性或效率上加以改進而相繼被提出，而最近兩三年來已有幾個兩方通行碼驗證金鑰交換協定被正規地證明其安全性，因此，兩方通行碼驗證金鑰交換協定的研究是相對較成熟的。儘管如此，我們在本論文中仍將提出一個改進的並可證明安全的兩方通行碼驗證金鑰交換協定，這個改進是分別結合兩個已發表協定的優點－1995年Steiner、Tsudik與Waidner所提的MDHEKE協定及2000年Bellare、Pointcheval與Rogaway所提的DHEKE2協定。

　　三方(Three-Party，也就是一個被信任的server與兩個欲通訊的users)通行碼驗證金鑰交換協定能夠對使用者間的通訊提供較有效率的金鑰管理，在這方面的研究，從1989年開始陸續有新的協定被提出，然而，至今還沒有一個三方通行碼驗證金鑰交換協定有正規地證明其安全性。此外，這些已發表的三方通行碼驗證金鑰交換協定幾乎都是使用server的公開金鑰來加密通行碼以防止通行碼猜測攻擊，雖然直接使用一個公開金鑰加密系統可以簡化協定的設計及方便協定的安全分析，然而卻也另外增加了使用者驗證或儲存此公開金鑰的負擔與不便。Steiner、Tsudik與Waidner曾經提出一個不需使用server公開金鑰的三方通行碼驗證金鑰交換協定，可是隨後被Ding與Horster指出會遭受無法偵測的線上通行碼猜測攻擊(Undetectable On-Line Password Guessing Attacks)。基於以上所述三方通行碼驗證金鑰交換協定研究上的缺憾，本論文將對三方通行碼驗證金鑰交換協定的研究多所著墨，並達到以下的貢獻：

1. 我們將指出：Steiner、Tsudik與Waidner所提的三方通行碼驗證金鑰交換協定還會遭受更強的離線通行碼猜測攻擊。
2. 提出一個新的使用server公開金鑰的三方通行碼驗證金鑰交換協定，這個新的協定是目前最有效率的。
3. 提出一個不需使用server公開金鑰的三方通行碼驗證金鑰交換協定，這是目前唯一不使用server公開金鑰且安全的三方通行碼驗證金鑰交換協定。
4. 將依據Bellare與Rogaway於1995年對三方驗證金鑰交換的安全證明及Bellare、Pointcheval與Rogaway於2000年對兩方通行碼驗證金鑰交換的安全證明，來證明以上我們所提的兩個三方通行碼驗證金鑰交換協定之安全性。

　　Network security is an important topic of great concern. User authentication is usually the basic and first step in ensuring a secure network. Users must be identified and authenticated so that they can be held accountable and given specific privileges. In open network environments, when users have been authenticated, the next question is the protection of sensitive information transmitted between the sender and receiver. The most effective method for solving this problem involves negotiating a shared secret key to provide data privacy and integrity. A protocol that provides both user authentication and session-key distribution can meet the security requirements mentioned above, and is referred to as Authenticated Key Exchange (AKE). Furthermore, the use of user-chosen passwords is the least expensive solution for user authentication. User-chosen passwords are typically easy to remember, so such a solution is very convenient for users. Authenticated key exchange protocols based on passwords are referred to as Password Authenticated Key Exchanges (PAKE), on which this thesis concentrates.

　　Password guessing attacks are the primary threat to security in password authenticated key exchanges because users tend to choose easy-to-remember strings as passwords. Consequently, an exhaustive search over the space of passwords is feasible. Password guessing attacks have caused many proposed password authenticated key exchange protocols to be insecure, years after such protocols were first proposed.

　　For a long time, heuristic security analysis has been the main method for evaluating protocol security. That is, a protocol would be proposed and heuristic arguments for its security would be made, and if no one was able to break the protocol after a long time (for example, of ten years or more), then its security was widely accepted. Such a methodology results in several proposed protocols that were supposed to be secure but were later found to have been flawed. A protocol with heuristic security analysis cannot completely specify all possible security attacks that it wants to resist, and therefore its security is not guaranteed; accordingly, provable security is desirable. In recent years, significant progress in provable security has been made, and provable security is considered to be indispensable to password authenticated key exchange protocols.

　　In 1992, Bellovin and Merritt first proposed two-party password authenticated key exchange protocols. Since then numerous two-party PAKE protocols have been proposed to meet various desirable security and performance requirements. Furthermore, some recently proposed two-party PAKE protocols have provided formal proofs for their security. Hence, research on two-party PAKE is quite advanced. Even so, this thesis will propose a provably secure two-party PAKE protocol, which represents an improvement on both the MDHEKE protocol of Steiner et al. and the DHEKE2 protocol of Bellare et al.

　　Compared with two-party PAKE, three-party PAKE provides more efficient key management for user-to-user communications. In 1989, the first three-party PAKE protocol was proposed, since then numerous three-party PAKE protocols have been presented. However, a three-party PAKE protocol that provides provable security rather than heuristic security has not yet been proposed. For preventing password guessing attacks, almost all proposed three-party PAKE protocols use a server public key to encrypt passwords. The use of a server public key by employing a public-key cryptosystem facilitates the design and analysis of protocols. However, it also raises authentication and storage problems of the server public key to the protocol. Steiner et al. proposed a three-party PAKE protocol that did not use a server public key. However, Ding and Horster later showed that the three-party PAKE protocol of Steiner et al. is not resistant to undetectable on-line password guessing attacks. Following this line of research, this thesis will also

1. show that Steiner et al.’s three-party PAKE protocol is also vulnerable to an off-line password guessing attack;
2. propose a three-party PAKE protocol with a server public key, which so far is the most efficient one among previously proposed three-party PAKE protocols;
3. propose a three-party PAKE protocol without a server public key, which is the only one that is secure and does not use a server public key;
4. follow the formal proof by Bellare and Rogaway in 1995 for three-party AKE security and the formal proof by Bellare, Pointcheval and Rogaway in 2000 for two-party PAKE security to rigorously construct security proofs for the foregoing two proposed three-party PAKE protocols.

[1] M. Bellare, R. Canetti and H. Krawczyk, “Keying hash functions for message authentication,” Advances in Cryptology – CRYPTO’96, pp. 1–15, 1996.

[2] M. Bellare, R. Canetti and H. Krawczyk, “A modular approach to the design and analysis of authentication and key exchange protocols,” Proc. of the 30th Annual ACM Symposium on the Theory of Computing, pp. 419–428, 1998

[3] M. Bellare, A. Desai, D. Pointcheval and P. Rogaway, “Relations among notions of security for public-key encryption schemes,” Advances in Cryptology – CRYPTO’98, pp. 26–45, 1998.

[4] M. Bellare, D. Pointcheval and P. Rogaway, “Authenticated key exchange secure against dictionary attack,” Advances in Cryptology – EUROCRYPT’00, pp. 122–138, 2000.

[5] M. Bellare and P. Rogaway, “Entity authentication and key distribution,” Advances in Cryptology – CRYPTO’93, pp. 232–249, 1993.

[6] M. Bellare and P. Rogaway, “Provably secure session key distribution – the three party case,” Proc. of the 27th ACM Symposium on the Theory of Computing, pp. 57–66, May 1995.

[7] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” Proc. of the First ACM Conference on Computer and Communications Security, pp. 62–73, November 1993.

[8] S. M. Bellovin and M. Merritt, “Encrypted key exchange: password-based protocols secure against dictionary attacks,” IEEE Symposium on Research in Security and Privacy, pp. 72–84, 1992.

[9] S. M. Bellovin and M. Merritt, “Augmented encrypted key exchange: a password based protocol secure against dictionary attacks and password file compromise,”Proc. of the First ACM Conference on Computer and Communications Security, pp. 244–250, 1993.

[10] J. Black and P. Rogaway, “Cipher with arbitrary finite domains,” Proc. of the RSA Cryptographer’s Track, pp. 114–130, 2002.

[11] S. Blake-Wilson and A. Menezes, “Authenticated Diffie-Hellman key agreement protocols,” Proc. of the 5th Annual Workshop on Selected Areas in Cryptography (SAC’98), pp. 339–361, 1998.

[12] D. Boneh, “The decision Diffie-Hellman problem,” Proc. of Third Algorithmic Number Theory Symposium, pp. 48–63, 1998.

[13] M. Boyarsky, “Public-key cryptography and password protocols: The multi-user case,” Proc. of the 6th ACM Conference on Computer and Communication Security, pp. 63–72, 1999.

[14] V. Boyko, P. MacKenzie and S. Patel, “Provably secure password-authenticated key exchange using Diffie-Hellman,” Advances in Cryptology – EUROCRYPT’00, pp. 156–171, 2000.

[15] E. Bresson, O. Chevassut and D. Pointcheval, “Provably authenticated group Diffie-Hellman key exchange - the dynamic case,” Advances in Cryptology – ASIACRYPT’01, pp. 290–309, 2001.

[16] E. Bresson, O. Chevassut and D. Pointcheval, “Dynamic group Diffie-Hellman key exchange under standard assumptions,” Advances in Cryptology – EUROCRYPT’02, pp. 321–336, 2002.

[17] E. Bresson, O. Chevassut and D. Pointcheval, “Group Diffie-Hellman key exchange secure against dictionnary attacks,” Advances in Cryptology – ASIACRYPT’02, pp. 497–514, 2002.

[18] E. Bresson, O. Chevassut, D. Pointcheval and J. J. Quisquater, “Provably authenticated group Diffie-Hellman key exchange,” Proc. of the 8th ACM conference on Computer and Communications Security, pp. 255–264, 2001.

[19] R. Canetti, O. Goldreich and S. Halevi, “The random oracle methodology, revisited,” Proc. of the 30th Annual ACM Symposium on Theory of Computing, pp. 209–218, 1998.

[20] R. Canetti and H. Krawczyk, “Analysis of key-exchange protocols and their use for building secure channels,” Advances in Cryptology – EUROCRYPT’01, pp. 453–474, 2001.

[21] R. Cramer and V. Shoup, “A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack,” Advances in Cryptology – CRYPTO’98, pp. 13–25, 1998.

[22] D. E. Denning and M. S. Sacco, “Timestamps in key distribution protocols,”Communications of the ACM, Vol. 24, No. 7, pp. 533–536, August 1981.

[23] W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, Vol. 22, No. 6, pp. 644–654, 1976.

[24] Y. Ding and P. Horster, “Undetectable on-line password guessing attacks,” ACM Operating Systems Review, Vol. 29, No. 4, pp. 77–86, 1995.

[25] D. Dolev, C. Dwork and M. Naor, “Non-malleable cryptography (extended abstract),” Proc. of the Twenty Third Annual ACM Symposium on Theory of Computing, pp. 542–552, May 1991.

[26] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithm,” IEEE Transactions on Information Theory, pp. 469–472, 1985.

[27] O. Goldreich and Y. Lindell, “Session-key generation using human passwords only,” Advances in Cryptology – CRYPTO’01, pp. 408–432, 2001.

[28] S. Goldwasser and S. Micali, “Probabilistic encryption,” Journal of Computer and System Sciences, Vol. 28, No. 2, pp. 270–299, April 1984.

[29] S. Goldwasser, S. Micali and C. Racko, “The knowledge complexity of interactive proof systems,” SIAM Journal on Computing, Vol. 18, No. 1, pp. 186–208, February 1989.

[30] L. Gong, “Optimal authentication protocols resistant to password guessing attacks,” Proc. of the 8th IEEE Computer Security oundation Workshop, pp. 24–29, 1995.

[31] L. Gong, M. Lomas, R. Needham and J. Saltzer, “Protecting poorly chosen secrets from guessing attacks,” IEEE Journal on Selected Areas in Communications, Vol. 11, No. 5, pp. 648–656, 1993.

[32] S. Halevi and H. Krawczyk, “Public-key cryptography and password protocols,” ACM Transactions on Information and System Security, Vol. 2, No. 3, pp. 25–60, 1999.

[33] D. Jablon, “Strong password-only authenticated key exchange,” ACM Computer Communications Review, Vol. 20, No. 5, pp. 5–26, 1996.

[34] D. Jablon, “Extended password key exchange protocols immune to dictionary attack,” Proc. of the WETICE’97 Workshop on Enterprise Security, pp. 248–255, June 1997.

[35] B. Jaspan, “Dual-workfactor encrypted key exchange: eciently preventing password chaining and dictionary attacks,” Proc. of the Sixth Annual USENIX Security Conference, pp. 43–50, 1996.

[36] J. Katz, R. Ostrovsky and M. Yung, “Efficient password-authenticated key exchange using human-memorable passwords,” Advances in Cryptology – EUROCRYPT’01, pp. 475–494, 2001.

[37] J. Katz and M. Yung, “Complete characterization of security notions for probabilistic private-key encryption,” Proc. of the 32nd Annual ACM Symposium on Theory of Computing, pp. 245–254, 2000.

[38] T. Kwon, M. Kang, S. Jung and J. Song, “An improvement of the password-based authentication protocol (K1P) on security against replay attacks,” IEICE Transactions on Communications, Vol. E82-B, No. 7, pp. 991–997, 1999.

[39] T. Kwon, M. Kang and J. Song, “An adaptable and reliable authentication protocol for communication networks,” Proc. of IEEE INFOCOM’97, pp. 737–744, 1997.

[40] T. Kwon and J. Song, “Secure agreement scheme for gxy via password authentication,” Electronics Letters, Vol. 35, No. 11, pp. 892–893, 1999.

[41] C. L. Lin, H. M. Sun, and T. Hwang, “Three-party encrypted key exchange: Attacks and a solution,” ACM Operating Systems Review, Vol. 34, No. 4, pp. 12–20, 2000.

[42] C. L. Lin, H. M. Sun, M. Steiner and T. Hwang, “Three-party encrypted key exchange without server public-keys,” IEEE Communications Letters, Vol. 5, No. 12, pp. 497–499, December 2001.

[43] T. M. A. Lomas, L. Gong, J. H. Saltzer and R. M. Needham, “Reducing risks from poorly chosen keys,” ACM Operating Systems Review, Vol. 23, No. 5, pp. 14–18, December 1989.

[44] S. Lucks, “Open key exchange: how to defeat dictionary attacks without encrypting public keys,” Proc. of the Workshop on Security Protocols, pp. 79–90, 1997.

[45] P. MacKenzie, “More ecient password authenticated key exchange,” RSA Conference’01, pp. 361–377, 2001.

[46] P. MacKenzie, S. Patel and R. Swaminathan, “Password-authenticated key exchange based on RSA,” Advances in Cryptology – ASIACRYPT’00, pp. 599–613, 2000.

[47] P. MacKenzie, T. Shrimpton and M. Jakobsson, “Threshold passwordauthenticated key exchange,” Advances in Cryptology – CRYPTO’02, pp. 385–400, 2002.

[48] S. Micali, C. Racko and R. H. Sloan, “The notion of security for probabilistic cryptosystems,” SIAM Journal on Computing, Vol. 17, No. 2, pp. 412–426, April 1988.

[49] R. Morris and K. Thompson, “Password security: a case history,” Communications of the ACM, pp. 594–597, 1979.

[50] M. Naor and O. Reingold, “Number-theoretic constructions of ecient pseudorandom functions,” Proc. of 38th FOCS, pp. 458–467, 1997.

[51] R. M. Needham and M. D. Schroeder, “Using encryption for authentication in large networks of computers,” Communications of the ACM, Vol. 21, No. 12, pp. 993–999, December 1978.

[52] R. M. Needham and M. D. Schroeder, “Authentication revisited,” ACM Operating Systems Review, Vol. 21, No. 1, pp. 7, January 1987.

[53] National Institute of Standards and Technology (NIST), “Announcement of weakness in the secure hash standard”, 1994.

[54] National Institute of Standards and Technology (NIST), “Advanced encryption standard,” December 2000, http://www.nist.gov/aes.

[55] R. L. Rivest, “RFC 1321: the MD5 message-digest algorithm”, Internet Activities Board, 1992.

[56] R. L. Rivest, A. Shamir and L. Adleman, “A method of obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, No. 2, pp. 120–126, February 1978.

[57] V. Shoup, “On formal models for secure key exchange (version 4),” Research Report, IBM Research, Number RZ 3120, November 1999.

[58] M. Steiner, P. Buhler, T. Eirich and M. Waidner, “Secure password-based cipher suite for TLS,” ACM Transactions on Information and System Security, Vol. 4, No. 2, pp. 134–157, 2001.

[59] J. G. Steiner, C. Neuman and J. I. Schiller, “Kerberos: an authentication service for open network systems,” Proc. of the USENIX Winter Conference, pp. 191–202, February 1988.

[60] M. Steiner, G. Tsudik and M. Waidner, “Refinement and extension of encrypted key exchange,” ACM Operating Systems Review, Vol. 29, No. 3, pp. 22–30, 1995.

[61] T. Wu, “The secure remote password protocol,” Proc. of the 1998 Internet Society Network and Distributed System Security Symposium, pp. 97–111, 1998.