一个高效的基于身份签名方案的安全性分析

杨小东,肖立坤,李雨桐,陈春霖,王彩芬

(1.西北师范大学 计算机科学与工程学院,兰州 730070; 2.密码科学技术国家重点实验室,北京 100878)

0 概述

在基于身份签名的方案中,用户的公钥是Email地址、电话号码等唯一的身份信息,而相应的私钥由一个可信的密钥生成中心(Private Key Generator,PKG)产生。由于基于身份签名无需数字证书来验证公钥的正确性和用户身份的真实性,从而解决了传统签名中数字证书的管理和分发开销问题,因此被广泛应用于体域网、无线通信等领域[1]。

文献[2]提出了基于身份密码体制的思想。文献[3]提出了一个在随机预言模型下安全的基于身份的签名方案。然而,当用具体的哈希函数实例化理想的预言机时,在随机预言模型中的安全方案在现实中并不一定是安全的。文献[4]提出了无随机预言机的基于身份签名方案,其安全性在标准模型中依赖于CDH(Computational Diffie-Hellman)假设。为了提升该方案的性能,文献[5-6]分别提出了相应的改进方案,但文献[7]发现这些改进的方案无法抵抗伪造攻击。文献[8]提出强不可伪造的基于身份签名方案,不仅能防止攻击者伪造新消息的签名,而且能阻止攻击者利用以前的消息/签名对生成新的合法签名。尽管文献[8]方案提升了基于身份签名方案的安全性,但该方案的计算开销较大,实用性比较差。文献[9]构造了另外一个强不可伪造的基于身份签名方案,但文献[10]发现该方案的安全性证明是错误的。因此,迫切需要研究更安全、更高效的基于身份签名方案。

为了抵抗重放攻击,文献[11]在2017年提出了一个高效的基于身份签名方案(下文简称Huang方案),具有较短的系统参数和较低的计算开销,并在标准模型中证明了该方案满足强不可伪造性,其安全性可归约到CDH假设。Huang方案的安全性证明采用了基于混合游戏的证明方法,但本文发现该方案的安全性证明存在严重的安全缺陷。首先设计一个多项式时间算法,区分一个签名来自Huang方案证明中的模拟游戏还是真实游戏。其次构造一个多项式算法来伪造Huang方案的签名,使挑战者利用该算法输出的伪造签名来解决CDH问题。

1 预备知识

1.1 双线性映射

令G1和G2是2个阶为素数p的循环群,g是G1的一个生成元,如果一个可有效计算的映射e:G1×G1→G2满足以下条件,则称e是一个双线性映射[4]。

2)非退化性:e(g,g)≠1。

1.2 计算复杂度假设

定义1(CDH假设) 如果没有一个概率多项式时间算法能以不可忽略的概率求解G1上的CDH问题,则称CDH问题是困难的[4]。

1.3 基于混合游戏的安全性证明方法

通常直接证明一个密码方案的安全性是非常困难的。为了降低证明密码方案的复杂度,文献[12]提出了基于混合游戏的安全性证明方法,并已成为大部分密码方案证明其安全性的主要方法。对于基于身份签名方案,主要由攻击者和挑战者之间的2个安全游戏组成:

1)真实游戏Game0:挑战者生成主密钥和系统参数,并运行实际的算法来响应攻击者发起的密钥询问和签名询问。

2)模拟游戏Game1:挑战者首先获得一个困难数学问题的实例,然后在不知道主密钥的情况下,通过模拟密钥和签名来响应攻击者发起的密钥询问以及签名询问,最后利用攻击者伪造的签名来解决困难数学问题的实例。

如果以下2个条件成立,则称基于身份签名的方案是可证明安全的:

1)没有一个多项式时间算法能以不可忽略的概率区分真实游戏Game0与模拟游戏Game1。

2)在模拟游戏Game1中,如果攻击者伪造了一个合法的签名,则挑战者能以不可忽略的概率求解困难数学问题。

基于混合游戏的安全性证明方法主要采用了归约的证明思想,将方案的安全性归约到关联的数学问题的计算困难性。由于求解困难数学问题的概率是可忽略的,因此在模拟游戏Game1中攻击者能伪造一个合法签名的概率是可忽略的;而真实游戏Game0与模拟游戏Game1是不可区分的,所以攻击者在真实游戏Game0中获胜的概率也是可忽略的。因此,只要方案基于的数学问题是计算困难的,则可证明相应的基于身份方案是安全的。

2 Huang等人的基于身份签名方案

为了简化表述,令χ(d):G1→{0,1}*表示一个映射;当d∈G1的x轴坐标为奇数时,设置χ(d)=1;当d∈G1的x轴坐标为偶数时,设置χ(d)=0。Huang方案的具体描述如下:

σ= (Q1,Q2,Q3)=(d1(vτ2wh)rm,d2,grm)=

4)验证。对于一个消息m和时戳Ti的签名σ=(Q1,Q2,Q3),如果Ti>Ti-1不成立,则验证者拒绝接受签名;否则,验证者计算h=T(m)|Ti,并验证等式:

e(Q1,g)=e(g2,g1)e(xτ1yID,Q2)e(vτ2wh,Q3)

如果上述等式成立,验证者接受σ是一个合法的签名;否则,拒绝σ。

3 Huang方案的安全性分析

本文通过2个定理来分析Huang方案[11]的安全性,发现Huang方案的安全证明不满足1.3节的基于混合游戏的安全性证明方法中的2个条件。这表明该方案的安全证明存在安全缺陷,进而说明Huang方案的安全证明无法正确地证明该方案的强不可伪造性。

证明:当攻击者A请求关于消息mi、身份IDi和时戳Ti的签名σi=(Qi,1,Qi,2,Qi,3)时,挑战者B无法生成χ(Qi,3)=0的签名,从而导致χ(Qi,3)=0与χ(Qi,3)=1之间的概率分布存在差异。虽然差异较小,但经过多项式次的签名询问后,这个差异使得D能以不可忽略的概率区分χ(Qi,3)=0与χ(Qi,3)=1的2种分布。

令L表示D允许询问签名的最大次数,则D的具体描述如下:

1)设置初始值c=0。

2)对于i=1:L,D每次进行如下操作:

(1)随机选择一个身份IDi,一个消息mi和一个时戳Ti;

(2)向挑战者B请求并获得关于IDi、mi和Ti的签名σi=(Qi,1,Qi,2,Qi,3);

(3)如果χ(Qi,3)=1,则设置c=c+1。

由于D仅进行了有限次的签名询问,因此D是基于身份签名方案的安全模型中被允许的攻击者。下面分析D成功的概率:

1)如果D与真实游戏Game0进行交互,在实际的签名算法中rmi是随机选取的,则Pr[χ(Qi,3)=0]=1/2,Pr[χ(Qi,3)=1]=1/2。

2)如果D与模拟游戏Game1进行交互,则挑战者B不能生成χ(Qi,3)=0或χ(di,2)=0的签名。在G1中对于qE次的密钥询问有概率Pr[χ(di,2)=0]=qE/2,因此,在G1中:

定理2如果一个攻击者A以不可忽略的概率伪造Huang方案的签名,则存在一个多项式时间算法F也以不可忽略的概率伪造Huang方案的签名,但挑战者B无法利用算法F的伪造签名求解G1上的CDH问题。

证明:对于A发起的密钥和签名询问,F首先将相应的询问转交给B,然后将B的回答作为响应发送给A,如图1所示。

图1 询问-响应流程

令λ是Huang方案的安全参数,F的具体操作描述如下:

1)F从挑战者B获得系统参数params,并转发给攻击者A。

2)F收到A请求的密钥和签名询问后,首先将相应的询问转发给挑战者B,然后将B对询问的回答作为响应发送给A。

由于F只是进行A和B之间询问与响应的转发,因此在基于身份签名方案的安全模型中,F是被允许的攻击者。

因为从F的构造过程可知,F是Huang方案的一个合法攻击者,所以Huang方案的安全性并不能规约到CDH问题的困难性,从而使得Huang方案的安全性与CDH假设无关。这也表明Huang方案的安全性证明不满足基于混合游戏证明方法的第2个条件。

综合定理1和定理2很容易发现,Huang方案的安全性证明存在严重的安全缺陷,无法从理论上证明Huang方案的安全性。

4 结束语

Huang等人设计了一个具有较短系统参数的基于身份签名方案,并在标准模型中证明该方案是强不可伪造的。本文对该方案进行安全性分析,发现其安全性证明并不满足基于混合游戏证明方法的2个条件,从而表明将Huang方案的安全性规约到CDH假设的结论是错误的。即存在一个多项式时间算法能区分Huang方案的真实游戏和模拟游戏,挑战者无法利用攻击者伪造的签名求解CDH问题。Huang方案的安全性证明存在缺陷的主要原因是采用了安全性较低的Boneh和Boyen方案[14]。此外,Huang方案无法抵抗量子计算攻击[15-16]。因此,如何构造具有更短系统参数且抗量子计算攻击的基于身份签名方案,仍需要进一步研究。