不可区分属性的计算可靠性分析方法研究

胡亚希

摘要：针对目前越来越复杂的安全协议，在计算可靠的安全协议符号分析方法的基础上，提出了一种计算可靠且支持双线性对、对称加密以及密钥循环的安全协议符号模型，该模型明确指定双线性对实例生成器和加密算法需要满足的安全属性，并证明了在满足这些安全属性的条件下，符号方法分析的不可区分属性蕴含计算方法分析的不可区分属性，这保证了该模型具有计算可靠性。同时，该模型通过增强攻击者对密钥循环的控制能力去除了无密钥循环的限制。

关键词：安全协议;符号方法;计算可靠性;通用可复合;双线性对

中图分类号：TP393      文献标识码：A

文章编号：1009-3044（2021）32-0040-04

人类迈入21世纪，随着信息技术的蓬勃发展，计算机网络逐渐成为人们工作和生活不可或缺的一部分。在互联网上，每天交换着巨量的数据，如何保证这些数据的安全，成为当下网络安全研究者们的关注焦点。

密码协议是保障通信系统安全的重要手段，其本身的安全性和可靠性直接关系到网络与通信系统的安全[1]。对于网络安全协议的形式化分析，一直存在两类不同的方法：计算方法和符号方法。计算方法是在概率论和计算复杂性理论基础上的一种“归约”方法，其结果更具密码学可靠性，但是证明过程是高度创造性的手工数学式证明，这对于目前越来越复杂的安全协议，不仅证明本身越来越复杂，而且证明的正确性也越来越不容易[2]。符号方法用形式化语言和符号推理对协议进行分析和验证，更容易实现自动化分析。但是由于对密码学原语和攻击者能力的理想建模，使得这类分析方法的肯定性结论往往并不直接具有现实意义，被认为没有真正建立起密码学的可靠性[3]。

Abadi和Rogaway[4]于2000年首次结合计算方法和符号方法，研究了不可区分属性的计算可靠性，提出在无密钥循环且对称加密算法满足type-0安全的条件下，如果消息在符号模型下具有不可区分性，则它们在计算模型下对应的二进制位串同样具有不可区分性。Abadi和Rogaway的研究虽然揭示了符号模型和计算模型之间关联，但其要求消息中只能包含对称加密原语，且不包含密钥循环。为此，本文通过扩展该方法，提出了包含双线性对和对称加密等原语的符号模型，去除了无密钥循环的限制，并证明了扩展后的方法依然具有计算可靠性。

1 符号模型

在符号模型中，消息通过符号表达式表示。Data，Keys和Nonce是互不相交的可数集合，分别表示协议中所有的数据、密钥和新鲜值的符号集合。d，d1，d2，…通常表示集合Data中的元素，k， k1， k2，…通常表示集合Keys中的元素，x， x1， x2，…通常表示集合Nonce中的元素。g1和g2分别表示双线性对中加法循环群G1和乘法循环群G2的生成元。p表示形如ax1x2x3+ bx4x5x6+…的多项式（Ploy），a， b等均为任意实数。

定义1-1：消息。消息的语法可由如下BNF规则给出：

msg∷=keys |d |x |g1x|（msg，msg） |{msg}keys

keys∷=k | g2p

消息（M，N）表示消息M和N的连接。{M}k表示用密钥k加密消息M。g1x，g2p分别表示群G1和群G2中的元素。表达式中的项都是符号，而不是实际应用中的二进制位串。例如，（M，N）=（M′，N′）当且仅当M=M′且N=N′;（M，N）必定和{M′}k不相等;类似地，{M}k={M′}k′当且仅当M=M′且k=k′。通常（（M1，M2）， M3）简写成（M1，M2， M3），{（M1，M2）}k简写成{M1，M2}k。

为了表示攻击者不能解密的消息，引入模式的定义，增加了符号“ÿ”。直观上，模式是表达式集合的扩展，增加了攻击者不能解密的消息表达式类型。但消息的模式比消息本身的结构要简单。

定义1-2：模式。模式的语法可由如下BNF规则给出：

pat∷=keys |d |x |g1x|（pat，pat） |{pat}keys| ÿ

keys∷=k | g2p

在给出安全性定义之前，需要先定义攻击者获取信息的能力，即推演关系“⊢”。M ⊢t表示在没有任何先验知识的情况下，攻击者通过消息集合M可以推断得到t。

定义1-3：推演关系。推演关系“⊢”是一种最小关系，需满足以下三个条件：

1） 若tÎM，则M⊢t， M⊢l;

2） 若M⊢x，则M⊢ g1x;

若M⊢x且M⊢ g1y， M⊢ g1z，则M⊢ g2xyz;

若M⊢g2p且M⊢g2q，则M⊢ g2lp+q， lÎZ;

3） 若M⊢t1且M⊢t2，则M⊢（t1，t2）;

若M⊢（t1，t2），则M⊢t1且M⊢t2;

若M⊢t且M⊢k，则M⊢{t}k;

若M⊢{t}k且M ⊢k，则M⊢t;

为了表示消息和消息模式之间的对应关系，定义模式函数p（M，T）。将给定密钥集合T和消息M映射到一个模式P，直观上，该模式就是攻击者在拥有密钥集合T的情况下从M能获得的信息。

定義1-4：模式函数。模式函数 p（M，T）定义如下：

1） p（k，T）=k （kÎKeys）

2） p（d，T）=d （dÎData）

3） p（x，T）=x （xÎNonces）

4） p（g1x，T）= g1x （xÎNonces）

5） p（g2p，T）= g2p （pÎPoly）

6） p（（M，N），T）=（p（M，T），p（N，T））

7） 若kÎT，则p（{M}k，T）={p（M，T）}k

8） 若kÏT，则p（{M}k，T）=struct（{M}k）

其中struct（M）定义如下：

1） struct（k）= ÿ （kÎKeys）

2） struct（d）= ÿ （dÎData）

3） struct （x）= ÿ （xÎNonces）

4） struct （g1x）=ÿ （xÎNonces）

5） struct （M，N）=（struct （M），struct （N））

6） struct （{M}k）={struct （M）}ÿ

定义1-5 ：消息模式。消息M的模式，用pattern（M）表示，定义为：

pattern（M）=p（M，FIX（ÁM））。

其中ÁM（T）= r（p（M，T）），而r（P）={kÎKeys |parts（P）⊢k}，parts（P）定义如下：

1） parts（k）= k  （kÎKeys）

2） parts （d）= d （dÎData）

3） parts （x）= x （xÎNonces）

4） parts （g1x）= g1x （xÎNonces）

5） parts （P，Q）=parts （P）Èparts （Q）

6） parts （{P}k）= {P}Èparts （P）

parts（P）表示在模式P中出現的所有子表达式的集合，除去其中仅作为对称加密用的密钥。r（P）表示模式P的可恢复密钥集合。FIX（ÁM）=Ç0lÁMi（Keys），l=|Keys（M）|，在这里Keys（M）表示消息表达式M中出现的所有密钥的集合。在定义攻击者拥有的密钥集合T时使用了求最大不动点的方式，使得攻击者可以获得消息中的循环密钥。

例1：M= （， ）

ÁM（Keys） = r（p（M，Keys））

= r （，）

= {k1，， }

ÁM2（Keys） =r（p（M，{k1，， }））

= r（， ）

= {， }

ÁM3（Keys） =r（p（M，{， }））

= r（， ）

= {， }

FIX（ÁM） ={， }

pattern（M）=p（M，FIX（ÁM））=（ ， ）

消息之间的不可区分通过等价关系定义，表示在没有预知相关密钥的情况下，两条消息在攻击者看来是等价的。例如，攻击者不能仅仅通过密文{0}k1和{1}k2获得密钥，因此攻击者不能解密和区分这些密文，所以{0}k1和{1}k2是等价的。类似地，对偶（0，{0}k1）和（0，{1}k2）也是等价的。但是，（k1，{0}k1）和（k2，{1}k2）就不是等价的了，因为攻击者可以从其获知密钥，并解密{0}k1和{1}k2得到0和1，以此区分这两条消息。

定义1-6：等价。两条消息等价当且仅当存在密钥替换s1和s2使得他们对应的消息模式相同，即M@N当且仅当 pattern（M） = pattern（Ns1s2）

其中密钥替换s1是密钥集合Keys上的双射函数。密钥替换s2是保持线性关系的多项式换名，即对g2p中指数p的换名，对消息中出现的若干多项式pi以及攻击者可获得的mj，"aiÎZ，"bjÎZ，s2满足åaipi=åbjmj当且仅当åai（pis2）=åbjmj，其中mj={xyz|x，y，zÎNonces且M⊢ g2mj}。

例2：M=， N=，

pattern（M）=

pattern（N）=

M@N

例3：M=，N=，

pattern（M）=

pattern（N）=

M[≅]N

2 计算模型

在计算模型中，消息就是{0，1}*上的二进制位串。

定义2-1：可忽略函数。negl（）为可忽略函数，若对于任意一个多项式p，都存在一个N（自然数），使得当n>N时，都能满足negl（n） <1/p（n）。

定义2-2：计算不可区分。两个概率总体D={Dh}和D′={D′h}。A代表任意概率多项式时间攻击者，h代表安全参数，存在可忽略函数negl（h），使得：

|Pr[x←Dh：A（h，x）=1]-Pr[x←D′h：A（h，x）=1]|£negl（h）

则称D和D′是计算不可区分的，记作D≈D′。

定义2-3：对称加密算法。对称加密算法（SE）由密钥生成算法（Gen）、加密算法（Enc）和解密算法（Dec）三个关于安全参数h的多项式时间算法组成，即SE=（Gen，Enc，Dec）。

定义2-4：不可区分选择明文攻击安全。对于任意安全参数h，任意概率多项式时间图灵机攻击者A的优势：

Adv（A）= Pr[AOL（h）=1]-Pr[AOR（h）=1]

如h为可忽略函数，则可认为SE=（Gen，Enc，Dec）满足不可区分选择明文攻击安全。

攻击者是一个图灵机，它和预言机商定了一个目标密码体制SE，预言机通过Gen生成随机密钥k，攻击者可以选择两条不同的消息m0和m1发送给预言机。该预言机有OL和OR两种方式：用Enck及新鲜随机硬币加密询问m0或者加密m1。攻击者的优势就是预言机以第一种方式实现时攻击者输出1的概率和预言机以第二种方式实现时攻击者输出1的概率差。若攻击者的最大优势是一个关于攻击者的计算资源慢增长的函数，则认为该加密算法是IND-CPA安全的。

定义2-5：双线性映射和双线性对。令q是一个大素数，G1是一个阶为q的加法循环群，g1为G1中的生成元，G2是一个阶为q的乘法循环群。定义在（G1 ，G1）上的一个双线性对是一个映射关系e：G1×G1® G2，满足下面的三条性质[5]：

双线性：对于任意P， Q1， Q2ÎG1，x，yÎZq*，有：

e（Q1x，Q2y）=e（Q1，Q2）xy，

e（P，Q1+Q2）=e（P，Q1）e（P，Q2），

e（Q1+Q2，P）=e（Q1，P）e（Q2，P），

非退化性：e（g1，g1）是G2的生成元，用g2表示，g2¹1G2。

可计算性：对于任意Q1， Q2Î G1，存在一种有效的算法能够快速计算e（Q1，Q2）。

双线性对实例生成器IG是一个概率多项式时间算法，给定安全参数h，输出五元组（q，G1，G2，g1，e）。

定义2-6：判定双线性Diffie-Hellman假设（DBDH假设）。对于任意安全参数h，任意概率多项式时间图灵机攻击者A的优势：

Adv（A）=Pr[（q，G1，G2，g1，e）¬IG（h）， x，y，zÎZq： A（g1，g1x，g1y，g1z，g2xyz）=1]

-Pr[（q，G1，G2，g1，e）¬IG（h），x，y，z，rÎZq： A（g1，g1x，g1y，g1z，g2r）=1]

是h的可忽略函数，则称实例生成器IG满足DBDH假设，即攻击者在只有g1x，g1y，g1z的情形下，区分g2xyz和随机群元素的概率是可忽略的。

为了获得符号模型消息不可区分的计算可靠性，首先需要通过一个映射算法将消息的符号表达式转换为计算模型中的二进制位串。

定义2-7：符号表达式的计算解释。给定对称加密算法SE=（Gen，Enc，Dec）和双线性对实例生成器IG，以及安全参数h，消息符号表达式M在计算模型中有其对应计算解释，即概率总体[M]SE，IG，h，可以通过如下两个步骤得到：

首先初始化，使用双线性对实例生成器IG（h）生成五元组得到t（g1）和t（g2），对消息M中出现的每个符号k，通过密钥生成算法Gen（h）随机生成位串t（k）与之对应，对消息M中出现的每个符号d，从位串{0，1}n中随机选择值t（d）与之对应，对消息M中出现的每个符号x，从Zq中随机选择值t（x）与之对应;

其次，根据消息的语法定义使用算法Convert递归解释M中的每个项：

1） 若M=k则返回<t（k），”key”>，

2） 若M=d则返回<t（d），”data”>，

3） 若M=x则返回<t（x），”nonce”>，

4） 若M= g1x则计算模幂e=t（g1）t（x）并返回<e，”exponent”>，

5） 若M= g2p则在Zq中计算t（p），以及模幂b=t（g2）t（p）并返回<b，”bilinear”>，

6） 若M=（M1，M2）则返回<（Convert（M1），Convert（M2）），”pair”>，

7） 若M={M1}k则计算x←Convert（M1），y←Enct（k） （x），并返回<y，”ciphertext”>。

2.1 计算可靠性

定理2-1：计算可靠性定理。

给定消息符號表达式M和N，且对称加密算法SE=（Gen，Enc，Dec）是IND-CPA安全的，双线性对实例生成器IG满足DBDH假设，则：M@NÞ[M] SE，IG≈[N] SE，IG。

证明：

前文已经说明符号表达式等价蕴含了计算不可区分，也就是如果有两条消息在符号方法中等价，则它们在计算解释下对应的概率分布总体也是计算不可区分的。为了证明该定理，首先引入3个引理。

引理1：给定消息符号表达式M，若对称加密算法SE=（Gen，Enc，Dec）满足IND-CPA安全，双线性对实例生成器IG满足DBDH假设，s1是密钥集合Keys上的双射函数，则[M] SE，IG≈[Ms1] SE，IG。

证明根据消息符号表达式的计算解释的定义，消息符号表达式在计算模型中给出对应计算解释时，消息M中出现的每个密钥符号通过密钥生成算法Gen（h）随机生成位串与之对应。因此密钥根据s1的换名不影响其计算解释的分布，所以不会影响消息的分布。引理1得证。

引理2：给定消息符号表达式M，若对称加密算法SE=（Gen，Enc，Dec）是IND-CPA安全的，双线性对实例生成器IG满足DBDH假设，s2是保持线性关系的多项式换名，则[M]SE，IG≈[Ms2] SE，IG。

证明由于s2是对g2p中指数p的换名，因此满足åaipi=åbjmj当且仅当åai（pis2）=åbjmj，mj={xyz|x，y，zÎNonces且M⊢g2mj}。下面分两种情况讨论。

第一种情况：若替换项xyz中某个指数在消息项中有出现，则必有一个指数不在消息项或者g1的指数出现。否则M⊢ g2xyz，此时必然存在ai，bj使得åaipi=åbjmj但åai（pis2）¹åbjmj。因此，xyz对其他项没有影响。由于指数的计算解释也是随机选取的，所以对其的替换不会影响消息的分布。

第二种情况：若替换项xyz中每个指数在消息项中都没有出现，则区分[M] SE，IG和[Ms2] SE，IG的概率与解决DBDH问题的概率相同，由于IG满足DBDH假设，因此[M] SE，IG≈[Ms2] SE，IG。引理2得证。

引理3：给定消息符号表达式M，若对称加密算法SE=（Gen，Enc，Dec）是IND-CPA安全的，双线性对实例生成器IG满足DBDH假设，则[M] SE，IG≈[pattern（M）] SE，IG。

证明根据模式函数的定义，有：

若kÎT，则p（{M}k，T）={p（M，T）}k，

若kÏT，则p（{M}k，T）= {struct（M）}k，

而M中出现的所有k都满足kÎKeys，因此，有：

p（M，Keys）=M，      （1）

同时，不难得到：

p（p（M，S），T）=p（M，SÇT）。 （2）

又r（M）={kÎKeys |parts（M）⊢k}，有：

r（p（M，T））Ír（M）。 （3）

由等式（1），有：

[M]SE，IG=[p（M，Keys）]SE，IG=[p（M，ÁM0（Keys））]SE，IG，

而根据消息模式的定义，有：

pattern（M） =p（M，FIX（ÁM）），

FIX（ÁM）=Ç0lÁMi（Keys）， l=|Keys （M）|，

ÁM（K）=r（p（M，K））。

所以，由等式（2）（3），有：

若K1ÍK2Í Keys，则

ÁM（K1）=r（p（M，K1））

=r（p（M，K1Ç K2））

=r（p（p（M，K2）， K1））

Ír（p（M， K2））

=ÁM（K2），

即ÁM（K1） ÍÁM（K1）。

因此，ÁM是单调函数，且FIX（ÁM）= ÁMl（Keys （M）），l= |Keys （M）|。

所以，有：

[pattern（M）]SE，IG=[p（M，FIX（ÁM））]SE，IG=[p（M， ÁMl（Keys））]SE，IG。

因此，若能证得"i，有：

[p（M，ÁMi（Keys））]SE，IG≈[p（M，ÁMi+1（Keys））]SE，IG       （4）

则根据传递性，有：

[p（M，ÁM0（Keys））]SE，IG≈[p（M，ÁMl（Keys））]SE，IG。

下面证明等式（4）。

令T=ÁMi（Keys），

M′=p（M，T）=p（M，ÁMi（Keys））    （5）

对模式p（M′，r（M′））进行分层。根据r（M′）定义，Keys（M′）-r（M′）={k1，k2，…，kn}为M′中没有在加密的消息中出现，而仅作为对称加密用的密钥。因此，{k1，k2，…，kn}中没有密钥循环。令M′i= p（M′， r（M′）È { k1， k2，…，kn}），其中若M′i中有子消息项是ki对kj加密，则i>j。根据安全性定义，若存在区分器D可区分[M′i]SE，IG和[M′i+1] SE，IG，则可构造攻破对称加密算法SE=（Gen，Enc，Dec）的IND-CPA安全的攻击者A，且攻击者A的优势不可忽略，与已知矛盾。

因此，有：

[M′ i] SE，IG i≈[M′i+1] SE，IG。

根据传递性，有

[M′0] SE，IG i≈[M′n] SE，IG。

而

M′0= p（M′，r（M′）），M′n=M′，

所以[M′]SE，IG≈[p（M′，r（M′））]SE，IG。

又，由等式（5）（2）以及ÁM的单调性，有

p（M′，r（M′）） =p（p（M，T），ÁM（T））

=p（M，TÇÁM（T））

=p（M，ÁM（T）），

因此[M′]SE，IG≈[p（M′，r（M′））]SE，IG≈[p（M，ÁM（T））]SE，IG。

由于p（M，ÁMi+1（Keys）） =p（M，ÁM（T）），

从而[p（M，ÁMi（Keys））]SE，IG=[M′]SE，IG

≈[p（M，ÁM（T））]SE，IG

≈[p（M，ÁMi+1（Keys））]SE，IG，

等式（4）得證。

因此，有：

[M]SE，IG≈[pattern（M）] SE，IG。

引理3得证。

下面开始证明定理1。

由引理3可得

[M]SE，IG≈[pattern（M）]SE，IG

[pattern（N）]SE，IG≈[N]SE，IG，

由引理1可得

[pattern（M）]SE，IG≈[pattern（Ms1）]SE，IG

由引理2可得

[pattern（Ms1）]SE，IG≈[pattern（Ms1s2）]SE，IG

由于M@N，则根据等价关系的定义

pattern（N）=pattern（Ms1s2），

综上所述，可得

[M]SE，IG≈[pattern（M）]SE，IG

≈[pattern（Ms1）]SE，IG

≈[pattern（Ms1s2）]SE，IG

≈[pattern（N）]SE，IG

≈[N]SE，IG，

即[M]SE，IG≈[N] SE，IG。

定理1得证。

参考文献：

[1] 雷新锋，宋书民，刘伟兵，等.计算可靠的密码协议形式化分析综述[J].计算机学报，2014，37（5）：993-1016.

[2] 付浩.基于双线性对的踪迹属性计算可靠性分析[J].计算机与数字工程，2017，45（7）：1360-1365.

[3] 付浩，肖建新.基于密钥循环的通用可复合符号分析[J].计算机与数字工程，2017，45（8）：1586-1591.

[4] Abadi M，Rogaway P.Reconciling two views of cryptography[M]//Theoretical Computer Science：Exploring New Frontiers of Theoretical Informatics.Berlin，Heidelberg：Springer Berlin Heidelberg，2000：3-22.

[5] 付玮，刘广亮.一种基于身份的门限盲代理盲签名方案[J].聊城大学学报（自然科学版），2012，25（3）：85-88.

【通联编辑：谢媛媛】