黃欣沂, 陳榮茂, 王 毅, 邢倩倩
1. 福建師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院, 福州350117
2. 福建師范大學(xué) 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室, 福州350117
3. 國防科技大學(xué) 計(jì)算機(jī)學(xué)院, 長沙410073
可證明安全理論為現(xiàn)代密碼學(xué)提供了嚴(yán)謹(jǐn)?shù)陌踩苑治龇椒? 主要思想是基于計(jì)算復(fù)雜性理論, 將敵手攻擊密碼算法的過程與破解公認(rèn)困難性數(shù)學(xué)問題建立近似等價(jià)聯(lián)系, 證明密碼算法的安全性. 可證明安全已被廣泛用于密碼算法的設(shè)計(jì)與安全性分析, 為促進(jìn)密碼技術(shù)在現(xiàn)實(shí)生活中的應(yīng)用提供了理論上的安全保障. 然而, 越來越多的安全事件表明, 理論上已被證明安全的密碼算法在實(shí)際應(yīng)用中仍然可能失效. 這是因?yàn)榭勺C明安全主要針對密碼算法的規(guī)范(specification) 進(jìn)行理論分析, 而密碼算法在實(shí)際部署(implementation)應(yīng)用時(shí)因?yàn)楦鞣N原因可能沒有嚴(yán)格遵守相應(yīng)的規(guī)范,導(dǎo)致算法的安全性無法達(dá)到理論上已證明的安全級別, 甚至遭到徹底破壞.
2013 年著名的“斯諾登事件” 披露, 以美國國家安全局為代表的安全機(jī)構(gòu)為了能夠?qū)ヂ?lián)網(wǎng)用戶實(shí)施大規(guī)模監(jiān)聽, 控制密碼算法標(biāo)準(zhǔn)的制定, 篡改密碼產(chǎn)品中相關(guān)算法的軟硬件部署, 通過植入密碼后門獲取用戶私鑰, 破壞用戶的通訊隱私[1,2]. 因?yàn)槊艽a后門設(shè)計(jì)巧妙, 具有極強(qiáng)的隱蔽性, 所以直到“斯諾登事件”所披露的相關(guān)文檔公開之后才被公眾所知. “斯諾登事件” 在國際密碼學(xué)界迅速引起廣泛關(guān)注, 研究人員開始從技術(shù)層面研究美國政府大規(guī)模監(jiān)聽背后的技術(shù)手段, 逐漸形成以研究密碼算法后門嵌入形式、工作原理和防范技術(shù)為核心的“后斯諾登密碼學(xué)”[3].
在2014 年的美密會上, Bellare 等提出“算法替代攻擊” (algorithm substitution attack, ASA)[4],用于刻畫對稱加密算法在實(shí)際部署時(shí)被篡改導(dǎo)致密鑰滲漏的一種特殊攻擊方法. 該種攻擊假設(shè)敵手可以控制加密算法的實(shí)際部署, 在算法中植入特定的后門, 使得算法在保持原有加密功能的情況下, 將用戶密鑰信息嵌入到可以正常解密的密文中. 攻擊者在捕獲到密文之后, 就可以利用后門信息從密文中分析還原用戶密鑰信息, 從而解密密文得到明文信息. 這種攻擊的雛形最早可以追溯到上世紀(jì)90 年代由Young 等提出的“盜碼學(xué)” (kleptography) 概念[5–7]. 該攻擊技術(shù)主要考慮在黑盒密碼體制中秘密嵌入后門(secretly embedded trapdoor with universal protection, SETUP) 破壞密碼算法安全性的情況. 與Bellare 等提出的ASA 攻擊不同, SETUP 攻擊主要考慮的是非對稱方式嵌入的后門, 即被嵌入后門與攻擊者還原密鑰所用的后門信息是公私鑰的關(guān)系. 從攻擊者的角度來講, 這種攻擊方式可以更好地保持攻擊專有性(exclusivity), 即使內(nèi)嵌的后門信息被發(fā)現(xiàn), 也無法攻擊其他被嵌入相同后門的密碼系統(tǒng).
在Bellare 等的工作之后,國內(nèi)外學(xué)者圍繞對稱加密[8,9]、數(shù)字簽名[10–12]、格上公鑰加密[13]、消息驗(yàn)證碼[14]等不同密碼算法開展了深入的后門攻擊評估. 本文將在1.3 節(jié)對這些工作進(jìn)行總結(jié)闡述. 雖然這些攻擊在具體的定義上不完全相同, 但都是通過篡改算法部署, 將密鑰信息嵌入算法的輸出中, 達(dá)到密鑰滲漏的目的. 因此, 為了后面敘述的一致性, 本文將這類攻擊統(tǒng)一稱之為“密鑰滲漏攻擊” (key exfiltration attack, KEA). KEA 也可以用于隱蔽傳輸其他秘密信息, 比如加密的明文和加密過程產(chǎn)生的隨機(jī)數(shù)等敏感信息. 這一點(diǎn)和以實(shí)現(xiàn)隱蔽傳輸為目標(biāo)的隱寫術(shù)(steganography) 是類似的. 文獻(xiàn)[15] 已經(jīng)從理論上嚴(yán)
謹(jǐn)論證了該種攻擊和傳統(tǒng)隱寫術(shù)之間存在近似等價(jià)的相互轉(zhuǎn)換關(guān)系, 即對于輸出具有一定最小熵值的加密算法, 存在和算法內(nèi)部運(yùn)行細(xì)節(jié)無關(guān)的通用后門攻擊.
我國自主設(shè)計(jì)的國產(chǎn)商用密碼是實(shí)現(xiàn)信息系統(tǒng)安全可控的核心保障, 在使用過程中也將遭受一系列不同動機(jī)的安全分析和惡意攻擊. 由于國產(chǎn)商用密碼在設(shè)計(jì)之初沒有考慮密鑰滲漏攻擊, 目前也未見公開發(fā)表的針對國產(chǎn)商用密碼的密鑰滲漏攻擊分析(下面簡稱KEA), 所以本文重點(diǎn)評估國產(chǎn)商用密碼SM2 數(shù)字簽名算法和公鑰加密算法面臨的KEA 威脅, 并提出相應(yīng)的防范技術(shù). 雖然Bellare 等提出的“偏密文攻擊”(biased-ciphertext attack)[4]和Ateniese 等提出的“偏隨機(jī)數(shù)攻擊”(biased randomness attack)[10]具有通用性, 也同樣適用于SM2 算法, 但這些KEA 攻擊方式有兩個(gè)不足:
(1) 采取“逐比特滲漏” 方式進(jìn)行密鑰滲漏. 該方式具有很強(qiáng)的通用性, 但滲漏效率比較低. 其核心思路是通過“拒絕采樣” (rejection sampling) 的方式生成隨機(jī)數(shù), 直到算法的輸出滿足預(yù)設(shè)的條件(如在某個(gè)特定函數(shù)下表示某一比特密鑰信息).
(2) 采用“對稱方式” 植入后門密鑰, 即算法內(nèi)嵌后門信息和攻擊者提取密鑰所用的后門信息相同. 該種形式后門簡單通用, 但某種程度上會弱化密鑰滲漏攻擊能力的專有性. 一旦用戶發(fā)現(xiàn)算法內(nèi)嵌的后門信息, 就可以獲得和攻擊者同樣的攻擊能力.
因此, 本文旨在探索SM2 算法是否面臨比“逐比特滲漏” 方式更加高效且基于非對稱后門(和SETUP 類似[5–7]) 的密鑰滲漏攻擊威脅.
針對上述問題, 本文首先給出適用于數(shù)字簽名算法和公鑰加密算法的KEA 模型, 主要刻畫KEA 攻擊的兩個(gè)性質(zhì): “攻擊不可檢測性” 和“密鑰可還原性”. 前者用于刻畫攻擊的隱蔽性, 即用戶通過觀察算法的輸入輸出無法辨別算法是否被篡改. 后者用于描述該種攻擊的危害性, 即攻擊者通過捕獲分析算法的輸出可以提取密鑰. 在給出攻擊模型的基礎(chǔ)上, 本文針對SM2 數(shù)字簽名算法和公鑰加密算法進(jìn)行KEA 威脅評估, 具體結(jié)果如下:
(1) 提出針對SM2 數(shù)字簽名算法的對稱密鑰滲漏攻擊. 該攻擊使得攻擊者通過2 個(gè)連續(xù)的簽名就能提取簽名密鑰. 和Ateniese 等提出的“偏隨機(jī)數(shù)攻擊”[10]相比, 本文提出的攻擊將完整還原密鑰所需的簽名數(shù)量從與密鑰長度線性相關(guān)降低到常數(shù).
(2) 提出針對SM2 公鑰加密算法的非對稱密鑰滲漏攻擊.與對稱加密算法不一樣,公鑰加密算法的運(yùn)行沒有用戶私鑰的參與. 本文提出了一種能夠高效滲漏SM2 公鑰加密會話密鑰(session key) 的攻擊. 該攻擊使得攻擊者通過當(dāng)前密文能夠成功預(yù)測下一次會話使用的加密密鑰, 從而具備解密能力.
此外, 本文還對現(xiàn)有相關(guān)的抗KEA 技術(shù)進(jìn)行分類總結(jié), 并結(jié)合SM2 數(shù)字簽名算法和公鑰加密算法的構(gòu)造特點(diǎn)選取具有可行性的防范技術(shù)進(jìn)行討論.
目前國際密碼學(xué)界在后斯諾登密碼學(xué)領(lǐng)域取得了一定的進(jìn)展, 主要體現(xiàn)在對一系列密碼算法的后門威脅評估和基于各種假設(shè)條件的防范方法設(shè)計(jì)兩個(gè)方面. 文獻(xiàn)[16] 已經(jīng)做了比較全面的總結(jié), 下面按照不同的密碼算法分類介紹與KEA 威脅評估相關(guān)的工作.
對稱加密算法: Bellare 等針對密文中包含IV 等公開隨機(jī)數(shù)的對稱加密算法, 在文獻(xiàn)[4] 中提出了IV-replacement attack. 主要思路是在算法輸出的密文中將包含用戶密鑰的密文作為IV 直接輸出, 因此比“偏密文攻擊” 更加高效. 隨后, Bellare 等[8]提出了一種改進(jìn)的攻擊方法, 避免“偏密文攻擊” 需要維護(hù)內(nèi)部狀態(tài)、記錄所滲漏密鑰比特位置信息的不足. 主要思路是通過采用特殊的評估函數(shù), 不僅可以根據(jù)每次密文提取密鑰比特信息, 還可以獲取該比特所在的位置信息. 該種攻擊由于采用coupon collection 的原理,因此比“逐比特滲漏”的效率更低. Degabriele 等[9]提出了“輸入觸發(fā)攻擊”(input-trigger attack).該種攻擊只有在加密算法接收到特定輸入信息的時(shí)候才會被觸發(fā), 而且可以直接將密鑰輸出, 因此效率很高.
數(shù)字簽名算法: Ateniese 等[10]則針對簽名體制開展了KEA 探索, 提出了兩種攻擊方式: “隨機(jī)數(shù)可提取攻擊” (coin-extractable attack) 和“偏隨機(jī)數(shù)攻擊” (biased randomness attack). 前種攻擊與Bellare 等提出的IV-replacement attack 類似, 主要是將滲漏密鑰的密文作為算法輸出中的公開隨機(jī)數(shù),第二種攻擊則和“偏密文攻擊” 類似, 也是通過“拒絕采樣” 的方式, 產(chǎn)生特定的合法簽名輸出. Teseleanu等[11]針對基于離散對數(shù)困難性假設(shè)的數(shù)字簽名方案提出了門限SETUP 攻擊方式. 柳馳等在文獻(xiàn)[12]中針對“可分割數(shù)字簽名方案” 提出了一種高效的KEA. 該攻擊方式類似于SETUP 攻擊, 采用非對稱方式在算法中嵌入后門, 且僅需要2 個(gè)連續(xù)簽名就能滲漏整個(gè)密鑰.
公鑰加密算法: 陳榮茂等[17]對采用混合式加密(hybrid encryption) 的公鑰加密方案進(jìn)行了嚴(yán)謹(jǐn)?shù)恼撟C分析, 發(fā)現(xiàn)現(xiàn)有大部分采用該結(jié)構(gòu)的公鑰加密方案面臨一種非常高效的加密會話密鑰滲漏攻擊. 攻擊者通過上一個(gè)密文能夠成功預(yù)測下一個(gè)會話中的加密密鑰. 事實(shí)上, 文中針對公鑰加密方案的密鑰滲漏攻擊可以看做是陳榮茂等攻擊框架在SM2 公鑰加密方案下的一種實(shí)例化, 因此進(jìn)一步證實(shí)了該種攻擊的廣泛存在性. 在具體方案攻擊方面, 楊智超等[13]針對格上公鑰加密方案提出了具體的KEA 攻擊. Russell等在[18] 中也針對公鑰加密方案提出了一種通用的攻擊, 其主要思路是采用Bellare 等[4]提出的“偏密文攻擊” 方法.
其他密碼算法: 除了上述主流的密碼體制, Armour 等[14]也分析了MAC 所面臨的密鑰滲漏威脅.呂佳憲等[19]則對云數(shù)據(jù)審計(jì)協(xié)議中挑戰(zhàn)因子的可信問題進(jìn)行研究, 提出了一種通過挑戰(zhàn)信息滲漏簽名密鑰的具體攻擊. 此外, 還有一些工作[20,21]針對密碼算法的參數(shù)安全問題進(jìn)行了研究.
本文組織結(jié)構(gòu)如下: 第2 節(jié)介紹相關(guān)預(yù)備知識. 第3 節(jié)形式化定義針對數(shù)字簽名方案和公鑰加密方案的KEA 模型. 第4 節(jié)提出針對SM2 數(shù)字簽名算法的具體KEA 攻擊以及形式化分析. 第5 節(jié)提出針對SM2 公鑰加密算法的具體KEA 攻擊以及形式化分析. 第6 節(jié)討論適用于SM2 密碼算法的抗KEA 技術(shù).
本節(jié)介紹后續(xù)章節(jié)使用的主要符號表示和涉及的密碼基礎(chǔ)概念.
對于任意非空集合X,x ←$X表示從X中隨機(jī)選取元素x. 對于任意隨機(jī)算法F(·),y ←$F(x)表示算法F的隨機(jī)輸出. poly(n) 表示n的多項(xiàng)式函數(shù); 如果某n的函數(shù)比n的任何多項(xiàng)式函數(shù)的倒數(shù)衰減得更快, 則稱其為可忽略函數(shù), 使用negl(n) 表示. 如果對于任何長度為n的輸入, 算法A最多在poly(n) 步內(nèi)結(jié)束, 則稱A為概率多項(xiàng)式時(shí)間(PPT) 算法. 對于任意整數(shù)i,j滿足i
定義1 (計(jì)算性Diffie-Hellman (CDH) 困難性假設(shè)) 令正整數(shù)n為安全參數(shù), G 為一個(gè)階為素?cái)?shù)p的群,g為群G 的生成元. 計(jì)算性Diffie-Hellman 困難性假設(shè)指的是對于所有的PPT 算法A,
定義2 (熵平滑的密碼雜湊函數(shù)簇) 令正整數(shù)n為安全參數(shù),F={Fκ}κ∈K表示一個(gè)具有密鑰的密碼雜湊函數(shù)簇, 其中K為密鑰空間. 假設(shè)該函數(shù)簇中的每個(gè)密碼雜湊函數(shù)Fκ將群G 中的元素映射到集合{0,1}?中. 我們稱該函數(shù)簇是熵平滑的, 當(dāng)且僅當(dāng)對于所有的PPT 算法D,
數(shù)字簽名方案主要由4 個(gè)算法組成: 分別是初始化算法、密鑰生成算法、簽名算法和驗(yàn)證算法.
? 初始化算法Setup: 輸入安全參數(shù)1n, 輸出系統(tǒng)參數(shù)pp;
? 密鑰生成算法KGen: 輸入系統(tǒng)參數(shù)pp, 輸出簽名私鑰sk 和驗(yàn)證公鑰vk;
? 簽名算法Sign: 輸入簽名私鑰sk 和消息M, 輸出簽名σ;
? 驗(yàn)證算法Vrfy: 輸入驗(yàn)證公鑰vk, 消息M和簽名σ, 若σ是M的合法簽名, 輸出1; 否則輸出0.
簡潔起見, 本文將系統(tǒng)參數(shù)pp 從簽名算法Sign 和驗(yàn)簽算法Vrfy 的輸入中省略.
令M為消息空間, 數(shù)字簽名方案的正確性要求對于任意的系統(tǒng)參數(shù)pp←$Setup(1n), 任意的簽名私鑰和驗(yàn)證公鑰(vk,sk)←$KGen(pp) 和任意消息M ∈M,
公鑰加密方案主要由4 個(gè)算法組成: 分別是初始化算法、密鑰生成算法、加密算法和解密算法.
? 初始化算法Setup: 輸入安全參數(shù)1n, 輸出系統(tǒng)參數(shù)pp;
? 密鑰生成算法KGen: 輸入系統(tǒng)參數(shù)pp, 輸出公私鑰對(pk,sk);
? 加密算法Enc: 輸入公鑰pk 和明文M, 輸出密文C;
? 解密算法Dec: 輸入私鑰sk 和密文C, 輸出明文M或者特殊符號⊥.
簡潔起見, 本文將系統(tǒng)參數(shù)pp 從加密算法Enc 和解密算法Dec 的輸入中省略.
令M為明文空間, 公鑰加密方案的正確性要求對于任意的系統(tǒng)參數(shù)pp←$Setup(1n), 任意的公私鑰對(pk,sk)←$KGen(pp) 和任意的明文M ∈M,
本節(jié)將分別介紹針對數(shù)字簽名算法和公鑰加密算法的KEA 模型及其性質(zhì).
? 初始化階段: 運(yùn)行Setup(1n) 生成系統(tǒng)參數(shù)pp, 運(yùn)行KGen(pp) 生成簽名私鑰sk 和驗(yàn)證公鑰vk,運(yùn)行SKGen(pp) 生成后門密鑰ssk, 并將(pp,sk,vk) 發(fā)送給檢測者D;
? 挑戰(zhàn)階段: 隨機(jī)選取b ←${0,1}. 令SignProc(·) 為如下簽名詢問應(yīng)答機(jī), 假設(shè)詢問輸入為消息M:
檢測者D向SignProc(·) 發(fā)起q(n) 次詢問, 其中q(n) 為關(guān)于n的任意多項(xiàng)式;
? 猜測階段: 在詢問階段結(jié)束后, 檢測者D輸出b′. 當(dāng)b=b′時(shí), 該游戲輸出1, 否則輸出0.
本節(jié)將首先對SM2 數(shù)字簽名方案進(jìn)行簡要介紹, 然后給出針對SM2 數(shù)字簽名算法的具體KEA 方案, 最后證明該KEA 具有不可檢測性和簽名私鑰可還原性.
SM2 數(shù)字簽名方案的系統(tǒng)參數(shù)pp 包括: 有限域Fq, 橢圓曲線E(Fq) 及該曲線上的無窮遠(yuǎn)點(diǎn)O, 任意選取的基點(diǎn)G= (xG,yG)(G ?=O), 基點(diǎn)G的階n及其余因子h, 消息摘要長度為v比特的密碼雜湊函數(shù)Hv, 部分橢圓曲線系統(tǒng)參數(shù). 假設(shè)系統(tǒng)參數(shù)pp 還包括用戶A的可辨別標(biāo)識, 和用戶A公鑰的雜湊值為ZA. SM2 數(shù)字簽名方案中的密鑰生成算法、簽名算法和驗(yàn)證算法分別如算法1—算法3 所示.
算法1 SM2 簽名密鑰生成算法Input: 系統(tǒng)參數(shù)pp Output: 簽名私鑰及驗(yàn)證公鑰對(sk,vk)1 dA ←$ [1,n ?1]2 PA = [dA]G 3 (sk,vk) = (dA,PA)4 return (sk,vk)算法2 SM2 簽名算法Input: 系統(tǒng)參數(shù)pp, 簽名私鑰dA, 消息M Output: 簽名σ 1 ^M = ZA||M 2 e = Hv(^M)3 k ←$ [1,n ?1]4 (x1,y1) = [k]G 5 r = (e+x1) mod n 6 s = ((1+dA)?1 ·(k ?r·dA)) mod n 7 σ = (r,s)8 return σ
算法3 SM2 驗(yàn)證算法Input: 系統(tǒng)參數(shù)pp, 驗(yàn)證公鑰dA, 消息M′,簽名σ′Output: 1 或0 1 (r′,s′) = σ′2 if r′ /∈[1,n ?1]∨s′ /∈[1,n ?1] then 3 return 0 4 end 5 ^M′ = ZA||M′6 e′ = Hv(^M′)7 t = (r′ +s′) mod n 8 (x′1,y′1) = [s′]G+[t]PA 9 R = (e′ +x′1) mod n 10 if R ?= r′ then 11 return 0 12 end 13 return 1
在進(jìn)行攻擊前, 攻擊者需要運(yùn)行算法SKGen 生成后門密鑰ssk: 攻擊者首先從G 中隨機(jī)選取生成元PS, 然后從密碼雜湊函數(shù)簇F={Fκ}κ∈K中隨機(jī)選擇密碼雜湊函數(shù)Fκ:G→[1,n ?1], 其中G 為橢圓曲線E(Fq) 上所有點(diǎn)的集合. 因此, ssk=(PS,Fκ).
根據(jù)引理1,G0和G1對于任意PPT 算法而言不可區(qū)分. 綜上所述, 上述攻擊是不可檢測的.定理2 上述攻擊是簽名私鑰可還原的.
根據(jù)上述步驟, 攻擊者A可以還原出簽名私鑰.
本節(jié)將首先簡要介紹SM2 公鑰加密方案, 然后給出針對SM2 公鑰加密算法的具體KEA 方案, 最后證明該KEA 具有不可檢測性和明文可還原性.
SM2 公鑰加密方案的系統(tǒng)參數(shù)pp 包括: 有限域Fq, 橢圓曲線E(Fq) 及該曲線上的無窮遠(yuǎn)點(diǎn)O, 任意選取的基點(diǎn)G= (xG,yG)(G ?=O), 基點(diǎn)G的階n及其余因子h, 密鑰派生函數(shù)KDF 和密碼雜湊函數(shù)H, 其中密鑰派生函數(shù)KDF 輸入比特串Z和整數(shù)?, 輸出長度為?的密鑰數(shù)據(jù)比特串K. 和數(shù)字簽名方案的密鑰生成算法類似, SM2 公鑰加密方案的密鑰生成算法首先從[1,n ?1] 中隨機(jī)選取一個(gè)整數(shù)dB作為私鑰, 然后計(jì)算公鑰PB= [dB]G. SM2 公鑰加密方案中的加密算法和解密算法分別如算法4 和算法5 所示.
算法4 SM2 加密算法Input: 系統(tǒng)參數(shù)pp, 公鑰PB, 明文M Output: 密文C 1 k ←$ [1,n ?1]2 C1 = [k]G 3 S = [h]PB 4 if S = O then 5 return ⊥6 end 7 (x2,y2) = [k]PB 8 klen = |M|9 t = KDF(x2||y2,klen)10 C2 = M ⊕t 11 C3 = H(x2||M||y2)12 C = C1||C2||C3 13 return C
算法5 SM2 解密算法Input: 系統(tǒng)參數(shù)pp, 私鑰dB, 密文C Output: 明文M 或特殊符號⊥1 S = [h]C1 2 if S = O then 3 return ⊥4 end 5 (x2,y2) = [dB]C1 6 klen = |C2|7 t = KDF(x2||y2,klen)8 M = C2 ⊕t 9 u = H(x2||M′||y2)10 if u ?= C3 then 11 return ⊥12 end 13 return M
下面形式化分析該攻擊具備不可檢測性和簽名私鑰可還原性.
定理3 在隨機(jī)預(yù)言機(jī)模型下, 令q(n) 為檢測者D發(fā)起EncProc 詢問的次數(shù),q′(n) 為檢測者D發(fā)起H′詢問的次數(shù), 若任意PPT 算法解決計(jì)算性Diffie-Hellman 問題的優(yōu)勢為θ(n), 那么上述攻擊是(q(n)?1)·q′(n)·θ(n)-不可檢測的.
證明: 我們將通過設(shè)計(jì)一系列游戲來證明上述非對稱攻擊的不可檢測性. 令Ei表示事件b=b′在游戲Gi中發(fā)生.
? 游戲G3與游戲G2相同, 除了在游戲G3中加密詢問應(yīng)答機(jī)EncProc(·) 的實(shí)現(xiàn)與游戲G2中的略有不同. 具體來說, 游戲G3中的加密詢問應(yīng)答機(jī)EncProc(·) 在b= 1 時(shí)也輸出C ←$Enc(pk,M). 顯然, 此時(shí)在游戲G3中Pr[E3]=1/2.
綜上所述,?(n)≤(q(n)?1)·q′(n)·θ(n). 該定理成立.定理4 上述攻擊是明文可還原的.
根據(jù)上述攻擊的描述, 攻擊者A可以還原出除密文C1以外的所有密文的明文.
由于KEA 具有很強(qiáng)的破壞性且不在傳統(tǒng)安全性分析的考慮范疇, 因此需要研究設(shè)計(jì)新的技術(shù)手段來抵御這種攻擊. 目前學(xué)術(shù)界已有若干研究工作嘗試提出具備一定可行性的防范技術(shù). 本文將介紹部分具有代表性的研究工作, 并結(jié)合SM2 密碼算法方案進(jìn)行討論. 更具體詳細(xì)的總結(jié)可以參考國內(nèi)學(xué)者李耕等的綜述工作[16].
現(xiàn)有提出的KEA 雖然在具體實(shí)施細(xì)節(jié)上各有不同, 但本質(zhì)上都是因?yàn)槊艽a算法輸出的不確定性所造成的. 由于密碼算法輸出的不確定性與其運(yùn)行時(shí)臨時(shí)生成的隨機(jī)數(shù)直接相關(guān), 因此有一部分學(xué)者建議采用不依賴于隨機(jī)數(shù)的密碼機(jī)制[4,9,10,22]來抵抗KEA. 特別地, Bellare 等[4]提出了具備唯一密文(unique ciphertext) 性質(zhì)的對稱加密算法, 即給定一個(gè)明文, 加密算法所輸出的合法密文只有一個(gè). 類似的, Ateniese 等[10]提出了具備唯一簽名(unique signature) 性質(zhì)的數(shù)字簽名算法. 文獻(xiàn)[4,10] 通過形式化分析證明, 在KEA 具備不可檢測性的情況下, 上述類型的密碼算法可以實(shí)現(xiàn)抵抗KEA 的安全性.
上述方法具備一定的可行性. 然而隨機(jī)數(shù)是密碼算法常規(guī)情況下實(shí)現(xiàn)特定安全性(如選擇明文攻擊不可區(qū)分性) 的必備條件. 因此放棄隨機(jī)數(shù)的使用從實(shí)現(xiàn)密碼算法安全性的角度來講不是一種很理想的選擇.針對這個(gè)問題, 另外一些學(xué)者嘗試在使用隨機(jī)數(shù)情況下設(shè)計(jì)抵抗密鑰滲漏攻擊的可行技術(shù). 然而文獻(xiàn)[15]從理論上證明了所有隨機(jī)化算法均面臨KEA 威脅, 因此需要基于新的假設(shè)性條件(如可信第三方), 否則無法實(shí)現(xiàn)抗KEA 安全性. 需要指出的是, 由于假設(shè)條件的不同, 現(xiàn)有提出的防范技術(shù)之間不具備可比性.下面我們將根據(jù)假設(shè)條件分類闡述, 并結(jié)合SM2 密碼算法進(jìn)行討論.
密碼逆向防火墻技術(shù)是Mironov 等[23]在2015 年首次提出的概念. 類似于傳統(tǒng)的網(wǎng)絡(luò)防火墻, 逆向防火墻部署在密碼算法所運(yùn)行機(jī)器的網(wǎng)絡(luò)邊界, 負(fù)責(zé)對被保護(hù)算法所有發(fā)送和收到的消息進(jìn)行處理從而實(shí)現(xiàn)抵抗KEA 的目的. 實(shí)際上, 密碼逆向防火墻可以看做是一段運(yùn)行在可信機(jī)器上的重隨機(jī)化算法代碼, 其工作的主要原理是在不破壞協(xié)議功能性的情況下重隨機(jī)化算法所輸出的消息, 從而消除被篡改密碼算法在其輸出消息中所嵌入的密鑰比特信息. 密碼逆向防火墻技術(shù)已被證明可以用于實(shí)現(xiàn)很強(qiáng)的抗KEA 安全性, 在某些特定的情況下甚至可以防范任意的密鑰滲漏攻擊行為, 因此得到了若干工作[10,24–27]的進(jìn)一步拓展研究. 然而該技術(shù)要求被保護(hù)密碼算法具備可重隨機(jī)化的性質(zhì), 因此無法直接適用于不具備這種性質(zhì)的SM2 密碼算法. 一個(gè)具有潛在可行性的解決思路是弱化對于密碼逆向防火墻透明性的要求, 使其與終端機(jī)器進(jìn)行交互獲得輔助信息, 從而具備重隨機(jī)化簽名和密文的能力, 但如何降低密碼逆向防火墻對原有算法安全性的影響是需要考慮的主要問題.
Russell 等[18]從體系結(jié)構(gòu)設(shè)計(jì)的角度提出了程序分割(split-program) 模型. 該模型假設(shè)密碼算法由若干個(gè)獨(dú)立的模塊構(gòu)成. 而這些模塊在實(shí)際部署的時(shí)候會由一個(gè)擁有各個(gè)模塊對應(yīng)標(biāo)準(zhǔn)規(guī)范(specification) 的可信“監(jiān)視犬” (watchdog) 逐個(gè)進(jìn)行比對檢測. 只有通過檢測的模塊才能被組裝成完整的密碼算法投入使用. 基于這種模塊化設(shè)計(jì)思想, 文獻(xiàn)[18] 從理論上證明, 通過watchdog 檢測模塊所組裝成的密碼算法可以實(shí)現(xiàn)抗KEA 安全性. 其核心思路是將密碼算法分成確定性模塊和隨機(jī)數(shù)生成模塊. 前者可以通過比對檢測保證與相關(guān)規(guī)范的一致性, 而后者通過特殊的構(gòu)造可以生成可信的隨機(jī)數(shù). 這種“分割-融合” (decomposition and amalgamation) 的思想具有較強(qiáng)的通用性, 已被應(yīng)用于構(gòu)造隨機(jī)數(shù)生成器[18]、數(shù)字簽名算法[18,28]、公鑰加密方案[29,30]以及隨機(jī)預(yù)言機(jī)[31]等. 由于SM2 數(shù)字簽名算法和公鑰加密算法是隨機(jī)化算法, 因此上述技術(shù)同樣適用.
Fischlin 等[32]提出了基于“自我防護(hù)” (self-guarding) 思想的密碼算法構(gòu)造技術(shù). 其假設(shè)密碼算法部署在某個(gè)時(shí)期(如早期階段) 沒有遭到篡改. 在這種假設(shè)條件下, 通過收集該階段算法執(zhí)行所產(chǎn)生的消息流, 并用這些“干凈” 的樣本對后期可能被攻擊的密碼算法輸出進(jìn)行修改, 可以實(shí)現(xiàn)抵抗KEA 的安全性.該技術(shù)和密碼逆向防火墻的本質(zhì)思想是一樣的, 都是依賴可信的隨機(jī)數(shù)對可能內(nèi)嵌密鑰信息的算法輸出進(jìn)行處理從而抵抗KEA. 不同的是, 該技術(shù)不需要依賴可信的第三方而需要假設(shè)算法存在沒有被攻擊的階段. 自我防護(hù)技術(shù)可以作為解決密碼逆向防火墻無法適用不具備可重隨機(jī)化性質(zhì)密碼算法時(shí)的一種可行思路. 不足的地方是, 這種技術(shù)需要修改原有密碼方案的設(shè)計(jì), 而且只能防范某個(gè)時(shí)間段發(fā)起的密鑰滲漏攻擊類型(如時(shí)間炸彈攻擊), 并依賴于算法安全階段所收集的樣本數(shù)量. 文獻(xiàn)[32] 分別給出了抗KEA 的公鑰加密、對稱加密和數(shù)字簽名方案構(gòu)造. 其中數(shù)字簽名算法的構(gòu)造同樣適用于SM2 數(shù)字簽名. 而公鑰加密算法構(gòu)造由于要求具有同態(tài)性質(zhì), 因此并不直接適用于SM2 公鑰加密方案.
針對密碼算法開展密鑰滲漏攻擊評估是“后斯諾登密碼學(xué)” 領(lǐng)域的重要研究問題之一. 本文定義了評估密鑰滲漏攻擊的兩個(gè)性質(zhì): 不可檢測性和密鑰/明文可還原性. 在此基礎(chǔ)上, 針對國產(chǎn)商用密碼SM2 數(shù)字簽名算法和公鑰加密算法, 分別提出兩種高效的密鑰滲漏攻擊. 通過理論分析, 證明提出的密鑰滲漏攻擊滿足上述兩個(gè)性質(zhì). 本文的研究結(jié)果表明, SM2 數(shù)字簽名算法和公鑰加密算法面臨的密鑰滲漏攻擊威脅比已知的通用攻擊更加嚴(yán)重, 在實(shí)際部署時(shí)應(yīng)采取相應(yīng)的防范技術(shù).
需要指出的是, 我們暫時(shí)還沒有發(fā)現(xiàn)針對SM2 數(shù)字簽名算法的具有非對稱形式的密鑰滲漏攻擊. 柳馳等的工作[12]實(shí)現(xiàn)的非對稱方式的密鑰滲透攻擊僅針對特定的數(shù)字簽名類型, 即“可分割數(shù)字簽名方案”. 而SM2 數(shù)字簽名算法并不屬于這一類別, 因此無法將現(xiàn)有攻擊方式應(yīng)用到該簽名算法.
本文提出的高效密鑰滲漏攻擊并不能適用于SM2 密碼算法中的密鑰交換協(xié)議. 主要原因是SM2 密鑰交換協(xié)議采用單輪交互, 協(xié)議雙方在執(zhí)行過程中只交換臨時(shí)隨機(jī)數(shù), 并沒有公開傳輸與用戶私鑰相關(guān)的信息. 因此, 雖然本文提出的攻擊方法可以完整滲漏雙方密鑰協(xié)商時(shí)所生成的內(nèi)部隨機(jī)數(shù), 卻無法用于高效還原用戶私鑰. 此外, 由于雙方協(xié)商的會話密鑰由用戶私鑰和臨時(shí)隨機(jī)數(shù)共同決定, 因此攻擊者在只獲得隨機(jī)數(shù)的情況下也仍然無法還原會話密鑰.