楊小東,肖立坤,李雨桐,陳春霖,王彩芬

(1.西北師范大學(xué) 計算機科學(xué)與工程學(xué)院,蘭州 730070; 2.密碼科學(xué)技術(shù)國家重點實驗室,北京 100878)

0 概述

在基于身份簽名的方案中,用戶的公鑰是Email地址、電話號碼等唯一的身份信息,而相應(yīng)的私鑰由一個可信的密鑰生成中心(Private Key Generator,PKG)產(chǎn)生。由于基于身份簽名無需數(shù)字證書來驗證公鑰的正確性和用戶身份的真實性,從而解決了傳統(tǒng)簽名中數(shù)字證書的管理和分發(fā)開銷問題,因此被廣泛應(yīng)用于體域網(wǎng)、無線通信等領(lǐng)域[1]。

文獻[2]提出了基于身份密碼體制的思想。文獻[3]提出了一個在隨機預(yù)言模型下安全的基于身份的簽名方案。然而,當(dāng)用具體的哈希函數(shù)實例化理想的預(yù)言機時,在隨機預(yù)言模型中的安全方案在現(xiàn)實中并不一定是安全的。文獻[4]提出了無隨機預(yù)言機的基于身份簽名方案,其安全性在標(biāo)準(zhǔn)模型中依賴于CDH(Computational Diffie-Hellman)假設(shè)。為了提升該方案的性能,文獻[5-6]分別提出了相應(yīng)的改進方案,但文獻[7]發(fā)現(xiàn)這些改進的方案無法抵抗偽造攻擊。文獻[8]提出強不可偽造的基于身份簽名方案,不僅能防止攻擊者偽造新消息的簽名,而且能阻止攻擊者利用以前的消息/簽名對生成新的合法簽名。盡管文獻[8]方案提升了基于身份簽名方案的安全性,但該方案的計算開銷較大,實用性比較差。文獻[9]構(gòu)造了另外一個強不可偽造的基于身份簽名方案,但文獻[10]發(fā)現(xiàn)該方案的安全性證明是錯誤的。因此,迫切需要研究更安全、更高效的基于身份簽名方案。

為了抵抗重放攻擊,文獻[11]在2017年提出了一個高效的基于身份簽名方案(下文簡稱Huang方案),具有較短的系統(tǒng)參數(shù)和較低的計算開銷,并在標(biāo)準(zhǔn)模型中證明了該方案滿足強不可偽造性,其安全性可歸約到CDH假設(shè)。Huang方案的安全性證明采用了基于混合游戲的證明方法,但本文發(fā)現(xiàn)該方案的安全性證明存在嚴重的安全缺陷。首先設(shè)計一個多項式時間算法,區(qū)分一個簽名來自Huang方案證明中的模擬游戲還是真實游戲。其次構(gòu)造一個多項式算法來偽造Huang方案的簽名,使挑戰(zhàn)者利用該算法輸出的偽造簽名來解決CDH問題。

1 預(yù)備知識

1.1 雙線性映射

令G1和G2是2個階為素數(shù)p的循環(huán)群,g是G1的一個生成元,如果一個可有效計算的映射e:G1×G1→G2滿足以下條件,則稱e是一個雙線性映射[4]。

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

1.2 計算復(fù)雜度假設(shè)

定義1(CDH假設(shè)) 如果沒有一個概率多項式時間算法能以不可忽略的概率求解G1上的CDH問題,則稱CDH問題是困難的[4]。

1.3 基于混合游戲的安全性證明方法

通常直接證明一個密碼方案的安全性是非常困難的。為了降低證明密碼方案的復(fù)雜度,文獻[12]提出了基于混合游戲的安全性證明方法,并已成為大部分密碼方案證明其安全性的主要方法。對于基于身份簽名方案,主要由攻擊者和挑戰(zhàn)者之間的2個安全游戲組成:

1)真實游戲Game0:挑戰(zhàn)者生成主密鑰和系統(tǒng)參數(shù),并運行實際的算法來響應(yīng)攻擊者發(fā)起的密鑰詢問和簽名詢問。

2)模擬游戲Game1:挑戰(zhàn)者首先獲得一個困難數(shù)學(xué)問題的實例,然后在不知道主密鑰的情況下,通過模擬密鑰和簽名來響應(yīng)攻擊者發(fā)起的密鑰詢問以及簽名詢問,最后利用攻擊者偽造的簽名來解決困難數(shù)學(xué)問題的實例。

如果以下2個條件成立,則稱基于身份簽名的方案是可證明安全的:

1)沒有一個多項式時間算法能以不可忽略的概率區(qū)分真實游戲Game0與模擬游戲Game1。

2)在模擬游戲Game1中,如果攻擊者偽造了一個合法的簽名,則挑戰(zhàn)者能以不可忽略的概率求解困難數(shù)學(xué)問題。

基于混合游戲的安全性證明方法主要采用了歸約的證明思想,將方案的安全性歸約到關(guān)聯(lián)的數(shù)學(xué)問題的計算困難性。由于求解困難數(shù)學(xué)問題的概率是可忽略的,因此在模擬游戲Game1中攻擊者能偽造一個合法簽名的概率是可忽略的;而真實游戲Game0與模擬游戲Game1是不可區(qū)分的,所以攻擊者在真實游戲Game0中獲勝的概率也是可忽略的。因此,只要方案基于的數(shù)學(xué)問題是計算困難的,則可證明相應(yīng)的基于身份方案是安全的。

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

為了簡化表述,令χ(d):G1→{0,1}*表示一個映射;當(dāng)d∈G1的x軸坐標(biāo)為奇數(shù)時,設(shè)置χ(d)=1;當(dāng)d∈G1的x軸坐標(biāo)為偶數(shù)時,設(shè)置χ(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]的安全性,發(fā)現(xiàn)Huang方案的安全證明不滿足1.3節(jié)的基于混合游戲的安全性證明方法中的2個條件。這表明該方案的安全證明存在安全缺陷,進而說明Huang方案的安全證明無法正確地證明該方案的強不可偽造性。

證明:當(dāng)攻擊者A請求關(guān)于消息mi、身份IDi和時戳Ti的簽名σi=(Qi,1,Qi,2,Qi,3)時,挑戰(zhàn)者B無法生成χ(Qi,3)=0的簽名,從而導(dǎo)致χ(Qi,3)=0與χ(Qi,3)=1之間的概率分布存在差異。雖然差異較小,但經(jīng)過多項式次的簽名詢問后,這個差異使得D能以不可忽略的概率區(qū)分χ(Qi,3)=0與χ(Qi,3)=1的2種分布。

令L表示D允許詢問簽名的最大次數(shù),則D的具體描述如下:

1)設(shè)置初始值c=0。

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

(1)隨機選擇一個身份IDi,一個消息mi和一個時戳Ti;

(2)向挑戰(zhàn)者B請求并獲得關(guān)于IDi、mi和Ti的簽名σi=(Qi,1,Qi,2,Qi,3);

(3)如果χ(Qi,3)=1,則設(shè)置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進行交互,則挑戰(zhàn)者B不能生成χ(Qi,3)=0或χ(di,2)=0的簽名。在G1中對于qE次的密鑰詢問有概率Pr[χ(di,2)=0]=qE/2,因此,在G1中:

定理2如果一個攻擊者A以不可忽略的概率偽造Huang方案的簽名,則存在一個多項式時間算法F也以不可忽略的概率偽造Huang方案的簽名,但挑戰(zhàn)者B無法利用算法F的偽造簽名求解G1上的CDH問題。

證明:對于A發(fā)起的密鑰和簽名詢問,F首先將相應(yīng)的詢問轉(zhuǎn)交給B,然后將B的回答作為響應(yīng)發(fā)送給A,如圖1所示。

圖1 詢問-響應(yīng)流程

令λ是Huang方案的安全參數(shù),F的具體操作描述如下:

1)F從挑戰(zhàn)者B獲得系統(tǒng)參數(shù)params,并轉(zhuǎn)發(fā)給攻擊者A。

2)F收到A請求的密鑰和簽名詢問后,首先將相應(yīng)的詢問轉(zhuǎn)發(fā)給挑戰(zhàn)者B,然后將B對詢問的回答作為響應(yīng)發(fā)送給A。

由于F只是進行A和B之間詢問與響應(yīng)的轉(zhuǎn)發(fā),因此在基于身份簽名方案的安全模型中,F是被允許的攻擊者。

因為從F的構(gòu)造過程可知,F是Huang方案的一個合法攻擊者,所以Huang方案的安全性并不能規(guī)約到CDH問題的困難性,從而使得Huang方案的安全性與CDH假設(shè)無關(guān)。這也表明Huang方案的安全性證明不滿足基于混合游戲證明方法的第2個條件。

綜合定理1和定理2很容易發(fā)現(xiàn),Huang方案的安全性證明存在嚴重的安全缺陷,無法從理論上證明Huang方案的安全性。

4 結(jié)束語

Huang等人設(shè)計了一個具有較短系統(tǒng)參數(shù)的基于身份簽名方案,并在標(biāo)準(zhǔn)模型中證明該方案是強不可偽造的。本文對該方案進行安全性分析,發(fā)現(xiàn)其安全性證明并不滿足基于混合游戲證明方法的2個條件,從而表明將Huang方案的安全性規(guī)約到CDH假設(shè)的結(jié)論是錯誤的。即存在一個多項式時間算法能區(qū)分Huang方案的真實游戲和模擬游戲,挑戰(zhàn)者無法利用攻擊者偽造的簽名求解CDH問題。Huang方案的安全性證明存在缺陷的主要原因是采用了安全性較低的Boneh和Boyen方案[14]。此外,Huang方案無法抵抗量子計算攻擊[15-16]。因此,如何構(gòu)造具有更短系統(tǒng)參數(shù)且抗量子計算攻擊的基于身份簽名方案,仍需要進一步研究。