Analysis of cryptographic protocols using logics of belief: an overview

Authors

  • David Monniaux Ecole Normale Superieure, Paris, France

DOI:

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

Keywords:

cryptographic protocols, logics of belief, BAN, GNY, decidability

Abstract

When designing a cryptographic protocol or explaining it, one often uses arguments such as "since this message was signed by machine B, machine A can be sure it came from B" in informal proofs justifying how the protocol works. Since it is, in such informal proofs, often easy to overlook an essential assumption, such as a trust relation or the belief that a message is not a replay from a previous session, it seems desirable to write such proofs in a formal system. While such logics do not replace the recent techniques of automatic proofs of safety properties, they help in pointing the weaknesses of the system. In this paper, we present briefly the BAN (Burrows-Abadi-Needham) formal system [10, 11] as well as some derivative. We show how to prove some properties of a simple protocol, as well as detecting undesirable assumptions. We then explain how the manual search for proofs can be made automatic. Finally, we explain how the lack of proper semantics can be a bit worrying.

Downloads

Download data is not yet available.

References

[1] M. Abadi and A. D. Gordon, "A calculus for cryptographic protocols: the spi calculus", in ACM Conf. Comput. Commun. Secur., 1997, pp. 36-47.
View in Google Scholar

[2] M. Abadi and A. D. Gordon, "Reasoning about cryptographic protocols in the spi calculus", in CONCUR'97, Concurrency Theory, 8th International Conference, A. Mazurkiewicz and J. Winkowski, Eds., Lecture Notes in Computer Science. Springer, 1997, vol. 1243, pp. 59-73.
View in Google Scholar

[3] M. Abadi and A. D. Gordon, "A calculus for cryptographic protocols: the spi calculus". Res. Rep. 149, Compaq Systems Research Center, Palo Alto, CA, USA, Jan. 1998.
View in Google Scholar

[4] M. Abadi and M. R. Tuttle, "A semantic for a logic of authentication", in 10th Annual ACM Symposium on Principles of Distributed Computing, L. Logrippo, Ed. ACM Press, 1991, pp. 201-216.
View in Google Scholar

[5] R. Amadio and D. Lugiez, "On the reachability problem in cryptographic protocols". Res. Rep. 3915, INRIA, 2000.
View in Google Scholar

[6] R. Amadio and D. Lugiez, "On the reachability problem in cryptographic protocols", in CONCUR'00, Lecture Notes in Computer Science. Springer, 2000, vol. 1877.
View in Google Scholar

[7] F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman, "Magic sets and other strange ways to implement logic programs (extended abstract)", in International Conference on Management of Data and Symposium on Principles of Database Systems. ACM, 1986.
View in Google Scholar

[8] D. A. Basin, "Lazy infinite-state analysis of security protocols", in Secure Networking - CQRE (Secure) '99, International Exhibition and Congress, R. Baumgart, Ed., Lecture Notes in Computer Science. Springer, 1999, vol. 1740, pp. 30-42.
View in Google Scholar

[9] P. Bieber, "A logic of communication in hostile environment", in Comput. Secur. Found. Worksh. (III), 1990, pp. 14-22.
View in Google Scholar

[10] M. Burrows, M. Abadi, and R. Needham, "A logic of authentication". Tech. Rep. 39, Digital Equipment Corporation, Systems Research Centre, Febr. 1989.
View in Google Scholar

[11] M. Burrows, M. Abadi, and R. Needham, "A logic of authentication", ACM Trans. Comput. Syst., vol. 8, no. 1, pp. 18-36, 1990.
View in Google Scholar

[12] A. Church, "An unsolvable problem of elementary number theory", Am. J. Math., vol. 58, no. 2, pp. 345-363, 1936.
View in Google Scholar

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

[14] N. Durgin, P. Lincoln, J. Mitchell, and A. Scedrov, "Undecidability of bounded security protocols", in Proc. Worksh. Form. Meth. Secur. Protoc. (FMSP), N. Heintze and E. Clarke, Eds., 1999.
View in Google Scholar

[15] J. Y. Girard, Proof and Types. Cambridge University Press, 1990. (Translated and with appendices by Paul Taylor, Yves Lafont).
View in Google Scholar

[16] L. Gong, "Cryptographic protocols for distributed systems". Ph.D. thesis, University of Cambridge, Cambridge, England, April 1990.
View in Google Scholar

[17] L. Gong, R. Needham, and R. Yahalom, "Reasoning about belief in cryptographic protocols", in IEEE Symposium on Research in Security and Privacy. IEEE Computer Society Press, 1990, pp. 234-248.
View in Google Scholar

[18] J. Hintikka, Knowledge and Belief: An Introduction to the Logic of Two Notions. Cornell University Press, 1962.
View in Google Scholar

[19] D. Kindred and J. M. Wing, "Fast, automatic checking of security protocols", in Second USENIX Workshop on Electronic Commerce. USENIX, 1996, pp. 41-52.
View in Google Scholar

[20] C. Meadows, "The NRL protocol analyzer: an overview", J. Log. Program., 1995 (to appear).
View in Google Scholar

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

[22] S. P. Miller, B. C. Neuman, J. I. Schiller, and J. H. Saltzer, "Kerberos authentication and authorization system", in Project Athena Technical Plan. MIT, 1987, ch. E.2.1.
View in Google Scholar

[23] D. Monniaux, "Decision procedures for the analysis of cryptographic protocols by logics of belief", in 12th Computer Security Foundations Workshop. IEEE, 1999.
View in Google Scholar

[24] R. M. Needham and M. D. Schroeder, "Using encryption for authentication in large networks of computers", Commun. ACM, vol. 21, no. 12, 1978.
View in Google Scholar

[25] D. Nessett, "A critique of the Burrows, Abadi and Needham logic", ACM Oper. Syst. Rev., vol. 24, no. 2, pp. 35-38, 1990.
View in Google Scholar

[26] L. C. Paulson, "Proving properties of security protocols by induction", in 10th Computer Security Foundations Workshop. IEEE Computer Society Press, 1997, pp. 70-83.
View in Google Scholar

[27] D. Prawitz, Natural Deduction: a Proof-Theoretical Study. Almqvist & Wiksell, Stockholm, 1965.
View in Google Scholar

[28] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key cryptosystems", in SIMMONS: Secure Communications and Asymmetric Cryptosystems, 1982.
View in Google Scholar

[29] M. Rusinowitch and M. Turuani, "Protocol insecurity with finite number of sessions is NP-complete", in 14th IEEE Comput. Secur. Found. Worksh., Cape Breton, Nova Scotia, Canada, June 2001.
View in Google Scholar

[30] B. Schneier, Applied Cryptography. 2 ed. Wiley, 1996.
View in Google Scholar

[31] J. Schumann, "Automatic verification of cryptographic protocols with SETHEO", in Proceedings of the 14th International Conference on Automated Deduction, W. McCune, Ed., Lecture Notes in Artificial Intelligence. Berlin: Springer, 1997, vol. 1249, pp. 87-100.
View in Google Scholar

[32] D. Song, "Athena: a new efficient automatic checker for security protocol analysis", in 12th Computer Security Foundations Workshop. IEEE, 1999.
View in Google Scholar

[33] P. Syverson, "Adding time to a logic of authentication", in 1st ACM Conf. Comput. Commun. Secur., 1993, pp. 97-101.
View in Google Scholar

[34] P. Syverson and P. C. van Oorschot, "On unifying some cryptographic protocol logics", in 1994 IEEE Comput. Soc. Symp. Res. Secur. Priv., May 1994, pp. 14-28.
View in Google Scholar

[35] P. Syverson, "Towards a strand semantics for authentication logics", in Electronic Notes in Theoretical Computer Science. 1999, vol. 20.
View in Google Scholar

[36] P. Syverson and I. Cervesato, "The logic of authentication protocols", in FOSAD'00, R. Focardi and R. Gorrieri, Eds. Springer, 2001, vol. 2171.
View in Google Scholar

[37] A. Tarski, "What is elementary geometry?", in The Axiomatic Method, with Special Reference to Geometry and Physics, P. Suppes and A. Tarski, Eds., Studies in Logic and the Foundations of Mathematics. North-Holland, 1959, pp. 16-29.
View in Google Scholar

Downloads

Published

2002-12-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
D. Monniaux, “Analysis of cryptographic protocols using logics of belief: an overview”, JTIT, vol. 10, no. 4, pp. 57–67, Dec. 2002, doi: 10.26636/jtit.2002.4.145.