對(duì)短公鑰的基于身份數(shù)字簽名算法的安全性攻擊*

鄭 紅， 范 佳

(1.四川九洲空管科技有限責(zé)任公司，四川 綿陽(yáng) 621000;2.保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041)

0 引言

1984年Shamir[1]提出了基于身份的密碼體制。在該體制下，用戶的公鑰是用戶的身份信息，如email地址、身份證號(hào)碼和員工工號(hào)等;并且用戶的私鑰是由一個(gè)可信的第三方，稱為私鑰生成中心(private key generator，PKG)的機(jī)構(gòu)來(lái)產(chǎn)生。因?yàn)榛谏矸莸拿艽a系統(tǒng)不需要使用數(shù)字證書，因此可以避免傳統(tǒng)的公鑰密碼系統(tǒng)(基于PKI的公鑰密碼系統(tǒng))建立和管理公鑰基礎(chǔ)設(shè)施的代價(jià)。

2001年，Boneh，Shacham和Lynn(BSL)提出了基于雙線性對(duì)的數(shù)字簽名[2]。雙線性對(duì)運(yùn)算使得BSL方案不僅簽名非常短，而且構(gòu)造簡(jiǎn)單，驗(yàn)證也非常方便。但是BSL簽名方案只能在隨機(jī)預(yù)言機(jī)模型下提供可證安全分析。2006年，Paterson和Schuldt(PS)同樣基于雙線性對(duì)，構(gòu)造了第一個(gè)可以在標(biāo)準(zhǔn)模型下證明安全的基于身份數(shù)字簽名算法(簡(jiǎn)稱為PS算法)[3]。PS算法是Waters簽名算法[4]的擴(kuò)展，直接使用了兩次獨(dú)立的Waters身份處理函數(shù)，所以其效率并不高。最近幾年密碼學(xué)者們一直在為提高這個(gè)算法而努力。2009年李繼國(guó)等[5]提出一個(gè)對(duì)PS數(shù)字簽名算法的一個(gè)改進(jìn)方案。改進(jìn)后的方案在計(jì)算效率上有所提高，主要體現(xiàn)在驗(yàn)證簽名時(shí)，改進(jìn)算法的計(jì)算量比PS算法減小了三分之一。2011年王之怡等人[6]對(duì)李繼國(guó)等的算法進(jìn)一步進(jìn)行改進(jìn)，提出了一種短公鑰的基于身份的數(shù)字簽名方案，該方案聲稱其通過(guò)改進(jìn)參數(shù)選擇，從而大大減少了公鑰參數(shù)數(shù)量。2013年黃斌和鄧小鴻[7]對(duì)李繼國(guó)等設(shè)計(jì)的方案[5]成功進(jìn)行了攻擊，使得攻擊者能夠構(gòu)造任意ID的用戶私鑰。

本文將對(duì)王之怡等人提出的短公鑰的基于身份數(shù)字簽名算法進(jìn)行安全性攻擊。

1 簽名算法回顧

王之怡等人設(shè)計(jì)的短公鑰的基于身份的數(shù)字簽名算法共包含如下四個(gè)算法，算法描述如下:

(2)私鑰提取DerMSK(ID):TA隨機(jī)選擇r∈Zp，計(jì)算身份為ID的用戶私鑰為:

(3)簽名SMPK(dID，M):身份為ID的簽名者首先進(jìn)行一個(gè)隨機(jī)化處理得到

緊接著，身份為ID的簽名者隨機(jī)選擇t∈Zp，生成對(duì)消息M的簽名 σ ={σ0，σ1，σ2}為:

(4)驗(yàn)證 VID(M，σ):令(M，σ0，σ1，σ2)為收到的簽名，驗(yàn)證者驗(yàn)證等式:

若該等式成立，則簽名合法，否則為非法簽名。

2 對(duì)該簽名算法的攻擊

該算法的設(shè)計(jì)者宣稱該算法滿足以下安全性:令H1，H2，H3，H4是抗碰撞Hash函數(shù)，假設(shè)在雙線性映射群中計(jì)算Diffie-Hellman(CDH)數(shù)學(xué)難題成立，那么該算法是能抗適應(yīng)性選擇消息偽造簽名攻擊(UCMA)的。

UCMA安全性定義如下的攻擊游戲來(lái)描述。該攻擊游戲由一個(gè)挑戰(zhàn)者和一個(gè)攻擊者來(lái)完成。該游戲包含如下三個(gè)階段:

第一階段:挑戰(zhàn)者運(yùn)行Setup(1k)獲得主公私鑰對(duì)(MPK，MSK)，并將主公鑰MPK發(fā)送給攻擊者;

第二階段:攻擊者適應(yīng)性地進(jìn)行以下兩種詢問(wèn)。

(1)私鑰提取詢問(wèn):攻擊者提交身份ID給挑戰(zhàn)者，挑戰(zhàn)者使用主私鑰計(jì)算dID=DerMSK(ID)，并將進(jìn)行應(yīng)答;

(2)簽名詢問(wèn):攻擊者適應(yīng)性地選取身份和消息{ID，M}進(jìn)行簽名詢問(wèn)，挑戰(zhàn)者首先生成身份對(duì)應(yīng)的私鑰dID=DerMSK(ID)，進(jìn)一步使用dID生成簽名，最后返回簽名結(jié)果;

第三階段:攻擊者輸出{σ*，M*，ID*}，要求攻擊者未詢問(wèn)過(guò)身份ID*的私鑰且未詢問(wèn)過(guò){M*，ID*}的簽名，如果攻擊者輸出的簽名能通過(guò)驗(yàn)證，那么攻擊者攻擊成功。

UCMA安全性定義:如果任何概率多項(xiàng)式時(shí)間攻擊者在以上游戲中攻擊成功的優(yōu)勢(shì)∈(其中∈=|Pr[攻擊者攻擊成功]-1/2|)可以忽略，則稱一個(gè)基于身份簽名算法是UCMA安全的。

以下將通過(guò)兩種攻擊說(shuō)明該算法并不滿足以上的UCMA安全性。

攻擊1:具體的攻擊步驟如下:

(1)在 H2中尋找碰撞(ID1，ID2)滿足 ID1≠ID2，H2(ID1)=H2(ID2):注意到在算法中描述時(shí)只提到H2:{0，1}*→Zk1，并沒(méi)有明確k1的大小。在后面的安全性證明的過(guò)程中才確定k1=1+qE，(其中qE為攻擊者在攻擊游戲中進(jìn)行簽名詢問(wèn)的次數(shù)，qE=230)。目前一臺(tái)普通的單機(jī)(2.93G雙核CPU，4G內(nèi)存)運(yùn)行一次SHA-1的時(shí)間大約為2-22秒，運(yùn)行230+2次運(yùn)算的時(shí)間為128秒。假設(shè)H2運(yùn)行時(shí)間與SHA-1時(shí)間相當(dāng)，在H2中找到一個(gè)碰撞的時(shí)間至多為128秒(由于k1=230+1，運(yùn)行230+2次H2，必然會(huì)找到一個(gè)碰撞)。

(2)攻擊者通過(guò)私鑰詢問(wèn)獲得ID1的私鑰:

可以很容易地驗(yàn)證

(4)由于此時(shí)攻擊者已經(jīng)掌握了身份為ID2的用戶的合法私鑰，因此可以偽造該用戶的所有簽名。

攻擊2:具體的攻擊步驟如下:

攻擊者通過(guò)找尋H4的碰撞((M1)，(M2))滿足M1≠M(fèi)2，H4(M1)=H4(M2)。通過(guò)詢問(wèn)某個(gè)ID對(duì)消息M1的簽名，可以構(gòu)造該ID對(duì)于M2的簽名。

3 結(jié)語(yǔ)

本文對(duì)一個(gè)具有短公鑰特征的基于身份的數(shù)字簽名算法進(jìn)行了安全性分析，發(fā)現(xiàn)其并不滿足其所

聲稱的安全性——抗適應(yīng)性選擇消息偽造簽名攻擊。本文的第一種公鑰針對(duì)用戶私鑰。在該種攻擊下，攻擊者如果獲得某個(gè)用戶私鑰，則他可以計(jì)算系統(tǒng)內(nèi)所有其他用戶的合法私鑰。本文的第二種攻擊針對(duì)簽名偽造。在該種攻擊下，攻擊者如果獲得了某個(gè)用戶的一個(gè)合法簽名，則他可以偽造該用戶對(duì)任意其他消息的合法簽名。

[1] Shamir A.Identity-based Crypto Systems and Signature Schemes[C]//Advances in Cryptology-Crypto'84.Berlin:Springer-Verlag，1984:47-53.

[2] Boneh D，Shacham H and Lynn B.Short Signatures from the Weil Pairing[J].J.of Cryptology，2004，17(4):297-319.

[3] Paterson K，Schuldt J.Efficient Identity-based Signatures Security in Standard Model[C]//Advances in Cryptology Proceedings of ACISP 2006.Berlin:Springer-Verlag，2006:207-222.

[4] Waters B.Efficient Identity-based Encryption Without Random Oracles[C]//Proc.of Eurocrypt'05，Berlin:Springer-Verlag，2005:114-127.

[5] 李繼國(guó)，姜平進(jìn).標(biāo)準(zhǔn)模型下可證安全的基于身份的高效簽名方案[J].計(jì)算機(jī)學(xué)報(bào)，2009，32(11):2130-2136.

[6] 王之怡，劉鐵，康立等.短公鑰的可證明安全基于身份數(shù)字簽名算法[J].計(jì)算機(jī)科學(xué)，2011，38(3):136-139.

[7] 黃斌，鄧小鴻.高效的基于身份簽名方案的安全性分析[J].計(jì)算機(jī)應(yīng)用，2013，33(1):168-170.