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

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

(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]。因此,如何構造具有更短系統參數且抗量子計算攻擊的基于身份簽名方案,仍需要進一步研究。