Is it possible to decide whether a cryptographic protocol is secure or not?

Authors

  • Hubert Comon Ecole Normale Superieure de Cachan & CNRS
  • Vitaly Shmatikov SRI International, Menlo Park, CA, USA

DOI:

https://doi.org/10.26636/jtit.2002.4.149

Keywords:

cryptographic protocols, decision procedures, logic, security

Abstract

We consider the so called "cryptographic protocols" whose aim is to ensure some security properties when communication channels are not reliable. Such protocols usually rely on cryptographic primitives. Even if it is assumed that the cryptographic primitives are perfect, the security goals may not be achieved: the protocol itself may have weaknesses which can be exploited by an attacker. We survey recent work on decision techniques for the cryptographic protocol analysis.

Downloads

Download data is not yet available.

References

[1] M. Abadi, "Security protocols and their properties", in Foundations of Secure Computation, F. L. Bauer and R. Steinbrueggen, Eds. NATO Science Series, IOS Press 2000, pp. 39-60 (in 20th Int. Summer School Found. Secure Comput., Marktoberdorf, Germany, 1999).
View in Google Scholar

[2] M. Abadi and A. Gordon, "A calculus for cryptographic protocols: the spi calculus", Inform. Comput., vol. 148, no. 1, pp. 1-70, 1999.
View in Google Scholar

[3] M. Abadi and R. Needham, "Prudent engineering practice for cryptographic protocols", IEEE Trans. Softw. Eng., vol. 22, no. 1, pp. 6-15, 1996.
View in Google Scholar

[4] R. Amadio and D. Lugiez, "On the reachability problem in cryptographic protocols", in Proc. CONCUR, Lecture Notes in Computer Science. Springer, 2000, vol. 1877, pp. 380-394.
View in Google Scholar

[5] R. Amadio, D. Lugiez, and V. Vanackere, "On the symbolic reduction of processes with cryptographic functions". Tech. Rep. 4147, INRIA, March 2001.
View in Google Scholar

[6] D. Bolignano, "Towards a mechanization of cryptographic protocol verification", in Proc. 9th Int. Conf. Comput. Aid. Verif. (CAV), 1997, pp. 131-142.
View in Google Scholar

[7] D. Bolignano, "Integrating proof-based and model-checking techniques for the formal verification of cryptographic protocols", in Proc. 10th Int. Conf. Comput. Aid. Verif. (CAV), 1998, pp. 77-87.
View in Google Scholar

[8] M. Boreale, "Symbolic trace analysis of cryptographic protocols", in Proc. 28th International Conference on Automata Languages and Programming (ICALP), Lecture Notes in Computer Science. Springer, 2001, vol. 2076, pp. 667-681.
View in Google Scholar

[9] R. Canetti, "A unified framework for analyzing security of protocols". IACR Cryptology ePrint Archive 2000/067, Dec. 2000.
View in Google Scholar

[10] I. Cervesato, N. Durgin, P. D. Lincoln, J. C. Mitchell, and A. Scedrov, "A meta-notation for protocol analysis", in Proc. 12th IEEE Comput. Secur. Found. Worksh., 1999, pp. 55-69.
View in Google Scholar

[11] I. Cervesato, N. Durgin, P. D. Lincoln, J. C. Mitchell, and A. Scedrov, "Relating strands and multiset rewriting for security protocol analysis", in Proc. 13th IEEE Comput. Secur. Found. Worksh., 2000, pp. 35-51.
View in Google Scholar

[12] J. Clark and J. Jacob, "A survey of authentication protocol literature: version 1.0". Draft paper, 1997.
View in Google Scholar

[13] E. M. Clarke, S. Jha, and W. Marrero, "Verifying security protocols with Brutus", to appear in ACM Trans. Softw. Eng. Meth.
View in Google Scholar

[14] H. Comon, V. Cortier, and J. C. Mitchell, "Tree automata with memory, set constraints and ping pong protocols", in Proc. 28th International Conference on Automata Languages and Programming (ICALP), Lecture Notes in Computer Science. Springer, 2001, vol. 2076, pp. 682-693.
View in Google Scholar

[15] W. Charatonik and A. Podelski, "Set constraints with intersection", in Proc. IEEE Symp. Log. Comput. Sci., Warsaw, Poland, 1997.
View in Google Scholar

[16] W. Diffie and M. Hellman, "New directions in cryptography", IEEE Trans. Inform. Theory, vol. 22, no. 6, pp. 644-654, 1976.
View in Google Scholar

[17] N. Durgin, P. D. Lincoln, J. C. Mitchell, and A. Scedrov, "Undecidability of bounded security protocols", in Proc. FLOC Worksh. Form. Meth. Secur. Protoc., Trento, Italy, 1999.
View in Google Scholar

[18] D. Dolev and A. Yao, "On the security of public key protocols", IEEE Trans. Inform. Theory, vol. 29, no. 2, pp. 198-208, 1983.
View in Google Scholar

[19] M. Fiore and M. Abadi, "Computing symbolic models for verifying cryptographic protocols", in Proc. 14th IEEE Comput. Secur. Found. Worksh., 2001, pp. 160-173.
View in Google Scholar

[20] J. Goubault-Larrecq, "A method for automatic cryptographic protocol verification", in Fifth International Workshop on Formal Methods for Parallel Programming: Theory and Applications (FMPPTA 2000), D. Mery and B. Sanders, Eds., Lecture Notes in Computer Science. Springer, 2000, vol. 1800, pp. 977-984.
View in Google Scholar

[21] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography. CRC Press, 1997.
View in Google Scholar

[22] C. A. R. Hoare, Communicating Sequential Processes. Prentice-Hall, 1985.
View in Google Scholar

[23] M. Harrison, W. L. Ruzzo, and J. Ullman, "Protection in operating systems", Commun. ACM, no. 8, pp. 461-471, 1976.
View in Google Scholar

[24] A. Huima, "Efficient infinite-state analysis of security protocols", in Proc. FLOC Worksh. Form. Meth. Secur. Protoc., Trento, Italy, 1999.
View in Google Scholar

[25] J. T. Kohl and B. C. Neuman, "The Kerberos network authentication service (version 5)". Internet Request for Comments RFC-1510, Sept. 1993.
View in Google Scholar

[26] B. Lampson, "Protection", in Proc. 5th Princeton Conf. Inform. Sci. Syst., Princeton, 1971 (reprinted in ACM Oper. Syst. Rev., vol. 8, no. 1, pp. 18-24, 1974).
View in Google Scholar

[27] P. D. Lincoln, J. C. Mitchell, M. Mitchell, and A. Scedrov, "A probabilistic poly-time framework for protocol analysis", in Proc. 5th ACM Conf. Comput. Commun. Secur., 1998, pp. 112-121.
View in Google Scholar

[28] P. D. Lincoln, J. C. Mitchell, M. Mitchell, and A. Scedrov, "Probabilistic polynomial-time equivalence and security analysis", in Proc. Formal Methods'99, Lecture Notes in Computer Science. Springer, 1999, vol. 1708, pp. 776-793.
View in Google Scholar

[29] G. Lowe, "Breaking and fixing the Needham-Schroer public-key protocol using FDR", in Proc. Tools Algorithms for the Construction and Analysis Systems (TACAS '96), T. Margaria and B. Steffen, Eds., Lecture Notes in Computer Science. Springer, 1996, vol. 1055, pp. 147-166.
View in Google Scholar

[30] G. Lowe, "A hierarchy of authentication specifications", in Proc. 10th IEEE Comput. Secur. Found. Worksh., 1997, pp. 31-43.
View in Google Scholar

[31] G. Lowe, "Towards a completeness result for model checking of security protocols", J. Comput. Secur., vol. 7, no. 2-3, pp. 89-146, 1999.
View in Google Scholar

[32] B. Berard, M. Bidoit, F. Laroussinie, A. Petit, L. Petrucci, and P. Schnoelen, Systems and Software Verification. Model-Checking Techniques and Tools. Springer, 2001.
View in Google Scholar

[33] C. Meadows, "The NRL protocol analyzer: an overview", J. Log. Program., vol. 26, no. 2, pp. 113-131, 1996.
View in Google Scholar

[34] Z. Manna and A. Pnueli, Temporal Verification of Reactive Systems. Springer, 1995.
View in Google Scholar

[35] J. Millen and V. Shmatikov, "Constraint solving for bounded-process cryptographic protocol analysis", in Proc. 8th ACM Conf. Comput. Commun. Secur., 2001.
View in Google Scholar

[36] R. Milner, "Functions as processes", Math. Struct. Comput. Sci., no. 2, pp. 119-141, 1992.
View in Google Scholar

[37] J. C. Mitchell, M. Mitchell, and U. Stern, "Automated analysis of cryptographic protocols using murphi", in Proc. IEEE Symp. Secur. Priv., 1997, pp. 141-153.
View in Google Scholar

[38] D. Monniaux, "Abstracting cryptographic protocols with tree automata", in Proc. 6th International Static Analysis Symposium (SAS'99), Lecture Notes in Computer Science. Springer, 1999, vol. 1694.
View in Google Scholar

[39] "Announcement of weakness in the secure hash standard". National Institute of Standards and Technology (NIST), 1994.
View in Google Scholar

[40] R. Needham and M. Schroer, "Using encryption for authentication in large networks of computers", Commun. ACM, vol. 21, no. 12, pp. 993-999, 1978.
View in Google Scholar

[41] L. Paulson, "The inductive approach to verifying cryptographic protocols", J. Comput. Secur., no. 6, pp. 85-128, 1998.
View in Google Scholar

[42] B. Pfitzmann and M. Waidner, "Composition and integrity preservation of secure reactive systems", in Proc. 7th ACM Conf. Comput. Commun. Secur., 2000, pp. 245-254.
View in Google Scholar

[43] B. Pfitzmann and M. Waidner, "A model for asynchronous reactive systems and its application to secure message transmission". IBM Res. Rep. RZ 3304, Dec. 2000.
View in Google Scholar

[44] B. Pfitzmann and M. Waidner, "A model for asynchronous reactive systems and its application to secure message transmission", in Proc. IEEE Symp. Secur. Priv., 2001, pp. 184-200.
View in Google Scholar

[45] R. L. Rivest, RFC 1321: The MD5 Message-Digest Algorithm. Internet Engineering Task Force, 1992.
View in Google Scholar

[46] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Commun. ACM, vol. 21, no. 2, pp. 120-126, 1978.
View in Google Scholar

[47] A. W. Roscoe"Model-checking CSP", in A Classical Mind: Essays in Honor of C.A.R. Hoare. Prentice-Hall. 1994.
View in Google Scholar

[48] A. W. Roscoe"Modeling and verifying key-exchange protocols using CSP and FDR", in Proc. 8th IEEE Comput. Secur. Found. Worksh., 1995, pp. 98-107.
View in Google Scholar

[49] M. Rusinowitch and M. Turuani, "Protocol insecurity with finite number of sessions is NP-complete", in Proc. 14th IEEE Comput. Secur. Found. Worksh., 2001, pp. 174-190.
View in Google Scholar

[50] S. Schneider, "Security properties and CSP", in Proc. IEEE Symp. Secur. Priv., 1996, pp. 174-187.
View in Google Scholar

[51] D. Song, "Athena: a new efficient automatic checker for security protocol analysis", in Proc. 12th Comput. Secur. Found. Worksh., 1999, pp. 192-202.
View in Google Scholar

[52] A. Freier, P. Karlton, and P. Kocher, "The SSL protocol. Version 3.0".
View in Google Scholar

[53] S. D. Stoller, "A bound on attacks on payment protocols", in Proc. IEEE Log. Comput. Sci., 2001. Available as Tech. Rep. 537, Computer Science Dept., Indiana University, Febr. 2000.
View in Google Scholar

[54] F. J. Thayer Fabrega, J. C. Herzog, and J. D. Guttman, "Strand spaces: proving security protocol correct", J. Comput. Secur., no. 7, pp. 191-230, 1999.
View in Google Scholar

Downloads

Published

2002-12-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
H. Comon and V. Shmatikov, “Is it possible to decide whether a cryptographic protocol is secure or not?”, JTIT, vol. 10, no. 4, pp. 5–15, Dec. 2002, doi: 10.26636/jtit.2002.4.149.