Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 21 Issue 6
November  2006
Turn off MathJax
Article Contents
Abstract
References
Kai-Le Su, Qing-Liang Chen, Abdul Sattar, Wei-Ya Yue, Guan-Feng Lv, Xi-Zhong Zheng. Verification of Authentication Protocols for Epistemic Goals via SAT Compilation[J]. Journal of Computer Science and Technology, 2006, 21(6): 932-943.
Citation: Kai-Le Su, Qing-Liang Chen, Abdul Sattar, Wei-Ya Yue, Guan-Feng Lv, Xi-Zhong Zheng. Verification of Authentication Protocols for Epistemic Goals via SAT Compilation[J]. Journal of Computer Science and Technology, 2006, 21(6): 932-943.
shu

Verification of Authentication Protocols for Epistemic Goals via SAT Compilation

  • 1Department of Computer Science, Sun Yat-Sen University, Guangzhou 510275, P.R. China2Institute for Integrated and Intelligent Systems, Griffith University, Brisbane, Qld 4111, Australia3College of Computer Science and Technology, Beijing University of Technology, Beijing 100022, P.R. China4Department of Computer Science, Brandenburg University of Technology, Cottbus 03046, Germany

More Information
  • Received Date: August 16, 2005
  • Revised Date: May 08, 2006
  • Published Date: November 14, 2006
    Abstract
  • This paper introduces a new methodology thatuses {\it knowledge structures}, a specific form of Kripkesemantics for epistemic logic, to analyze communication protocolsover hostile networks. The paper particularly focuses on automaticverification of authentication protocols. Our approach is based onthe actual definitions of a protocol, not on somedifficult-to-establish justifications. The proposed methodology isdifferent from many previous approaches to automatic verification ofsecurity protocols in that it is justification-oriented instead offalsification-oriented, i.e., finding bugs in a protocol. The mainidea is based on observations: separating a principalexecuting a run of protocol from the role in the protocol, andinferring a principal's knowledge from the local observations ofthe principal. And we show analytically and empirically that thismodel can be easily reduced to Satisfiability (SAT) problemand efficiently implemented by a modern SAT solver.
    • FullText(HTML)
    • References (34)
  • [1]
    Hintikka J. Knowledge and Belief. Ithaca, NY: Cornell University Press, 1962.
    [2]
    Fagin R, Halpern J, Moses Y, Vardi M. Reasoning about Knowledge. Cambridge, MA: MIT Press, 1995.
    [3]
    Halpern J, Zuck L. A little knowledge goes a long way: -Simple} knowledge based derivations and correctness proofs for a family of protocols. -\it Journal of the ACM}, 1992, 39(3): 449--478.
    [4]
    Stulp F, Verbrugge R. A knowledge-based algorithm for the Internet protocol -TCP}. -\it Bulletin of Economic Research}, 2002, 54(1): 69--94.
    [5]
    Burrows M, Abadi M, Needham R M. A logic of authentication. -\it ACM Trans. Computer Systems}, 1990, 8(1): 18--36.
    [6]
    Li Gong, Roger Needham, Raphael Yahalom. Reasoning about beliefs in cryptographic protocols. In -\it Proc. IEEE Computer Society Symposium on Research in Security and Privacy}, Los Alamitos, California, 1990, IEEE Computer Society Press, pp.234--248.
    [7]
    Abadi M, Tuttle M R. A semantics for a logic of authentication. In -\it Proc. the 10th Annual ACM Symp. Principles of Distributed Computing}, Montreal, Canada, 1991, pp.201--216.
    [8]
    Boyd C, Mao M. On a limitation of -BAN} logic. In -\it Proc. EUROCRYPT'93}, Lofthus, Norway: Springer-Verlag, -\it LNCS 765}, 1993, pp.240--247.
    [9]
    P van Oorschot. Extending cryptographic logics of belief to key agreement. In -\it Proc. 1st ACM Conf. Computer and Communications Security}, Fairfax, USA, Nov. 1993, pp.232--243.
    [10]
    P F Syverson, P C van Oorschot. A unified cryptographic protocol logic. Technical Report 5540-227, CHACS, Naval Research Lab, 1996.
    [11]
    Kaile Su, Guanfeng Lv, Yan Zhang. Reasoning about knowledge by variable forgetting. In -\it Proc. the 9th Int. Conf. Principles of Knowledge Representation and Reasoning KR-2004}, Whistler, Canada, June 2004, pp.576--586.
    [12]
    Lowe G. A hierarchy of authentication specifications. In -\it Proc. 10th IEEE Computer Security Foundations Workshop}, IEEE Computer Society Press, Rockport, USA, 1997, pp.31--43.
    [13]
    Kaile Su, Guanfeng Lv, Qingliang Chen. Knowledge structure approach to verification of authentication protocols. -\it Science in China, Series E: Information Sciences}, April 2005, 35(4): 337--351.
    [14]
    Needham R M, Schroeder M D. Using encryption for authentication in large networks of computers. -\it Communication of the ACM}, 1978, 21(12): 993--999.
    [15]
    Gavin Lowe. Breaking and Fixing the -Needham-Schroeder} Public-Key Protocol using -FDR}. Tools and Algorithms for the Construction and Analysis of Systems, Margaria and Steffen (eds.), -\it LNCS 1055}, Passau, Germany: Springer Verlag, 1996, pp.147--166.
    [16]
    Kripke S. A semantical analysis of modal logic. I: Normal modal propositional calculi. -\it Z. Math. Logik Grundl. Math.}, 1963, 9: 67--96.
    [17]
    Fangzhen Lin. On strongest necessary and weakest sufficient conditions. In -\it Proc. Seventh Int. Conf. Principles of Knowledge Representation and Reasoning}, Breckenridge, Colorado, USA, April 11--15, 2000, pp.167--175.
    [18]
    Dolev D, Yao A C. On the security of public-key protocols. -\it IEEE Trans. Information Theory}, Aug. 1983, 29(8): 198--208.
    [19]
    Durgin N, Lincoln P, Mitchell J, Scedrov A. Undecidability of bounded security protocols. In -\it Proc. Workshop on Formal Methods and Security Protocols (FMSP'99)}, Trento, Italy, 1999, http://citeseer. nj.nec.com/durgin99undecidability.html.
    [20]
    Iliano Cervesato, Catherine Meadows, Dusko Pavlovic. An encapsulated authentication logic for reasoning about key distribution protocol. In -\it Eighteenth Computer Security Foundations Workshop --- CSFW-18}, IEEE Computer Society Press, Aix-en-Provence, France, 20--22 June, 2005, pp.48--61.
    [21]
    Nancy A Durgin, John C Mitchell, Dusko Pavlovic. A compositional logic for proving security properties of protocols. -\it Journal of Computer Security}, 2003, 11(4): 677--722.
    [22]
    F Javier Thayer, Jonathan C Herzog, Joshua D Guttman. Strand spaces. Technical Report, The MITRE Corporation, Nov. 1997.
    [23]
    John V Franco, Michal Kouril, John S Schlipf \it et al. \rm SBSAT: A state-based, BDD-based satisfiability solver. In -\it Proc. the Theory and Applications of Satisfiability Testing, 6th Int. Conf., SAT 2003.}, Santa Margherita Ligure, Italy, Springer, -\it LNCS 2919}, 2003, pp.398--410.
    [24]
    Pierre Bieber. A logic of communication in hostile environment. In -\it Proc. the 3rd IEEE Computer Security Foundations Workshop}, Franconia, USA, IEEE Computer Society Press, June 1990, pp.14--22.
    [25]
    Clarke E, Jha S Marrero. A machine checkable logic of knowledge for specifying security properties of electronic commerce protocols. In -\it Proc. 13th IEEE Annual Symposium on Logic in Computer Science -LICS98} Workshop on Formal Methods and Security Protocols}, Indianapolis, Indiana, June 21--24, 1998, http://citeseer.ist.psu.edu/clarke98machine.html.
    [26]
    Paul Syverson. Towards a strand semantics for authentication logic. -\it Electronic Notes in Theoretical Computer Science}, 1999, http://www.elsevier.nl/locate/entcs/volume20.html.
    [27]
    Joseph Y Halpern, Riccardo Pucella. On the relationship between strand spaces and multi-agent systems. -\it ACM Trans. Inf. Syst. Secur.}, 2003, 6(1): 43--70.
    [28]
    Anupam Datta, Ante Derek, John C Mitchell, Dusko Pavlovic. A derivation system for security protocols and its logical formalization. In -\it 16th IEEE Computer Security Foundations Workshop CSFW-16 2003}, Pacific Grove, CA, USA, IEEE Computer Society, June 30--July 2, 2003, pp.109--125.
    [29]
    Li Mengjun, Li Zhoujun, Chen Huowang. A survey of security protocol verification based on process algebra. -\it Chinese J. Computer Research and Development}, July 2004, 41(7): 1097--1103.
    [30]
    Abadi M, Gordon A. A calculus for cryptographic protocols: The spi calculus. In -\it Proc. 4th ACM Conf. Computer and Communication Security}, Zurich, Switzerland, April 1997, pp.36--47.
    [31]
    Huai Jinpeng, Li Xianxian. Algebra model and security analysis for cryptographic protocols. -\it Science in China, Series F: Information Sciences}, Feb. 2004, 47(2): 199--220.
    [32]
    Xue Rui, Feng Deng-Guo. New semantic model for authentication protocols in -ASMs}. -\it J. Comput. Sci. & Tech.}, 2004, 19(4): 555--563.
    [33]
    Clarke E M, Jha S, Marrero W. Verifying security protocols with Brutus. -\it ACM Trans. Software Engineering and Methodology}, October 2000, 9(4): 443--487.
    [34]
    Song D, Berezin S, Perrig A. Athena: A novel approach to efficient automatic security protocol analysis. -\it Journal of Computer Security}, 2001, 9(1, 2): 47--74.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (15) PDF downloads (1385) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return