Abstract
Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers only adversaries that can compose and replay messages, and decipher them with known keys. The Dolev-Yao model is a useful abstraction, but it suffers from some drawbacks: it cannot handle the adversary knowing protocol-specific information, and it cannot handle probabilistic notions, such as the adversary attempting to guess the keys. We show how we can analyze security protocols under different adversary models by using a logic with a notion of algorithmic knowledge. Roughly speaking, adversaries are assumed to use algorithms to compute their knowledge; adversary capabilities are captured by suitable restrictions on the algorithms used. We show how we can model the standard Dolev-Yao adversary in this setting, and how we can capture more general capabilities including protocol-specific knowledge and guesses.
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
Abadi, M., Fournet, C.: Mobile values, new names, and secure communication. In: Proceedings of the 28th ACM Symposium on Principles of Programming Languages (POPL 2001), pp. 104–115 (2001)
Abadi, M., Rogaway, P.: Reconciling two views of cryptography (the computational soundness of formal encryption). In: Watanabe, O., Hagiya, M., Ito, T., van Leeuwen, J., Mosses, P.D. (eds.) TCS 2000. LNCS, vol. 1872, pp. 3–22. Springer, Heidelberg (2000)
Abadi, M., Tuttle, M.R.: A semantics for a logic of authentication. In: Proc. 10th ACM Symp. on Principles of Distributed Computing, pp. 201–216 (1991)
Accorsi, R., Basin, D., Viganò, L.: Towards an awareness-based semantics for security protocol analysis. In: Goubault-Larrecq, J. (ed.) Electronic Notes in Theoretical Computer Science, vol. 55. Elsevier Science Publishers, Amsterdam (2001)
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)
Bieber, P.: A logic of communication in hostile environment. In: Proceedings of the Computer Security Foundations Workshop, pp. 14–22. IEEE Computer Society Press, Los Alamitos (1990)
Burrows, M., Abadi, M., Needham, R.: A logic of authentication. ACM Transactions on Computer Systems 8(1), 18–36 (1990)
Clarke, E.M., Jha, S., Marrero, W.: Using state space exploration and a natural deduction style message derivation engine to verify security protocols. In: Proceedings of the IFIP Working Conference on Programming Concepts and Methods, PROCOMET (1998)
Dolev, D., Yao, A.C.: On the security of public key protocols. IEEE Transactions on Information Theory 29(2), 198–208 (1983)
Durgin, N., Mitchell, J., Pavlovic, D.: A compositional logic for protocol correctness. In: Proceedings of the Computer Security Foundations Workshop, pp. 241–255. IEEE Computer Society Press, Los Alamitos (2001)
Even, S., Goldreich, O., Shamir, A.: On the security of ping-pong protocols when implemented using the RSA. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 58–72. Springer, Heidelberg (1986)
Fagin, R., Halpern, J.Y.: Belief, awareness, and limited reasoning. Artificial Intelligence 34, 39–76 (1988)
Fagin, R., Halpern, J.Y.: Reasoning about knowledge and probability. Journal of the ACM 41(2), 340–367 (1994)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge. The MIT Press, Cambridge (1995)
Gong, L., Needham, R., Yahalom, R.: Reasoning about belief in cryptographic protocols. In: Proc. IEEE Symposium on Security and Privacy, pp. 234–248 (May 1990)
Gordon, A.D., Jeffrey, A.: Authenticity by typing for security protocols. In: Proceedings of the 14th IEEE Computer Security Foundations Workshop (CSFW 2001), pp. 145–159. IEEE Computer Society Press, Los Alamitos (2001)
Halpern, J.Y., Moses, Y., Tuttle, M.R.: A knowledge-based analysis of zero knowledge. In: Proc. 20th ACM Symp. on Theory of Computing, pp. 132–147 (1988)
Halpern, J.Y., Tuttle, M.R.: Knowledge, probability, and adversaries. Journal of the ACM 40(4), 917–962 (1993)
Kripke, S.: A semantical analysis of modal logic I: normal modal propositional calculi. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 9, 67–96 (1963); Announced in Journal of Symbolic Logic 24, 323 (1959)
Lincoln, P., Mitchell, J.C., Mitchell, M., Scedrov, A.: A probabilistic poly-time framework for protocol analysis. In: Proceedings of the ACM Conference on Computer and Communications Security, pp. 112–121 (1998)
Lowe, G.: An attack on the Needham-Schroeder public-key authentication protocol. Information Processing Letters 56, 131–133 (1995)
Lowe, G.: Some new attacks upon security protocols. In: Proc. 9th IEEE Computer Security Foundations Workshop, pp. 162–169 (1996)
Lowe, G.: Analysing protocols subject to guessing attacks. In: Proceedings of the Workshop on Issues in the Theory of Security, WITS 2002 (2002)
Mao, W.: An augmentation of BAN-like logics. In: Proceedings of the 8th IEEE Computer Security Foundations Workshop, pp. 44–56. IEEE Computer Society Press, Los Alamitos (1995)
Meadows, C.: The NRL protocol analyzer: An overview. Journal of Logic Programming 26(2), 113–131 (1996)
Merritt, M., Wolper, P.: States of knowledge in cryptographic protocols. Unpublished manuscript (1985)
Millen, J.K., Clark, S.C., Freedman, S.B.: The Interrogator: Protocol security analysis. IEEE Transactions on Software Engineering 13(2), 274–288 (1987)
Mitchell, J., Mitchell, M., Stern, U.: Automated analysis of cryptographic protocols using murϕ. In: Proceedings of the IEEE Symposium on Research in Security and Privacy, pp. 141–151. IEEE Computer Society Press, Los Alamitos (1997)
Moore, J.H.: Protocol failures in cryptosystems. Proceedings of the IEEE 76(5), 594–602 (1988)
Moses, Y.: Resource-bounded knowledge. In: Vardi, M.Y. (ed.) Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge, pp. 261–276. Morgan Kaufmann, San Francisco (1988)
Needham, R.M., Schroeder, M.D.: Using encryption for authentication in large networks of computers. Communications of the ACM 21(12), 993–999 (1978)
Paulson, L.C.: The inductive approach to verifying cryptographic protocols. Journal of Computer Security 6(1/2), 85–128 (1998)
Ryan, P.Y.A., Schneider, S.A.: An attack on a recursive authentication protocol: A cautionary tale. Information Processing Letters 65(1), 7–10 (1998)
Stubblebine, S., Wright, R.: An authentication logic supporting synchronization, revocation, and recency. In: Proc. Third ACM Conference on Computer and Communications Security, pp. 95–105 (1996)
Syverson, P.: A logic for the analysis of cryptographic protocols. NRL Report 9305, Naval Research Laboratory (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halpern, J.Y., Pucella, R. (2003). Modeling Adversaries in a Logic for Security Protocol Analysis. In: Abdallah, A.E., Ryan, P., Schneider, S. (eds) Formal Aspects of Security. FASec 2002. Lecture Notes in Computer Science, vol 2629. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-40981-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-40981-6_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20693-4
Online ISBN: 978-3-540-40981-6
eBook Packages: Springer Book Archive