Decision Procedures for the Security of Protocols with Probabilistic Encryption against Offline Dictionary Attacks

We consider the problem of formal automatic verification of cryptographic protocols when some data, like poorly chosen passwords, can be guessed by dictionary attacks. First, we define a theory of these attacks and propose an inference system modeling the deduction capabilities of an intruder. This system extends a set of well-studied deduction rules for symmetric and public key encryption, often called Dolev–Yao rules, with the introduction of a probabilistic encryption operator and guessing abilities for the intruder. Then, we show that the intruder deduction problem in this extended model is decidable in PTIME. The proof is based on a locality lemma for our inference system. This first result yields to an NP decision procedure for the protocol insecurity problem in the presence of a passive intruder. In the active case, the same problem is proved to be NP-complete: we give a procedure for simultaneously solving symbolic constraints with variables that represent intruder deductions. We illustrate the procedure with examples of published protocols and compare our model to other recent formal definitions of dictionary attacks.     

Reducing Protocol Analysis with XOR to the XOR-Free Case in the Horn Theory Based Approach

In the Horn theory based approach for cryptographic protocol analysis, cryptographic protocols and (Dolev?CYao) intruders are modeled by Horn theories and security analysis boils down to solving the derivation problem for Horn theories. This approach and the tools based on this approach, including ProVerif, have been very successful in the automatic analysis of cryptographic protocols. However, dealing with the algebraic properties of operators, such as the exclusive OR (XOR), which are frequently used in cryptographic protocols has been problematic. In particular, ProVerif cannot deal with XOR. In this paper, we show how to reduce the derivation problem for Horn theories with XOR to the XOR-free case. Our reduction works for an expressive class of Horn theories. A large class of intruder capabilities and protocols that employ the XOR operator can be modeled by these theories. Our reduction allows us to carry out protocol analysis using tools, such as ProVerif, that cannot deal with XOR, but are very efficient in the XOR-free case. We implemented our reduction and, in combination with ProVerif, used it for the fully automatic analysis of several protocols that employ the XOR operator. Among others, our analysis revealed a new attack on an IBM security module.     

基于合一替换推理的密码协议分析

提出了一种简单的，更适合于自动化操作的密码协议分析方法，通过进一步分析攻击者的计算能力，形成一个有效的自动推理系统。攻击者为应答挑战主体的消息。把该消息应答转化为利用推理系统进行合一替换。并分别给出了Needham-Schroede协议的推理说明。     

The Practice of Cryptographic Protocol Verification

We present CASRUL, a compiler for cryptographic protocols specifications. Its purpose is to verify the executability of protocols and to translate them into rewrite rules that can be used by several kinds of automatic or semi-automatic tools for finding design flaws. We also present a related complexity results concerning the protocol insecurity problem for a finite number of sessions. We show the problem is in NP without assuming bounds on messages and with non-atomic encryption keys. We also explain that in order to build an attack with a fixed number of sessions the intruder needs only to forge messages of linear size, provided that they are represented as dags.For more information: http://www.loria.fr/equipes/protheo/SOFTWARES/CASRUL/.     

一种基于扩展Spi演算的类型系统

主要探讨了使用非形式化的原理和形式化的规则来获得密码协议安全属性的方法。这些原理和规则基于传统的等级和信息流的思想，通过将其扩展后用来处理密码协议中的并发进程。提出的规则是基于Spi演算扩展语法的一种类型规则。通过这些规则可以向用户担保．如果协议通过了类型检测，则该协议没有泄漏任何秘密的消息。     

一种基于模重写系统的攻击者推理方法

为了解决安全协议验证中攻击者模等式理论推理的可操作性问题,提出并设计了一种基于模重写系统的攻击者推理方法。该方法建立在一个反映两种密码原语代数特性的联合理论实例之上,由一组定向的重写规则和非定向的等式构成,前者进一步转化为项重写系统TRS(Term Rewriting System),而后者则转化为有限等价类理论,通过定义项间的模重写关系,使二者构成一个可以反映攻击者针对联合理论代数项操作能力的模重写系统。实例分析表明,该模型为攻击者模等式推理规则赋予了明确的操作语义,可以使攻击者达到对安全协议代数项规约、推理的目的。     

On the decidability of cryptographic protocols with open-ended data structures

Formal analysis of cryptographic protocols has concentrated mainly on protocols with closed-ended data structures, i.e., protocols where the messages exchanged between principals have fixed and finite format. In many protocols, however, the data structures used are open-ended, i.e., messages have an unbounded number of data fields. In this paper, decidability issues for such protocols are studied. We propose a protocol model in which principals are described by transducers, i.e., finite automata with output, and show that in this model security is decidable and PSPACE-hard in presence of the standard Dolev-Yao intruder.     

加密模式与密码协议的安全性

密码协议的设计和安全性分析是困难的,在密码协议中总是以所使用的密码算法是安全的为前提,但是人们却忽略了密码算法的加密模式对密码协议安全性的影响。论文针对一个改进的Needham-Schroeder协议,假设其使用了分组密码的CBC加密模式,我们通过使用一条旧信息的明密文对来修改当前会话中的信息,从而成功地欺骗用户双方,并分别与他们建立了一个会话密钥,对该协议进行了成功的攻击。结果说明密码算法的加密模式对密码协议的安全性有着巨大的影响。Schroederauthenticationprotocol125     

A game-theoretic framework for specification and verification of cryptographic protocols

We model security protocols as games using concepts of game semantics. Using this model we ascribe semantics to protocols written in the standard simple arrow notation. According to the semantics, a protocol is interpreted as a set of strategies over a game tree that represents the type of the protocol. The model uses abstract computation functions and message frames in order to model internal computations and knowledge of agents and the intruder. Moreover, in order to specify properties of the model, a logic that deals with games and strategies is developed. A tableau-based proof system is given for the logic, which can serve as a basis for a model checking algorithm. This approach allows us to model a wide range of security protocol types and verify different properties instead of using a variety of methods as is currently the practice. Furthermore, the analyzed protocols are specified using only the simple arrow notation heavily used by protocol designers and by practitioners.     

Completeness and Counter-Example Generations of a Basic Protocol Logic: (Extended Abstract)

We give an axiomatic system in first-order predicate logic with equality for proving security protocols correct. Our axioms and inference rules derive the basic inference rules, which are explicitly or implicitly used in the literature of protocol logics, hence we call our axiomatic system Basic Protocol Logic (or BPL, for short). We give a formal semantics for BPL, and show the completeness theorem such that for any given query (which represents a correctness property) the query is provable iff it is true for any model. Moreover, as a corollary of our completeness proof, the decidability of provability in BPL holds for any given query. In our formal semantics we consider a “trace” any kind of sequence of primitive actions, counter-models (which are generated from an unprovable query) cannot be immediately regarded as realizable traces (i.e., attacked processes on the protocol in question). However, with the aid of Comon-Treinen's algorithm for the intruder deduction problem, we can determine whether there exists a realizable trace among formal counter-models, if any, generated by the proof-search method (used in our completeness proof). We also demonstrate that our method is useful for both proof construction and flaw analysis by using a simple example.     

从Woo—Lam协议到网络协议的抽象验证

形式化方法是验证加密协议的重要手段,提出了一种新的验证方法,该方法基于Debbabi的推理规则,将参与者ID｜参与者密钥等数据结构从协议中抽象出来,建立起抽象的逻辑推理结构。以Woo-Lam协议为例,通过逆向递推的方式得到了协议的所有攻击路径,并以图的形式表示其关系,详尽分析了协议的漏洞,最后,提出了如何使协议更为安全的建议。     

运行模式法分析TW密码协议

在介绍两方密码协议运行模式分析法的基础上,运用运行模式分析法对自行设计的TW两方密码协议进行了分析,成功地发现了TW协议的攻击,并验证了此协议的安全性,说明了两方密码协议运行模式分析法的有效性。     

基于类型的密码协议验证方法

探讨使用一组形式化的规则来验证密码协议安全属性的方法.这些规则基于传统的等级和信息流的思想,通过将其扩展后用来处理密码协议中的并发进程.通过这些规则可以向用户提供一种检测方法,该方法用于判断:如果协议通过了检测,则可以认为该协议没有泄漏任何秘密的消息.     

An algebraic approach to the verification of a class of Diffie-Hellman protocols

We present a framework for reasoning about secrecy in a class of Diffie-Hellman protocols. The technique, which shares a conceptual origin with the idea of a rank function, uses the notion of a message-template to determine whether a given value is generable by an intruder in a protocol model. Traditionally, the rich algebraic structure of Diffie-Hellman messages has made it difficult to reason about such protocols using formal, rather than complexity-theoretic, techniques. We describe the approach in the context of the MTI protocols, and derive conditions under which each protocol in the suite can be considered secure.     

Algebra model and security analysis for cryptographic protocols

With the rapid growth of the Internet and the World Wide Web a large number of cryptographic protocols have been deployed in distributed systems for various application requirements, and security problems of distributed systems have become very important issues. There are some natural problems: does the protocol have the right properties as dictated by the requirements of the system? Is it still secure that multiple secure cryptographic protocols are concurrently executed? How shall we analy…     

Formalizing and Analyzing the Needham-Schroeder Symmetric-Key Protocol by Rewriting

This paper reports on work in progress on using rewriting techniques for the specification and the verification of communication protocols. As in Genet and Klay's approach to formalizing protocols, a rewrite system describes the steps of the protocol and an intruder's ability of decomposing and decrypting messages, and a tree automaton encodes the initial set of communication requests and an intruder's initial knowledge. In a previous work we have defined a rewriting strategy that, given a term t that represents a property of the protocol to be proved, suitably expands and reduces t using the rules in and the transitions in to derive whether or not t is recognized by an intruder. In this paper we present a formalization of the Needham-Schroeder symmetric-key protocol and use the rewriting strategy for deriving two well-known authentication attacks.     

An Optimized Intruder Model for SAT-based Model-Checking of Security Protocols

In previous work we showed that automatic SAT-based model-checking techniques based on a reduction of protocol (in)security problems to a sequence of propositional satisfiability problems can be used to effectively find attacks on protocols. In this paper we present an optimized intruder model that may lead in many cases to shorter attacks which can be detected in our framework by generating smaller propositional formulae. The key idea is to assume that some of the abilities of the intruder have instantaneous effect, whereas in the previously adopted approach all the abilities of the intruder were modeled as state transitions. This required non trivial extensions to the SAT-reduction techniques which are formally described in the paper. Experimental results indicate the advantages of the proposed optimization.     

Cryptographic protocol security analysis based on bounded constructing algorithm

1 Introduction 1.1 Background Cryptographic protocols have been used to provide security services for many applications on the open communication environment. More and more cryptographic protocols will be designed to solve the increasing security requirem…