Finite Models in FOL-Based Crypto-Protocol Verification | SpringerLink
Skip to main content
Springer Nature Link
Log in

Finite Models in FOL-Based Crypto-Protocol Verification

  • Conference paper
Foundations and Applications of Security Analysis (ARSPA-WITS 2009)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 5511))

Abstract

Cryptographic protocols can only be secure under certain inequality assumptions. Axiomatizing these inequalities explicitly is problematic: stating too many inequalities may impair soundness of the verification approach. To address this issue, we investigate an alternative approach (based on first-order logic) that does not require inequalities to be axiomatized. A derivation of the negated security property exhibits a protocol attack, and absence of a derivation amounts to absence of the investigated kind of attack.

We establish a fragment of FOL strictly greater than Horn formulas in which the approach is sound. We then show how to use finite model generation in this context to prove the absence of attacks. To demonstrate its practicality, the approach is applied to several well-known protocols, including ones relying on non-trivial algebraic properties. We show that it can be used to deal with infinitely many principals (and thus sessions).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Paulson, L.C.: The inductive approach to verifying cryptographic protocols. Journal of Computer Security 6(1-2), 85–128 (1998)

    Article  Google Scholar 

  2. Nipkow, T., Paulson, L.C., Wenzel, M.: Isabelle/HOL – A Proof Assistant for Higher-Order Logic. LNCS, vol. 2283. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  3. Weidenbach, C.: Towards an automatic analysis of security protocols in first-order logic. In: Ganzinger, H. (ed.) CADE 1999. LNCS, vol. 1632, pp. 314–328. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  4. Blanchet, B.: An Efficient Cryptographic Protocol Verifier Based on Prolog Rules. In: CSFW-14, pp. 82–96. IEEE Computer Society, Los Alamitos (2001)

    Google Scholar 

  5. Jürjens, J.: A domain-specific language for cryptographic protocols based on streams. Journal of Logic and Algebraic Programming (JLAP) (2009)

    Google Scholar 

  6. Blanchet, B.: From secrecy to authenticity in security protocols. In: Hermenegildo, M.V., Puebla, G. (eds.) SAS 2002. LNCS, vol. 2477, pp. 342–359. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  7. Comon, H., Nieuwenhuis, R.: Induction = I-axiomatization + first-order consistency. Technical report, ENS Cachan (1998)

    Google Scholar 

  8. Steel, G., Bundy, A., Maidl, M.: Attacking a protocol for group key agreement by refuting incorrect inductive conjectures. In: Basin, D., Rusinowitch, M. (eds.) IJCAR 2004. LNCS, vol. 3097, pp. 137–151. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  9. Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)

    Book  MATH  Google Scholar 

  10. Adámek, J., Rosický, J.: Locally Presentable and Accessible Categories. London Math. Soc. Lect. Note Ser., vol. 189. Cambridge University Press, Cambridge (1994)

    Book  MATH  Google Scholar 

  11. Jürjens, J.: On a problem of Gabriel and Ulmer. Journal of Pure and Applied Algebra 158, 183–196 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  12. Schumann, J.: Automatic verification of cryptographic protocols with SETHEO. In: CADE (1999)

    Google Scholar 

  13. Comon-Lundh, H., Cortier, V.: Security properties: two agents are sufficient. Sci. Comput. Program. 50(1-3), 51–71 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  14. Cohen, E.: First-order verification of cryptographic protocols. Journal of Computer Security 11(2), 189–216 (2003)

    Article  Google Scholar 

  15. Lassez, J.L., Maher, M.J., Marriott, K.: Elimination of negation in term algebras. In: Tarlecki, A. (ed.) MFCS 1991. LNCS, vol. 520, pp. 1–16. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  16. Comon, H., Fernández, M.: Negation elimination in equational formulae. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629. Springer, Heidelberg (1992)

    Chapter  Google Scholar 

  17. Weber, T.: SAT-based Finite Model Generation for Higher-Order Logic. PhD thesis, Technische Universität München (2008)

    Google Scholar 

  18. RSA Laboratories: PKCS #1: RSA Cryptography Standard Version 2.1. (June 2002)

    Google Scholar 

  19. Institute of Electrical and Electronics Engineers: IEEE Std 802.11-1997 (1997)

    Google Scholar 

  20. Lowe, G.: An attack on the Needham-Schroeder public key authentication protocol. Information Processing Letters 56(3), 131–136 (1995)

    Article  MATH  Google Scholar 

  21. Sutcliffe, G., Suttner, C.B.: The TPTP problem library: CNF release v1.2.1. Journal of Automated Reasoning 21(2), 177–203 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  22. Claessen, K., Sörensson, N.: New techniques that improve MACE-style finite model finding. In: CADE, Workshop W4 (2003)

    Google Scholar 

  23. Sutcliffe, G.: System on TPTP, http://www.cs.miami.edu/~tptp/cgi-bin/SystemOnTPTP (accessed January 9, 2009)

  24. Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2), 120–126 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  25. Bellare, M., Rogaway, P.: The exact security of digital signatures: How to sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  26. Lindenberg, C., Wirt, K.: SHA1, RSA, PSS and more. In: Klein, G., Nipkow, T., Paulson, L. (eds.) The Archive of Formal Proofs (May 2005), http://afp.sourceforge.net/entries/RSAPSS.shtml , Formal proof development

  27. Cortier, V., Delaune, S., Lafourcade, P.: A survey of algebraic properties used in cryptographic protocols. Journal of Computer Security 14(1), 1–43 (2006)

    Article  Google Scholar 

  28. Borisov, N., Goldberg, I., Wagner, D.: Intercepting mobile communications: The insecurity of 802.11. In: MOBICOM, pp. 180–188 (2001)

    Google Scholar 

  29. Selinger, P.: Models for an adversary-centric protocol logic. Electr. Notes Theor. Comput. Sci. 55(1) (2001)

    Google Scholar 

  30. Goubault-Larrecq, J.: Towards producing formally checkable security proofs, automatically. In: Computer Security Foundations (CSF), pp. 224–238 (2008)

    Google Scholar 

  31. Jürjens, J.: Security analysis of crypto-based java programs using automated theorem provers. In: ASE, pp. 167–176. IEEE Computer Society, Los Alamitos (2006)

    Google Scholar 

  32. Jürjens, J.: Secure information flow for concurrent processes. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 395–409. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Microsoft Research, Cambridge, and Robinson College (Univ. Cambridge), Open University (UK), UK

    Jan Jürjens

  2. Computer Laboratory, University of Cambridge, UK

    Tjark Weber

Authors
  1. Jan Jürjens
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tjark Weber
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Informatica, Università di Pisa, Largo Bruno Pontecorvo, 3, 56127, Pisa, Italy

    Pierpaolo Degano

  2. Dipartimento di Informatica, Università di Verona, Strada Le Grazie 15, 37134, Verona, Italy

    Luca Viganò

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Jürjens, J., Weber, T. (2009). Finite Models in FOL-Based Crypto-Protocol Verification. In: Degano, P., Viganò, L. (eds) Foundations and Applications of Security Analysis. ARSPA-WITS 2009. Lecture Notes in Computer Science, vol 5511. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03459-6_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-03459-6_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-03458-9

  • Online ISBN: 978-3-642-03459-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics