Abstract
Proofs are invaluable tools in assuring protocol implementers about the security properties of protocols. However, several instances of undetected flaws in the proofs of protocols (resulting in flawed protocols) undermine the credibility of provably-secure protocols. In this work, we examine several protocols with claimed proofs of security by Boyd & González Nieto (2003), Jakobsson & Pointcheval (2001), and Wong & Chan (2001), and an authenticator by Bellare, Canetti, & Krawczyk (1998). Using these protocols as case studies, we reveal previously unpublished flaws in these protocols and their proofs. We hope our analysis will enable similar mistakes to be avoided in the future.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
An, J.H., Dodis, Y., Rabin, T.: On the Security of Joint Signature and Encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83–107. Springer, Heidelberg (2002)
Bellare, M., Canetti, R., Krawczyk, H.: A Modular Approach to The Design and Analysis of Authentication and Key Exchange Protocols. In: STOC 1998, pp. 419–428. ACM Press, New York (1998)
Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated Key Exchange Secure Against Dictionary Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000)
Bellare, M., Rogaway, P.: Entity Authentication and Key Distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)
Bellare, M., Rogaway, P.: Provably Secure Session Key Distribution: The Three Party Case. In: STOC 1995, pp. 57–66. ACM Press, New York (1995)
Bleichenbacher, D.: Breaking a Cryptographic Protocol with Pseudoprimes. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 9–15. Springer, Heidelberg (2005)
Boyd, C., Mathuria, A.: Protocols for Authentication and Key Establishment. Springer, Heidelberg (2003)
Boyd, C., González Nieto, J.M.: Round-optimal Contributory Conference Key Agreement. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 161–174. Springer, Heidelberg (2002)
Bresson, E., Chevassut, O., Pointcheval, D.: Provably Authenticated Group Diffie–Hellman Key Exchange — The Dynamic Case. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 209–223. Springer, Heidelberg (2001)
Canetti, R., Krawczyk, H.: Analysis of key-exchange protocols and their use for building secure channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, p. 453–474. Springer, Heidelberg (2001); (Extended version available from http://eprint.iacr.org/2001/040/ )
Choo, K.-K.R., Boyd, C., Hitchcock, Y.: On Session Key Construction in Provably Secure Protocols. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 116–131. Springer, Heidelberg (2005); (Extended version available from http://eprint.iacr.org/2005/206 )
Diffie, W., van Oorschot, P.C., Wiener, M.J.: Authentication and Authenticated Key Exchange. Journal of Designs, Codes and Cryptography, 107–125 (1992)
Dolev, D., Yao, A.C.: On the Security of Public Key Protocols. IEEE Transaction of Information Technology, 198–208 (1983)
Goldwasser, S., Micali, S.: Probabilisitic Encryption. Journal of Computer and System Sciences, 270–299 (1984)
Hitchcock, Y., Tin, Y.-S.T., Boyd, C., González Nieto, J.M.: Tripartite Key Exchange in the Canetti-Krawczyk Proof Model. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 17–32. Springer, Heidelberg (2004); (Extended version available from http://sky.fit.qut.edu.au/~boydc/papers/ )
Hitchcock, Y., Tin, Y.-S.T., Boyd, C., González Nieto, J.M., Montague, P.: A Password-Based Authenticator: Security Proof and Applications. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 388–401. Springer, Heidelberg (2003)
Hwang, Y.H., Yum, D.H., Lee, P.J.: EPA: An Efficient Password-Based Protocal for Authenticated Key Exchange. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727. Springer, Heidelberg (2003)
Jakobsson, M., Pointcheval, D.: Mutual Authentication and Key Exchange Protocol for Low Power Devices. In: Syverson, P.F. (ed.) FC 2001. LNCS, vol. 2339, pp. 169–186. Springer, Heidelberg (2002)
Kaliski, B.S.: An Unknown Key-Share Attack on the MQV Key Agreement Protocol. ACM Transactions on Information and System Security (TISSEC), 275–288 (2001)
Koblitz, N., Menezes, A.: Another Look at Provable Security. Technical report CORR 2004-20, Centre for Applied Cryptographic Research, University of Waterloo, Canada (2004)
Krawczyk, H.: SKEME: A Versatile Secure Key Exchange Mechanism for Internet. In: NDSS 1996, pp. 114–127. IEEE Internet Society Press, Los Alamitos (1996)
Krawczyk, H.: HMQV: A High-Performance Secure Diffie-Hellman Protocol. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 546–566. Springer, Heidelberg (2005); (Extended version available from http://eprint.iacr.org/2005/176/ )
Kwon, T.: Authentication and Key Agreement via Memorable Passwords. In: Juels, A., Brainard, J. (eds.) NDSS 2001. Internet Society Press (2001)
Rogaway, P.: On the Role Definitions in and Beyond Cryptography. In: Maher, M.J. (ed.) ASIAN 2004. LNCS, vol. 3321, pp. 13–32. Springer, Heidelberg (2004)
Wan, Z., Wang, S.: Cryptanalysis of Two Password-Authenticated Key Exchange Protocols. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 164–175. Springer, Heidelberg (2004)
Wong, D.S., Chan, A.H.: Efficient and Mutually Authenticated Key Exchange for Low Power Computing Devices. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 272–289. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Choo, KK.R., Boyd, C., Hitchcock, Y. (2005). Errors in Computational Complexity Proofs for Protocols. In: Roy, B. (eds) Advances in Cryptology - ASIACRYPT 2005. ASIACRYPT 2005. Lecture Notes in Computer Science, vol 3788. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11593447_34
Download citation
DOI: https://doi.org/10.1007/11593447_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30684-9
Online ISBN: 978-3-540-32267-2
eBook Packages: Computer ScienceComputer Science (R0)