基于理想的协议安全性分析

1998年,Guttman等人提出了串空间理论作为一种新的密码协议形式化分析的工具.并在1999年第1次引入了关于消息代数上的理想以及诚实的概念来分析协议的保密性.由于理想结构的特殊性使得它可以刻画协议运行中消息之间的关系.利用理想的结构来分析协议的一些安全性质,例如保密性、认证性、零知识性以及如何抵抗猜测攻击.     

Relating symbolic and cryptographic secrecy

We investigate the relation between symbolic and cryptographic secrecy properties for cryptographic protocols. Symbolic secrecy of payload messages or exchanged keys is arguably the most important notion of secrecy shown with automated proof tools. It means that an adversary restricted to symbolic operations on terms can never get the entire considered object into its knowledge set. Cryptographic secrecy essentially means computational indistinguishability between the real object and a random one, given the view of a much more general adversary. In spite of recent advances in linking symbolic and computational models of cryptography, no relation for secrecy under active attacks is known yet. For exchanged keys, we show that a certain strict symbolic secrecy definition over a specific Dolev-Yao-style cryptographic library implies cryptographic key secrecy for a real implementation of this cryptographic library. For payload messages, we present the first general cryptographic secrecy definition for a reactive scenario. The main challenge is to separate secrecy violations by the protocol under consideration from secrecy violations by the protocol users in a general way. For this definition, we show a general secrecy preservation theorem under reactive simulatability, the cryptographic notion of secure implementation. This theorem is of independent cryptographic interest. We then show that symbolic secrecy implies cryptographic payload secrecy for the same cryptographic library as used in key secrecy. Our results thus enable formal proof techniques to establish cryptographically sound proofs of secrecy for payload messages and exchanged keys.     

Secrecy by interpretation functions

This paper presents a novel approach to verify the secrecy property of cryptographic protocols. Basically, the idea is to establish sufficient conditions under which the secrecy property of a given protocol is guaranteed. The idea behind the sufficient conditions is to restrict the principals involved in the analyzed protocol so that they never decrease the security level of any piece of information when they send it over the network. For example, a principal is not allowed to protect a “top secret” information by a secret or a public key. Only keys having a security level greater or equal to “top secret” can protect “top secret” information. The proposed conditions can be syntactically verified on a cryptographic protocol in acceptable time. This proposed approach is general in the way that it can be applied to any cryptographic protocols and with any set of security levels (the set {public, secret, topSecret}, or the set {0,1}, etc).     

Static Equivalence is Harder than Knowledge

There are two main ways of defining secrecy of cryptographic protocols. The first version checks if the adversary can learn the value of a secret parameter. In the second version, one checks if the adversary can notice any difference between protocol runs with different values of the secret parameter.We give a new proof that when considering more complex equational theories than partially invertible functions, these two kinds of secrecy are not equally difficult to verify. More precisely, we identify a message language equipped with a convergent rewrite system such that after a completed protocol run, the first problem mentioned above (adversary knowledge) is decidable but the second problem (static equivalence) is not. The proof is by reduction of the ambiguity problem for context-free grammars.     

Decidability and Combination Results for Two Notions of Knowledge in Security Protocols

In formal approaches, messages sent over a network are usually modeled by terms together with an equational theory, axiomatizing the properties of the cryptographic functions (encryption, exclusive or, ...). The analysis of cryptographic protocols requires a precise understanding of the attacker knowledge. Two standard notions are usually considered: deducibility and indistinguishability. Those notions are well-studied and several decidability results already exist to deal with a variety of equational theories. Most of the existing results are dedicated to specific equational theories and only few results, especially in the case of indistinguishability, have been obtained for equational theories with associative and commutative properties (AC)(\textsf{AC}). In this paper, we show that existing decidability results can be easily combined for any disjoint equational theories: if the deducibility and indistinguishability relations are decidable for two disjoint theories, they are also decidable for their union. We also propose a general setting for solving deducibility and indistinguishability for an important class (called monoidal) of equational theories involving AC\textsf{AC} operators. As a consequence of these two results, new decidability and complexity results can be obtained for many relevant equational theories.     

Tree automata with one memory set constraints and cryptographic protocols

We introduce a class of tree automata that perform tests on a memory that is updated using function symbol application and projection. The language emptiness problem for this class of tree automata is shown to be in DEXPTIME.We also introduce a class of set constraints with equality tests and prove its decidability by completion techniques and a reduction to tree automata with one memory.Finally, we show how to apply these results to cryptographic protocols. We introduce a class of cryptographic protocols and show the decidability of secrecy for an arbitrary number of agents and an arbitrary number of (concurrent or successive) sessions, provided that only a bounded number of new data is generated. The hypothesis on the protocol (a restricted copying ability) is shown to be necessary: without this hypothesis, we prove that secrecy is undecidable, even for protocols without nonces.     

一种多项式时间复杂度的密码协议秘密性验证方法

密码协议的秘密性验证是网络安全领域的一个难题,本文在提出协议行为结构的基础上,通过对协议行为及其结构的分析,提出了一种新的密码协议的秘密性验证算法,该算法的时间复杂度是多项式时间的,从而简化了秘密性验证过程,文中最后,作为实例,给出了TMN密码协议的秘密性验证。     

One Picture Is Worth a Dozen Connectives: A Fault-Tree Representation of NPATRL Security Requirements

In this paper, we show how we can increase the ease of reading and writing security requirements for cryptographic protocols at the Dolev-Yao level of abstraction by developing a visual language based on fault trees. We develop such semantics for a subset of NRL protocol analyzer temporal requirements language (NPATRL), a temporal language used for expressing safety requirements for cryptographic protocols, and show that the subset is sound and complete with respect to the semantics. We also show how the fault trees can be used to improve the presentation of some specifications that we developed in our analysis of the group domain of interpretation (GDOI) protocol. Other examples involve a property of Kerberos 5 and a visual account of the requirements in Lowe's authentication hierarchy.     

Cryptographic Secrecy of Steganographic Matrix Embedding

Some recent information-hiding schemes are scrutinized in terms of their cryptographic secrecy. The schemes under study appeal to the so-called matrix embedding strategy, designed to optimize embedding capacity under distortion constraints, as opposed to any cryptographic measure. Nonetheless, we establish conditions under which a key equivocation function is optimal, and show that under reasonable key generation models, a perfect secrecy property is nearly satisfied, limited by a mutual information measure that decreases exponentially with the block length.      

IKE2协议的安全性分析

本文首先扩展了串空间的理想理论,然后应用此扩展理论分析IKE2协议的核心安全：秘密性和认证性。通过分析,证明了IKE2协议的密钥交换和认证安全性,但同时发现它不能在主动攻击模式下保护发起者身份,对此我们提出了一个修改意见。对IKE2的分析也为扩展串空间理论在复杂协议分析中的应用提供了一个实践基础。     

Unification Modulo Homomorphic Encryption

Encryption ‘distributing over pairs’ is a technique employed in several cryptographic protocols. We show that unification is decidable for an equational theory HE specifying such an encryption. The method consists in transforming any given problem in such a way, that the resulting problem can be solved by combining a graph-based reasoning on its equations involving the homomorphisms, with a syntactic reasoning on its pairings. We show HE-unification to be NP-hard and in EXPTIME. We also indicate, briefly, how to extend HE-unification to Cap unification modulo HE, that can be used as a tool for modeling and analyzing cryptographic protocols where encryption follows the ECB mode, i.e., is done block-wise on messages.     

Computing Knowledge in Security Protocols Under Convergent Equational Theories

The analysis of security protocols requires reasoning about the knowledge an attacker acquires by eavesdropping on network traffic. In formal approaches, the messages exchanged over the network are modelled by a term algebra equipped with an equational theory axiomatising the properties of the cryptographic primitives (e.g. encryption, signature). In this context, two classical notions of knowledge, deducibility and indistinguishability, yield corresponding decision problems. We propose a procedure for both problems under arbitrary convergent equational theories. Since the underlying problems are undecidable we cannot guarantee termination. Nevertheless, our procedure terminates on a wide range of equational theories. In particular, we obtain a new decidability result for a theory we encountered when studying electronic voting protocols. We also provide a prototype implementation.     

JFK协议的安全性分析

重新定义了串空间理想概念，并扩展了有关命题和定理，从而使串空间理论能分析包含丰富密码原语的安全协议，进一步应用此扩展串空间理论分析JFK协议（一个新提出的IPsec密钥交换协议）的桉心安全属性：秘密性和认证性．通过分析证明了JFK协议的密钥和认证安全性，对JFK的分析也为扩展串空间理论的广泛应用打下了一个坚实的基础．     

Reducing Equational Theories for the Decision of Static Equivalence

Static equivalence is a well established notion of indistinguishability of sequences of terms which is useful in the symbolic analysis of cryptographic protocols. Static equivalence modulo equational theories allows for a more accurate representation of cryptographic primitives by modelling properties of operators by equational axioms. We develop a method that allows us in some cases to simplify the task of deciding static equivalence in a multi-sorted setting, by removing a symbol from the term signature and reducing the problem to several simpler equational theories. We illustrate our technique at hand of bilinear pairings.     

ACTAS : A System Design for Associative and Commutative Tree Automata Theory

ACTAS is an integrated system for manipulating associative and commutative tree automata (AC-tree automata for short), that has various functions such as for Boolean operations of AC-tree automata, computing rewrite descendants, and solving emptiness and membership problems. In order to deal with high-complexity problems in reasonable time, over- and under-approximation algorithms are also equipped. Such functionality enables us automated verification of safety property in infinite state models, that is helpful in the domain of, e.g. network security, in particular, for security problems of cryptographic protocols allowing an equational property. In runtime of model construction, a tool support for analysis of state space expansion is provided. The intermediate status of the computation is displayed in numerical data table, and also the line graphs are generated. Besides, a graphical user interface of the system provides us a user-friendly environment for handy use.     

基于Petri网的密码协议分析

在Federico提出的一种密码协议进程语言的基础上,建立了便于进行密码协议分析的简化Petri网模型,给出了协议满足秘密性的充要条件,并以NS公钥协议为例,用Petri网模型,结合归纳方法和串空间分析方法从密钥、新鲜数和协议主体三个方面的秘密性分析了该协议的秘密性,简化了协议秘密性的分析。     

A formalization of card-based cryptographic protocols via abstract machine

Consider a face-down card lying on the table such that we do not know whether its suit color is black or red. Then, how do we make identical copies of the card while keeping its color secret? A partial solution has been devised: using a number of additional black and red cards, Niemi and Renvall proposed an excellent protocol which can copy a face-down card while allowing only a small probability of revealing its color. In contrast, this paper shows the nonexistence of a perfect solution, namely, the impossibility of copying a face-down card with perfect secrecy. To prove such an impossibility result, we construct a rigorous mathematical model of card-based cryptographic protocols; giving this general computational model is the main result of this paper.     

密码协议的秘密性证明

在Paulson的归纳方法基础上提出一种新的密码协议秘密性的证明方法，该方法在消息事件结构中引入会话标识符，给出协议满足秘密性的充要条件，大大简化了协议秘密性的证明，高效且适合机械化实现。     

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

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

Security extension for the Canetti-Krawczyk model in identity-based systems

The Canetti-Krawczyk (CK) model is a formalism for the analysis of key-exchange protocols, which can guarantee many security properties for the protocols proved secure by this model. But we find this model lacks the ability to guarantee key generation center (KGC) forward secrecy, which is an important security property for key-agreement protocols based on Identity. The essential reason leading to this weakness is that it does not fully consider the attacker's capabilities. In this paper, the CK model is accordingly extended with a new additional attacker's capability of the KGC corruption in Identity-based systems, which enables it to support KGC forward secrecy.