Abstract
Password-Authenticated Key Exchange (PAKE) protocols enable two or more parties to use human-memorable passwords for authentication and key exchange. Since the human-memorable passwords are vulnerable to off-line dictionary attacks, PAKE protocols should be very carefully designed to resist dictionary attacks. However, designing PAKE protocols against dictionary attacks proved to be quite tricky. In this paper, we analyze two PAKE protocols and show that they are subject to dictionary attacks. The analyzed protocols are EPA which was proposed in ACISP 2003 and AMP which is a contribution for P1363. Our attack is based on the small factors of the order of a large group \({\mathbb Z_p^*}\) (i.e., the DLP of subgroup attack), by which the secret password can be fully discovered. We intend to emphasize that our attack is valid since the protocols neither select secure parameter p nor check the order of received values for achieving good efficiency.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anderson, R., Vaudenay, S.: Minding Your p’s and q’s. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 236–247. Springer, Heidelberg (1995)
Bao, F.: Security Analysis of a Password Authenticated Key Exchange Protocol. In: Boyd, C., Mao, W. (eds.) ISC 2003. LNCS, vol. 2851, pp. 208–217. Springer, Heidelberg (2003)
Bleichenbacher, D.: Generating ElGamal Signatures without Knowing the Secret. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 10–18. Springer, Heidelberg (1996)
Bellovin, S., Merritt, M.: Encrypted Key Exchange: Password-based Protocols Secure Against Dictionary Attacks. In: Proceedings of IEEE Symposium on Security and Privacy, pp. 72–84 (1992)
Bellovin, S., Merritt, M.: Augumented Encrypted Key Exchange: A Password-based Protocol Secure Against Dictionary Attacks and Password File Compromise. In: Proceedings of CCS 1993, pp. 244–250 (1993)
Boyko, V., MacKenzie, P., Patel, S.: Provably-secure Password Anthentiation and Key Exchange Using Diffie-Hellman. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 156–171. Springer, Heidelberg (2000)
Gong, L.: Optimal Authentication Protocols Resistant to Password Guessing Attacks. In: 8th IEEE Computer Security Foundations Workshop, pp. 24–29 (1995)
Hwang, Y.H., Yum, D.H., Lee, P.J.: EPA: An Efficient Password-Based Protocol for Authenticated Key Exchange. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 452–463. Springer, Heidelberg (2003)
Jablon, D.: Strong Password-Only Authenticated Key Exchange. ACM Computer Communications Review 26(5) (1996)
Kwon, T.: Authentication and Key Agreement via Memorable Password. In: Proceedings of the ISOC NDSS Symposium (2001)
Kwon, T.: Summary of AMP, Contribution for the P1363 standard (August 2003), available at http://grouper.ieee.org/groups/1363/passwdPK/contributions/ampsummary.pdf
Kwon, T.: Addendum to Summary of AMP, Contribution for the P1363 standard (November 2003), available at http://grouper.ieee.org/groups/1363/passwdPK/contributions/ampsummary2.pdf
Lim, C.H., Lee, P.J.: A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 249–263. Springer, Heidelberg (1997)
Lucks, S.: Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys. In: Christianson, B., Lomas, M. (eds.) Security Protocols 1997. LNCS, vol. 1361, pp. 79–90. Springer, Heidelberg (1998)
MacKenzie, P., Patel, S., Swaminathan, R.: Password-Authenticated Key Exchange Based on RSA. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 599–613. Springer, Heidelberg (2000)
MacKenzie, P.: The PAK Suite: Protocols for Password-Authenticated Key Exchange, Submission to IEEE P1363.2 (April 2002)
MacKenzie, P.: More Efficient Password-Authenticated Key Exchange. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 361–377. Springer, Heidelberg (2001)
Mao, W., Lim, C.H.: Cryptanalysis in Prime Order Subgroups of Z∗n. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 214–226. Springer, Heidelberg (1998)
Patel, S.: Number Theoretic Attacks on Secure Password Schemes. In: Proceedings of IEEE Symposium on Research in Security and Privacy, pp. 236–247 (1997)
Pavlovski, C., Boyd, C.: Attacks Based on Small Factors in Various Group Structures. In: Varadharajan, V., Mu, Y. (eds.) ACISP 2001. LNCS, vol. 2119, pp. 36–50. Springer, Heidelberg (2001)
Pohlig, S., Hellman, M.: An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance. IEEE Transactions on Information Theory 24(1), 106–110 (1978)
Pollard, J.M.: Monte Carlo Methods for Index Computation (mod p). Math. Comp. 32(143), 918–924 (1978)
van Oorschot, P.C., Wiener, M.: On Diffie-Hellman Key Agreement with Short Exponents. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 332–343. Springer, Heidelberg (1996)
Vaudenay, S.: Hidden Collisions on DSS. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 83–88. Springer, Heidelberg (1996)
Wu, T.: Secure Remote Password Protocol. In: ISOC Network and Distributed System Security Symposium (1998)
Zhu, F., Wong, D.S., Chan, A.H., Ye, R.: Password authenticated key exchange based on RSA for imbalanced wireless networks. In: Chan, A.H., Gligor, V.D. (eds.) ISC 2002. LNCS, vol. 2433, pp. 150–161. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wan, Z., Wang, S. (2004). Cryptanalysis of Two Password-Authenticated Key Exchange Protocols. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds) Information Security and Privacy. ACISP 2004. Lecture Notes in Computer Science, vol 3108. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27800-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-27800-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22379-5
Online ISBN: 978-3-540-27800-9
eBook Packages: Springer Book Archive