对两个基于身份签密方案的分析与攻击*
2014-03-06张李军
张李军,范 佳
(保密通信重点实验室,四川 成都 610041)
0 引言
1997年,Zheng[1]提出了签密体制的概念。该体制将公钥加密体制和数字签名体制融为一体,同时实现公钥加密和数字签名的功能,而且效率远远高于“先签名后加密”或者“先加密后签名”的方式。基于身份的签密是一种特殊的签密体制,用户公钥可以是与用户身份相关的一串字符,比如用户的身份证号码,名字等[2]。这就大大减轻了传统的基于公钥基础设施的繁重的公钥证书管理工作。2002年Malone-Lee利用双线性对构造了第一个基于身份的签密方案。
在目前所有实用的基于身份的签密方案中,绝大部分方案的安全性都基于随机预言机模型。该模型假设所有的哈希函数都是一个随机函数,然而实际使用的哈希函数都不是随机函数。有学者构造了能够在随机预言机模型下安全但是在标准模型下却不安全的密码方案[3]。标准模型下安全的密码方案已成为可证明安全公钥密码方案设计的趋势。2009年Yu等人[4]设计了第一个在标准模型下安全的基于身份的签密方案。随后多篇文献对该方案所声称的保密性进行了成功的攻击。Yu的方案虽然被攻破,但是其构造的思路被随后多篇文献借鉴。
Jin 等人[5]和 Zhang[6]设计的方案都声称其在标准模型下可以证明在保密性方面满足IND-CCA安全性且在不可伪造性方面满足EUF-CMA安全性。针对这两个方案的安全性进行了分析,并对Jin等人方案所声称的IND-CCA和EUF-CMA安全性进行了成功攻击,然后对Zhang方案所声称的INDCCA安全性进行了成功攻击,分析该方案满足EUF-CMA安全性,并进一步对这两个方案的其他强度的安全性进行了分析和总结。
1 基于身份的签密模型
基于身份的签密模型包括签密语义以及保密性和不可伪造性两个方面的定义。
1.1 签密语法定义
1)系统建立算法(Setup):由密钥生成中心PKG完成,输入安全参数k,输出系统主私钥msk和系统公钥参数mpk。PKG保密msk,公开mpk。
2)私钥提取算法(Extract):输入一个用户的身份IDU和系统参数mpk,PKG使用系统主私钥msk计算用户的私钥skU并通过安全方式发送给该用户。
3)签密算法(Signcrypt):输入 mpk,明文 M,接收者的身份IDR和发送者的私钥skS,输出密文。
4)解签密算法(Unsigncrypt):输入密文,系统参数mpk,接收者的私钥skR和发送者的身份IDS,输出明文M或输出符号“⊥”表示解签密失败。
这些算法满足基于身份的签密方案的一致性要求,即如果 Signcrypt(mpk,M,skS,IDR),那么 M=Unsigncrypt(mpk,IDS,skR)。
1.2 签密的保密性
目前对于签密的保密性定义包括两种,INDCCA安全和IND-gCCA安全。其中IND-CCA是最常使用的一种安全性。IND-gCCA安全比INDCCA安全稍弱,但也是一种被广泛认可的安全定义。签密的IND-CCA安全性定义如下:
游戏包括以下五个阶段:
1)初始阶段:挑战者C输入安全参数k,运行系统建立算法获得(mpk,msk),并将系统参数mpk发送给攻击者A。
2)询问阶段1:攻击者A执行适应性询问。
私钥提取询问:A提交一个身份IDU,C计算skU=Extract(mpk,msk,IDU)并将结果发送给 A。
签密询问:A提交两个身份IDS和IDR,一个明文M。C计算Signcrypt(mpk,M,skS,IDR)并将签密结果发送给A。
解签密询问:A选择两个身份IDS和IDR,一个密文。C首先计算私钥 skR=Extract(mpk,msk,IDR),然后计算 Unsigncrypt(mpk,IDS,skR),最后发送结果明文M或符号“⊥”给A。
3)挑战阶段:A生成两个相同长度的明文M0,M1和希望挑战的两个身份IDS*,IDR*,其中IDR*不能是已经执行过私钥提取询问的身份。C随机选择β∈{0,1},计算=Signcrypt(mpk,Mβ,skS*,IDR*)并将结果发送给A。
4)询问阶段2:攻击者A可以像询问阶段1那样执行适应性询问。但是在这一阶段,A不能对IDB执行签密询问,也不能对密文执行解签密询问。
5)猜测阶段:A输出一个值β%作为对β的猜测。如果β%=β,A赢得游戏。
定义1 如果没有任何攻击者能够在多项式时间内以一个不可忽略的优势Adv(A)取胜(Adv(A)=|Pr[β'=β]-1/2|),则称一个基于身份的签密方案满足IND-CCA安全性。
签密的IND-gCCA定义如下:
IND-gCCA游戏的描述和IND-CCA游戏的描述类似,只是在询问阶段2还有一个附加条件,即如果Mβ=Unsigncrypt(mpk,σ,IDS,skR),则攻击者不能输入(σ,IDS,IDR)进行解签密询问。
定义2 如果没有任何攻击者能够在多项式时间内以一个不可忽略的优势Adv(A)取胜(Adv(A)=|Pr[β'=β]-1/2|),则称一个基于身份的签密方案满足IND-gCCA安全性。
1.3 签密的不可伪造性
目前对于不可伪造性的定义有两种,一种是EUF-CMA,另一种是 sEUF-CMA。sEUF-CMA 安全性比EUF-CMA安全性稍强。签密的EUF-CMA安全性定义如下:
考虑挑战者C和伪造者F之间的游戏:
1)初始阶段:挑战者C输入安全参数k,运行系统建立算法,将系统参数mpk发送给伪造者F。
2)询问阶段:F像IND-CCA游戏中的A那样可以执行多次询问。
3)伪造阶段:F输出一个新的三元组,如果以下三个条件满足,则F赢得游戏:
a)F没有对IDS*执行过私钥提取询问。
b)Unsigncrypt(σ*,IDS*,skR*)的结果不是符号“⊥”。
c)F没有对(M*,IDS*,IDR*)执行过签密询问,其中 M*=Unsigncrypt(σ* ,IDS*,IDR*)。
定义3 如果没有任何伪造者F能在多项式时间内以一个不可忽略的优势Adv(F)取胜(Adv(F)=Pr[F赢得EUF-CMA游戏]),称一个基于身份的签密方案满足EUF-CMA安全性。
签密的sEUF-CMA安全性定义如下:
sEUF-CMA和EUF-CMA游戏类似,只是sEUF-CMA游戏在伪造阶段的第三个条件变为:
3)不是任何一个签密询问的输出结果。
定义4 如果没有任何伪造者F能在多项式时间内以一个不可忽略的优势Adv(F)取胜(Adv(F)=Pr[F 赢得 sEUF-CMA]),则称一个基于身份的签密方案满足sEUF-CMA安全性。
2 对JWD方案的分析
在文献[5]中,Jin,Wen和Du提出了一种基于身份的签密方案,并声称是IND-CCA和EUF-CMA安全的,本节将证明事实并非如此。
该方案的详细算法如下:
1)Setup(1k):输入安全参数k,输出系统公私钥对(mpk,msk)。首先密钥生成中心PKG,选择大素数p阶群G和GT,g是群G的一个生成元,由此构造出双线性对e:G×G→GT;选择抗碰撞哈希函数H:{0,1}k→{0,1}l和双射 φ:R→GT,其中 R 是{0,1}k+l的p个元素的子集,并记φ-1是φ的逆映射;随机选择 G 中的元素 α,g2,u',m',并计算 g1←gα;选取长度分别为l和n的向量和,其中mi和ui都是G中的元素。算法输出的系统私钥msk为,公钥参数为e,H,g等。
2)Extract(mpk,IDP):输入系统公钥mpk和用户身份IDP,输出用户私钥skP。设IDP是长度为n的比特串,UP[i]表示 IDP的第 i个比特。符号 up表示满足条件UP[i]=1的指标集。KGC随机选择rp,计算IDP的私钥skP为((u'∏i∈uPui)rP,grP)。
3)Signcrypt(mpk,M,IDA,IDB,skA):现在 Alice(身份为IDA)向Bob(身份为IDB)发送消息M∈{0,1}k,skA为 Alice的私钥。Alice 随机选择 rp∈Zp和 R∈{0,1}l,且满足 M||R∈R。输出签密密文 σ=(σ1,σ2,σ3,σ4,σ5)分别为 e(g1,g2)rφ(M||R),gr,(u'∏i∈uPui)r,dA1(m'∏j∈Nmj)r,dA2,其中 N={j∈Z:H(M)[j]⊕R[j]=1}。
4)Unsigncrypt(σ,IDA,IDB,skB):收 到 密文 σ=(σ1,σ2,σ3,σ4,σ5),Bob 利用私钥 skB计算M||R←σ1e(dB2,σ3)e(dB1,σ2)-1,并生成指标集 N={j∈Z:H(M)[j]⊕R[j]=1}。
若 e(σ4,g)=e(g1,g2)e(u'∏i∈uPui,σ5)·e(m'∏j∈Nmj,σ2)则输出明文 M;否则输出符号⊥。
2.1 对IND-CCA安全性的攻击
我们可以在下面的步骤中对IND-CCA安全性进行攻击:
1)根据IND-CCA安全性的定义,在挑战阶段中,对于发送方和接收方身份(IDS*,IDR*),攻击者A将获得一个挑战密文 σ*=(σ1*,σ2*,σ3* ,σ4* ,σ5*)。
2)然后在询问阶段2中,A随机选择r'∈Zp,通过对密文(σ,IDS*,IDR*)进行解签密询问(其中 σ=(σ1* ,σ2* ,σ3* ,σ4*(u'∏i∈uS*ui)r',σ5*gr')),得到消息M。
3)在猜测阶段中,A检查是否M=M0,若该等式成立,则输出猜测比特0,否则输出1。
2.2 对EUF-CMA安全性的攻击
虽然根据文献[6],(σ4,σ5)是对 H(M)⊕R(按比特异或)的数字签名,但并不等于对M和R的签名。我们可以对EUF-CMA安全性进行攻击:
在询问阶段中,伪造者F执行以下步骤:
1)伪造者F选择(M,IDS,IDR)进行签密询问,得到相应签密密文σ,且伪造者F保证始终不对身份IDS发起私钥提取询问。
2)伪造者F对身份IDS发起私钥提取询问,得到私钥dR。
在伪造阶段中,F进行以下攻击:
1)对密文(σ,IDS,IDR)运行 Unsigncrypt算法,得到随机数R。
2)选择一个任意的不是M的消息M'。
3)寻找满足N'=N的比特串R'∈{0,1}l。
4)计算 σ1'=σ1φ(M'||R')/φ(M||R)。
5)令 σ'=(σ'1,σ2,σ3,σ4,σ5)。
容易验证σ'是一个有效签密密文。至此,伪造者F成功地进行了一次攻击。
对其他强度安全性的分析:2.1节中的攻击方法对于IND-gCCA安全性的攻击是无效的。因为在攻击的第2步中询问的密文σ的解签密结果为,这违背了IND-gCCA安全性定义中对攻击者的限制。
由于sEUF-CMA的安全性比EUF-CMA安全性更强,且2.2节的攻击已经表明JWD方案不满足EUF-CMA安全性,因此,JWD方案自然也不满足sEUF-CMA安全性。
3 对Zhang签密方案的攻击
在文献[6]中,Zhang对Yu的方案进行了改进,并提出一种新的基于身份的签密方案,且声称是IND-CCA和EUF-CMA安全的。本节将对该方案进行安全性分析。
该方案的详细算法如下:
1)Setup(1k):输入安全参数k,输出系统公私钥对(mpk,msk)。密钥生成中心首先PKG选择大素数p阶群G和GT,g是群G的一个生成元,由此构造出双线性对e:G×G→GT;选择两个抗碰撞的哈希函数,H2:G→{0,1}l;随机选择 G中的元素α并计算g1←gα;选取长度分别为l和n的向量和,其中mi和ui都是G中的元素。算法输出的系统私钥对钥msk为,公钥参数为 e,H1,H2,g 等。
2)Extract(mpk,msk,IDP):对用户身份 IDP,算法输出用户私钥skP。与JWD方案中的Extract算法相同,PKG计算对应身份IDP的私钥skP=(dp1,dp2)为((u'∏i∈uPui)rP,grP)。
3)Signcrypt(mpk,M,IDA,IDB,skA):现在Alice(身份为IDA)向Bob(身份为IDB)发送消息 M,skA为 Alice的私钥。Alice随机选择 r,s,计算 R=e(g1,g2)r,t=H1(M||R),m″=H2(gths)。令 M'表示满足条件m[j]=1指标集,其中 m[j]表示 m″的第 j个比特。密文 σ=(σ1,σ2,σ3,σ4,σ5,σ6)为 R·M,gr,(u'∏i∈uPui)r,dA1(m'∏j∈M'mj)r,dA2,s。
4)Unsigncrypt(mpk,σ,IDA,IDB,skB):收到密文σ后,Bob利用自己的身份 IDB和私钥 skB计算 R←e(dB2,σ3)-1e(dB1,σ2),M←σ1R-1,t←H1(M||R),m″←H2(gthσ6);利用 m″生成对应的指标集M',满足 m″的第 j个比特 m[j]=1。若 e(σ4,g)=e(g1,g2)e(u'∏i∈uAui,σ5)e(m'∏j∈M'mj,σ2),则输出明文M;否则输出符号⊥。
3.1 对IND-CCA安全性的攻击
我们采用类似对JWD方案IND-CCA安全性的攻击方法进行如下攻击:
1)根据IND-CCA安全性的定义,在挑战阶段中,对于挑战发送方和接收方身份(IDS*,IDR*),攻击者A将得到一个挑战密文σ*。
2)紧接着在询问阶段2中,A随机选择r并输出(σ,IDS*,IDR*)进 行 解签密询 问,其 中 σ=(σ1* ,σ2* ,σ3* ,σ4*(u'∏i∈uSui)r',σ5*gr',σ6)。
3)在猜测阶段中,攻击者A检查是否有M=M0,若该等式成立,则输出0,否则输出1。
类似对JWD方案IND-CCA安全性攻击的分析,可以得出,Zhang方案也不满足IND-CCA安全性。
3.2 对EUF-CMA安全性的分析
根据Zhang方案中对签密密文σ的设置可以看出,(σ4,σ5,σ6)是对 M‖e(g1,g2)r的数字签名,因为是级联的关系,所以(σ4,σ5,σ6)包含了对消息 M的签名。因此Zhang方案满足EUF-CMA安全性。
对其他强度安全性的分析:类似对JWD方案IND-gCCA安全性的分析可以得出,以上对于Zhang方案IND-CCA安全性的攻击也不能用于对该方案进行IND-gCCA安全性攻击。因此,Zhang方案的IND-gCCA安全性还不能确定。
对于Zhang方案的sEUF-CMA安全性我们发现了如下的攻击:
1)在询问阶段中,伪造者 F选择(M,IDS,IDR)并进行签密询问,得到相应的签密密文σ。
2)在伪造阶段中,F 选择r,计算 σ*=(σ1,σ2,σ3,σ4(u'∏i∈uS*ui)r',σ5gr',σ6),显然 σ* 是一个有效签密密文。因此方案不是sEUF-CMA安全的。
对JWD和Zhang构造的两个基于身份签密方案分别进行了详细的安全性分析,结果如表1所示。
表1 方案安全性分析结果Table 1 Result of security analysis
4 结语
一个安全的签密方案需要同时满足保密性和不可伪造性两个方面的安全性。JWD方案在不可伪造性方面既不满足EUF-CMA安全性,也不满足sEUF-CMA安全性。所以即使该方案满足IND-gCCA安全性,也不是一个安全的签密方案。而Zhang方案满足EUF-CMA安全性,如果其还满足IND-gCCA安全性,则该方案是一个安全的签密方案。因此,进一步对Zhang方案的IND-gCCA安全性的确定,无论是攻击还是安全性证明,都是一个值得研究的问题。
[1]ZHENG Y.Digital Signcryption or How to Achieve Cost(signature&encryption)<< Cost(Signature)+Cost(Encryption)[C]//Advances in Cryptology CRYPTO97,LNCS.[s.l.]:Springer,1997:165-179.
[2]马丁,龙恺.基于互联网实名制的电子交易强认证方法[J].通信技术,2013,46(12):86-88.MA Ding,LONG Kai.Strong Authentication of Electronic Trading based on Internet Real-Name System [J].Communications Technology,2013,46(12):86-88.
[3]CANETTI R,GOLDREICH O,HALEVI S.The Random Oracle Methodology Revisited(Preliminary Version)[J].STOC,1998:209-218.
[4]YONG Y,YANG B,YING S,et al.Identity-based Signcryption Scheme without Random Oracles[J].Computer Standards& Interfaces,2009,31(01):56-62.
[5]JIN Z,WEN Q,DU H.An Improved Semantically-secure Identity-based Signcryption Scheme in the Standard Model[J].Computers & Electrical Engineering,2010,36(03):545-552.
[6]ZHANG B.Cryptanalysis of an Identity Based Signcryption Scheme without Random Oracles[J].Journal of Computational Information Systems,2010,6(06):1923-1931.