Abstract
On a case study, we present a new approach for verifying cryptographic protocols, based on rewriting and on tree automata techniques. Protocols are operationally described using Term Rewriting Systems and the initial set of communication requests is described by a tree automaton. Starting from these two representations, we automatically compute an over-approximation of the set of exchanged messages (also recognized by a tree automaton). Then, proving classical properties like confidentiality or authentication can be done by automatically showing that the intersection between the approximation and a set of prohibited behaviors is the empty set. Furthermore, this method enjoys a simple and powerful way to describe intruder work, the ability to consider an unbounded number of parties, an unbounded number of interleaved sessions, and a theoretical property ensuring safeness of the approximation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bolignano, D.: Towards a Mechanization of Cryptographic Protocol Verification. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254. Springer, Heidelberg (1997)
Borovanský, P., Kirchner, C., Kirchner, H., Moreau, P.-E., Vittek, M.: ELAN: A logical framework based on computational systems. In: Proc. 1st WRLA. ENTCS, vol. 4, Asilomar, California (1996)
Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997), http://l3ux02.univ-lille3.fr/tata/
Coquidé, J., Dauchet, M., Gilleron, R., Vágvölgyi, S.: Bottom-up tree pushdown automata and rewrite systems. In: Book, R.V. (ed.) RTA 1991. LNCS, vol. 488, pp. 287–298. Springer, Heidelberg (1991)
Dauchet, M., Tison, S.: The theory of ground rewrite systems is decidable. In: Proc. 5th LICS Symp., Philadelphia (Pa., USA), pp. 242–248 (June 1990)
Denker, G., Meseguer, J., Talcott, C.: Protocol Specification and Analysis in Maude. In: 2nd WRLA Workshop, Pont á Mousson, France (1998)
Dershowitz, N., Jouannaud, J.-P.: Handbook of Theoretical Computer Science. In: Rewrite Systems, vol. B, ch. 6, pp. 244–320. Elsevier Science Publishers, Amsterdam (1990) (Also as: Research report 478, LRI)
Genet, T.: Tree Automata Library, http://www.loria.fr/ELAN/
Genet, T.: Decidable approximations of sets of descendants and sets of normal forms. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol. 1379, pp. 151–165. Springer, Heidelberg (1998)
Genet, T., Klay, F.: Rewriting for cryptographic protocols verification (extended version). Technical report, INRIA (2000), http://www.irisa.fr/lande/genet/publications.html
Gilleron, R., Tison, S.: Regular tree languages and rewrite systems. Fundamenta Informaticae 24, 157–175 (1995)
Jacquemard, F.: Decidable approximations of term rewriting systems. In: Ganzinger, H. (ed.) Proc. 7th RTA Conf., New Brunswick (New Jersey, USA), pp. 362–376. Springer, Heidelberg (1996)
Lowe, G.: An Attack on the Needham-Schroder Public-Key Protocol. IPL 56, 131–133 (1995)
Lowe, G.: Breaking and fixing the Needham-Schroeder public-key protocol using CSP and FDR. In: Margaria, T., Steffen, B. (eds.) TACAS 1996. LNCS, vol. 1055, pp. 147–166. Springer, Heidelberg (1996)
Lowe, G.: Some New Attacks upon Security Protocols. In: 9th Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos (1996)
Mastercard & Visa. Secure Electronic Transactions (1996), http://www.visa.com/set/
Meadows, C.A.: Analyzing the Needham-Schroeder Public Key Protocol: A comparison of two approaches. In: Martella, G., Kurth, H., Montolivo, E., Bertino, E. (eds.) ESORICS 1996. LNCS, vol. 1146, pp. 351–364. Springer, Heidelberg (1996)
Monniaux, D.: Abstracting Cryptographic Protocols with Tree Automata. In: Proc. 6th SAS, Venezia, Italy (1999)
Needham, R.M., Schroeder, M.D.: Using Encryption for Authentication in Large Networks of Computers. CACM 21(12), 993–999 (1978)
Paulson, L.: Proving Properties of Security Protocols by Induction. In: 10th Computer Security Foundations Workshop. IEEE Computer Society Press, Los Alamitos (1997)
Salomaa, K.: Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems. J. of Computer and System Sciences 37, 367–394 (1988)
Weidenbach, C.: Towards an Automatic Analysis of Security Protocols. In: Ganzinger, H. (ed.) CADE 1999. LNCS (LNAI), vol. 1632, pp. 378–382. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Genet, T., Klay, F. (2000). Rewriting for Cryptographic Protocol Verification. In: McAllester, D. (eds) Automated Deduction - CADE-17. CADE 2000. Lecture Notes in Computer Science(), vol 1831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10721959_21
Download citation
DOI: https://doi.org/10.1007/10721959_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67664-5
Online ISBN: 978-3-540-45101-3
eBook Packages: Springer Book Archive