协议分析验证

协议分析验证（精选十篇）

协议分析验证篇1

由于人们倾向于使用较为简单的密码, 安全协议利用它们很容易进行猜测攻击[1]。我们来考虑下面这个协议:

Msg1. a→s:a

Msg2. s→a:ns

Msg3. a→s:{ns}passwd (a, s)

(用户a的目的是向服务器s验证自己的正确性) 。

现在, 攻击者通过观察这些主体之间的通信就可以通过猜测用户的密码来发起一个猜测攻击。例如, 如果协议的使用者是本文作者之一的话, 他可能会猜想"zzuzhou"作为密码。这时他就可以对ns进行加密得到{ns}zzuzhou, 并将其和第三条消息相比较从而得到消息{ns}passwd (a, s) 。比较表明, 发生的概率较高的就很可能是用户的密码。过去仅仅考虑了协议在独立执行的时候遭受到的攻击, 实际上, 安全协议很少是独立执行的, 它还要和其他的安全协议发生相互作用即对协议进行混合操作。

对此, 我们着重研究的几个问题是:

(1) 两个协议混合构成的混合协议能否发现协议在单独执行时所不能发现的新的攻击?

(2) 单独的一个协议很容易分析。但是, 当这些协议混合起来组成了一个复杂的运行环境的时候, 我们该怎样对协议进行分析?

(3) 在哪些情况下一个协议可以安全地执行而不必担心被其他协议中的混合信息所攻击?

在本文中, 我们引入一种新的攻击称为“多协议猜测攻击”。首先, 我们概括地说明一下串空间模型的形式化分析方法;然后根据这种方法去分析协议在一个复杂的环境中执行的时候仍然是安全的即不会遭受到多协议猜测攻击。最后我们做一下总结, 并提出下一步工作展望。

1串空间模型

在本节中, 我们主要来说明一下串空间和串空间模型的概念[2,3,4]。

1.1项和子项

项表示协议参与者可能交换的消息, 一个协议的所有参与者可能交换的消息集合称为项集合A。原子项分为文本项 (包含身份标识和随机数等) 和密钥项 (参与者的密钥集合) , 分别属于文本项集合T和密钥项集合K。项可以由原子项经过连接和加密得到。文本项集合T和密钥项集合K都是项集合A的子项, 并且T∩K=ϕ。

定义1 符号项是一个有序对〈σ, t〉, t∈A, σ为+或–, 记作+t或–t;+t表示发出项t, –t表示接收到项t。 (±A) *是符号项的有限序列的集合。

定义2 项a是项b的子项, 即a⊂b。子项的关系定义如下:

(1) 若a⊂b, b∈T, 则要求b=a;

(2) 若a⊂b, b∈K, 则要求b=a;

(3) 若a⊂{g}K, 则要求a⊂g或者a={g}K;

(4) 若b=g·h, 则要求a⊂g或者a⊂h或者a=gh。

1.2串空间和丛

定义3 一个串空间是指一个集合Σ以及在该集合上的迹映射:tr:Σ→ (±A) *。集合Σ中的元素称为串。

这里的tr表示由Σ到A中元素组成的序列的一个映射, 称之为迹映射, 映射的像称为原像的迹。通常把像的代表元记作<<σ1, a1>, …, <σn, an>>。通常省略掉迹映射, 只用∑表示一个串空间。迹映射可以不是单射。

定义 4 C= (Nc, Ec) 是有向图 (N, E) 的子图, 其中Ec⊆E是边的集合, Ec⊆E是与Ec中的边相关联的结点的集合。如果下列条件满足, 那么C是Bundle:

(1) C是有限的无环图;

(2) 若n2∈Nc, 且term (n2) 为负, 则存在唯一的结点n1, 使得n1 →c n2 ;

(3) 若n2∈Nc, 且n1⇒n2, 则n1 →c n2 。

因为Bundle是一个图, 所以在边→和⇒下, 结点的关系形成偏序关系, 表示为⪯C。C的任何非空结点子集在⪯C下都有最小元。

1.3攻击者模型

定义5 攻击者用它已知的信息或截取的消息来产生新的消息, 这些行为可以用攻击者角色来表示:

(1) M[t] 产生原子文本消息:<+t> (t∈T) ;

(2) F[g]接收消息:<-g>;

(3) T[g] 接收并多次发送消息:<-g, +g, +g>;

(4) C[g, h] 级连收到的消息:<-g, -h, +g·h>;

(5) S[g, h]分割收到的消息:<- g·h , +g, +h>;

(6) K[k] 发送密钥:<+k>, k∈Keyp.Keyp=Ki∪K $_{p}^{- 1}$ ∪Kpx;

(7) E[k, h]加密消息:<-h, +{h}k>, k∈Keyp;

(8) D[k, h] 解密消息:<-{h}k , +h>, k-1∈Keyp。

定义6 一个混合的串空间是由几个不同的协议合并组成的。一些特殊的串在串空间里被称为主串, 其他的我们需要考虑的串称为次要串。对于集合I∈Fact的入口点如果不依赖于次要串, 那么在一个串空间里I是不被服务的。同样, 如果在集合I内没有起源于次要串的元素, 那么I也是不被服务的。

1.4分析方法举例说明

现在我们以GONG提出的论证协议为例, 来说明一下我们所使用的分析方法。

LOWE分析了这个协议, 没有发现攻击。为了阐明我们的分析方法, 我们假设服务器不能发现重放攻击。

用init, resp和serv分别表示协议里面的正则串a, b和s。在阐述的过程中, 我们去掉一些冗余的步骤, 因为由对称性我们可以明显地看到:a和b在消息格式上有4条消息是一样的。

步骤1 首先我们要确认出那些意想不到的服务是由serv提供的:从协议中我们可以发现消息1和3是无用的, 例如, 任何一个意想不到的服务都可以使用重放法去欺骗主体a或b。因此, 串serv在不同的时间使用不同的密钥传递消息{na1, na2⊕k}passwd (a) 来抵抗重放攻击。

步骤2 在协议里可以被猜测的是passwd (a) 或passwd (b) 。

步骤3 攻击者P所知道的初始信息是a, b, s, Ks, {a, b, na1, na2, ca, {ta}Ka}Ks, {b, a, nb1, nb2, cb, {tb}Kb}Ks, {na1, na2⊕k}Ka, {nb1, nb2⊕k}Kb, {ra}k, {f1 (ra) , rb}k和{f2 (rb) }k。

步骤4 通过考虑攻击者P的所有交互 (a, b) , (Pa, b) , (a, P) , (Pa, P) 我们将列举出一些可推导的事实。由于协议的对称性, 我们没有必要考虑其他的事实可能性。从组合 (a, b) 和 (Pa, P) 和服务者串给出的两个实例{na1, na2⊕k}Ka攻击者P就可以获得下述信息:{na1, na2⊕k}Ka和{na1, na2⊕k′}Ka。此时k≠k′。

步骤5 现在我们使用集合G (信息能够被猜测的集合) 中的元素去获得一切可索取的事实, 它们是{na1, na2⊕k}, {nb1, nb2⊕k}。当然, 攻击者也可以获得消息na2, 在组合 (a, P) 的第四步, 由于攻击者P知道密钥K因此它可以从na2⊕k获得na。

步骤6 我们现在考虑集合V (能够被验证的集合) , 从第四步使用集合D (攻击者能够获得的信息集合) , 通过猜测出密码passwd (a) , 并使用它进行加密, 攻击者P可以在{na1, na2⊕k}passwd (a) 和{na1, na2⊕k′}passwd (b) 中比较消息na1。例如:如果g是猜测出的密码, 那么它可以做如下操作: $({{n a 1, n a 2 \oplus k}_{p a s s w d (a)}}_{g^{- 1}}) 1 ≐ ({{n a 1, n a 2 \oplus k^{'}}_{p a s s w d (a)}}_{g^{- 1}}) 1$ 。

步骤7 下面将说明我们如何发现本协议的另一个攻击以及在本协议中ca和cb的重要性。我们将设法找出攻击者P利用它在先前的步骤中或一些记录信息里所拥有的知识建立一个攻击的事实。首先, 从消息1里移除ca, 那么消息剩余的部分包含a, b, na1, na2, 它们都能被攻击者所获得。时间戳ts是任意的, 因此可以在第五步用对消息4解密的密钥对消息进行加密。结合本协议就可以构建一条和消息1形式相同的消息使用Ks进行加密并和原来的实际记录值相比较。

这里ca的重要性很明显, 并且要注意到攻击者P不可以通过先前步骤或信息获取ca。因此, 如果ca在目前的消息1里, 它就可以阻止猜测攻击, 以防止攻击者P可以构建类似信息去核实猜测。对于cb的分析是类似的情况。

2混合协议验证分析

2.1混合协议的脆弱性分析

文献[5,6]的作者已经分析了多协议攻击, 并提出几种技术以确保协议在一个复杂的环境中仍然是安全的。在这篇文章中, 我们在多协议攻击的基础上, 考虑到一些针对低熵密码进行的猜测攻击, 将他们进行混合, 进而对多协议攻击做进一步的论证。Guttman对此作了一些实用证明, 但是Guttman证明的结论并不总是适合于所有的多协议攻击。我们使用EKE协议来说明多协议猜测攻击是如何进行的。首先我们根据文章的分析需要对猜测攻击做两个假设:

(1) 能够被猜测的密码通常都是一些低熵密码。与此相对的一些像机器产生的高熵密码通常都有一个很大的密钥选择空间, 那么猜测攻击就很难实现。

(2) 核实一个猜测并不需要和其他部分在线交互。在本文中, 我们只考虑完全离线的猜测攻击。

现在我们来看一下由Mellovin和Berritt提出的EKE协议[7]:

主体a和b试图对共享会话密钥k达成一致, a的不对称密钥passwd (a, b) 代表a与b和pka共享的密码, Lowe[8]使用FDR分析了这个协议没有发现攻击。

我们再考虑另外一个由GONG提出的协议[1]:

Msg1. a→b:{c, n}k1

Msg2. b→a:{f (n) }passwd (a)

K1是a的公开密钥, c是一个用于阻止攻击的多余的随机数。n是一个任意数, f是一个公开的函数。这个协议在单独执行的时候也没有发现攻击的存在。然而, 如果这个协议和EKE组合在一起, 形成了一个混合的环境, 那么下述攻击就会出现:

攻击1 用p1代表EKE协议, p2代表GONG提出的协议。攻击者起初可以猜测出p1的密码passwd (a) 并用它加密消息1进而得到pka, 攻击者可以猜测p2的密码passwd (a) 从而得到f (n) 。从攻击者得到的这些信息它就可以得到数据值n, 并用从p1得到的密码passwd (a) 对n进行加密。最后, 它可以将获得的值与它在消息1中的记录值进行比较去证实它的猜测。

现在我们考虑另外一个和在文献[1]中提出的协议类似的认证协议, 协议描述如下:

Msg1. a→s:a, s

Msg2. b→a:ns

Msg3. b→a:{{a, ns}pva}passwd (a)

将这个协议作为p3。这里用户a的目的是向服务器S认证自己的正确性。如果相应的a的公钥pka对于攻击者来说是未知的, 那么这个协议也是安全的。然而, 当协议与p1混合在一起使用的时候, 由于其他原因, 下述攻击就会出现:

攻击2 起初, 攻击者通过猜测密码passwd (a, b) 并且在p1中解密消息1得到pka。接下来攻击者又可以猜测密码passwd (a) 并且解密消息3进而得到{a, ns}pva.最后, 攻击者使用pka解密消息{a, ns}pva, 并将p1中的信息ns与它发送消息2里的信息ns相比较匹配, 从而证实他的猜测。

在现有的协议里都可以发现类似的攻击。协议p1, p2, p3在独立的环境中执行都是安全的情况下这些攻击也可能发生。

2.2混合协议的健壮性验证

在本节中, 我们以EKE协议为例, 从2.1节提到的多协议猜测攻击的脆弱性分析中获得一些关键信息, 通过这些信息, 我们对多协议猜测攻击附加一些限制条件, 从而保证了多协议运行的安全性。并对多协议的安全性做了形式化的验证。EKE协议如图1所示。

步骤1这里意想不到的服务仅仅是主体b的, 对应{pk}passwd (a, b) , b给出了{{k}pk}passwd (a, b) 。

步骤2 G={passwd (a, b) }。

步骤3 MP={{pka}passwd (a, b) , {{k}pk}passwd (a, b) , {na}k, {na, nb}k, {nb}k}。

步骤4 可能的交互有以下五个: (a, b) , (a, P) , (a, Pb) , (P, b) , (Pa, b) 。通过 (a, P) 交互, 攻击者P可以得到消息PK′a。因此D={PK′a}。

步骤5 通过猜测获得的Facts为O={PKa, {k}PKa}。

步骤6 可以验证下述信息:facts (V) :V=ϕ;不管怎样, 通过第四步和第五步, 攻击者就可以进行下面的操作:pk′a={{pka}passwd (a, b) }g-1 (攻击者P首先要猜测出g)

步骤7 一个可行的事实是C=ϕ。因为在MP∪D∪O中找不到一个可以用来建造一条记录值进行验证的项。从上述的分析结果来看更详细一点, 从第六步和第七步来看, 只要下述条件满足, 那么协议仍然是安全的,

1) pka不是从其他的串得到的;

2) 没有用pva进行加密的项 (其中pva=pk $_{a}^{- 1}$ ) ;

3) 要确保没有用pka加密的项。

现在我们在一个混合的环境中来描述这些情况, 此时EKE协议作为主要的协议, 其他的协议都作为次要的协议。

定义7 Σ是一个串空间,

(1) Init[pka, passwd (a, b) , k, na, nb]是在Σ中的一个串空间集合, 它的迹是:

<+{pka}passwd (a, b) , -{{k}pk}passwd (a, b) , +{na}k, -{na, nb}k, +{nb}k> (Σinit是发起者串) ;

(2) Resp[pk, passwd (a, b) , k, na, nb]是在Σ中的一个串空间集合, 它的迹是:

<-{pka}passwd (a, b) , +{{k}pk}passwd (a, b) , -{na}k, +{na, nb}k, -{nb}k> (Σresp是响应者串) 。

Σinit, Σresp是一对不相交的串, 它们形成了串空间Σ的主串, 记作ΣP (=Σinit∪Σresp) Σ中其余的串都是次要串记作ΣΣP (ΣΣP是一个集合的不同操作者) 。

定义8 对L0和ID作如下定义:

L0表示所有项的集合, 例如对于:

1) ∀pk∈PK, ∃f ∈MP ∪ D∪ O pk⊂f

2) ID=Ik[D], k =PVa∪PKa

使用上述的程序分析方法和串空间分析方法, 我们对上述的情况进行建模。我们的主要定理表明:只要串空间模型满足下列条件, 那么一个把EKE协议作为主要协议的混合协议环境在遭受到猜测攻击的时候仍然是安全的。

定理1 Σ代表一个混合的串空间, EKE协议代表混合协议环境中的主串, C代表Σ中的一个丛。如果下列条件满足, 那么在丛C中就不会遭受到猜测攻击:

1) pka在Σ中是不被服务的;

2) ID 在Σ中是肯定不被服务的。

证明:我们先来做一个分析。首先, 通过观察我们知道, 使用集合V或C来做验证如果能成功的话, 那么一个猜测攻击就是可行的。因此, 我们使用上述的条件考虑这些集合以证明这套在上述条件满足的情况下永远是NULL的情况。

1) pka是不被服务的。从第五步来看, 如果 (D∪MP∪KP) ∩O≠ϕ, 那么验证任何g∈G是可能的。在这种情况下, 通过我们的分析可知, 当且仅当pka=pk′a的时候 (D∪MP∪KP) ∩O= (pka) 。然而, 根据定理1的条件, pka在串空间模型Σ中是不被服务的, 例如:如果pka源于 (=Σinit∪Σresp) , 那么对于任意的pk′a源于ΣΣP, 并且pka≠pk′a, 因此, (D∪MP∪KP) ∩O≠ϕ。

2) 为了做验证, 再注意到因为O={pka, {k}pka}, 并且k∉ (D∪MP∪KP) , 我们必须保证pka是可验证的。这一分析过程表明pka在攻击者串P中是不可验证的。第一部分的内容表明如果在串空间Σ中pka是不被服务的, 那么在串空间Σ中pka是不可验证的。如果用pka或者pk $_{a}^{- 1}$ 加密的f∈ΣΣP是可验证的, 那么一个验证是可行的。然而, 矛盾的是:条件2要求ID在串空间Σ中是肯定不被服务的。否则也就不会有源于次要串的项。因此, 只要该条件成立那么一个验证尝试是不可行的[9], 从而保证了混合协议的健壮性要求。

3结论及下一步计划

在这篇文章中, 我们介绍了一种新型的攻击称为基于低熵密码的多协议猜测攻击。我们使用一种系统化的程序分析方法分析了多协议的脆弱性。接下来我们使用串空间模型的方法证明了只要在我们分析出的条件满足的情况下, 那么一个协议就不会遭受到多协议猜测攻击。此时, 有一些点值得提一下:当我们仅仅考虑攻击者的知识能力, 或者仅仅考虑固定攻击者的能力的时候, 我们的协议分析方法相对来说更健壮。我们分析方法的独特性在于当一个协议在一个混合的环境中运行的时候它允许存在脆弱性, 但是根据我们限定的条件, 它禁止再出现其它新的脆弱性, 那么我们去更具体地设计一个协议是可能的。

这项工作的下一步计划是自动化程序, 我们已用来探测可能的猜测攻击。另外一个可能的计划是找到一个普遍的实用性的技术去阻止多协议猜测攻击。

摘要：对安全协议进行猜测攻击, 如果攻击者不能正确猜测用户秘密, 那么他就会设法使用其他的信息来验证这种猜测。过去仅考虑了协议在独立执行的时候所遭受到的攻击。现引入一种新类型攻击称为多协议猜测攻击, 它可以存在于混合协议中。接着, 采用程序化分析方法对协议可能遭受到的猜测攻击进行了分析即协议的脆弱性分析。最后, 加入一定的限制条件并使用串空间建模, 进而保证了协议的安全性即协议的健壮性验证。

关键词：多协议猜测攻击,串空间,程序化分析,形式化分析

参考文献

[1]Li Gong, T Mark A Lomas, Roger M Needham, et al.Protecting poorlychosen secrets from guessing attacks.IEEE Journal on Selected Areasin Communications, 1993, 11 (5) :648-656.

[2]Thayer F′abrega F J, Herzog J C, Guttman J D.Why is a security protocolcorrect?IEEE Computer Symposium on Security and Privacy, 1998.

[3]Thayer F′abrega F J, Herzog J C, Guttman J D.Strand spaces:Provingsecurity protocols correct.Journal of Computer Security, 1999, 7 (2/3) :191-230.

[4]Javier Thayer F′abrega, Jonathan F, Herzog C, et al.Mixed StrandSpaces.In Proceedings of the 12th IEEE Computer Security Founda-tions Workshop, volume 27 (2) .IEEE Computer Society Press, June1999:10-14.

[5]Alves-Foss J.Multi-Protocol Attacks and the Public Key Infrastructure.In proc.National Information System Security Conference, October1998:566-576.

[6]Alves-Foss J.Cryptograpyhic Protocol Engineering:Building Securityfrom the Ground Up.In Proceedings of International Conference on In-ternet Computing, June 2000.

[7]Bellovin S M, Merritt M.Encrypted key exchange:Password-based pro-tocols secure against dictionary attacks.In Proceedings of the 1992IEEE Computer Security Conference on Research in Privacy, 1992:72-84.

[8]Gavin Lowe.Analyzing protocols subject to guessing attacks.Workshopon Issues in the Theory of Security (WITS’02) , January 2002.

[9]Joshua D, Guttman, Javier F.Thayer.Protocol Independence through Dis-joint Encryption.13th IEEE Computer Security Foundations Workshop, 2000:24-34.

协议分析验证篇2

甲方：上海市人才服务中心人才诚信部乙方：

为办理相关人事事务，乙方自愿委托甲方对其_______________________________________________学校（研究生□；本科□；专科□；其他□）学历，（博士□；硕士□；学士□）学位，进行诚信验证。一经委托，验证工作不得中途停止，费用不予退还。（评估将会产生三种结果：属实、虚假、非学历教育。特此说明。）①学历诚信验证费元/证书，共本；②学位诚信验证费元/证书，共本； ③其他费用______________元，事项：；

以上费用共计________________元（RMB）（大写）。

如无特殊情况，验证工作将于协议签订生效后第二天起（伍□；拾□；拾伍□）个工作日内完成。期间_____本证书原件；_____本证书复印件；_____本学历或学位证明，暂保管于甲方。

证书存在以下污损状况： ____________________________________________________________；验证结束后乙方持本协议领取评估报告及真实证书原件。

甲方：上海市人才服务中心人才诚信部

经办人：

受理日期：200年月日

注：本协议个人涂改无效乙方：受理日期：200年月日

（证书验证进展情况查询及疑义证书处理流程见背面）

诚信验证委托协议及告知书

甲方：上海市人才服务中心人才诚信部乙方：

乙方自愿委托甲方对其___________________________学校（研究生□；本科□；专科□；其他□）学历，（博士□；硕士□；学士□）学位，进行诚信验证。一经委托，验证工作不得中途停止，费用不予退还。（评估将会产生三种结果：属实、虚假、非学历教育。特此说明。）

①学历诚信验证费元/证书，共本；②学位诚信验证费元/证书，共本； ③其他费用______________元，事项：；

以上费用共计________________元（RMB）（大写）。

证书存在以下污损状况： ____________________________________________________________；验证结束后乙方持本协议领取评估报告及真实证书原件。

甲方：上海市人才服务中心人才诚信部

经办人：

受理日期：200年月日

注：本协议个人涂改无效乙方：受理日期：200年月日

（证书验证进展情况查询及疑义证书处理流程见背面）

验证进程查询及疑义证书的后续办理告知

一、查询证书验证进程：

1、登录市人才服务中心证书验证查询网页，http://61.152.159.229/index.ftl；

2、在“学历认证查询”区域点击“more”；

3、输入证书上的姓名和颁发证书的学校；凡标记为“鉴定完毕”的，可至受理窗口领取验证结果。

二、疑义证书后续办理流程：

1、若甲方认为证书真实性存在疑义，（证书真实性存疑、学籍存疑、经历存疑）将向乙方出具《证书保管通知》；

2、乙方在收到《证书保管通知》2个月内向甲方提供证书颁发机构出具的证明；

3、甲方在收到乙方重新提供的证明材料后的5至10个工作日内对材料进行复核；

4、若复核结果属实，甲方将向乙方归还证书，出具验证报告（学习或工作经历属实但证书虚假的不在此列）；

5、若复核结果为不属实，或乙方无法提供证明材料，甲方有权将该信息归入上海市人事不良信息查询系统及上海市联合征信系统；

6、存在不良信用信息记录的人员，需建立人事信用档案，通过相应流程消除不良信用记录。

联系地址：中山西路620号3楼A座；

中山西路620号1楼7号窗口；联系电话：62337946 联系电话：62738701*29

4验证进程查询及疑义证书的后续办理告知

一、查询证书验证进程：

1、登录市人才服务中心证书验证查询网页，http://61.152.159.229/index.ftl；

2、在“学历认证查询”区域点击“more”；

3、输入证书上的姓名和颁发证书的学校；凡标记为“鉴定完毕”的，可至受理窗口领取验证结果。

二、疑义证书后续办理流程：

1、若甲方认为证书真实性存在疑义，（证书真实性存疑、学籍存疑、经历存疑）将向乙方出具《证书保管通知》；

2、乙方在收到《证书保管通知》2个月内向甲方提供证书颁发机构出具的证明；

3、甲方在收到乙方重新提供的证明材料后的5至10个工作日内对材料进行复核；

4、若复核结果属实，甲方将向乙方归还证书，出具验证报告（学习或工作经历属实但证书虚假的不在此列）；

5、若复核结果为不属实，或乙方无法提供证明材料，甲方有权将该信息归入上海市人事不良信息查询系统及上海市联合征信系统；

6、存在不良信用信息记录的人员，需建立人事信用档案，通过相应流程消除不良信用记录。

联系地址：中山西路620号3楼A座；

协议分析验证篇3

从表1信号质量经验上看前三面天线应属同一档次，0.10m口径差值信号质量差值都是4％。需说明的是0.55m中卫天线是出口型天线，早就试收感觉精度较好，与某厂0.60m天线相当；同洲CAK45-PW天线是同洲CAK45-PW是深圳市同洲电子股份有限公司针对中国直播卫星项目开发的卫星电视接收天线，是中九同洲套站用天线，初次使用第一感觉是外观漂亮，设计合理，实收效果、精度感觉都不错（图1）。后两面天线质量要差些也是常规经验判断，0.55m天线与0.75m天线口径差值0.20m，信号质量差值仅3％与前面天线径差信号质量太多，至于差多少，天线效率有多高很难凭经验判断，这后两面也是正厂天线，天线差点效率应该有60％才合常理是一般判断。还有同洲N6188信号质量与帝霸901信噪比的关系，就是说信号质量1％相当于信噪比多少，也值得探讨，以方便以后收视作较科学的判断。这些年我一直认为信噪比显示的分贝（dB）值与天线分贝、载噪比（C/N）分贝近似，这次动用几面天线测试以准备再次厘清，有这个想法就产生了本文《中星九号直播卫星测试数据验证分析报告》。据表1天线增益数据加上后初步分析，假定这些天线的效率为70％，表后列出了这5面天线在该效率下的天线增益值，设定前三面天线效率为70％，信号质量、天线增益值表1可查，0.35~0.55m天线径差增益、信号质量来求取之间的等值关系，（35.22-31.74）÷（42-34）=0.435（dB），即信号质量1％相当于天线增益0.435dB，这只是初步收视假设推论计算结果，还得继续收视验证这一最初数据。表1中0.35—0.45—0.55—0.35m天线增益级差值分别是1.78—1.70—3.48dB，这些天线增益级差以备后分析用。

为了准确获得测试数据，再次复测已是获得表1数据一月以后的事情。这次要厘清信号质量—信噪比—天线增益三者间的关系，其方法是用这看似三面精度相当的天线，同一只圆极化高频头，收视中九直播和天浪直播的圆极化信号，其理由都是圆极化信号且频点接近，中九用ABS信号、天浪用DVB信号传送邻星干扰少。用三面天线径差信号质量—信噪比—天线增益取得其间关系值，这个值原理上是数学上等值关系来导取。这里级差天线增益与天线效率高低无关，天线效率相等，级差相等、增益相等论，“借用”级差增益值达到验证级差信噪比的目的。

用这3面精度接近的天线都在适当位置精心调试对准中九，选用了一只刚收到经测试是我手中4只中九头最好的，同洲CL11RA改进型圆极化高频头，此高频头也是同洲为中九直播开发设计的配套专用中九圆极化高频头（图2），噪声系数≤1.3dB无水分。同洲中九专用头波导管腔中的极化片用料设计精良，与有机玻璃极化片比高出0.5～0.8dB。这只高频头与其它中九专用高频头对比测试，信号质量要高出2～3％，达精选O.S 22M及台扬AP8双本振线极化高频头品质水平，可称中九专用头精品，其它中九头0.35m天线本地收不下122°E右旋天浪直播，否则动用O.S 22M、台扬AP8双本振来虚拟收视中九，需用DVB-S、ABS-S功分联机工作，DVB-S机设置22K开关保障10600MHz本振工作正常，工厂码修改中九机参数来测试完成。用这只同洲高频头在无云天气下短时间测完3面天线中九直播的4个频点，又用这3面天线转向收视天浪直播4个频点，0.35m天线天浪最后一个频点还是没法过门限，最后只取天浪前3个频点数据。多频点测试目的是得到更多的测试数据有较多的比较，中九直播收视数据见表2，天浪直播收视数据见表3。也复测了0.75m、0.90m天线中九收视，11840频点分别是47％和50％。

从表2可看出，天线换用高频头后中九直播信号质量有所等值提高，但天线0.10m级差信号质量4％并没有改变。分析表3天浪直播收视数据，0.35—0.45m天线频点信噪比差值依次为1.75—1.75—1.70dB，平均值是1.73dB；0.45—0.55m天线频点信噪比差值依次为1.8—1.75—1.8，平均值是1.78；0.35—0.55m天线信噪比平均值是3.51dB，即以上两信噪比平均差值之和。把以上天线级差信噪比平均值与表1对应天线信号质量、天线增益级差例表4供分析之用。表3是收视原始记录数据，没作任何技术修正。

此项目的是寻找信号质量—信噪比—天线增益间的换算值。信号质量—信噪比的换算值:0.35~0.55m数据对比分析中误差最小，选中此项，即信号质量1％等值于信噪比（3.51÷8=0.43875dB）的实测数据，保留2位小数即同洲N6188信号质量1％等值于帝霸901信噪比0.44dB。天线增益—信噪比的换算值:表4中这三面天线级差实收信噪比—设定天线增益误差都很小（此误差放在天线效率讨论），以此认定天线增益分贝与实测信噪比分贝是等值关系应当没有争议，这样的测试，有条件都可以验证。

表4数据分析验证了信噪比与天线增益间的等值关系，帝霸901信噪比分贝等同于天线增益分贝物理量有了结论，多年的近似值得到了等同值验证结果，帝霸901的信噪比完全可当载噪比值（C/N）直接应用，其门限值与载噪比门限值也接近。同洲N6188信号质量1％等值于信噪比采用实测数据0.44dB直接应用，也可以说就是0.44dB，与表1初步推论（0.435dB）也相当接近。一次中九直播与天浪直播收视分析，卫星收视器材是普通卫星天线和ABS-S、DVB-S接收机，业余条件下当测试仪器应用结果，原理就是数学上的等值替换法在卫星收视中的一种推理应用。

笔者这些年关注卫星收视技术，总想在业余条件下完成较为专业的测试工作，今天不妨把上面的分析验证结果推广应用，试一下业余条件下测试这五面卫星天线效率和验证有关收视理论中的载噪比（C/N）值，其中C/N值涉及场强、门限、天线增益等卫星收视专业技术参数，也可间接验证上述有关的技术测定推论的准确性。通常在业余条件下，测试天线效率（增益）用以下两种方法:方法①用已知天线效率（标准天线）、推测另一天线（测试天线），这两天线同收一个卫星频点，用两天线的信号品质换算成天线增益分贝值，计算即可求出测试天线的增益（效率）；方法②用测试天线收视得到信号质量（信噪比）换算成C/N值查表来求取天线增益估测值，但C/N值涉及接收机门限、LNB噪声系数、场强、环境噪声等都会影响天线效率计算的正确值，只能得到大概的估测天线增益。

表4前三面天线分析中发现，信噪比实收两位小数的显示，可反映这三面天线微小的增益差值，相反信号质量就不能显示微小差值。看表中对比误差值，这三面天线效率相当接近但也存在很小的增益差距。仔细笔对表4中对比误差项，0.35—0.55m天线信噪比（实收）与设定增益（70％）误差最小（+0.03dB），说明这两面天线的效率最接近。再比对表4中0.35—0.45—0.55m对比误差（-0.05dB）—（+0.08dB），明显是0.45m天线增益略低一点，如果0.45m天线实收信噪比提高0.05dB、0.55m天线信噪比低0.03dB，这三面增益（效率）相等。在这里用天线效率差值无法证明这些天线效率的真实高低，只能设定评审方法来判断天线效率。

表1中实收信号质量，其实是间接代表了各天线收视的C/N值，也反映了天线效率在收视中的差别。知道了数字接收机信号品质能换算成实用分贝值，用表1、表3实收信号品质数据，再计算天线效率（增益）就不再是难事。只要设定一面天线的效率标准，用此天线的级差增益与其它测试天线实收级差信号品质比对，测试天线的增益（效率）简单计算就可得到。天线等级是这样划分的，效率70％（优）、60％（良）、50％（合格）。下面试用设定评审方法来鉴定这些天线的品质。表4中0.35—0.55m这两面天线效率最接近，就从这里开始。二次设定0.35m天线效率为70％为基准试计算这五面天线的效率和增益，前三面天线增益微小差别参照表5、表1数据，其余天线采用表1数据，看看计算的结果是否符合情理就知道了（计算过程略）。

天线效率级差增益是这样计算的:80—70—60—50％、0.58—0.67—0.79dB。

0.35m天线设定效率70％，天线增益31.74dB。末打磨前天线效率63.43％，天线增益31.30dB。

0.45m天线实际效率经计算为69.25％，天线增益33.47dB。

0.55m天线实际效率经计算为70.52％，天线增益35.25dB。

0.75m天线实际效率用上方法①0.35m为标准天线，参照表1数据计算，天线效率53.04％，天线增益36.58dB。

0.90m天线与0.75m天线使用多年，早就多次测定过这两面天线信噪比差值为1.5dB，中九直播收视信号质量在3～4％间属正常显示值，就以此来计算天线效率。经计算0.90m天线效率为50.13％，天线增益38.08dB。多年来今天才真正弄清了这两面天线的实际效率和增益，在天线等级中只能算合格产品，与以前估测和常理判断天线效率差了10％左右。如果这两面天线效率能达70％，收视中九直播还可稳定提高信号质量3％。

以上是笔者设定评审计算结果，却较真实反映了这些天线的品质，应当都满意，好的是优级品，低的在合格品内。这五面天线实测的增益和效率整理见表5，后两面天线实测与厂商宣传提供天线增益参数少了2dB左右。

知道了同洲N6188信号质量1％等值于0.44dB，用以下方法，还可计算门限、载噪比（C/N）值，下例计算采用表1数据其理由是高频头增益适中，这只同洲中九头比百昌、高斯贝尔信号质量要高1％，又比后来那只同洲头L极化信号质量差2％。

同洲N6188门限C/N值: 同洲N6188门限信号质量实测为12％，0.44x12=5.28dB，该机在FEC=3/4时，其信号门限值为C/N=5.28dB，与帝霸901门限差不多，低于国际标准C/N=6dB的门限值，但画质优于帝霸901。

0.35m天线实际收视本地中九场强44dBw的C/N值: 本地0.35m天线实收信号质量34％，0.44x34=14.96dB，本地0.35天线实收中九直播卫星C/N=14.96dB，已超过一般广播收转C/N=14dB水平级别。

0.35m天线门限余量:0.44x（34-12）=9.68dB ，0.35m天线本地门限余量为9.68dB，如果换用表2高频头，门限余量升到10.56dB。

为了验证以上计算的可行性，特地摘录了合符中九直播场强等值线Ku波段天线直径与场强及C/N的关系列表（表6）（注2），以验证以上实收计算的正确性。表中数据采用DVB-S制计算出来的。中星九号直播卫星采用的是ABS-S制式数字信号压缩传送，其门限比DVB-S低1.5～2dB，表5场强用于ABS-S查场强还应加1.5～2dB。笔者本地中星九号场强是54dBw，查表5应按56dBw值查询，可以看出0.35m天线实收C/N=14.96dB与表5表中（0.34m、C/N=14dB）计算值误差约（+0.8dB），说明本地中星九号直播卫星落地场强确有54dBw，也间接再次验证了上面推理计算结果的正确性。

实际收视也作过简单验证，用0.35m天线收视中九，用边料地砖挡去天线大部分（见图3、图4），这时信号质量还在门限上（16％），验证表明本地小于0.20m天线可过门限，表5查询本地门限值天线最小0.15m。

最后剩下这三面天线设定70％真实效率讨论，能否达此标准来研讨，以前也对天线效率讨论过，能达70％效率天线是优质品不多见。以上设定评审天线方法有一定的说服力。这里再用0.35m天线实收C/N值来讨论:0.35m天线本地C/N=14.96dB，这里天线效率70％、LNB1.30dB、接收机门限5.30（5.28）dB，笔对表6天线效率、门限误差要扣除约1.40dB，实际C/N=13.56dB，与表6误差约（-0.40）dB，换用表3中九头实际C/N=14.44dB，这些实收C/N值与理论计算值（查表）误差在小数级别应当可信。天线效率讨论过，场强相信本地应有54dBw，唯一没讨论过LNB噪声系数，表1用高频头属中等货，手中4只中九头上差信号质量2％，下差1％，悬殊1.30dB之多，换算成天线效率就是18％的差距（天线效率50～70％间），可见高频头品质的选用与要求同卫星天线精度是一样的重要，对C/N值的影响一样不亚于天线效率，能真正达LNB 100°K（1.29dB）噪声系数标准算优质品了，那些标称噪声系数0.50dB的高频头水份太重。笔者认为，以上多种方法客观公正全面验证了这些天线效率，虽然是业余级别水平，最简单的收视设备，供参考的可信度还是较高的，是业余条件下较佳的测试方法之一。

笔者卫视收视多年，初期过于相信厂商提供的参数，初次用0.75、0.90m天线推测信噪比与天线增益值是这样换算的（1.8:1.5=1.2:1），忽略了天线效率不等出了偏差，认为信噪比值偏小天线增益值，参照天线效率估测偏高，导至推测其它天线增益出现误差偏大后果。今天重新评审使用中2.40m网状极轴天线的效率，多次与上面0.75m、0.90m收视对比过，信噪比多出7.50dB、6.00dB，今天来计算这面2.40m网状极轴天线的Ku增益是（38.08+6.00=44.08dB），查表得知相当于1.83m天线50％效率的天线增益（44.22dB）水平，这面正馈天线使用感觉一直不错，很多2.40m天线Ku效率只有0.90m偏馈天线水平。从使用帝霸901至今已5、6个年头，其实这期间一直在探讨信噪比的问题，今天才得到圆满答案，在业余条件下花了不少时间，走了一个漫长的艰辛探寻之路。就这次数据分析报告，并不是一次复测就完成了，中间长达一月以上，并非一帆风顺。四川冬季要找好天气不容易，天气不好天线前方漂浮不定的云层影响测试数据；在楼顶测试地点选址也重要，其间也遇到天线换位置后，信号质量总是误差1％，分析原因在于受通讯微波干扰造成，只得寻找干扰最小的同一地点重新测试完成；在本文数据分析时由于方法不正确也曾一度中断过，分析笔对、资料整理也相当花时间。收视圆极化波线极化高频头免不了极化片，笔者非常关注这方面的研究，想用插拔极化片来验证信号质量1％与信噪比间的关系，却因线极化腔体及极化误差诸多原因，导致系列数据不一误差太大无法采用，耗了不少时间。但对Ku圆极化高频头有了全面深入了解，也获得了有关极化片测试的宝贵数据，对极化片设计、制作、选料都重新作过研究验证，用0.55m天线实测极化片增益，不同品牌高频头收视中九信号质量6～9％，收视天浪信噪比2.5～3.4dB。有兴趣再另文详述。

注1:见《寻星2000》P151。

快速身份验证协议概述篇4

1 FIDO快速身份验证协议概述

FIDO (fast identity online) 线上快速身份验证联盟是2012年成立的行业协会, 旨在提出一个开放标准的强认证协议。目前在线用户多依赖于以密码为主要验证手段的验证方式, 既繁琐又不能保证安全, 而且随着数据泄露事故的频发, 传统的基于密码的验证方式已越来越不能满足用户的需求, FIDO协议的目标就是减少用户对密码的依赖, 少用或不用密码, 并且保障强认证进行安全身份验证。FIDO通过两个子协议实现安全登录验证, 分别是通用认证框架 (Universal Authentication Framework, UAF) 与通用第二因子 (Universal 2nd Factor, U2F) 。FIDO协议以公开密钥密码学为基础, 采用规范的非对称公私钥对来保障安全, 通过物理密令的方式进行登录账户。

2 FIDO认证协议工作流程

当用户打开浏览器时, 插入他的本地验证设备, 客户端发现能够被服务器识别的设备中可用的认证器, 客户端显示服务器允许的认证器列表, 然后用户选择一种方式进行注册, 认证器生成一对公私钥对, 客户端存储认证器和用户信息, 这样用户就可以使用本地设备开始网站注册, 当用户认证成功后, 即可登录到与设备厂商合作的商家网站或应用程序, 整个验证过程同时验证设备和用户信息, 提高了用户体验也保证了安全。以本地设备密码卡为例, 认证协议工作流程主要包括:注册, 登录, 交易确认, 注销。验证的具体流程如下:

2.1 注册消息流

如图1所示;在注册阶段, 当用户第一次使用时, 客户端提示用户注册, 用户输入用户名和口令, 客户端验证后传递注册请求给服务器, 服务器返回注册响应, 密码卡生成一对公私钥对, 私钥保存在密码卡内, 服务器保存公钥, 并将用户信息保存在数据库, 验证注册消息的合法性后, 发送验证结果给客户端, 提示用户注册成功。

2.2 认证消息流

如图2所示;在认证阶段, 客户端本地验证用户输入的账号和口令, 传递认证请求给服务器, 服务器查询数据库, 返回认证响应, 密码卡根据认证需求用私钥对认证请求进行签名, 并返回密钥认证数据, 接着服务器查询公钥等用户注册信息, 并验签认证信息的合法性, 返回校验结果。

2.3 交易确认消息流

如图3所示;在确认阶段, 用户使用客户端输入交易内容, 客户端验证密码卡用户口令正确后发送交易确认请求给服务器, 服务器查询数据库验证其是合法设备返回交易确认响应, 密码卡内私钥进行交易确认请求签名, 服务器查询公钥等用户注册信息, 验签交易确认信息合法性并返回校验结果。

2.4 注销消息流

在销户阶段, 用户发起销户请求, 客户端验证用户口令后, 发起销户请求给服务器, 服务器验证其是合法设备后标注用户为删除状态, 返回用户销户处理给客户端, 客户端删除密码卡内用户私钥并提示操作完成。删除状态的用户将不能再进行认证和交易确认。

3 FIDO协议的应用

从在2012年7月建立之初的Pal Pal、Nok Nok Labs、联想等不到十位联盟成员到2015年9月已有240多位成员, FIDO联盟成员致力于建立一个统一的产品体系, 使得用户能通过使用满足FIDO协议规范的产品登录到网站、在线服务或用于支付, 用户登录设备更加方便, 企业网络访问也更加安全。目前已经有许多支持FIDO协议的产品设计出来, 越来越多的厂商也加入FIDO联盟, 逐渐推出了符合FIDO标准的身份验证设备来投入应用。

Myris:基于人眼虹膜识别技术的设备, 是由FIDO联盟成员Strong Auth和Eyelock联合推出的使用USB接口的身份验证设备。Myris可将人眼的虹膜生物特征信息转换为特定的代码, 然后与用户的加密代码进行匹配, 从而决定是否授予访问者权限[3]。Eye Lock公司表示Myris比指纹验证更加精确, Myris使用双虹膜扫描技术, 降低了误报率, 且每个Myris支持多达5个用户, 用户在Myris中完成验证, 虹膜信息储存在Myris本地设备中, 保护了用户的生物信息不会暴露。

Yubikey:是一个可以在使用时生成一个一次性密码 (OTP) 的小型USB设备[4], 当用户插入设备时, 按下设备上的按钮, 设备会在窗口上自动模拟键盘, 在用户输入信息后生成设备ID和一次性密码, 同时签名一个挑战。Yubikey可以兼容SSO (Single Sign On, 单点登录) 认证的过程, 且Yubikey生成的一次性密码可以作为SSO认证的第二因子, 用来加强登录验证的安全性, 不过作为一个令牌设备, 需要随身携带。

Google也有了支持FIDO U2F标准验证技术的USB Security Key安全密钥来存取Google服务, 访问者可以使用Security Key作为登录的更为安全的两步验证机制进行Google服务。Security Key作为一种安全登录的USB设备, 用户在登录假冒的Google网站时, Security Key不会工作, 当登录正确的Google网站时, 无需输入密码, 只需按提示按下按钮。新版谷歌浏览器Chrome已经支持U2F协议, 所以除了Google服务, 其他支持FIDO U2F协议的网站也能通过内置符合该标准的Security Key让用户在Chrome进行登录。还有与联盟成员Pal Pal合作的三星Galaxy S5智能手机, 使用成员Nok Nok Labs的基于FIDO标准的指纹传感器技术, 只要用户使用指纹验证成功就可以登录到Pal Pal商家的网站, 不需要输入密码或登录信息。

4 结语

FIDO协议是最近新兴的一个身份验证协议, 协议使用户摆脱记忆密码的烦恼同时保证安全的强认证。本文通过分析FIDO认证协议流程和应用介绍, 阐述了FIDO协议的具体工作原理。未来FIDO联盟还需要更多的行业加入, 同时解决各厂商设备之间的互操作性来认证用户, 并且随着技术发展, 越来越多的FIDO设备的出现, FIDO将成为解决网络环境中用户安全简单认证的一个开放标准协议。

摘要：为了解决目前在线用户进行身份验证时, 选择的验证方式在可用性和安全性难以权衡的问题, FIDO联盟提出了去密码化的强认证安全协议——FIDO协议。它的特点是用户可以不用使用密码进行登录, 让用户从复杂的密码中摆脱出来, 且保护用户隐私。本文通过研究FIDO认证系统的工作原理, 分析了FIDO协议工作流程, 阐述了协议的应用。

关键词：验证,FIDO协议,密码

参考文献

[1]何争.网上交易安全[J].信息与电脑, 2014 (8) :69-70.

[2]李琛.一种基于两层在线身份认证的安全框架体系设计与实现[D].山东:山东大学, 2014.

[3]沈建苗.指纹OUT啦, 虹膜才是你的新身份[J].微电脑世界, 2014, 02:8-10.

外挂网络验证系统需求分析篇5

形势分析：

当前，外挂制作变得越来越“平民化”，很多程序新手加入到这个行列中来，外挂由此不再显得陌生和神秘。在这些制作外挂的人当中，有些是为了研究技术，有些是为了好奇，有些是为了自己玩游戏不那么累，有些是因为应朋友的要求而制作，另外还有一些就是专门以营利为目的，这些人水平有高有低，做出的外挂有好有坏。当他们的外挂制作得越来越实用、越来越成熟时，也就会想把自己的外挂进行推广。当然，这种推广不一定就是营利性质的，对于大部写程序的人来说，大家能使用自己写的程序是人生一大快乐，能满足自己小小的虚荣心。

由此会产生一个问题，那就是，自己辛苦写的外挂如何能不被他人滥用或盗用？很多人会想到，做一个网络验证系统！对，这的确是个好方法。但，并不是每一个写出外挂的人，都能写出网络验证系统。因为外挂技术与网络系统技术并没有太多的相似性。在这样的形势下，如果能有一个通用的网络验证系统，那该多好啊。诚然，当前网络上有一些免费的或者破解的网络验证系统，但其实用性、易用性不足，用户要往其中投入大量时间精力，影响原本的外挂开发进度。外挂制作者迫切需要一个简单实用的网络验证系统，以满足外挂网络验证的需求。

系统分析：

本网络验证系统，应当立足于外挂制作者的角度，全力构建一个简单快捷、方便实用的网络验证平台，要做到自动化程度高，同时追求安全高效，部署方便，使用方便。要最大限度的体现出本系统的通用性与易用性，充分发挥易维护性与拓展性，一劳永逸的解决外挂制作者对网络验证的烦恼。

技术分析：

本网络验证系统只是一个小型的系统，不需要很多的资源，因此，研究后认为，使用跨平台的JAVA技术可以快速实现该系统的功能，并且JAVA的相关工具及资源全部为免费资源，用户使用时没有后顾之忧。基于J2EE的JAVA系统，使用当前最新的SSH2框架，配合免费的MySQL数据库，以及免费的应用服务器Tomcat 5.5，组成本系统的主要技术成分及配备工具。

市场环境：

本网络验证系统基于面向外挂制作者这一受众，即决定了本系统的设计初衷：免费使用，有偿技术支持。对于愿意对本系统提供资金支持的用户，本系统开发员在此先谢过，相信有了大家的支持，本系统一定会更好更完美！

系统架构：

本系统主要可分为以下几个功能模块。

1.用户在线注册。

2.用户信息查看。

3.管理员对用户帐号的管理。

4.管理员给用户帐号冲值。（可选）

5.可多游戏共用

基于Spi演算的安全协议验证篇6

安全协议是信息安全的基础, 然而设计一个符合安全目标的协议十分困难。因此, 必须借助形式化方法, 对安全协议进行分析和验证[1]。基于进程代数的安全协议验证能够精确地描述协议中不同主体之间的交互过程, 得到了广泛的应用。Abadi和Gordon在pi演算[2,3]的基础上, 增加密码学描述原语, 建立了用来描述和验证安全协议的Spi演算。Spi演算保持了pi演算简单的语法和强大的描述能力, 采用互模拟等价理论对安全协议进行验证。

本文以Spi演算为工具对安全协议验证的过程进行描述, 并且在Spi演算框架内验证对经典NSSK协议的一种攻击方法。

1Spi演算的语法

pi演算是Robin Milner在CSS等进程演算[4,5]的基础上提出的, 已经成为并发计算的基础模型。pi演算能够表示通信拓扑结构可以动态变化的系统 (既移动进程) 。Spi演算[6]是对pi演算的增强和扩充, 增加了支持密码系统的原语。利用Spi演算, 我们能够对协议进行详细的抽象和分析。

1.1Spi演算的项

假设有名 (name) 所组成的无限集合, 这是安全协议中用来通讯的通道集合;以及有变量 (variable) 所组成的无限变量集合。定义Spi演算的项 (term) 集合如下:

在pi演算中, 名是唯一的项。Spi演算增加了描述对 (pair) 和数字 (zero, successor) 的项结构是为了便于在安全协议中描述它们。而将变量从名中区分开来则是为了简化一些等式的描述。另外, Spi演算增加了基于共享密钥加密的项结构, 项{M}N表示在共享密钥系统 (如DES) 中用密钥N对项M加密所得到的密文。

1.2Spi演算的进程

进一步, 定义Spi演算中的进程 (process) 集合:

进程的基本语义可以做如下的概述:

1) 输出进程 $\bar{m} [Ν] . Ρ$ 把消息N从通道m传送出去之后, 执行进行P;输入进程M (x) .P在通道M上等待任意的消息, 在接收到消息N后, 执行进程P[N/x]。输入进程和输出进程的交互是Spi演算中最基本的计算和同步机制。

2) (vn) P构造了一个可能出现在P中的名n, 这是一个私有的新名称。

3) 进程match, pair splitting和integer case的意义分别是:如果M和N是相同项, [M is N]P执行进程P;否则为0。如果M是一个pair项 (N, L) , 那么let (x, y) = M in P执行进程P[N/x][L/y];否则为0。如果M是0, case M of 0 : P suc (x) : Q执行进程P;或者存在某个N, M是suc (N) 此时执行Q[N/x];否则为0。

4) case L of {x}Nin P表示对称密钥的解密过程, 它尝试用密钥N来对项L进行解密。如果L确实是形如{M}N的密文, 那么将执行P[M/x];否则为0。

2安全性质的分析

现在, 我们可以把安全协议形式化表示成Spi演算进程。为了对协议的安全属性进行描述, 需要在Spi演算中寻找适当的操作语义和等价关系。Spi演算把协议运行的环境 (攻击者) 看作任意进程, 并且引入协议的规范 (Specification) 表示形式, 通过测试等价来描述协议满足的安全属性。

2.1协议规范形式

协议的规范形式是对协议在理想条件下运行的抽象表示。理想条件是指:在A和B需要通信时, 接收进程B已经“魔术般地”预知了发送进程A将要发送的消息。这是不实际的, 但是刻画了协议满足的安全目标, 因此是“更加正确”的协议。因此, 通过验证协议和协议规范是否存在某种程度的等价, 可以得到协议满足的安全性质。Spi演算中, 测试等价恰当地表述了这种等价关系。

2.2安全性质的验证

在Spi演算中, 安全协议的安全性质[7] (认证性, 保密性) 均用测试等价来进行刻画。安全协议满足保密性是指:通信过程中的信息不会被合法接收者外的任何第三方得到。安全协议满足认证性是指:协议攻击者不能伪装成安全协议的合法参与者, 进而参与安全协议的运行。

在Spi演算中, 如果我们已经把协议形式化描述为Inst (M) , 并且把协议规范表示为Instspec (M) 。我们可以刻画保密性和认证性如下:

Secrecy: Inst (M) ≃Inst (M′)

if F (M) ≃F (M′) , for any M, M′.

Authenticity: Inst (M) ≃Instspec (M) , for any M.

其中等价关系≃是测试等价[8]。直观上, 保密性要求消息M不能在传送过程中泄露, 因此攻击者不能区分任意两个消息M和M′。我们知道协议规范Instspec (M) 显然满足认证性, 如果对任意的消息M, Inst (M) 和Instspec (M) 满足测试等价, 那么Inst (M) 中的接受进程也总是“魔术般地”执行发送进程发送的消息M, 也就是说Inst (M) 满足认证性。

3Spi演算的语义

我们称在 (vn) P中, P中的名n是受限的 (Bounded) ;在M (x) .P中, P中的变量x是受限的;在case M of 0 : P suc (x) : Q中, 变量x在第二个分支Q中是受限的。如果名n不是受限的, 则称n是自由的 (Free) 。记进程P中所有的自由名的集合为fn (P) , 所有自由变量的集合为fv (P) 。如果一个进程中fv (P) =Ø, 则称该进程为闭进程。定义Spi演算闭进程下的各种关系:

3.1反应关系

定义1 封闭进程集合上的约简关系“>”由下列规则给出:

定义2 结构等价关系“≡”是封闭进程上满足下列等式规则的最小关系:

$\begin{array}{l} Ρ | 0 \equiv Ρ Ρ | Q \equiv Q | Ρ \\ Ρ | (Q | R) \equiv (Ρ | Q) | R (v m) (v n) Ρ \equiv (v n) (v m) Ρ \\ (v n) 0 \equiv 0 \\ (v n) (Ρ | Q) \equiv Ρ | (v n) Q i f n \notin f n (Ρ) \\ \frac{Ρ > Q}{Ρ \equiv Q} \frac{}{Ρ \equiv Ρ} \frac{Ρ \equiv Q}{Q \equiv Ρ} \\ \frac{Ρ \equiv Q Q \equiv R}{Ρ \equiv R} \frac{Ρ \equiv Ρ^{'}}{Ρ | Q \equiv Ρ^{'} | Q} \frac{Ρ \equiv Ρ^{'}}{(v m) Ρ \equiv (v m) Ρ^{'}} \end{array}$

满足结构等价进程的运行意义是一样的, 只不过在语法结构上有所不同。我们可以根据结构等价关系对进程进行结构上的调整而不影响其运行意义。进一步, 结构等价蕴含测试等价。

定义3 反应关系“→”是封闭进程上满足下列规则的最小关系:

$\bar{m} 〈 Ν 〉 . Ρ | m (x) . Q \to Ρ | Q [Ν / x]$

$\frac{Ρ \equiv Ρ^{'} Ρ^{'} \to Q^{'} Q^{'} \equiv Q}{Ρ \to Q}$

$\frac{Ρ \to Ρ^{'}}{Ρ | Q \to Ρ^{'} | Q} \frac{Ρ \to Ρ^{'}}{(v n) Ρ \to (v n) Ρ^{'}}$

此外Spi演算的另外一种操作语义——由Milner提出的委托关系 (Commitment Relation) [11]可以当作上述语义的补充和参考。

3.2测试等价

在安全协议验证过程中, 其安全属性与被加密信息的内容无关。测试等价关系恰好表达了这种粒度。满足测试等价的进程在外部观察者看起来是没有区别的。因此, 为了定义测试等价, 我们首先定义一个操作子, 用于描述进程可以与外界发生交互的能力。

定义4 闭进程上的可观察谓词 (Exhibit Predication) P↓β定义为:如果m是自由的名, 并且m是P可以与外界发生交互的通道, 即: $m (x) . Ρ ↓ m \bar{m} 〈 Ν 〉 . Ρ ↓ \bar{m}$ 。

定义5 如果P作了若干的动作以后变成P′, 并且P′↓β, 那么我们有集中谓词 (Convergence Predication) P⇓β。因此, 显然有:

定义6 我们将二元组 (R, β) 定义为一个测试, 这个二元组是由一个闭进程R和一个通道barb β组成。

定义7 测试等价P≃Q可定义为对于任意的测试 (R, β) , (P|R) ⇓β当且仅当 (Q|R) ⇓β。

4Spi演算的形式化验证

4.1验证过程

经过上面的分析, 可以看到利用Spi演算对安全协议进行验证可以分为四个步骤:

1) 利用Spi演算对协议参与主体和协议整体进行形式化表示。

2) 分析协议, 在Spi演算下写出满足安全目标的协议规范形式。

3) 使用任意第三封闭进程R和barb β对形式化的协议和其规范形式进行测试。在这个过程中, 我们可以使用反应关系对测试进行约简。

4) 验证协议满足2.2节所示的测试等价关系, 从而得到安全协议满足的性质。

4.2对NSSK协议的一种攻击方法

NSSK协议是Needham-Schroeder协议在对称密码体制下的版本[9]。在具有可信第三方的对称密钥体系中, NSSK用于在通信双方之间分配会话密钥。参加协议的主体有3个, 包括通信发起者A, 响应者B, 以及认证服务器S。NSSK协议的运行步骤如下:

Message 1: A→S: A, B, Na

Message 2: S→A:{Na, b, KAB, {KAB, A}KBS}KAS

Message 3: A→B:{KAB, A}KBS

Message 4: B→A: {Nb}KAB

Message 5: A→B:{Nb+1}KAB

协议完成A和B之间的双向认证, 前3条消息的作用是主体A在认证服务器S的帮组下, 进行会话密钥KAB的分配。第5条消息发送的Nb+1可以用任何一个Nb的函数代替, 用于帮助B对A进行认证。

在这个过程中, A极力向B证明其掌握有密钥KAB, 并且想让B相信这个KAB是由认证服务器S构造的新鲜密钥。然而, 这个过程必须基于Message 3是新鲜的。如果有旧密钥KAB被破解, 攻击者可以重放Message 3给B, 此时B将因为无法确定密钥的新鲜性而被欺骗[10]。我们可以在Spi演算中表示这个攻击过程。

4.3NSSK协议和协议规范的Spi演算表示

首先, NSSK协议本身可以在Spi演算下形式化表示为:

$\begin{array}{l} S e n d (i, j, Μ) ≜ (v Ν_{a}) (\bar{c_{s}} 〈 \underline{i}, \underline{j}, Ν_{a} 〉 . C_{i} (x_{c i p h e r}) . \\ c a s e x_{c i p h e r} o f {x_{n o n c e}, x_{B}, x_{k e y}, x_{s e n d}}_{Κ_{i s}} i n \\ [x_{n o n c e} i s Ν_{a}] [x_{B} i s \underline{j}] \bar{c_{j}} 〈 x_{s e n d} 〉 . c_{j} (y_{c i p h e r}) . \\ c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} i n \\ \bar{c_{j}} 〈 {s u c (y_{n o n c e})}_{x_{k e y}} 〉 . \bar{c_{j}} 〈 {Μ}_{x_{k e y}} 〉) \end{array}$

$\begin{array}{l} S ≜ c_{s} (x_{A}, x_{B}, x_{n o n c e}) . \prod_{i \in 1 . . n} [x_{A} i s \underline{i}] \prod_{i \in 1 . . n} [x_{B} i s \underline{j}] \\ (v Κ) \bar{c_{j}} 〈 {x_{n o n c e}, \underline{j}, Κ, {Κ, \underline{i}}_{Κ_{s j}}}_{Κ_{i s}} 〉 \end{array}$

$\begin{array}{l} R e c v (j) ≜ c_{j} (x_{c i p h e r}) . c a s e x_{c i p h e r} o f {x_{k e y}, x_{A}}_{Κ_{s j}} \\ i n \prod_{i \in 1 . . n} [x_{A} i s \underline{i}] (v Ν_{b}) (\bar{c_{i}} 〈 {Ν_{b}}_{x_{k e y}} 〉 . \\ c_{j} (y_{c i p h e r}) . c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} i n \\ [y_{c i p h e r} i s s u c (Ν_{b})] c_{j} (z_{c i p h e r}) . \\ c a s e z_{c i p h e r} o f {z_{p l a i n}}_{x_{k e y}} i n F (\underline{i}, \underline{j}, z_{p l a i n})) \\ S y s (Ι_{1}, \dots ‚ Ι_{m}) ≜ (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) (S e n d (Ι_{1}) | \dots | \end{array}$

Send (Im) |!S|!Recv (1) |…|!Recv (n) )

这是一个包含多个协议参与主体, 多次并发运行的安全协议形式化描述。我们用Send (i, j, m) 描述主体i向主体j传送消息M;用Recv (j) 描述接收消息的主体j;用Sys (I1, …, Im) 刻画整个协议。协议的复杂性体现在并发、多主体以及加密内容的多重组成。

同时, 用Spi演算形式化表示NSSK协议规范为:

Sendspec (i, j, M) ≜ (vp) (Send (i, j, p) |

$p (x) . F (\underline{i} \underline{j}, Μ))$

$\begin{array}{l} R e c v_{s p e c} (j) ≜ c_{j} (x_{c i p h e r}) . c a s e x_{c i p h e r} \\ o f {x_{k e y}, x_{A}}_{Κ_{s j}} i n \prod_{i \in 1 . . n} [x_{A} i s \underline{i}] (v Ν_{b}) \\ (\bar{c_{i}} 〈 {Ν_{b}}_{x_{k e y}} 〉 . c_{j} (y_{c i p h e r}) . c a s e y_{c i p h e r} o f \\ {y_{n o n c e}}_{x_{k e y}} i n [y_{c i p h e r} i s s u c (Ν_{b})] c_{j} (z_{c i p h e r}) . \\ c a s e z_{c i p h e r} o f {z_{p l a i n}}_{x_{k e y}} i n \bar{z_{p l a i n}} 〈 * 〉) \\ S y s_{s p e c} (Ι_{1}, \dots, Ι_{m}) ≜ (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) (S e n d_{s p e c} (Ι_{1}) | \dots | \end{array}$

Sendspec (Im) |!S|!Recvspec (1) |…|!Recvspec (n) )

其中, 认证服务器S的描述没有变化。在协议规范中发送进程不再直接发送消息M, 而是发送构造的新通道p。在通道p上和接收进程交互成功后, 发送进程直接执行M。因此如果执行了M, 必然是在期望的两个主体i和j之间进行的, 所以Sysspec (I1, …, Im) 满足认证性。

4.4攻击进程的描述

根据上面的讨论, 我们构造攻击进程R如下:

$R (i, j) ≜ \bar{c_{j}} 〈 {Κ_{A B}, \bar{i}}_{Κ_{s j}} 〉 . c_{i} (y_{c i p h e r}) . c a s e y_{c i p h e r} o f {y_{n o n c e}}_{Κ_{A B}}$

$i n \bar{c_{j}} [{s u c (y_{n o n c e})}_{Κ_{A B}}] . \bar{c_{j}} [{Μ_{R}}_{Κ_{A B}}]$

进程R (i, j) 表示对参与进程i和j之间的一次攻击:攻击者破解了以往旧通信的密钥KAB, 并截获旧通信中进程i发送的加密数据。攻击者对进程j重放这个加密数据, 解密j的响应数据{Nb}KAB, 然后对进程j进行回复。从而攻击者冒充进程i完成协议的整个认证过程。

4.5对NSSK协议攻击的分析

(1) 利用Spi演算对NSSK协议在攻击进程R (i, j) 下的运行情况进行分析:

$\begin{array}{l} S y s (Ι_{1}, \dots, Ι_{m}) | R \equiv (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) (S e n d (Ι_{1}) | \dots | S e n d (Ι_{m}) | \\ ! S |! R e c v (1) | \dots |! R e c v (n)) | R \\ \to \dots \to (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) ((v Ν_{a}) (\bar{c_{j}} 〈 x_{s e n d} 〉 . c_{i} (y_{c i p h e r}) . \\ c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} i n \bar{c_{j}} 〈 {s u c (y_{n o n c e})}_{x_{k e y}} 〉 . \\ \bar{c_{j}} 〈 {Μ}_{x_{k e y}} 〉) | R | R e c v (j) | S e n d (Ι_{1}) | \dots | \end{array}$

Send (Im) |!S|!Recv (1) |…|!Recv (n) )

协议在没有和攻击进程R (i, j) 交互的情况下执行到Message 3, 接下来让R (i, j) 开始攻击:

$\to \dots \to (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) ((v Ν_{a}) (\bar{c_{j}} [x_{s e n d}] . c_{i} (y_{c i p h e r}) .$

$c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} i n \bar{c_{j}} 〈 {s u c (y_{n o n c e})}_{x_{k e y}} 〉 .$

$\begin{array}{l} \bar{c_{j}} 〈 {Μ}_{x_{k e y}} 〉) | \bar{c_{j}} 〈 {Μ_{R}}_{Κ_{A B}} 〉 | c_{j} (z_{c i p h e r}) . c a s e \\ z_{c i p h e r} o f {z_{p l a i n}}_{x_{k e y}} i n F (\underline{i}, \underline{j}, z_{p l a i n})) | S e n d (Ι_{1}) \\ | \dots | S e n d (Ι_{m}) |! S |! R e c v (1) | \dots |! R e c v (n)) \end{array}$

攻击进程R (i, j) 假冒发送进程i, 引诱进程j执行Message 4和Message 5, 完成协议的认证过程。最后, 我们可以看到进程j执行了错误的消息MR:

$\begin{array}{l} \to \dots \to (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) ((v Ν_{a}) (\bar{c_{j}} 〈 x_{s e n d} 〉 . \\ c_{i} (y_{c i p h e r}) . c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} \\ i n \bar{c_{j}} 〈 {s u c (y_{n o n c e})}_{x_{k e y}} 〉 . \bar{c_{j}} 〈 {Μ}_{x_{k e y}} 〉) | \\ F (\underline{i}, \underline{j}, Μ_{R}) | S e n d (Ι_{1}) | \dots | S e n d (Ι_{m}) | \\ ! S |! R e c v (1) | \dots |! R e c v (n)) \end{array}$

(2) 利用Spi演算对NSSK协议规范在攻击进程R (i, j) 下的运行情况进行分析:

$S y s_{s p e c} (Ι_{1}, \dots, Ι_{m}) | R \equiv (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) (S e n d_{s p e c} (Ι_{1}) | \dots |$

$\begin{array}{l} S e n d_{s p e c} (Ι_{m}) |! S |! R e c v_{s p e c} (1) | \dots |! R e c v_{s p e c} (n)) | R \\ \to \dots \to (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) (((v p) ((v Ν_{a}) (\bar{c_{j}} 〈 x_{s e n d} 〉 . c_{i} (y_{c i p h e r}) . \\ c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} i n \bar{c_{j}} 〈 {s u c (y_{n o n c e})}_{x_{k e y}} 〉 . \end{array}$

$\bar{c_{j}} 〈 {p}_{x_{k e y}} 〉 | p (x) . F (\underline{i}, \underline{j}, Μ)) | S e n d_{s p e c} (Ι_{1}) | \dots |$

$\begin{array}{l} S e n d_{s p e c} (Ι_{m}) |! S | c_{j} (z_{c i p h e r}) . c a s e z_{c i p h e r} o f {z_{p l a i n}}_{x_{k e y}} i n \\ \bar{z_{p l a i n}} 〈 * 〉 | \bar{c_{j}} 〈 {Μ_{R}}_{Κ_{A B}} 〉 |! R e c v_{s p e c} (1) | \dots | \\ ! R e c v_{s p e c} (n)) \\ \to \dots \to (v \vec{Κ_{i s}}) (v \vec{Κ_{s j}}) (((v p) ((v Ν_{a}) (\bar{c_{j}} 〈 x_{s e n d} 〉 . c_{i} (y_{c i p h e r}) . \\ c a s e y_{c i p h e r} o f {y_{n o n c e}}_{x_{k e y}} i n \bar{c_{j}} 〈 {s u c (y_{n o n c e})}_{x_{k e y}} 〉 . \\ \bar{c_{j}} 〈 {p}_{x_{k e y}} 〉 | p (x) . F (\underline{i}, \underline{j}, Μ)) | S e n d_{s p e c} (Ι_{1}) | \dots | \end{array}$

可以看到, 在进程R (i, j) 的攻击下, 进程j没有被欺骗执行错误的消息MR。并且, 协议规范可以进一步执行, 从而进程j可以执行由进程i发送的消息M:

从上对NSSK协议和NSSK规范协议在攻击进程R (i, j) 下的分析可以看到, 两次的运行结果不在同一通道集合上满足可观测。也就是说NSSK协议和NSSK规范协议两者不满足测试等价关系。根据Spi演算中对安全属性的描述, NSSK协议不满足认证性要求。

5结论

本文在介绍Spi演算的语法表示和形式语义的基础上, 从验证安全协议的角度出发, 引出测试等价关系来分析协议的安全属性。对Spi演算下的安全协议分析过程进行了阐述, 并利用Spi演算对NSSK协议的一种攻击方法进行分析, 证明其不满足认证性。进一步的工作研究主要集中在两个方面[11]:一方面对Spi演算进一步扩展, 使其可以抽象更多的密码学内容;另一方面, 研究Spi演算的互模拟等价理论, 对更多的安全属性进行验证。

参考文献

[1]卿斯汉.安全协议20年研究进展[J].软件学报, 2003, 14 (10) :1740-1752.

[2]Robin M, Joachimp P, David W.ACalculus of mobile processes, Parts?and Parts[J].Information and Computation, 100 (1) :1-40, 41-77.

[3]Robin M.Communication and mobile systems:the pi-calculus[M].Cambridge University Press, 1999.

[4]Hoare C.Communicating sequential processes[M].Prentice Hall, 1985.

[5]Robin M.Communication and concurrency[M].Prentice Hall, 1989.

[6]Martin A, Gordon A.A caculus for cryptographic protocols:the Spicalculus, The 4th ACM Conference on Computer and CommunicationSecurity[C].1997:36-47.

[7]Clark J, Jacob J.A survey of authentication protocol literature[OL].http://www.users.cs.york.ac.uk/～jac/under the linkSecurity Pro-tocols Review.Version 1.0.1997.

[8]Nicola R, Hennessy M.Testing equivalences for processes[J].Theo-retical Computer Science, 1984, 34:83-133.

[9]Needham R, Schroeder M.Using encryption for authentication in largenetworks of computers[J].Communications of the ACM, 1978, 21 (12) :993-999.

[10]Denning D, Sacco G.Timestamps in key distribution protocols[C]//Communications of the ACM, 1981, 24 (8) :533-536.

协议分析验证篇7

关于安全组密钥协商,国内外学者已做了大量研究工作,提出了很多组密钥协商方案[1,2,3,4,5,6,7],但大多数组密钥协商协议都是基于Diffie-Hellman密钥交换协议以及Weil双线性对,存在密钥协商轮数多、消息传送量大等不足。2002年,Boneh和Silverberg提出了多线性表的概念,并利用此概念提出了一轮多方DH密钥交换协议[8],然而由于该协议缺乏对参与者的身份认证,因此容易遭受中间人攻击。文献[9]克服了该问题,并提出了MAK协议,该协议将MTI协议和MQV协议扩展到多线性表的应用中来,然而它需要结合证书提供对参与者的身份认证,这也是前期组密钥协商协议实现认证性通常采用的机制。为了解决该类机制带来的证书认证需要的大量计算和存储空间,Boneh and Franklin[10]提出了基于身份的加密体制,随后出现了大量基于身份的认证组密钥协商协议[11,12,13,14]。文献[13]在MAK协议基础上提出ID-MAK协议,旨在通过引入基于身份的公钥密码体制来撤消对数字证书的使用,以及提供隐、显式密钥认证,然而该协议并未达到预期的目的。文献[14]在此基础上对其进行了分析和改进,在多线性DH问题假设下提出了两个基于身份的组密钥协商协议,并给出了对应的成员动态变化和组密钥更新的相关协议,弥补了ID-MAK协议的不足,但该方案没有提供显式密钥认证和密钥一致性确认。本文在此基础上利用椭圆曲线离散对数进行了改进,并利用应用pi演算辅以ProVerif自动化验证工具对安全性进行了形式化分析。

1 组密钥协商方案

1.1 初始化参数设置

设G1和G2是阶同为素数q的有限椭圆曲线循环群,P为G1的生成员,en:G1n→G2为n线性映射。令H1:{1,0}*→G1表示将用户身份信息映射成G1中的一个元,H2:G2→{1,0}n表示将G2中的元映射成指定长度的密钥值。组成员分别用U1,U2,…,Un来表示,其中任意成员Ui的身份为IDi,假设存在一个离线的私钥生成中心(PKG),它按如下方法建立初始系统:PKG在[1,q-1]中随机选择一个私钥s(s∈Zq*),计算其公钥PPKG=s.P,并公布系统参数(G1,G2,en,P,q,H1,H2,PPKG),同时根据身份信息计算成员Ui的公/私钥(pki,ski)并保密分发给各组成员,其中pki=H1(IDi)。

1.2 组密钥协商方案

系统初始化设置完成后,假定有m(m≤n)个组成员参加会话密钥协商,其过程如图1所示。

(1)成员Ui(i=1,…,m)随机选择ri∈Zq*,计算并广播KEi=ri·pki(KEi∈G1)给网络其他成员Uj(j=1,…,m且j≠i);成员Ui收到其他成员发来的KEi消息后,计算会话密钥如下:

会话密钥k=H2(Ki)。

(2)成员Ui(i=1,…,m)利用计算出来的会话密钥k加密(对称加密算法)其身份信息IDi和其选定的随机数的倒数ri-1,即Ei={IDi,ri-1}k,广播给网络其他成员Uj(j=1,…,m且j≠i);成员Ui收到其他成员发来的消息Ei后,首先利用自己计算出来的会话密钥k解密消息,然后利用其身份信息IDi生成其公钥pki=Hi(IDi),计算比较,所有成员都通过此验证后,协商生成的组会话密钥即可生效。

1.3 正确性分析

系统在完成初始化设置后,组成员各自只需要广播发送两条消息并作如下计算即可完成经过一致性确认的可认证的组会话密钥协商:

组会话密钥的一致性。各成员收到第一组消息KEi后,用多线性映射函数en首先计算:

各成员最终可以得到共享组会话密钥k=H2(K1)=H2(K2)=…H2(Km)。

组会话密钥协商认证过程的正确性。各成员收到第二组消息Ei后,用计算出来的会话密钥k解密消息得到IDi和ri-1,然后计算:

通过比较分析,各成员可完成组会话密钥协商的认证过程。

1.4 性能分析

通信开销和计算量是衡量组密钥协商方案性能好坏的重要标志,本文通过运用椭圆曲线离散对数结合多线性映射的方法,将基于身份公钥的认证机制有效地内嵌其中,组密钥协商既达到了一致性确认和身份认证,又避免了此类协议的复杂签名与验证运算;同时,在本文的密钥协商方案中,每个组成员仅需要广播发送两条较短的消息,通信开销相对来说也比较小。通过下文的安全性分析可以看出,本文的方案既实现了高安全性,又确保了较好的性能。当然,多线性映射函数的实现还需要进一步研究。

2 协议的安全性分析

2.1 应用pi演算与ProVerif

应用pi演算[15]是进程代数中的一种。它定义了完备的交互、并发理论框架,能够建模、描述并推导协议的安全属性。该演算适合分析并发、分布式协议,以其简洁高效的特点得到广泛应用。ProVerif是一个验证应用pi演算模型的自动化工具,可以降低分析过程的难度及手工推导失误,提高分析速度和准确性。Blanchet等人于2002年提出了基于Horn逻辑的安全协议分析理论,并基于该理论开发出ProVerif。本文在分析密钥协商协议安全性的过程中,首先形式化定义了协议的应用pi演算模型和安全性质,然后采用ProVerif来完成验证,分析过程采用的是ProVerif v1.14p14。

2.2 协议的应用pi演算模型

形式化建模组密钥协商过程用到的函数主要包括:

应用pi演算把协议的参与主体描述为进程,多个进程并发构成系统进程反映协议的运行情况。在以上定义的基础上,可以建立如下协议模型:

Ii代表其中任意一个组成员进程:

系统进程S由各个组成员进程Ii(进程Ii中分别取i=1,2,…,m)并发组成,同时包括了PKG进程,PKG进程负责生成用户名及公/私钥,并保密分发私钥。系统进程S如下:

通道init、connect代表协议与主机交互的隐藏信道,环境无法与这些信道进行交互。通道keyi分别用来建模PKG与组成员传递信息的私有、安全信道,攻击者不能得到通道内的内容。

2.3 安全性分析

本文的可认证组密钥协商方案,由于组密钥协商需要所有组成员独立的参与,显然满足密钥独立性和抗同谋破解。下文中将进一步对其他安全属性进行分析。首先考虑协议的保密性。该协议用于协商建立共享组密钥,当环境无法区分在协商过程中传递的身份信息IDi和随机数ri-1时,则协议实现了对内容的保护,即协议满足密钥保密性。因此对保密性的验证可以被建模为安全属性查询:攻击者能否获得消息中的内容IDi和ri-1。为了编程实现的需要,分别验证了3个、4个、5个组成员协商密钥的过程,在自动化工具ProVerif下查询(query)以下事实是否成立。

输出结果如图2所示,该结果表明:协议能够满足保密性,同时实现对组成员身份的保护。

协议的认证性。认证性可以解释为:如果组成员接受了协商出的共享组会话密钥,则其他组成员必定发起了该协商,并且所声称的身份是真实的。对认证性的验证可以用一下语句查询:

输出结果如图3所示,该结果表明:协议能够满足认证性。

3 成员变化与组密钥更新

移动自组网中,组成员的动态性变化要求组成员安全高效地更新组密钥,以确保前向安全性和后向安全性得到满足。下面以单个成员为例进行说明。根据前面设定的网络规模n,该网络在没有节点退出的情况下,最多只允许再有n-m个成员加入,直到成员数达到n。

3.1 成员加入

如果此前有m个成员进行了组密钥协商,则当有新成员Um+1加入时,他向m个节点广播信息,其中jion_request是Um+1的加入请求(该请求可经过PKG签名),KEm+1=rm+1·pkm+1。其他成员Ui(i=1,…,m)在收到此消息后,将Kei=ri·pki(i=1…,m)发送给Um+1,也可由指定的其中一个成员发送所有这些公开消息,其中ri与此前协商阶段使用的相同,不需要重新选择,这样所有m+1个成员通过如下计算得到新的组密钥:

上式中i=1,…,m+1,各成员最终可以得到共享组会话密钥。

新的组密钥计算完成后,各成员再采用前述方法发送第二条消息进行身份认证和密钥一致性确认。

3.2 成员退出

如果此前有m个成员进行了组密钥协商,当成员Um要退出时,他向m-1个节点广播信息M2={quit_request,IDm},其中jion_request是Um的退出请求(该请求和Um的身份信息IDm一起经过组密钥加密)。其他成员Ui(i=1,…,m-1)在收到此消息后,通过如下计算得到新的组密钥(其中ri与此前协商阶段使用的相同,不需要重新选择):

上式中i=1,…,m-1,这样所有m-1个成员最终可以得到共享组会话密钥。

新的组密钥计算完成后,各成员再采用前述方法发送第二条消息进行身份认证和密钥一致性确认。

3.3 密钥更新

密钥的更新包括会话组密钥和节点的公/私钥对的更新,这里仅就会话组密钥的更新作简单说明。在没有节点的加入和退出时,组会话密钥在使用中还需要定期更新,以减少密钥泄露的可能性。当然,此时的更新可以采取通过指定的组成员来发起,该组成员在规定的时间间隔内向其他成员广播密钥更新消息,然后所有成员重新执行组密钥协商协议即可。

4 结论

协议分析验证篇8

关键词：安全协议,计算模型,CryptoVerif

0 引言

安全协议是通信主体利用约定的流程序列交换消息, 并利用密码体制加密被交换消息, 以保证实现预定的安全目标:秘密性和认证性。为了实现安全性, 需要对协议进行验证。对协议验证主要使用两种方法:手工验证和形式化软件验证。手工验证繁琐易出错, 局限于验证者的个人能力, 且难以推广;形式化软件验证主要基于两种模型:Delve-Yao模型和计算模型。Delve-Yao模型把密码体制黑盒化, 通过验证消息序列来证明协议安全性;计算模型把协议里的消息作为字符串, 把攻击者对协议的攻击以对消息字符串的函数运算表示, 通过各操作的概率来表示协议安全性。

本文将介绍基于计算模型的协议验证软件CryptoVerif, 与其它软件不同, 不仅可以验证协议, 也可以验证密码算法。

1 CryptoVerif原理

CryptoVerif建立在计算模型上, 协议以概率多项式时间的进程代数表示, 消息用位串表示, 加密算法表示为位串的函数, 通过对特定事件 (event) 的到达和参数的询问 (query) 来证明安全属性。CryptoVerif使用Spi演算, 把协议表示为Spi演算下的进程;使用Game序列来形式化验证过程:协议作为初始Game, 通过一系列转换操作为安全性可容易识别的最终Game。Game转换以计算密码学下的观察等价 (Observational Equivalence) 概念为基础, 观察等价是CryptoVerif的核心。

1.1 CryptoVerif语法 (语法用图一起表示, 原稿是单独表示)

CryptoVerif利用改进的Spi演算表达协议:用项 (term) 来表示参数、密码体制、函数, 用进程 (process) 来表示协议主体行为, 并分为输入进程和输出进程, 并把参数存入数组中方便操作, 具体语法如下所示, 其中M、N表示项, Q表示输入进程, P表示输出进程。

1.2 观察等价

CryptoVerif进行协议证明有两个基础:密码原语安全性和观察等价。密码原语安全性是CryptoVerif证明的标准, 是密码原语的进程代数表示;观察等价是进行Game转换的基础, 它是用概率来表示的, 通过严格的数学性来证明其正确性。

观察等价涉及评价环境 (evaluation context) 概念。环境 (context) 是一个可引入参数的空进程 (与0输入空进程不同) , 评价环境则是引入了通道、进程组合的环境。CryptoVerif以评价环境来表示攻击者。 (下边的观察等价定义改变)

观察等价的定义如下:Q和Q`为两个进程, V表示两进程变量集合, 称Q和Q`在变量集V下是观察等价的, 对任一Q, Q`, V可接受的评价环境S, 对任一通道c和位串undefined是可忽略的。

1.3 Game转换规则

CryptoVerif里的Game转换基于Spi演算的3个属性:只一次定义、使用前定义和类型化。前两者是自明的;Spi里参数类型化, 确定参数的功能和防止类型攻击。

Game转换规则有3个, 分别论述如下:①项赋值删除:当项以赋值的方式被定义时, 用值来替换赋值定义;②项重命名:重命名是为了保证每个项在进程里名称唯一;③简化:依据Spi演算的不变性和观察等价概念, 把一些复杂的项和进程用简单形式来替换。有两种类型的简化:等式简化和依赖于随机值低碰撞概率简化。

1.4 CryptoVerif可证明的安全性

CryptoVerif可证明的安全属性包括秘密性和认证性, 秘密性用密码体制的安全性表示, 认证性用协议里的事件映射表示。

1.4.1 秘密性 (表述改变)

CryptoVerif可证明的秘密性分两种:会话秘密性和秘密性。

会话秘密性 (One-session secrecy) 。满足会话秘密性的协议, 攻击者不能区分开输出秘密值的进程和输出随机数的进程。

秘密性 (Secrecy) 。满足秘密性的协议, 攻击者不能区分多次输出相同秘密值的进程和输出独立随机数的进程, 是比会话秘密性更强的属性。

1.4.2 认证性 (表述改变)

CryptoVerif使用单射和非单射的对应来证明认证性。当两事件满足单射时, 可证明其认证性;反之, 则不能证明。

2 CryptoVerif使用

经过上边的讨论, 我们利用CryptoVerif来证明一个简单协议的秘密性。该协议描述如下:发送方A和接收方B共享加密密钥Kab和消息认证密钥Mab, 在两者间传递临时会话密钥Kab’。我们利用CryptoVerif验证Kab和Kab’的两类秘密性。

在CryptoVerif里, 我们用询问query来标示待验证秘密性, 用k2表示Kab, k3表示Kab’, 如下所示:

query secret1 k2.

query secret1 k3.

query secret k2.

query secret k3.

在CryptoVerif里, processA为输入进程, processB为输出进程, process表示待验证协议, 如下所示:

运行CryptoVerif结果如下, 可以发现, 本协议的共享密钥的秘密性和会话秘密性是可证明的, 只能证明临时会话密钥的会话秘密性, 这是与现实情况相符的。

同时, 对协议分析结果可以更进一步分析, 可以通过分析结果里的各个协议组成部分的概率表示, 计算性地表明协议的潜在脆弱点。

3 CryptoVerif的使用现状和不足

CryptoVerif主要对双方和三方协议进行分析, 使用CryptoVerfi已经对Needham-Schroeder 协议共享密钥和公钥两版本、Yahalom 协议、Kerberos5协议等进行了证明, 取得了很好的结果。

不过, CryptoVerif对涉及群组协议的分析能力不足;只能对秘密性和认证性进行验证, 不能对匿名性、不可否认性和公平性等安全属性进行验证。在目前基础之上, 作者将对其他安全性在CryptoVerif里的表示和群组协议的安全性验证展开研究。

参考文献

[1]DOLEV D, YAO A.On the security of public-key protocols[J].IEEE Transaction on the Information Theory, 1983 (29) .

[2]P D LINCOLN, J C MITCHELL, M MITCHELL, et al.A probabi-listic poly-time framework for protocol analysis[C].In ACM Com-puter and Communication Security (CCS-5) :112-121.

[3]BLANCHET B.A computionally sound mechanized prover for se-curity protocols[C].In Proc.27th IEEE Symposium on Security&Privacy, 2006.

[4]J C Mitchell, A Ramanathan, A Secdrov, et al.A probabilistic poly-time calculus for the analysis of cryptographic protocols[J].Theo-retical Computer Science, 2006.

[5]赵倩倩, 李周军, 周倜.Kerberos5协议的形式化分析综述[J].计算机科学, 2009 (5) .

协议分析验证篇9

随着安全协议验证领域的不断发展,近五年提出的一些衍生类协议验证方法正在引领着协议验证分析领域的新潮流,如绑定项证明法［14］、软件模拟法［15］、SPVT验证工具［16］、理性安全协议推理系统［17］、改进的BAN逻辑［18］、改进型有色Petri网的协议验证法［19］、基于Horn扩展逻辑的非否认建模与验证方法［20］、基于SAT的安全协议惰性形式化分析方法［21］、串空间的改进方法IVAP［22］、含时间因素的安全协议形式化分析方法［23］、混合的安全协议分析法［24］、新的协议验证逻辑［25］等。这些安全协议着重于对经典的协议验证方法的改进、扩展或提出了新的通信协议验证方法。但在安全协议形式化分析领域,每一类验证方法都存在着相应的缺陷或不足。因此,对于这些改进或新提出的安全协议进行总结、分析,并在此基础上指出新的研究方向显得十分必要。

下面,本文就以下几类安全协议验证方法做详细介绍。

1 逻辑推理分析法

逻辑推理分析法指的是在协议的验证过程中,通过将协议描述为对应验证规则的语法,对相应变量进行假设,在符合假设和约定规则的前提下,进行逻辑推导验证协议是否达到了预期目的的验证方法,逻辑推理分析法的对比如表1 所示。

注: 协议类型中,a为无可信第三方的认证协议; b为应用密码检验函数的认证协议; c为具有可信第三方的对称密钥协议; d为对称密钥重复认证协议; e为无可信第三方的公开密钥协议; f为具有可信第三方的公钥协议。

1) BAN逻辑是由Michael Burrows,Martin Abadi等提出的,它是协议形式化分析的工具之一。BAN逻辑是一种基于主体信念来从已知的信念中推出新的信念的逻辑规则。通过应用BAN逻辑来验证协议从信息传递过程中是否可以推出最终运行的结果。BAN逻辑的应用过程: 将协议的条件进行合理的假设,通过假设来构造BAN逻辑中的公式,然后将这些公式应用BAN逻辑的语法进行推理,最终得出验证结果。

2) GNY逻辑于1990 年由Gong,Needham和Yahalom提出。属于类BAN逻辑的扩展,相较于BAN逻辑对逻辑分析能力、可识别概念、判断规则等方面进行了改进。GNY逻辑总共44 条规则,推导过程较为复杂。

3) AT逻辑是由Abadi M和Tuttle M R提出的。AT逻辑较BAN逻辑而言,重新形式化了BAN逻辑,采用将信仰作为源绑定形式和可作废的知识对待,具备了更好的自然逻辑语义模型和合理的计算模型。

4) SVO逻辑是由Syverson和Van Oorschot提出,SVO逻辑吸取BAN、GNY、AT等逻辑的优势,建立自己简洁合理的推理模型,在形式化语义方面,SVO逻辑取消了AT逻辑中的部分限制,重新定义了部分概念。当前SVO逻辑被主要用于电子商务中相关协议的研究。

5) Kailar逻辑［26］的提出主要是为了电子商务协议的可追究性,以解决主体向第三方证明另一方执行的责任行为。然而它缺乏对签名密文的分析能力,证明协议时不够严格。

6) CS逻辑［27］由Coffey和Saidha提出,它结合了谓词逻辑和模态逻辑的特点,也是一种将时间和逻辑结构相结合的逻辑。但CS逻辑对环境因素考虑不足,在某些特定环境下不能对协议进行有效验证。

7) KG逻辑［28］由Kailar和Gligor提出的,来验证双方的最终信仰,即验证双方互相发送和接收报文能否从最初的信仰发展成协议要达到的最终目的。通过验证协议运行中的信仰变换来检测协议中是否存在着缺陷。

2 模型模拟检测法

模型模拟检测法指的是采用模拟工具或构建模型的方式,将初始状态下的协议进行检测,通过对协议运行开始到运行结束的路径进行检测,判断是否协议存在缺陷的验证方法。模型模拟检测法具有高度自动化的特点,模型模拟检测法则对比见表2。

1) 有限状态机FSM［29］是一种应用于系统动态行为的建模,借助状态图进行可视化表示。通过对有限状态机的不断的研究,可以被用于更多更复杂行为的建模。但FSM的实现也存在着复用性差,维护困难等问题。

2) Dolev-Yao模型是由Dolev和Yao最早提出,经过后来研究者T Genet和F Klay［30］等的进一步扩展。Dolev-Yao模型首先对安全协议进行层次划分,将安全算法和协议本身区分研究,然后对协议的正确性、安全性等进行研究。提出了重视攻击者知识和能力的原则。

3) CSP方法［31］即通信顺序进程方法,由C. A. R. Hoare提出。他将输入、输出作为程序语言的基本要素,将实现顺序进程间通信的并行组合。对安全协议进行验证时首先从协议说明中建立模型,再结合FDR工具( 故障偏差精炼检测器)［32］检测协议是否存在问题。

4) Spin模拟检测方法［33］是由贝尔实验室的形式化小组研发的协议检测模型,使用Promela语言建模,整个系统可以看作是扩展的有限状态机。主要用于对于线性时态逻辑的正确性检测。

5) murφ 模型检测法［34］由J. C. Mitchell,M . Mitchell和Stern最早应用于对协议预期性质的建模,通过加入入侵者模型,在应用状态枚举法来检测系统状态都符合规范。

6) Interrogator由Millen等人提出的,基于状态机技术的协议分析器。Interrogator对协议分析时采取前向搜索,从初始状态直到最终状态存在不安全路径。

7) NRL模型检测工具由Meadows等人研发,它是Dolev-Yao模型的扩充版本。NRL工具采取后向搜索方式,从协议执行的最终状态出发搜寻是否存在到达初始状态的路径。

3 定理归纳证明法

定理归纳证明法是通过将协议形式化的模型和规则进行验证,在协议的模型中是否满足了初始的规则。定理归纳证明法相较模型模拟检测法是从协议的正方向验证,直接对协议的规约进行证明。定理归纳证明法对比如表3 所示。

1) 串空间模型( strand space model) 由Thayer和Herzog等人提出的形式化方法。主要用于安全协议的认证性和私密性的验证。卿斯汉等针对此方法的不足进行了扩展,并提出了扩展后的通用串空间模型。随着对串空间方法的不断研究,串空间与信任管理相结合,使得串空间模型更好地应用于多种安全协议的验证。

2) Paulson归纳法由L C Paulson提出,这种方法通过将协议归纳定义为所有时间可能路径的集合。一条路径即为一个包含多轮协议的通信事件序列。可以模拟所有攻击及密钥丢失事,通过对路径归纳来证明属性安全。

3) 重写逼近法( Rewriting Approximation Method )［35］由Boichut Y等人提出。此方法的验证目标是验证协议中不存在任何攻击。在实际协议验证中,重写逼近法对协议的安全属性进行正面验证,较其他测试方法而言具有更好的可靠性。

4 其他衍生验证法

其他衍生验证法指的是通过研究一些经典协议的验证方法,对这些协议验证方法进行扩展,或者选取新的验证角度,构建出全新的协议验证模型。

1) 绑定项证明法指的是由微观角度通过形式化理论来判定协议的绑定项( 即加密项) 的完备性。验证过程中若存在绑定项不符合规则,可认定协议存在缺陷,快速准确地给予判定协议结果。

2) 软件模拟法是指利用软件模型模拟出协议运行环境,从而对安全协议进行验证。针对RFID安全协议而言,利用Linux系统、gcc编译器、Mysql数据库相结合模拟出RFID系统,在将协议导入模拟系统中运行,最终得出验证结果。

3) SPVT验证工具是基于Objective Caml开发的协议验证工具。利用类 π 演算来描述安全协议。SPVT验证工具根据逻辑程序的不动点计算验证安全性质,来验证出不满足安全性质的缺陷。

4) 理性安全协议推理系统是基于博弈逻辑ATL和ATEL的扩展研究,针对理性环境下,在传统博弈逻辑的基础下,提出了新的推理系统r A-TEL-A。在此推理系统中,将协议进行形式化描述,并对协议进行模拟验证。

5) 改进的BAN逻辑是根据BAN逻辑在对协议验证过程中存在的一些缺陷,而对其进行改进的协议验证逻辑。在使用BAN逻辑验证协议的过程中,BAN逻辑的初始假设、消息形式化描述转换、逻辑语义、推理规则及探测协议存在的攻击等几方面存在不足。通过对这方面分析及改进,改进的BAN逻辑又从消息形式化描述、消息含义推理规则、先行判断规则这三个角度对改进的BAN逻辑进行了验证,提高了BAN逻辑验证的安全可靠性。

6) 改进型有色Petri网的协议验证法通过对传统有色Petri的分析改进而提出的。运用传统有色Petri网安全协议分析法对协议进行验证,主要通过倒推的方法即在检测前确定出可能的不安全状态,验证此不安全状态可达,从而分析协议可能的缺陷,但对于未知的不安全状态无法进行检测。另外,对于验证入侵者的协议时,构造协议模型时由于对入侵者的攻击步骤不了解,使其状态规模快速增长,导致空间爆炸的问题。然而改进型有色Petri网在对协议进行分析验证时,不必了解未知的安全状态,只需要了解一个攻击成功的目标。改进型有色Petri网对攻击成功的知识集与可以获取的知识集进行整合,将其融入到传统的有色Petri网中缩小入侵攻击步骤的范围,缓解了传统有色Petri网在验证协议时所引起的空间爆炸问题。

7) 基于Horn扩展逻辑的非否认建模与验证方法是基于Horn逻辑扩展模型验证非否认协议的验证方法。本方法主要强调验证非否认协议的非否认性和公平性,并对协议的非否认性和公平性建模。在对协议的建模过程中还需要对协议的诚实主体、恶意主体、仲裁进行建模,提出了适用于非否认协议的验证算法。基于Horn逻辑扩展的模型可应用于无穷会话交叠运行的情况,提高了对协议保密性的验证效率。

8) 基于SAT的安全协议惰性形式化分析方法是一种基于SAT问题的协议分析方法。加入惰性思想优化初始状态和转换规则,根据协议的复杂度自动调用命题公式的范式形式,提升了模型的验证效率。其次根据在消息类型上定义的偏序关系,本方法可以检测到更多类型的缺陷攻击。

9) 串空间的改进方法IVAP是一种以串空间为理论基础,根据认证协议的一致性属性及测试分量唯一性属性而建立的安全性验证算法。本方法证明了安全协议的安全性,而且能运用改进协议生成算法为有漏洞的协议生成安全的改进协议。但本方法不能实现对无线认证协议的安全属性验证。

10) 含时间因素的安全协议形式化分析方法是一种针对包含时间因素的有色Petri网形式化分析法。本方法利用有色Petri网中内置的全局自动时钟标记,并通过仿真和生成状态图的方式对时间相关性质进行验证。由于利用系统的内置自动时钟,在建模及验证过程中,系统提供时钟支持方法,因此对于一些复杂的包时间因素的安全协议,此方法依然可以清晰的描述验证。

11) 混合的安全协议分析法是以SPALL逻辑为基础,结合了可证安全的思想,提出概率推导的分析方法。本方法将形式化证明中的模态逻辑分析法和可证明安全法两者相结合,将逻辑假设的成立概率结合到协议的推导过程中,形成一种概率推导方法。根据概率的条件,来判别协议假设安全与否,从而确定协议整体的安全性。此方法克服了两种方法的各自缺陷,具有简单易用、分析全面的特点。

12) 新的协议验证逻辑是一种可以验证安全协议的认证性、非否认性、公平性等特性的逻辑方法。本方法提出了新的逻辑构件、推理规则及公理。通过增加Hash函数的密码原语相关的逻辑谓词、推理规则和公理,实现了对基于对称密钥体制、公钥密码体制和Hash函数密码体制协议的分析验证能力。并通过串空间语义对新逻辑进行验证,证明了此逻辑方法具备了逻辑验证的正确性。

13) 基于SPIN的安全自适应协议栈的形式化验证法［36］属于一种自动化的模型检测方法。本方法将相邻搜索机制和路由协议作为切入点,对安全协议进行自动检测、分析并指出存在缺陷。因此本验证法具备自动化程度高、缺陷自动检测等优点,但是在对协议建模的过程中需要采集各方面的约定规则、抽象假设,导致在构建协议的premola描述模型时较为复杂。

14) 变异性监测( Veriability) 验证法［37］是一种针对密码协议进行自动化验证的方法。本方法主要应用于电子选举协议,可以对匿名认证用户的加密信息进行检测,同时对于部署广泛的加密协议可以自动评估检测,发现其不安全的漏洞。本验证法具备部分自动化、验证安全属性较为全面,但由于仅仅针对电子投票协议的验证,所以此方法存在验证的局限性。

15) 一种自动化的模型检测方法［38］是集合了模型提取和代码生成于一体的验证方法。本方法通过代买编写、模型抽取的方式来自动构建协议的验证模型,同时尽可能编译出真实的协议环境,达到更精确的验证。本方法具有自动化程度高、验证精确度高等优点,然而对于代码的编译过程较为复杂,构建出的模型具有针对性,所以验证角度有限。

16) 协议代码模块化验证方法［39］是一种基于声明和执行不变论密码学的应用方法,本方法开发了加密嵌入逻辑模型的库结构,并提出了一个验证理论,证明了模块化代码验证的合理性。同时本方法具备验证结果精确度高、可扩展性强的优点,但对于验证角度而言仅针对协议中的加密代码模块进行验证。

17) 基于拍处理的自动化验证方法［40］属于自动化模型检测的验证法。本方法应用了关于概率的时间演算的加密算法,以此更好地对协议的实时性、概率性、加密性等几方面进行验证。本方法具备自动化程度高、验证精确性高的优点,但其验证存在局限性,而且不能对外部攻击者进行追踪检测。

5 协议验证法的比较

针对以上的安全协议验证方法,分析对比各类验证方法的优缺点,如表4 所示。对各类验证方法的特点进行比较,总结出每类验证方法适合验证的安全协议。逻辑推理分析法虽然简单直观、可视化,但其由于过度抽象化等原因只适用于验证规模较小、特定的小系统的安全协议; 模型模拟检测法具备自动化程度高、协议自动校正等优势,但不能很好地克服空间控制及主题数目限制的问题,根据其这些特点适用于模型适中、较大系统的安全协议; 定理归纳证明法虽然自动化程度不高、部分证明复杂,但由于其语义清晰、分析直观、避免了空间控制问题等特点,所以其适用于不受模型限制、大型系统的安全协议; 其他衍生验证法是前几类安全协议验证法的延伸,通过对一些经典的的验证方法进行了改进及扩展,并加以创新,推动了安全协议验证领域不断发展,这一类安全协议验证方法适用于验证更为广泛的安全协议。

6 总结与展望

当前,随着有线电视网络承载的应用量越来越多,其安全性必须得到保障。因此,验证电视网络通信协议的验证方法的研究就显得极为重要。协议验证法是从确定协议系统与其运行环境的界面、协议行为的描述、协议特性的定义及证明协议符合规定语义等角度对协议的安全性进行分析验证。然而以上的协议验证方法虽然经过不断的研究扩展具备了各自的特点,但每类协议验证法都或多或少存在着一些不足。为了研究出一种更加简洁、通用、自动化程度高的协议验证方法,还需要做进一步的努力。针对当前的安全协议验证领域提出如下的研究方向:

1) 对于逻辑角度证明,降低形式化抽象的“完美假设”。对于应用逻辑推理法来对安全协议进行验证时,首先要对安全协议的运行环境、理论条件作出假设,然而这些假设或多或少存在着缺陷,如过度理想化、条件完整化等。这些过于完美的初始假设已然使协议的精确验证出现了部分偏差,因此在对安全协议进行初始假设的过程中,尽量将抽象假设的理想程度降低,以此提高对协议验证的准确性。

2) 将自动化验证理念进一步扩展,以适应更广泛的安全协议。对于安全协议验证领域而言,若验证工具可以自动的对安全协议进行查找漏洞、缺陷修复、构建修正协议,那么将极大地提高安全协议的验证效率。在安全协议验证领域中,模型模拟检测法在自动化验证方面较其他协议验证方法具有着很大的优势,但此方法也存在着不容忽视的缺陷。因此如何改进模型模拟检测法的缺陷或者提高其他验证方法的自动化程度将值得对此进行进一步研究。

3) 尝试将几类协议验证法进行结合,优势互补,推出一种验证性能优越的协议验证法。安全协议验证方法的类型如上文所述,每一种安全协议验证方法都有着自己的优势和不足。若用某一类验证方法对安全协议进行验证,那么得出的验证结果并不能完全确定所验证协议是否是安全的、正确的、可行的。因此如何将几类安全协议验证法进行结合,使得结合后的验证方法具备了这几种验证法的优势,同时弥补这几种验证法的不足,最终得出的协议验证方法可以对安全协议进行更加可靠、更加全面的验证。这种将验证法相结合的研究方向势必成为通信协议验证领域研究的新趋势。

摘要：在有线电视网络领域,安全的网络通信协议是信息安全传输的保障,因此研究有效的协议安全性验证方法显得至关重要。当前,随着互联网的普及,数字电视的双向化、智能化趋势日益明显,处于互联网中的数字电视将面临严峻的信息安全威胁,必须通过通信协议的安全性验证法选择出安全性更高的通信协议,才能确保双向数字电视传输网络的安全性。目前,关于验证通信协议的方法主要分为逻辑推理分析法、模型模拟检测法、定理归纳证明法以及其他衍生验证法。在前期研究的基础上,对近五年提出的典型协议验证方法进行总结比较,分析各验证方法的优缺点。最后,对协议验证领域存在的问题及未来的发展趋势做以阐述。

协议分析验证篇10

在分布式共享主存的多处理器系统中, 处理器通过各种互连结构 (总线、开关、网络等) 访问主存或相互通讯, 驻留在每个处理器内部的私有Cache成为提高层次存储系统性能的关键。但是私有Cache的引入在提高系统性能的同时, 也带来了数据的不一致问题。图1为一个简单的分布式共享主存的多处理器系统结构示意图。

在多处理器系统中, 每个处理器都有一个私有的Cache, 而主存是共享的, 这样很容易造成各私有Cache之间的数据不一致, 表1就是一个例子。

在表1所示的情况下, 如果不考虑数据一致性, 处理器0和处理器1最后的结果是x=1, y=1, 但实际上, x和y的值最后应该是2。这是由于处理器0和处理器1共享主存而拥有私有Cache导致的, 这就是本文所说的数据不一致现象。

Cache一致性协议是为实现共享数据访问的一致性、提供逻辑统一的共享主存访问界面并尽量减少网络通信流量的额外增加所采用的机制[2]。Cache一致性协议设计和实现的正确性不仅直接决定系统的正确性, 而且对系统的规模和性能有着至关重要的影响, 是实现分布式共享主存多处理器系统的关键。因此, 在多处理器系统研制过程中, 必须对Cache一致性协议的功能正确性进行全面而有效的验证。

2 SystemC简介

SystemC[3]是一种能同时实现较高层次软件和硬件描述的系统级设计语言, 它的本质是在C++基础上添加硬件扩展库和仿真核。一方面可以把它看作是与VHDL或Verilog HDL类似的硬件语言, 另一方面可以把它看作纯粹的C++程序, 只是拥有类似VHDL的类库支持。将SystemC用于Cache协议建模和验证可以有效的解决由Soc系统复杂度提高带来的系统级设计、验证和测试带来的不便, 将精力放在Cache协议建模上。

SystemC源代码可以使用任何标准C++编译环境进行编译, 生成可执行文件。运行可执行文件可以生成VCD格式的波形文件, 可以使用综合工具将SystemC的寄存器传输级 (RTL) 描述综合为Verilog HDL代码用于FPGA或者ASIC设计, 也可以使用体系结构综合工具综合为包括软件和硬件的片上系统。

3 验证FLASH SCI Cache一致性协议

3.1 FLASH SCI Cache一致性协议

SCI协议[4] (Scalable Coherent Interface protocol) 作为IEEE标准1596-1992而出名, SCI协议的目标是使用较少的存储开销记录大规模系统的共享信息。如图2所示, SCI协议的中心思想是使用双向链表链接共享结点, 而且链表的指针是分布式的, 不像动态指针分配协议[4]那样将指针集中在指针池中。由于SCI协议的存储器行的状态和一个指向共享链表头结点的指针域, 所以它比位向量协议[4]和动态指针分配协议的目录头小得多。为了遍历共享链表, SCI协议必须沿着目录头中的指针遍历, 直到到达目的结点, 这个结点一定是保维护着“Tag副本集” (其中保存的是当前处理器私有Cache的状态副本) 数据结构的。

SCI协议的分布式特征有两个优势:一是极大地减少存储开销, 因为处理器私有Cache行的数量相比于主存中Cache行的数量是微不足道的, 所有Tag副本信息对于每个处理器而言只是增加了极小的开销;二是解决了存储系统中的“hot spot”问题, 所谓“hot spot”是指某个结点在一段时间内频繁执行一致性动作。假设每个结点的主存大小为64MB (226bytes) , 处理器私有Cache大小为1MB (220bytes) , Cache行大小为128bytes, 目录头大小为2bytes, Tag副本大小为8bytes, 则SCI协议的目录头和Tag副本结构的存储开销如等式 (3-1) 所示。SCI协议的存储开销为:

位向量/粗粒度向量协议的存储开销为6.25%[4], 动态指针分配协议的存储开销为7.03%[4]。相比较而言, SCI协议的存储开销非常小, 在存储墙称为计算机发展瓶颈之一的今天, SCI协议占优巨大优势。

FLASH SCI协议[4]设计的目的是在FLASH结构[5]的机器环境下尽可能的实现标准SCI协议。FLASH SCI协议与IEEE标准1596-1992 SCI协议的不同之处在于:

(1) 只有Tag副本记录Cache状态;

(2) INVAL消息在链表上连续传播;

(3) 使用64项替换Buffer和Hash表;

(4) 写回操作无延迟;

(5) 遍历链表时不能操作处理器Cache中的数据;

(6) 优化D状态读/写请求;

(7) 精简结点ID位数和Cache状态位数。

在FLASH SCI协议中Cache状态只在Tag副本中有记录, 比起原来在Cache中专门留出部分空间保存Cache状态, 而Tag副本中又存储一份状态副本的设置, FLASH SCI协议减少了冗余信息, 提高了存储效率, 一定程度上加快了协议执行。

FLASH SCI协议在处理器Cache行被替换时并不是简单将数据覆盖, 而是将Cache行数据和状态复制到替换Buffer中, 一旦下次需要该数据时可以快速获得数据。替换Buffer的大小为64个Cache行大小并且是通过一个Hash表来查询的。这样的设计虽然在一定程度上使协议更加复杂了, 但由程序的时间局部性原理可知这样做有利于处理器的执行效率。

即使有了替换Buffer, FLASH SCI也是不允许需要写回的数据暂存于Buffer的, 在FLASH SCI中写回是立即执行, 不允许有延迟。同时, 为了保护数据, FLASH SCI不允许处理器通过遍历链表来操作Cache中的数据。

最后, FLASH SCI的目录项指针域和Tag副本数据结构中的前指针和后指针都只有10 bits, 而IEEE标准SCI协议中是16 bits。同时, 对于Cache状态, FLASH SCI也不需要标准SCI那么多, 标准SCI中本来就有很多Cache状态是备用的。

3.2 验证模型及验证方法

在SystemC中, 所有的信号和变量的初始化工作在构造函数中进行, 它比其它函数先执行, 由此可避免像Verilog HDL中由于初始化顺序不同引起的不同仿真器仿真结果不一致。

为重点说明验证方法, 全面检验协议可行性, 本文所用的验证分析模型是由5个相同结构的结点组成, 每个结点包含一个处理器、一个私有Cache、主存的一部分和结点控制器。需要说明的是, 为简化验证模型, 每个Cache只考虑一个Cache行, 这样就可以只关注协议本身而忽略与Cache有关的算法[6]。图3给出了验证模型。

本文验证的Cache一致性协议执行的粒度是Cache行, 所以建立只有一个Cache行的系统模型对于本文所用到的Cache一致性协议的验证是足够的。对于执行粒度是字的Cache一致性协议, 就必须建立每个Cache行有几个字的系统模型。无论执行粒度是Cache行还是字, 验证的基本原理都是相同的[7]。

本文采用模拟验证方法, 并在FLASH结构上实现验证。模拟验证[8,9] (Simulation Verification) 是目前的主流验证方法, 通过在系统输入端施加外部激励, 观察系统模型在外部激励信号作用下的反应判断该协议是否实现了预期的功能。模拟技术通过各种不同的操作序列验证设计是否满足功能要求, 模拟时间通常与系统复杂性的平方成正比。在设计阶段早期可通过高层次模拟进行性能预测和分析;在设计阶段中期, 模拟可用于软件算法开发和硬件求精;在设计阶段后期, 模拟用于确定设计是否满足性能目标, 并验证硬件和软件的正确性和兼容性。

注:表中“—”表示该项不存在, “->”表示链表的连接符号。

当前, 模拟验证方法发展已经非常成熟, 并获得了广泛应用。尽管近年来, 随着设计复杂度提高, 模拟验证方法固有的不能穷尽验证所有情况的缺陷面临越来越大的挑战, 但事实证明, 目前功能验证解决方案仍需围绕基于模拟的验证方案展开, 并辅以形式化验证等其它的验证方法。

3.3 验证结果

本文实现的FLASH SCI协议运行于5个结点的分布式存储处理器系统上, 系统状态数量是惊人的, 即使等价合并后其数量也还是巨大的, 所以状态列举法不能用于本文的验证工作。本文选取了96个具有代表性的情况 (几乎涵盖了所有系统状态) 进行了模拟验证。其中几种情况的验证结果如下表2所示。

本次模拟验证时未涉及网络延时问题, 所有命令均在第一时间被执行。由表中数据可看出命令执行的快慢与当时情况的复杂度有关, 共享数据的结点越多, 操作该数据的难度越大。如表中第六项N1结点要写数据“0007”至地址为“0x01”的存储单元需要经过10个周期才能完成, 原因是“0x01”的数据被4个结点共享, 在修改该数据前必须是共享该数据的4个结点中的数据作废。即便如此, 在10个周期内对4个结点执行数据作废命令, 对一个存储单元执行写命令任然是非常快的。

本次模拟验证基本上证实了FLASH SCI协议的正确性, 也从一定程度上证实了其在执行效率上的优越性。

4 结语

随着高性能计算机飞速发展, 分布式共享主存存储系统成为一种趋势, 伴随而来的数据一致性问题成为技术瓶颈之一。尽管许多Cache一致性协议被相继提出, 但都面临着各种各样的问题, 从协议的存储开销到协议适应的系统规模再到协议执行效率等。Cache一致性协议的验证工作也成为系统设计过程中不可或缺的重要环节目前验证的主要方法主要有两种:形式化验证和软件模拟验证。然而, 对于复杂的协议, 由于规模巨大导致的状态空间爆炸的问题, 形式化验证往往无法处理完整的协议验证工作, 在这种情况下, 软件模拟验证仍然是目前可用的主要验证方法。本文首先从理论上分析了SCI协议在存储开销的具有的优势, 然后用System C高层次语言对FLASH SCI协议进行建模, 并验证其正确性, 从而证明FLASH SCI协议的正确性以及其在存储开销和执行效率上的优越性。

摘要：FLSAH SCI协议作为Cache一致性协议的一种, 具有灵活性、高效性和适应性强等特点, 是目前最具发展潜力的Cache一致性协议之一。该协议在继承标准SCI协议低存储开销、维护精确共享信息等优点的同时对标准SCI协议进行优化, 得到更为高效、灵活的FLASH SCI协议。本文用SystemC高层次语言对FLASH SCI协议进行建模与描述, 并验证其正确性。模拟结果证明了FLASH SCI协议的正确性以及其在存储开销和执行效率上的优越性。

关键词：Cache一致性协议,SystemC高层次语言,模拟验证,形式化验证,FLASH,SCI协议

参考文献

[1]夏竟.CC-NUMA系统中Cache一致性协议模拟验证方法研究[硕士学位论文].长沙:国防科技大学, 2009.

[2]李崇民, 王海, 李兆麟.CMP中Cache一致性协议的验证[J].电子技术应用, 2005年, 第12期:5-8.

[3]李挥, 陈曦.SystemC电子系统级设计[M].北京:科学出版社, 2010年.

[4]Heinrich M A.The Performance and Scalability of Distributed SharedMemory Cache Coherence Protocols[D].Stanford University, 1998.

[5]Jeffrey Kuskin, David Ofelt, Mark Heinrich et al.The StanfordFLASH Multiprocessor.Annual Internation Symposium on Com-puter Architecture[J].1999, Vol.21.pp:302-313.

[6]G.Delaznno.Constraint-Based Verification of ParameterizedCache Coherence Protocol[J].In Formal Methods in SystemC Design, 2003, 23 (3) .pp:257-301.

[7]孙昱东, 孙强南, 阮英刚.Cache一致性协议的研究与评价[J].计算机工程与应用, 1995年, 第5期:53-55.

[8]陈海燕, 郭阳, 刘祥远, 陈吉华.集成电路计算机辅助设计与验证实践[M].长沙:国防科技大学出版社, 2010年.

本文来自古文书网(www.gwbook.cn)，转载请保留网址和出处

LTE培训材料-7 LTE接口协议分析01-20

泰勒思想01-20

泰勒科学管理理论对现代企业的借鉴意义01-20

对泰勒科学管理理论的学习感悟01-20

悉尼大学泰勒学院01-20