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/.     

密码协议的归纳证明方法

通过对Otway-rees协议的分析,介绍了目前受到普遍关注的一种密码协议形式化分析方法－归纳方法。     

密码协议基于遍历的分析方法

文献[1]提出用两方密码协议的运行模式对协议进行分析,文章证明该方法未能列举出全部运行模式,因此一些协议的漏洞不能被发现。文章提出一种遍历分析法,让导致攻击成功的假冒消息遍历攻击者在各种情况下消息接收集来对协议进行分析,从而发现协议漏洞。     

Partial-Order Reduction in Symbolic State-Space Exploration

State-space explosion is a fundamental obstacle in the formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reduction and symbolic state-space search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable states. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable states as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first search for the analysis of asynchronous network protocols, and symbolic breadth-first search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.     

关于密码协议攻击的研究

该文通过具体实例从不同的角度讨论了对密码协议的各种攻击,并阐述了这些攻击产生的原因及防止它们的一般方法。     

Symbolic Protocol Verification with Queue BDDs

Symbolic verification based on Binary Decision Diagrams (BDDs) has proven to be a powerful technique for ensuring the correctness of digital hardware. In contrast, BDDs have not caught on as widely for software verification, partly because the data types used in software are more complicated than those used in hardware. In this work, we propose an extension of BDDs for dealing with dynamic data structures. Specifically, we focus on queues, since they are commonly used in modeling communication protocols. We introduce Queue BDDs (QBDDs), which include all the power of BDDs while also providing an efficient representation of queue contents. Experimental results show that QBDDs are well-suited for the verification of communication protocols.     

抗原语分析的密码协议设计原则

列举了一个因密钥破解造成的协议失败案例,提出了协议设计的唯密文原则以最大限度地保证长期密钥的安全性,同时唯密文原则还可以抵抗重放、初始化和剪切粘贴攻击。     

密码函数的正规性

指出一个好的密码函数除了自身需要具备良好的复杂性外,对其做一个较小的改动后仍需具有良好的复杂性;基于此思想对布尔函数的正规性这一复杂性指标作了改进,定义了扩展的正规性,讨论了扩展正规性和正规性之间的关系以及扩展正规性和代数免疫之间的关系;并从布尔函数代数正规型的角度分析了函数的正规性和代数免疫阶,为正规性和代数免疫的分析提供了一条新的思路。     

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

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

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.     

Symbolic protocol analysis in the union of disjoint intruder theories: Combining decision procedures

Most of the decision procedures for symbolic analysis of protocols are limited to a fixed set of algebraic operators associated with a fixed intruder theory. Examples of such sets of operators comprise XOR, multiplication, abstract encryption/decryption. In this report we give an algorithm for combining decision procedures for arbitrary intruder theories with disjoint sets of operators, provided that solvability of ordered intruder constraints, a slight generalization of intruder constraints, can be decided in each theory. This is the case for most of the intruder theories for which a decision procedure has been given. In particular our result allows us to decide trace-based security properties of protocols that employ any combination of the above mentioned operators with a bounded number of sessions.     

Symbolic modeling of robot kinematics and dynamics

As a component of advanced manufacturing technology, this report presents applications of FORM to solve symbolically a class of usual robotic problems. One advantage of this symbolic manipulation code is to perform, even on PCs, the manipulation of giant formulae. Though the code has a low built-in knowledge, but handles indices, vectors, matrices, traces, tensors, as well as factorial and delta functions, it can be directly ported on a large variety of computers such as Alliant, Appolo, Atari ST, Gould (NP1 and 9080), MacIntosh, PCs, SUN and VAX (VMS and Ultrix). The symbolic programs given in this paper perform on PCs the kinematics and dynamics analysis of simple robots via the free version 1.0 of FORM. This approach shows us a way to develop at low cost many useful robotic packages for education as well as Research & Development purposes.     

基于逻辑编程的EKE协议分析

基于逻辑编程规则及Spi演算提出了一种验证密码协议安全性的新方法,利用该方法可以对密码协议的安全性质以程序化的方式进行验证。通过对EKE协议进行的分析,不但证明了协议已知的漏洞,而且发现了针对EKE协议的一个新的攻击——并行会话攻击。很好地验证了该新方法对密码协议的分析能力。     

Cryptographic protocol logic: Satisfaction for (timed) Dolev–Yao cryptography

This article is about a breadth-first exploration of logical concepts in cryptography and their linguistic abstraction and model-theoretic combination in a comprehensive logical system, called CPL (for Cryptographic Protocol Logic). We focus on two fundamental aspects of cryptography. Namely, the security of communication (as opposed to security of storage) and cryptographic protocols (as opposed to cryptographic operators). The logical concepts explored are the following. Primary concepts The modal concepts of knowledge, norms, provability, space, and time. Secondary concepts Individual and propositional knowledge, confidentiality norms, truth-functional and relevant (in particular, intuitionistic) implication, multiple and complex truth values, and program types. The distinguishing feature of CPL is that it unifies and refines a variety of existing approaches. This feature is the result of our wholistic conception of property-based (modal logics) and model-based (process algebra) formalisms. We illustrate the expressiveness of CPL on representative requirements engineering case studies. Further, we extend (core) CPL (qualitative time) with rational-valued time, i.e. time stamps, timed keys, and potentially drifting local clocks, to tCPL (quantitative time). Our extension is conservative and provides further evidence for Lamport’s claim that adding real time to an untimed formalism is really simple.     

代数符号计算的神经网络模型

文中给出一种p-adic数制式非对称连接神经网络模型,该网络在整个矢量空间只有唯一平衡点,因而可获得问题的最优解,且在存在计算误差,这种神经网络保持高度并行结构,可用了代数符号计算,本文重点分析了实现神经网络的方法,给代数符号计算提供了一个新的计算模型。     

基于符号模型检测的SDG故障诊断解形式化验证

由于定量信息和非线性因果关系的丢失,SDG的故障诊断解需要进一步的进行校核与验证。创新地将SDG故障诊断解的验证置于符号模型检测框架中进行研究,提出了基于符号模型检测的SDG故障诊断形式化验证方法。首先扩展、转换了SDG模型的有限状态变迁系统形式化描述,建立了SMV模型;其次引入故障传播时间建立了模型观测变量的动态验证信息,并基于步进式监控分析了动态验证策略,将SDG正向推理扩展建模为动态推理验证;然后面向符号模型检测扩展了动态推理验证过程的SMV模型,提出了验证算法SSDGFD_ SMC;最后,通过一个实例验证了算法的有效性。     

Symbolic algorithmic verification of intransitive generalized noninterference

Generalized noninterference can be used to formulate transitive security policies,but is unsuitable for intransitive security policies.We propose a new information flow security property,which we call intransitive generalized noninterference,that enables intransitive security policies to be specified formally.Next,we propose an algorithmic verification technique to check intransitive generalized noninterference.Our technique is based on the search for counterexamples and on the window induction proof,and can be used to verify generalized noninterference.We further demonstrate that the search of counterexamples and induction proof can be reduced to quantified Boolean satisfiability.This reduction enables us to use efficient quantified Boolean decision procedures to perform the check of intransitive generalized noninterference.It also reduces spatial requirement by representing the space compactly,and improves the efficiency of the verification procedure.