一種抗替換攻擊的SM2簽名算法

嚴都力，薛李波，楊龑棟，劉 翼，延照耀

（1.延安大學 數學與計算機科學學院；2.延安大學 石油與環境工程學院，陜西 延安 716000）

SM2橢圓曲線公鑰密碼算法［1］是中國自主設計的公鑰密碼算法，具有存儲空間小、簽名速度快等優勢，被廣泛用于教育、社保、金融、交通、公共安全、國防工業等重要領域。相關研究成果表明，雖然中國自主設計的國產密碼是實現信息系統安全可控的核心保障，但在使用過程中也將遭受一系列不同動機的分析和攻擊［2］。

算法替換攻擊［3-4］的主要攻擊對象是密碼算法本身，攻擊者在密碼算法設計或實現過程中加入一些僅自己可知的秘密信息或陷門信息，即在密碼算法中設置陷門，用一個被嵌入陷門信息的算法來替換原誠實算法，攻擊者即可在用戶不知情的情況下竊取其密鑰信息［5-6］。替換攻擊最早起源于SIMMONS［7］提出的閾下信道，通信雙方借助密碼學技術構建隱藏通道，隱藏傳輸的秘密信息。隨后，YOUNG 等［8］對RSA 加密、Diffie-Hellman 密鑰交換、ElGamal 簽名等算法給出了具體的攻擊方法。2015年，BELLARE等［9］給出了替換攻擊的形式化定義和安全模型。DEGABRIELE 等［10］克服了BELLARE 安全模型中設置攻擊者替換攻擊能力限制的局限性，提出了適用范圍更廣泛的輸入觸發替換攻擊。LIU等［11］研究了可拆分的特殊簽名體制的替換攻擊，攻擊者所持有的秘密后門信息無需嵌入替換算法便可提取簽名私鑰。JOONSANG 等［12］研究了DSA［13］簽名算法的替換攻擊，并給出了具體的顛覆方法和抵抗用戶利用簽名時間分析檢測顛覆攻擊的對策。BELLARE等［14］提出了參數顛覆的概念，并分析了非交互式零知識證明協議在公共參考串模型下遭受替換攻擊的安全性。DODIS 等［15］和DEGABRIELE 等［16］基于參數顛覆研究了偽隨機數生成器的替換攻擊問題。黃欣沂等［2］以中國商用密碼SM2的數字簽名算法和公鑰加密算法為分析對象，提出兩種高效難檢測的密鑰滲漏攻擊。此外，國內外學者圍繞對稱加密、數字簽名、密鑰協商協議和零知識證明系統等不同密碼算法深入的開展了后門攻擊評估［17］。

隨著各種替換攻擊事件的不斷曝光，如何構造抵抗替換攻擊的密碼算法，已經成為密碼學界備受關注的一個熱點問題。目前已有相關研究學者提出了一些替換攻擊的方法，BELLARE等［18］和ATENIESE等［19］分別設計了唯一密文和唯一簽名方案的防御措施來抵制替換攻擊。RUSSELL 等［20］基于檢測安全思想提出了直接檢測并抵制算法替換攻擊的看門狗（Watchdog）安全模型。RUSSELL 等［21］基于分割融合技術，提出了一種對隨機化密碼算法的替換攻擊防范方法。MIRONOV等［22］提出了一種功能保留、安全保留、抗泄漏的密碼逆向防火墻（Cryptographic reverse firewall，CRF）來抵御顛覆攻擊。FISCHLIN等［23］提出了區別于CRF 與Watchdog 防御機制的自防御方法，同時為隨機化單鑰加密體制和具有同態性質的公鑰加密體制設計了相應的安全防護方法?？挡綐s等［24］提出了抵抗隨機數后門攻擊的密碼算法，并對已有的抗隨機數后門攻擊密碼算法進行了總結和梳理。中國自主設計的國產商用密碼是實現信息系統安全可控的核心保障，雖然文獻［2］提出了針對SM2 簽名算法的秘鑰滲透攻擊，但尚未給出具體抗替換攻擊方案?；谖墨I［2］，在一般群模型下，本文設計了一種抗替換攻擊的SM2 簽名算法，主要研究內容如下：

1）刻畫了針對簽名算法的替換攻擊模型，攻擊者利用這一攻擊方法能夠達到秘鑰提取和不可檢測性兩種安全目標；

2）利用哈希函數將簽名私鑰、簽名消息與其隨機數的哈希結果作為簽名的隨機組件，對原始的SM2 簽名算法改進，在一般群模型下，構造具備抗替換攻擊的SM2 簽名方案，即使攻擊者替換原始SM2 簽名算法某些組件得到有效簽名，也無法獲得簽名私鑰的任何信息；

3）將抗替換攻擊的SM2 簽名算法與原始SM2簽名算法進行效率測試，實驗結果驗證了抗替換攻擊的SM2簽名算法的可行性。

1 預備知識

1.1 哈希函數

定義1［25］一個安全的密碼學哈希函數h：{0，1}*→{0，1}n，滿足以下性質：

1）抗碰撞性：找到2 個不同輸入M與M′，滿足h(M)=h(M′)在計算上是不可行的；

2）抗原像性：給定y=h(M)，對于概率多項式時間敵手找到一個M′，使得h(M′)=y在計算上不可行；

3）抗第二原像性：給定輸入M，對于概率多項式時間敵手找到一個M′(M′≠M)，使得h(M′)=h(M)在計算上是不可行的。

1.2 偽隨機函數

定義2［26］函數F：{0，1}λ×{0，1}ρ→{0，1}n記作一個有效的帶密鑰函數，函數表示所有f：{0，1}ρ→{0，1}n函數的集合。如果對所有概率多項式時間區分器D，存在一個可忽略的函數ε(λ)，滿足：

則稱F是一個偽隨機函數（Pseudorandom function，PRF）。區分器D、區分函數F與f優勢定義為

1.3 SM2簽名算法

SM2 簽名算法是基于橢圓曲線的公鑰密碼算法，SM2 包含加解密算法、數字簽名算法和密鑰交換協議。定義SM2=(KeyGenSM2，SignSM2，VeyifySM2)為原始的簽名方案。選擇一個256 位素數域E(Fq)上的橢圓曲線，其參數定義為pp={q，Fq，a，b，G，n，Hv，f，ZA}，其中p為Fp特征，參數a，b∈Fp確定了安全的橢圓曲線E(Fp)：y2=x3+ax+b，任意選取基點G=(xG，yG)，其中G≠O，O表示橢圓曲線上的無窮遠點，素數n表示基點G的階；h：{0，1}*→Zn表示哈希函數，Hv：{0，1}*→{0，1}256表示消息長度為vbit 的哈希函數，在SM2 簽名算法中v取值為256；f：→Zn表示將橢圓曲線上的坐標點轉化為整數；ZA=Hv(ENTL||ID||a||b||xG||yG||xP||yP)表示簽名身份標識與系統參數的哈希值，ENTL由2個字節標識的ID的bit 長度，ID為用戶身份標識，xG、yG為基點，xP、yP為用戶的公鑰。SM2簽名算法描述如下：

1）秘鑰生成算法（KeyGenSM2）

①簽名者任意選取整數d，其中1 ≤d≤n；

② 計算P=dG=(xP，yP)，P表示簽名公鑰，d表示簽名私鑰。

2）簽名算法（SignSM2）

② 計算e=h()；

③任意選取隨機數k∈[1，n-1]，計算kG=(x1，y1)；

④ 計算x1=f(kG)；

⑤ 計算簽名r=(e+x1)modn，若r=0 或r+k=n，則重新選擇隨機數k；

⑥ 計算簽名s=(1+d)-1?(k-rd)modn，若s=0，則重新選擇隨機數k；

⑦ 輸出消息M的簽名σ=(r，s)。

3）驗證算法（VerifySM2）

①驗證者收到任意消息M的簽名σ=(r，s)，利用系統參數和簽名公鑰對簽名σ=(r，s)驗證是否有效；

② 驗 證r∈[1，n-1]和s∈[1，n-1]是否成立，若不成立，則驗證不通過；

④ 計算e=h()；

⑤ 計算t=(r+s)modn，若t=0，則驗證不通過；

1.4 一般群模型

一般群模型［27］是一種理想的安全模型。在該模型中，敵手只能訪問一個群中經過隨機編碼后的元素，而非實際的元素，系統外部用戶即使知道群中的元素也必須訪問群預言機，預言機模擬群運算。預言機以2 個經過隨機編碼的元素作為輸入，輸出則是第三個經過隨機編碼的元素。與隨機預言機模型類似，敵手自身不能進行群運算，必須以經過隨機編碼的元素向預言機查詢，以獲得經過隨機編碼的運算結果。

定義3［27］假設存在兩個同構群G1、G2，在一般群模型中，設ζ是一個編碼函數，一個預言機O 模擬群G1上的運算，即：給定兩個元素∈G1和兩個整數e1和e2，O計算F3=e1F1+e2F2，并返回

2 替換攻擊模型

替換攻擊指攻擊者在密碼算法設計或實現過程中時設置一些僅自己可知的陷門信息，用一個被嵌入陷門信息的算法來替換原始誠實算法，攻擊者即可在用戶不知情的情況下竊取其密鑰信息，替換攻擊的形式化定義如下。

定義4［5］SS=(KeyGen，Sign，Verify)記為原始簽名方案，攻擊者通過某種手段破壞SS，得到替換后的簽名方案具體算法描述如下：

替換后的簽名方案需滿足正確性要求，即

替換簽名方案除滿足正確性要求外，還需同時滿足“密鑰提取”和“不可檢測性”。其定義如下：

密鑰提?。↘eyExtract）：正常情況下，攻擊者從原始簽名中分析獲得簽名私鑰是計算上不可行的。假設存在攻擊者A 可通過在簽名方案中嵌入陷門信息，提取簽名私鑰或簽名中其他秘密信息，A首先需要對原始簽名進行替換獲得有效的替換簽名，然后利用若干個替換后的簽名與替換密鑰提取簽名私鑰，這類攻擊是當前最為普遍的替換攻擊方式，又被稱顛覆攻擊。其形式化定義如下：

定義5［5］SS=(KeyGen，Sign，Verify)記為原始簽名方案記作被嵌入陷門信息替換后的簽名方案，A 為概率多項式時間敵手，C 定義為挑戰者，A 提取密鑰游戲定義為

1）初始化：C 執行KeyGen(1λ)與算法，生成正常簽名密鑰對(pk，sk)和替換密鑰subk，C將公鑰pk發送給A；

2）簽名詢問：A 任意選擇消息mi進行簽名詢問，C將mi的簽名應答給A；

A 成功提取密鑰的優勢定義為安全參數λ的函數：

不可檢測性（detect）：該安全目標從敵手A的視角定義，一般情況下擁有簽名私鑰的用戶對檢測替換簽名更加感興趣，即在不可檢測性定義中，用戶被賦予擁有簽名私鑰能力的檢測者來檢測簽名。對于沒有替換密鑰的用戶，他們無法檢測簽名是正常簽名算法還是替換后的簽名算法生成的簽名。用戶與挑戰者之間刻畫檢測替換簽名的游戲定義為

1）初始化：挑戰者C 執行KeyGen(1λ) 和算法生成原始簽名密鑰對(pk，sk)和替換密鑰subk，C將公鑰pk發送給D；

2）訓練：D詢問C關于消息mi的簽名，C將對應的簽名σi返回給D；

3）挑戰：D輸入消息mi，C選擇b∈{0，1}，若b=0，C執行σi=Sign(sk，mi)，得到簽名σi作為應答，否則，C執行將作為應答；

4）猜測：D 輸出一個b′，如果b′=b，D 檢測替換簽名成功。

3 抗替換攻擊的SM2簽名算法

根據文獻［2］對SM2 簽名算法的替換攻擊，攻擊者在攻擊前，運行密鑰生成算法生成替換密鑰subk，然后借助密碼雜湊函數Fκ計算隨機數ki。被篡改后SM2簽名算法與原始SM2簽名算法區別在于隨機數k的選擇，ki為第i次運行被篡改SM2 簽名算法所使用的隨機數，該攻擊方法最終達到秘鑰提取和不可檢測性安全目標，詳細攻擊方案及安全性分析見文獻［2］。

為了抵抗攻擊者對SM2 簽名算法的替換攻擊，對SM2 簽名算法進行改進，借助哈希函數和簽名私鑰計算簽名中輔助隨機數α=h(d||M||k)，其中，d是簽名私鑰，M是簽名消息，k為隨機數。針對不同簽名消息m計算得到不同的α，且α只能被簽名者計算，然后將α作為簽名組件應用于生成簽名。簽名中輔助隨機數α的計算與簽名消息M、簽名私鑰d綁定目的為了保證α值的唯一性。由于改進后的SM2簽名方案中使用的輔助隨機數α由特定方法計算，即使攻擊者嘗試通過替換k達到攻擊目的，簽名者也可以通過計算和判斷α來確定是否繼續執行簽名算法。若簽名者計算α=h(d||M||k)，則繼續執行簽名算法；否則，終止。此判斷過程保證了簽名算法中使用的隨機數α的正確有效性，抗替換的SM2簽名方案描述如下。

1）密鑰生成算法（KeyGenSM2）

①簽名者任意選取整數d，其中，1 ≤d≤n；

② 計算P=dG，P表示簽名公鑰，d表示簽名私鑰。

2）簽名算法（SignSM2）

② 計算e=h()；

③ 任意選取隨機數k∈[1，n-1]，計算α=h(d||M||k)；

④ 計算αG=(x1，y1)；

⑤ 計算x1=f(αG)；

⑥ 計算簽名r=(e+x1)modn，若r=0 或r+k=n，則重新選擇隨機數k；

⑦ 計算簽名s=(1+d)-1?(α-rd)modn，若s=0，則重新選擇隨機數k；

⑧ 輸出消息M的簽名σ=(r，s)。

3）驗證算法（VerifySM2）

①驗證者收到任意消息M的簽名σ=(r，s)，利用系統參數和簽名公鑰對簽名σ=(r，s)驗證是否有效；

② 驗 證r∈[1，n-1]和s∈[1，n-1]是否成立，若不成立，則驗證不通過；

④ 計算e=h()；

⑤ 計 算t=(r+s)modn，若t=0，則驗證不通過；

⑦ 計算x1′=f(sG+tP)；

4 安全性分析

4.1 正確性分析

由s=(1+d)-1?(α-rd)modn、t=(r+s)modn和P=dG得

4.2 抗替換攻擊性

定理1假設攻擊者A 在概率多項式時間qt內，經過qs次簽名詢問得到兩個連續有效的抗替換攻擊SM2 簽名，A 利用密鑰提取的方法提取出私鑰d的概率是可忽略的。

證明若攻擊者A獲得任意兩個連續消息Mi-1和Mi的替換攻擊SM2簽名，分別為和，A按照秘鑰提取方法提取簽名私鑰：

①計算ki=Fκ([ri]G)；

②計算αi=h(d||Mi||ki)；

③依據等式si=(1+d)-1?(αi-rid)modn；

⑤ 判斷d′=d是否成立。

上述步驟②等式中，因αi=h(d||Mi||ki)中d是簽名私鑰A 未知，A 無法計算出αi，即使A 已知其他簽名組件信息，也無法繼續計算得到d′，更無法判斷d′=d是否成立，所以A 提取私鑰d失敗。此外，即使可以替換每個抗替換攻擊SM2 簽名中使用的隨機數ki，當A獲取x個有效簽名，其中x≤qs：

根據以上方程式，敵手A 已知簽名Mi、ri、si和ki，但A 仍然無法在概率多項式時間內計算簽名中的αi，x個方程等式中有x+1個未知數，A 無法通過已知簽名信息提取出簽名私鑰d。

綜上得證，攻擊者A 利用密鑰提取的方法提取簽名密鑰d的概率是可忽略的，證畢。

4.3 存在性不可偽造

定理2若h是均勻一致且抗碰撞的哈希函數，f是幾乎可逆的函數，則抗替換攻擊的SM2 簽名方案在一般群模型下是滿足自適應選擇消息攻擊下存在性不可偽造。

證明假設攻擊者A 不能直接訪問雙線性群的元素，而只能通過與預言機O 交互獲得群元素的隨機映射的像，群運算由預言機O 執行，攻擊者可以通過訪問預言機O 獲得新的群元素。敵手可以從公鑰或者簽名預言機查詢中獲取群元素句柄。實際上，A 可以使用公鑰中的句柄和簽名作為“基礎”來執行進一步的群操作。

令(G，P)是公鑰中的群元素句柄是簽名查詢中創建的群元素句柄，qs表示簽名查詢詢問的次數，根據假設A 想要計算的所有群元素都有一個表單其中，是A 隨機選擇的已知整數，因此，可以通過以下方式統一群操作查詢系數向量(z1，z2，…，例如，將基本元素G乘以整數z可以表示為一個群操作查詢(z，0，…，0)。

假設存在一個概率多項式敵手A，存在挑戰者C模擬A 的攻擊環境，使A 的優勢可以忽略不計。為了回答A 的群操作查詢，挑戰者C 將用一個L來記錄群查詢操作中生成的信息。挑戰者C首先選擇基點G，將(1，G，-，-)添加到列表L中，然后隨機選擇一個整數d∈Zn，計算P=dG，將(d，P，-，-)添加至L列表中，設qs表示敵手A 進行簽名詢問的次數，qc表示C 與A 交互過程中當前進行簽名查詢的次數作為將在簽名查詢中生成的群元素處理。C 與A 交互過程中群操作查詢和簽名查詢的回答如下：

①令j為最大索引且zj≠0；

② 若j>qc+2，返回⊥退出；

③對于每一個i∈{1，2，…，j}，從(αi，Vi，-，-)列表中取αi計算z′=z1+z2d+z3α1+…+zjαjmodn；

④ 如果存在(z′，V′，-，-)在列表L中，挑戰者C返回V′給A，否則，分為以下兩種情形：

情形1 如果z2=0，任意選擇V′，將(z′，V′，(z1，添加至列表L，將V′返回給A；

情形2 如果z2≠0，任意選擇Z′∈{0，1}256，M′∈M3，計算h(Z′||M′))，然后將添加至列表L中，然后返回V′給A。

2）對于某些消息M的簽名詢問，挑戰者C任意選取k∈Zn，計算α=h(d||M||k)；然后，進行群操作查詢(α，0，…，0)獲取V，計算x=f(V)，r=h(Z||M) +xmodn，s=(α-rd)/(1+d)modn，其中，Z為SM2簽名算法中已知確定的信息；最后，挑戰者C返回簽名(r，s)作為A的詢問應答。

假設哈希函數h是均勻分布且抗碰撞的，敵手A 通過上述詢問，對于任意一個消息偽造出消息M*的簽名(r*，s*)的概率是可忽略的，下面進行具體分析：

挑戰者C 誠實地生成了公鑰和簽名，如果C 能夠完美地回答群操作查詢，那么說明C 幾乎能夠為敵手A 模擬一個完美的攻擊環境。實際上，除了群操作查詢的情形2 之外，所有的群元素句柄都是隨機統一選擇的?，F在，假設情形2 中生成的V′=也是均勻分布的，事實上，Z′和M′是隨機均勻選擇的，且h是均勻哈希函數，則情形2 中f-1的輸入是均勻分布的。根據f-1幾乎可逆的事實，有V′是均勻分布的。另外，根據Schwartz-Zippel 引理［28］，在列表L中存在兩個分量(z′，V′，-，-) 和(z′′，V′′，-，-)，其中，z′≠z″但V′≠V″，其概率是可忽略的，qG表示敵手A執行的群操作查詢總數。

為了繼續完成上述證明，只需要證明(r*，s*)在M*上有效簽名的概率是可以忽略的。令α*=s*+(s*+r*)d，(r*，s*)是消息M*上有效的簽名，當且僅當(α*，V*，-，-) 出現在列表L中，其中V*=f-1(r*-h(Z||M*))。若要證明(r*，s*)在M*上的有效簽名概率是可以忽略不計的，就等價于證明(α*，V*，-，-)出現在表L中的概率是可忽略的。此處聲明，V*?{G，P}，否則，敵手A 可以通過使用s*≠0和s*+r*≠0確定地從(r*，s*)中計算d，此處與d對敵手A 完全隱藏的事實相矛盾。換句話說，V*只能在群操作查詢或簽名查詢時創建。有以下兩種情形：

情形1（V*在簽名查詢中被創建）：如果V*∈{V1，V2，…}，對于某個i設置V*=Vi，并設置(ri，si)為第i個簽名查詢消息Mi和輔助信息Zi的簽名。換句話說，存在s*+(s*+r*)d=si+(si+ri)d，由于私鑰d對敵手是完全隱藏的，所有只有當s*=si和s*+r*=si+ri同時保持一致才成立，這種情況才會發生且概率不可忽略。在這種情況下，(r*，s*)是M*上的有效簽名，當且僅當方程h(Zi||Mi)=rf(V*)=h(Z||M*)保持成立。然而M*≠Mi，以上意味著敵手A 必須找到一個碰撞(Zi||Mi，Z||M*)，然而哈希函數h是抗碰撞的，所以以上情況只會以忽略不計的概率發生。

綜上，在哈希函數h是抗碰撞的假設下，簽名(r*，s*)是M*上有效簽名的概率是可以忽略的，證畢。

5 性能分析

5.1 計算復雜度分析

下面針對抗替換攻擊的SM2 簽名算法的模乘、模逆及點積運算進行分析，一次模逆運算約等于算法執行9 次點積運算。本文采用[mc]、[mn]和[dj]分別表示模乘、模逆與點積運算，設一次模乘運算的數據規模為n，則一次模乘、模逆與點積運算的復雜度分別為O(n2log2n)、O(9n2)和O(n2)，其中[mn]=9[dj]。T1、T2分別表示SM2 簽名算法與抗替換攻擊的SM2 簽名算法的總運算量，兩種簽名方案的運算量比較如表1所示。

表1 SM2簽名算法與抗替換攻擊的SM2簽名算法運算量比較

表1 中T1=O[(2 log2n+13)n2]，T2=O[(2 log2n+13)n2]，抗替換攻擊SM2 簽名算法的計算復雜度等于SM2簽名算法的計算復雜度。

5.2 算法執行效率分析

下面分別對SM2 簽名算法和抗替換攻擊的SM2 簽名算法的效率進行測試，并對每個算法執行10 000 次，求其效率平均值。實驗環境為Inter（R）Core（TM）惠普i5-7400CPU@3.00 GHz 處理器、Ubuntu16.0.4 LTS，64位操作系統，內存容量為6.00 GB的臺式機，編譯環境采用JetBrains PyCharm 2019.2.3版本，編譯語言采用python 3.6.5編譯程序。兩種簽名方案的密鑰生成、簽名及驗證算法執行效率分別作對比如圖1所示。

圖1 兩種簽名算法執行效率對比圖

根據圖1 分析，SM2 簽名方案與本文提出的抗替換攻擊SM2 簽名算法在密鑰生成算法、驗證算法執行效率相同。由于抗替換攻擊SM2 簽名方案在計算簽名時引入了哈希函數計算輔助隨機數耗時的原因，簽名算法耗時比原始SM2 簽名算法耗時長0.023 ms。綜上，在簽名長度相同的情況下，抗替換攻擊的SM2 簽名算法執行效率與原始SM2 簽名算法的執行效率基本一致，而且還具備了抗替換攻擊性。

6 結論

本文首先簡要回顧了SM2 簽名算法遭受的替換攻擊；然后利用哈希函數將簽名私鑰、簽名消息與其簽名選擇的隨機數的哈希結果作為簽名的隨機組件，對原始的SM2 簽名算法改進，構造了具備抗替換攻擊的SM2 簽名方案，并在一般群模型下證明了方案的安全性；最后，對提出的抗替換攻擊SM2 算法與已有算法進行了效率測試，實驗結果證明了提出的算法在計算復雜度與算法執行效率方面與已有算法基本一致。該簽名算法的研究不僅有效的抵御了替換攻擊帶來的安全威脅，而且豐富了國產密碼體系。