李 耕, 劉建偉, 張宗洋

1. 北京航空航天大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京100083

2. 空天網(wǎng)絡(luò)安全工業(yè)和信息化部重點(diǎn)實驗室, 北京100083

1 引言

2013 年的“棱鏡門” 事件震驚全球, 美國前中央情報局職員愛德華· 斯諾登(Edword Snowden) 披露的信息以及其他證據(jù)顯示, 美國國家安全局(National Security Agency, NSA) 等情報機(jī)構(gòu)通過潛入各大網(wǎng)絡(luò)巨頭的服務(wù)器, 對全球網(wǎng)絡(luò)進(jìn)行大規(guī)模監(jiān)視, 竊取美國本土及世界范圍內(nèi)的公民隱私信息以及重要領(lǐng)域通信信息[1,2]. 2020 年2 月, 美國、德國和瑞士媒體聯(lián)合調(diào)查發(fā)現(xiàn)[3], 瑞士加密設(shè)備制造商Crypto 曾經(jīng)由美國和德國情報機(jī)構(gòu)秘密所有, 兩家情報機(jī)構(gòu)能夠通過故意植入的漏洞破解使用該公司生產(chǎn)的加密設(shè)備傳輸?shù)拿孛芪募? 而且, 此監(jiān)控計劃已經(jīng)持續(xù)了數(shù)十年. 目前對于此事件的進(jìn)一步調(diào)查正在進(jìn)行中.

在此類事件中, 部分國家使用的一些竊密手段跳脫了傳統(tǒng)密碼學(xué)的考慮范疇, 一些在傳統(tǒng)分析方法下被認(rèn)為是安全的密碼體制在新的環(huán)境下不再安全. 某些國家的情報機(jī)構(gòu)可以通過對密碼算法植入后門, 或在其執(zhí)行中加入不安全因素, 以損害密碼體制的安全性, 竊取用戶敏感信息. 此類對密碼體制的執(zhí)行過程進(jìn)行攻擊的手段具有理論上的隱蔽性, 在相當(dāng)長的時間內(nèi)無法通過技術(shù)手段被發(fā)現(xiàn). 例如, NSA 設(shè)計并強(qiáng)行通過了Dual_EC_DRBG[4]作為偽隨機(jī)數(shù)生成器, 在Dual_EC_DRBG 相關(guān)標(biāo)準(zhǔn)推薦的參數(shù)里, 后門的擁有者可以在獲取一定長度的隨機(jī)數(shù)生成器的輸出后, 預(yù)測后續(xù)輸出[2]; 而對于不持有后門的實體,其輸出可以達(dá)到一個偽隨機(jī)數(shù)生成器的安全性.

新的安全威脅受到了密碼學(xué)理論界的持續(xù)關(guān)注, 研究人員對大規(guī)模監(jiān)視的攻擊手段進(jìn)行重新分析, 逐步建立了后斯諾密碼學(xué)框架. 與傳統(tǒng)密碼學(xué)的重要不同在于, 后斯諾密碼學(xué)刻畫了敵手對密碼算法進(jìn)行“顛覆” 的過程, 即, 敵手可根據(jù)算法說明(specification), 通過嵌入后門等手段, 給出顛覆后的算法執(zhí)行(implementation). 而算法執(zhí)行對于使用者而言被建模為黑盒, 使用者無法獲取其內(nèi)部的運(yùn)算過程, 只能通過輸入輸出來判斷其是否誠實地按照算法說明執(zhí)行. 早在“棱鏡門” 事件發(fā)生之前, Young 等人[5]就已建立了kleptography 模型以刻畫顛覆攻擊, 并給出了相應(yīng)安全性定義. Russel 等人[6]在Bellare 等人[7]和Degabriele 等人[8]研究的基礎(chǔ)上, 給出了cliptography (改進(jìn)的kleptography) 模型. 這些安全模型與相關(guān)的一系列研究普遍認(rèn)為, 顛覆威脅下的密碼體制需要達(dá)到這樣的安全性: 除了本身能夠?qū)崿F(xiàn)傳統(tǒng)密碼學(xué)所定義的安全性外, 對于任何敵手給出的執(zhí)行, 要么從用戶角度能夠區(qū)分其輸出與算法說明的輸出, 要么敵手自身也無法區(qū)分其輸出與算法說明的輸出. Russel 等人[6]將這種思想形式化表示為無隱寫性(stego-freeness).

大規(guī)模監(jiān)視背景下敵手的較強(qiáng)能力, 給安全密碼體制的設(shè)計帶來了很大挑戰(zhàn). 為了設(shè)計抗顛覆的密碼體制, 在無隱寫性即類似安全目標(biāo)下, 研究人員提出了一系列針對顛覆攻擊的防御方法, 主要可分為以下幾類:

(1) 回歸確定性算法: 如Bellare 等人[7]提出的“唯一密文(unique ciphertexts) 體制”.

(2) 基于可信元素: 如Mironov 等人[9]提出的密碼反向防火墻(基于可信模塊),和Fischlin 等人[10]提出的自守衛(wèi)體制(基于可信階段) 等.

(3) 基于隨機(jī)喻言模型: 如Russel 等人[11]提出的基于“分割-融合模型” 的安全密碼體制設(shè)計等.

(4) 基于(可信) 公開隨機(jī)源: Ateniese 等人[12]提出的基于(可信) 公開的隨機(jī)源的防御方法.

(5) 基于多源算法: Li 等人[13]提出的通過采用多個不同來源的算法構(gòu)建抗顛覆密碼體制的方法.

然而, 由于當(dāng)前提出的這些防御方法存在各種各樣的問題, 比如應(yīng)用對象極其有限(確定性算法), 通過特定假設(shè)繞過了顛覆威脅下的關(guān)鍵問題(可信隨機(jī)數(shù)產(chǎn)生), 需要借助于強(qiáng)假設(shè)(隨機(jī)喻言), 需要復(fù)雜的工程實現(xiàn)方法及額外的成本開銷(多源算法) 等, 在現(xiàn)實中的可行性均存在限制, 不適合于廣泛應(yīng)用. 雖然針對相關(guān)防御方法的研究已經(jīng)有很多, 但仍缺少較好的解決方案, 本文重新審視了顛覆威脅下的安全模型和安全目標(biāo), 在擬合現(xiàn)實安全需求的前提下提出一種相對較弱的安全定義, 為設(shè)計可行性更強(qiáng)的防御方法提供方向和思路.

1.1 本文貢獻(xiàn)

1.1.1 抗顛覆職能安全

本文從現(xiàn)實應(yīng)用角度出發(fā), 總結(jié)以往相關(guān)研究[8,12,14], 提出了抗顛覆安全保留性. 在實際中, 不同的應(yīng)用場景對其中的密碼體制有相應(yīng)的安全要求(如語義安全, CPA 安全, CCA 安全等), 本文將其稱為目標(biāo)安全. 抗顛覆安全保留性的定義思想為, 在黑盒測試的保護(hù)下, 一個密碼體制如果在遭到顛覆攻擊時, 仍然能夠?qū)崿F(xiàn)特定場景下的目標(biāo)安全, 則稱其滿足抗顛覆安全保留性. 抗顛覆安全保留性不再追求以無隱寫性為代表的安全定義所要求的顛覆執(zhí)行與算法說明不可區(qū)分, 而僅要求密碼體制在顛覆環(huán)境下仍然能實現(xiàn)某種具體的安全性, 是一種較為直觀的定義思路, 但契合了現(xiàn)實中對密碼體制最直接的需求.

本文形式化分析了抗顛覆安全保留性與無隱寫性之間的關(guān)系. 證明了所有同時滿足目標(biāo)安全和無隱寫性的密碼體制均滿足抗顛覆安全保留性, 同時, 又通過構(gòu)造安全性介于無隱寫性和抗顛覆安全保留性之間的密碼體制, 證明了抗顛覆安全保留性弱于無隱寫性. 由此得出了圖1 所示的邏輯關(guān)系. 由于抗顛覆安全保留性是最為直接的現(xiàn)實需求, 說明在邏輯上無隱寫性定義過強(qiáng). 在之前的研究中, 研究人員始終在圖1 中的A 區(qū), 即安全性達(dá)到無隱寫性的區(qū)域構(gòu)造抗顛覆密碼體制, 而沒有研究B 區(qū)中的密碼體制. 目前在A 區(qū)并未得到可行性較高的抗顛覆防御策略, 因此抗顛覆安全保留性的提出, 對于拓寬抗顛覆密碼體制設(shè)計思路, 探索防御方法具有一定現(xiàn)實意義.

圖1 無隱寫性與抗顛覆安全保留性關(guān)系示意圖Figure 1 Relationship between stego-freeness and security-preservation against subversion

1.1.2 算法隔離運(yùn)行與抗顛覆密碼體制設(shè)計

本文基于Russel 等人[6]提出的“分割-融合模型”, 探索在圖1 中B 區(qū)設(shè)計密碼體制的方法. 首先, 本文將密碼系統(tǒng)中用戶的輸入信息, 如密鑰, 明文等, 定義為業(yè)務(wù)數(shù)據(jù), 并證明了在所有顛覆算法均能夠獲取業(yè)務(wù)數(shù)據(jù)(全知悉) 的條件下, 無隱寫性與抗顛覆安全保留性的等價性, 由此為設(shè)計B 區(qū)的密碼體制提供了方向, 即, 需要限制部分顛覆算法的知悉范圍.

本文提出了算法隔離運(yùn)行的概念. 算法隔離運(yùn)行, 即在“分割-融合模型” 的框架下, 將部分分割后的子算法置于一個與用戶業(yè)務(wù)數(shù)據(jù)“隔離” 的環(huán)境下運(yùn)行. 算法隔離運(yùn)行具有較強(qiáng)的現(xiàn)實可行性, 其簡單的實現(xiàn)方法之一為在業(yè)務(wù)數(shù)據(jù)產(chǎn)生之前, 先運(yùn)行被隔離的算法產(chǎn)生輸出, 從而達(dá)到隔離的效果. 算法隔離運(yùn)行排除了以“拒絕-采樣攻擊” 為代表的一類攻擊方法成功的可能性.

基于算法隔離運(yùn)行, 本文分別在部分顛覆模型和完全顛覆模型下設(shè)計了滿足抗顛覆安全保留性的對稱加密體制. 針對部分顛覆模型, 即密鑰生成算法能夠被安全執(zhí)行, 但加解密算法處于顛覆威脅下的情況, 引入了帶密鑰的偽隨機(jī)置換算法. 所設(shè)計的方案將隨機(jī)數(shù)生成器和偽隨機(jī)置換算法置于隔離運(yùn)行狀態(tài), 以用戶密鑰作為偽隨機(jī)置換的密鑰, 對隨機(jī)數(shù)生成器的輸出進(jìn)行置換并與明文進(jìn)行異或, 將異或結(jié)果與置換前的隨機(jī)數(shù)一同作為密文. 此設(shè)計沒有達(dá)到無隱寫性的安全性, 但是滿足抗顛覆安全保留性, 且具有較強(qiáng)的可行性.

針對完全顛覆模型, 本文設(shè)計了兩種方案. 方案一通過隨機(jī)單比特生成器獲取與均勻隨機(jī)字串不可區(qū)分的隨機(jī)字串, 繼續(xù)采用上述框架構(gòu)造安全體制. 方案二通過引入計算強(qiáng)提取器, 在密鑰僅能保證一定的最小熵的情況下獲取安全的隨機(jī)字串, 與明文異或產(chǎn)生輸出. 以上兩種方案雖然采用了Russel 等人[11]設(shè)計的使用單比特隨機(jī)源的方法, 但特點(diǎn)在于不需要保證密鑰和加密過程中使用的隨機(jī)數(shù)二者同時對于敵手計算上均勻隨機(jī), 這有利于降低密碼體制的構(gòu)建成本并提高算法執(zhí)行效率.

1.2 相關(guān)研究

1.2.1 顛覆威脅下的安全模型研究

早在“棱鏡門” 事件發(fā)生之前, Young 等人[5,15-17]就已對密碼體制執(zhí)行遭受敵手篡改的情況進(jìn)行過研究, 他們將此類攻擊方法概括為通用保護(hù)的內(nèi)嵌后門(secretly embedded trapdoor with universal protection, SETUP), 并提出了kleptography 安全模型的概念. Young 等人[5]將SETUP 攻擊區(qū)分為強(qiáng)SETUP、一般SETUP 和弱SETUP, 分別使用6 條規(guī)則概括其性質(zhì). 其后Young 等人[17]又通過游戲的方式形式化定義了強(qiáng)SETUP. Young 等人[5,15]針對常用的密碼體制, 如RSA、El-Gamal、DSA、Kerberos 協(xié)議等設(shè)計了攻擊方法并證明了其有效性.

Bellare 等人[7]提出了基于“檢測-監(jiān)視游戲” 的安全模型. 通過設(shè)計敵手參與的監(jiān)視游戲和使用者參與的檢測游戲, 定義密碼體制在顛覆威脅下的安全性. 在文獻(xiàn)[7] 的定義中, 如果監(jiān)視優(yōu)勢可忽略或檢測優(yōu)勢不可忽略, 則認(rèn)為密碼體制安全. Bellare 等人[7]假設(shè)顛覆的加密體制仍需要滿足可解密性①所有由顛覆的加密算法產(chǎn)生的密文均可由純凈的解密算法正確解密要求, 在此基礎(chǔ)上證明了唯一密文體制在顛覆威脅下的安全性. Degabriele 等人[8]認(rèn)為文獻(xiàn)[7] 中對于敵手的限制過強(qiáng), 在不默認(rèn)可解密性的前提下, 提出了輸入觸發(fā)攻擊, 從而否定了確定性算法在顛覆攻擊下的安全性.Degabriele 等人[8]在此基礎(chǔ)上提出了改進(jìn)的“檢測-監(jiān)視游戲” 的模型, 在此模型中, 檢測者并不關(guān)注算法是否被篡改, 而僅關(guān)注敵手是否通過被顛覆的算法獲取敏感信息. 在新定義的檢測游戲中, 檢測者可以獲取監(jiān)視游戲中的交互副本. Bellare 等人[18]參考Degabriele 等人[8]的觀點(diǎn), 改進(jìn)了文獻(xiàn)[7] 中的模型,對敵手提出了更高的要求, 要求其在監(jiān)視游戲中能夠返回完整的用戶密鑰.

Russel 等人[6]總結(jié)了文獻(xiàn)[5,7,8] 等研究中安全性定義的思想, 提出了改進(jìn)的kleptography 并命名為cliptography. cliptography 模型將檢測算法抽象為一個概念-看門狗(watchdog). 根據(jù)強(qiáng)度不同, 看門狗分為離線看門狗(oラine watchdog), 在線看門狗(online watchdog) 和全知看門狗(omniscient 看門狗). Russel 等人[6]提出了無隱寫性的安全目標(biāo), 即, 對于某密碼體制以及其所有的執(zhí)行, 要么不存在能夠區(qū)分該執(zhí)行的輸出與算法說明的輸出的PPT 敵手, 要么存在可以區(qū)分該執(zhí)行與算法說明的看門狗.

Ateniese 等人[12]在對顛覆攻擊的分析中引入了公開隨機(jī)源, 并提出了相應(yīng)的安全模型. 根據(jù)公開隨機(jī)源性質(zhì)的不同, Ateniese 等人將安全模型分為半私人、公共和透明三類. 在定義安全性時, Ateniese 等人將看門狗的檢測優(yōu)勢與使用顛覆算法情況下在傳統(tǒng)游戲中敵手的優(yōu)勢相比較, 如看門狗的優(yōu)勢始終大于敵手優(yōu)勢的常數(shù)倍, 則認(rèn)為該密碼體制安全. 此外, Ateniese 等人[12]把所有游戲分為約束性游戲和非約束性游戲, 以此決定在分析中選用離線看門狗還是在線看門狗.

此外, Ateniese 等人[19]、Dodis 等人[20]、Russell 等人[21]分別提出了針對顛覆威脅下簽名體制、偽隨機(jī)數(shù)生成器和隨機(jī)喻言機(jī)的形式化安全模型.

1.2.2 顛覆威脅下的防御方法研究

Bellare 等人[7]將所有明文最多只對應(yīng)唯一合法密文的加密體制定義為唯一密文體制, 并證明了唯一密文體制在“檢測-監(jiān)視游戲” 中的安全性.

Mironov 等人[9]提出了密碼反向防火墻(cryptographic reverse fire, CRF) 的概念. CRF 是部署于用戶密碼系統(tǒng)與外部之間的設(shè)備, 對所有用戶與外界交互的信息進(jìn)行處理. CRF 的特殊性在于, 一方面其被假設(shè)為是不可顛覆的, 即一定能夠誠實地執(zhí)行相應(yīng)算法; 另一方面, CRF 又被假設(shè)為公共設(shè)備, 不可獲取用戶的隱私信息(如密鑰等). Mironov 等人[9]通過功能保留性, 安全保留性與抗泄露性對CRF 進(jìn)行了形式化定義. Dodis 等人[22]繼續(xù)針對CRF 定義了檢測可失敗的概念, 并利用再隨機(jī)化加密體制為消息傳輸協(xié)議中的雙方設(shè)計了CRF 的通用構(gòu)造方法. Chen 等人[23]在平滑映射哈希函數(shù)[24]概念的基礎(chǔ)上提出了可延展平滑映射哈希函數(shù), 并基于此設(shè)計了CRF 的通用構(gòu)造方法.

Fischlin 等人[10]提出了自守衛(wèi)密碼體制. 其安全性基于一個假設(shè)可信的運(yùn)行階段, 稱為“安全啟動階段”. 在安全啟動階段中使用者可運(yùn)行可信的算法獲取部分隨機(jī)元素, 在其后的運(yùn)行階段這些隨機(jī)元素可被調(diào)用. Fischlin 等人[10]對El-Gamal 等常用密碼體制設(shè)計了自守衛(wèi)密碼體制的構(gòu)造方法.

Russel 等人[11]設(shè)計了“分割-融合模型”, 將一個完整的密碼算法分割為若干個子模塊, 所有子模塊融合在一起實現(xiàn)原算法的功能. Russel 等人在cliptography 模型下, 通過引入隨機(jī)喻言模型, 設(shè)計了具有無隱寫性的密碼體制的通用構(gòu)造方法. 此外, Russel 等人還在子模塊個數(shù)可以不為常數(shù)的前提下, 設(shè)計了無需隨機(jī)喻言機(jī)的無隱寫密碼體制.

Horel 等人[25]在抗顛覆防御方法的設(shè)計中引入了隱寫體制的思想. 他們利用顛覆的加密算法對于除監(jiān)視者本身以外的實體仍需要滿足特定安全性的性質(zhì), 設(shè)計了一種消息傳輸協(xié)議, 將真正需要傳輸?shù)南⑶度氲矫芪闹? 從而在通信雙方之間建立“潛信道”. Horel 等人的方案實現(xiàn)了當(dāng)監(jiān)視者能夠?qū)γ芪倪M(jìn)行解密的情況下, 被嵌入了消息的副本仍然與正常執(zhí)行顛覆算法產(chǎn)生的副本計算上不可區(qū)分.

Ateniese 等人[12]設(shè)計了通過引入一個公開的隨機(jī)源實現(xiàn)防御的方法. 分別在公開隨機(jī)源產(chǎn)生的隨機(jī)數(shù): (1) 可信但可被敵手獲知; (2) 可信但可被敵手和顛覆算法獲知; (3) 不可信的情況下, 設(shè)計了顛覆威脅下安全密碼體制的通用構(gòu)造方法.

Li 等人[13,26]設(shè)計了通過采用來源于不同監(jiān)視者的算法執(zhí)行構(gòu)造抗顛覆的密碼體制的方法. 在不同敵手完全隔絕的情況下, Li 等人[13]設(shè)計了一種安全的消息傳輸協(xié)議, 能夠?qū)崿F(xiàn)協(xié)議的副本對于所有敵手,要么與算法說明的輸出不可區(qū)分, 要么與誠實地執(zhí)行該敵手給出的顛覆執(zhí)行產(chǎn)生的副本不可區(qū)分. 在不同敵手之間可通過不同形式進(jìn)行有限交流的情況下, Li 等人[26]分別基于“分割-融合模型” 設(shè)計了滿足無隱寫性的對稱密碼體制的構(gòu)造方法.

1.3 本文組織結(jié)構(gòu)

第2 節(jié)介紹了本文中使用的主要表示方法即相關(guān)預(yù)備知識. 第3 節(jié)提出了抗顛覆安全保留性的概念,并形式化分析了其與無隱寫性定義之間的關(guān)系. 第4 節(jié)提出了算法隔離運(yùn)行的概念, 并論證了其在特定條件下的必要性. 第5 節(jié)分別在部分顛覆模型與完全顛覆模型下, 基于算法隔離運(yùn)行的方法設(shè)計了滿足抗顛覆安全保留性的對稱加密體制.

2 預(yù)備知識

2.1 表示方法定義

2.2 隨機(jī)數(shù)生成器

定義1 給出了隨機(jī)數(shù)生成器的形式化定義方法. 為了合理簡化分析, 本文忽略了除安全參數(shù)以外的隨機(jī)數(shù)生成器的其他輸入.

定義1令隨機(jī)數(shù)生成器Rg 的輸入為安全參數(shù)λ, 輸出為? 比特隨機(jī)字串. 如果對于所有的PPT 敵手A, r ←Rg(λ), 有

則稱Rg 滿足不可識別性.

2.3 偽隨機(jī)置換

本文使用了文獻(xiàn)[27] 中對于偽隨機(jī)置換算法的定義.

定義2[27]令PER={Pers} (s ∈S) 為{0,1}?上帶有密鑰的置換, Π?代表{0,1}?上所有置換的集合. 如果對于所有的PPT 敵手A,

則稱PER 為偽隨機(jī)置換.

2.4 無隱寫性

Russel 等人[11]定義了密碼算法在顛覆威脅下無隱寫性的概念, 本文使用其通用形式, 具體地,

定義3[11]考慮算法說明為Fspec的算法F, 如果存在看門狗算法W, 對于所有參與如圖2 中游戲的PPT 敵手A, 其中Fimpl為對應(yīng)于算法說明Fspec的執(zhí)行, IG 為算法應(yīng)用的輸入變量生成器.

其中

則稱Fspec滿足無隱寫性.

2.5 IND-CPA 安全

定義對稱密碼體制的IND-CPA 安全性如下:

定義4記對稱加密體制SE={K,E,D}, 其中K:1λ→K 為密鑰生成算法, E:K×M →C 為加密算法, D:K×C →M 為解密算法. 定義

其中, 游戲IND-CPA 如圖3 所示, 則稱密碼體制SE 滿足IND-CPA 安全.

圖2 無隱寫性游戲(通用形式)Figure 2 Game for stego-freeness (general form)

圖3 IND-CPA 游戲Figure 3 Game for IND-CPA

3 密碼體制的抗顛覆安全保留性

相對于當(dāng)前普遍使用的刻畫顛覆威脅下密碼體制安全性的無隱寫定義, 本節(jié)結(jié)合相關(guān)研究, 提出了抗顛覆安全保留性. 第3.1 節(jié)給出了抗顛覆安全保留性的形式化定義, 第3.2 節(jié)分析了其與無隱寫性之間的關(guān)系, 并證明了滿足抗顛覆安全保留性的密碼體制要多于滿足無隱寫性的密碼體制.

3.1 密碼體制的抗顛覆安全保留性

為了刻畫顛覆威脅下密碼算法的安全性, 本節(jié)形式化定義了密碼體制的抗顛覆安全保留性. 安全保留性的定義思想較為直觀, 相對于Russel 等人在文獻(xiàn)[6] 中提出的密碼體制的無隱寫性(詳見定義3), 其不再要求被顛覆的密碼執(zhí)行的輸出與純凈算法的輸出計算上不可區(qū)分, 而僅僅要求密碼體制即使在被顛覆的情況下仍能實現(xiàn)原體制的具體安全性. 實際上, 在Degabriele 等人[8]、Ateniese 等人[12]和Chow 等人[14]對于顛覆威脅下密碼體制的安全分析中, 也使用了此種思路定義了若干種具體的安全性, 本文所提出的抗顛覆安全保留性可視為對此類安全定義的通用形式表達(dá).

為了涵蓋現(xiàn)實中各種不同權(quán)限的監(jiān)視者,本模型兼顧部分顛覆和完全顛覆兩種情況②如果監(jiān)視者能夠顛覆密碼體制中的所有算法, 則稱為完全顛覆; 如果監(jiān)視者僅能夠顛覆密碼體制中的部分算法(例如在加密體制中能夠顛覆加解密算法, 而不能顛覆密鑰生成算法), 則稱為部分顛覆.,并使用了“分割-融合模型”[11]中的分析思路. 設(shè)密碼體制Π 在執(zhí)行中被拆分為若干個模塊{I1,I2,··· ,In,S1,S2,··· ,Sn},其中, Ii為暴露于顛覆威脅下的模塊(若考慮完全顛覆, 則無Si). 本模型仍然使用Bellare 等人[7]監(jiān)視游戲加檢測游戲的框架, 具體的:

監(jiān)視游戲:由挑戰(zhàn)者和監(jiān)視者參與. 其中監(jiān)視者根據(jù)其行為被劃分成兩個階段, 第一階段的監(jiān)視者用A1表示, A1根據(jù)相關(guān)算法的說明, 產(chǎn)生對應(yīng)的顛覆執(zhí)行. 第二階段的監(jiān)視者用A2表示, A2與挑戰(zhàn)者運(yùn)行一般的安全定義游戲, 游戲中挑戰(zhàn)者訪問的是經(jīng)過顛覆后的密碼體制, 這一過程用A2(·)G?C^F(·)(·) 簡化表示, 其中為經(jīng)顛覆的算法執(zhí)行. 具體的, 定義監(jiān)視者的監(jiān)視優(yōu)勢:

其中監(jiān)視游戲SURV 如圖4 所示, γ 為常數(shù).

檢測游戲:安全保留性的定義沿用了Russel 等人[6]cliptography 模型中在線看門狗的概念. 檢測游戲由挑戰(zhàn)者和看門狗參與, 看門狗試圖在游戲中判斷挑戰(zhàn)者給出的黑盒算法是純凈的算法還是經(jīng)監(jiān)視者顛覆的算法. 具體的, 定義看門狗的檢測優(yōu)勢:

其中檢測游戲DET 如圖4 所示.

圖4 抗顛覆安全保留性定義游戲Figure 4 Games for definition of security-preservation against subversion

基于監(jiān)視優(yōu)勢和檢測優(yōu)勢, 定義密碼體制的抗顛覆安全保留性:

3.2 安全保留性與無隱寫性的關(guān)系

從定義形式上看, 無隱寫性強(qiáng)調(diào)顛覆執(zhí)行與算法說明之間的對比, 以二者對敵手的不可區(qū)分來定義顛覆威脅下的安全性. 其定義過程并不體現(xiàn)密碼體制要實現(xiàn)的具體安全目標(biāo). 安全保留性則從密碼體制旨在實現(xiàn)的具體安全性出發(fā), 僅對顛覆執(zhí)行進(jìn)行分析. 鑒于在顛覆攻擊發(fā)生的情況下, 用戶信息的安全性取決于顛覆執(zhí)行的安全性, 因此抗顛覆安全保留性是一種更為直觀的定義方式, 直接刻畫了現(xiàn)實安全需求.

cliptography 主要關(guān)注密碼體制被不誠實執(zhí)行時的安全性, 因此相關(guān)研究都默認(rèn)作為研究對象的密碼體制被誠實執(zhí)行時是安全的. 在此前提下, Russel 等人[6]定義的無隱寫性不弱于3.1 節(jié)中密碼體制的安全保留性. 詳細(xì)定理描述如下.

定理1如果密碼體制Π 的說明是(G,γ) 安全的, 且其能夠滿足無隱寫性, 則其一定滿足抗顛覆-(G,γ)-安全保留性.

證明:假設(shè)Π 不滿足抗顛覆-(G,γ)-安全保留性, 即存在PPT 敵手A = (A1,A2), 對于所有PPT算法W, 有則可以構(gòu)造PPT 敵手A′= (A′1,A′2), 其調(diào)用敵手A 以攻破密碼體制Π 的無隱寫性. A′具體可采取以下策略:

因此, Π 也不滿足無隱寫性, 定理1 得證.

另一方面, 如果某密碼體制不滿足無隱寫性, 則必定存在這樣的顛覆執(zhí)行, 能夠通過其輸出向監(jiān)視者至少泄露一比特信息. 在此類情況下, 如果密碼體制中所有的顛覆算法都能夠掌握用戶的關(guān)鍵隱私信息,則密碼體制顯然亦不滿足抗顛覆安全保留性(相關(guān)證明詳見第4.1 節(jié)). 然而, 如果在密碼系統(tǒng)的工程實現(xiàn)過程中采取一定措施, 以限制算法執(zhí)行的信息知悉范圍, 則有可能實現(xiàn)不滿足無隱寫性但滿足抗顛覆安全保留性的體制, 具體的定義及設(shè)計詳見第5 節(jié). 因此, 綜合本文論據(jù), 密碼體制無隱寫性的安全性要高于抗顛覆安全保留性, 此方面具體討論見第6 節(jié).

4 算法隔離運(yùn)行

本節(jié)提出了算法隔離運(yùn)行的防御方法. 第4.1 節(jié)證明了在所有顛覆算法都能夠獲取全部用戶數(shù)據(jù)的情況下, 不滿足無隱寫性的密碼體制也不滿足抗顛覆安全保留性, 此否定性結(jié)論表明了限制部分顛覆執(zhí)行知悉范圍對于設(shè)計可行性更強(qiáng)的抗顛覆防御方法的是非常必要的. 第4.2 節(jié)給出了算法隔離運(yùn)行的形式化表示方法.

4.1 顛覆算法全知悉條件下的否定性結(jié)論

本文的主要目的之一在于重新審視cliptography 模型[6]中算法無隱寫性安全目標(biāo)的現(xiàn)實合理性, 試圖在保證算法實際安全的前提下, 適當(dāng)下調(diào)顛覆威脅下的安全目標(biāo), 為設(shè)計更加實用的抗顛覆防御策略提供理論基礎(chǔ). 第3.1 節(jié)提出了抗顛覆安全保留性的概念, 并形式化證明了抗顛覆安全保留性是算法無隱寫性的必要條件. 然而, 在密碼算法的實現(xiàn)過程缺少特定限制的情況下, 難以保證抗顛覆安全保留性真正弱于無隱寫性, 而體現(xiàn)其實際意義.

本節(jié)以對稱加密算法為例. 記對稱加密體制SE={K,E,D} 的目標(biāo)安全為IND-CPA(詳見定義4), 其中K:1λ→{0,1}κ為密鑰生成算法, E:{0,1}κ×{0,1}?→{0,1}n為加密算法, D:{0,1}κ×{0,1}n→{0,1}?為解密算法. 為了使結(jié)論更具一般性, 考慮部分顛覆, 即僅加密算法E 處于顛覆威脅下的情況(全顛覆模型亦包含此種情況). 針對加密算法E, 我們將密鑰k 與消息m 記為業(yè)務(wù)數(shù)據(jù). E 在“分割-融合模型” 下被分割為若干子算法{Sub-Ei}. 可以證明在所有子算法均可獲取業(yè)務(wù)數(shù)據(jù)時, 如果SE 不滿足無隱寫性, 則其亦不滿足抗顛覆安全保留性. 因為此時可以利用攻破無隱寫性的顛覆執(zhí)行, 逐比特泄露用戶的密鑰. 詳細(xì)定理描述如下.

定理2對于目標(biāo)安全為IND-CPA 的對稱加密體制SE, 如果加密算法E 的所有子算法{Sub-Ei} 的執(zhí)行均可獲取業(yè)務(wù)數(shù)據(jù)(k,m), 則如果SE 不滿足無隱寫性, 其亦不滿足抗顛覆-(IND-CPA,1/2)-安全保留性.

證明:假設(shè)存在PPT 敵手A, 能夠破壞SE 的無隱寫性, 則可構(gòu)造PPT 敵手A′, 其模擬挑戰(zhàn)者與A 運(yùn)行無隱寫游戲, 破壞SE 的抗顛覆-(IND-CPA,1/2)-安全保留性. A′具體執(zhí)行以下策略:

由定理2 及定理1 可知, 在顛覆算法對用戶業(yè)務(wù)數(shù)據(jù)全知悉的情況下, 不可能構(gòu)造安全性介于無隱寫性與抗顛覆安全保留性之間的密碼體制. 因此對顛覆執(zhí)行的知悉范圍進(jìn)行限制, 是構(gòu)造實用性更強(qiáng)的抗顛覆攻擊防御方法的思路之一.

4.2 算法隔離運(yùn)行模型

為了設(shè)計更加實用的抗顛覆防御策略, 構(gòu)造屬于圖1 中B 區(qū)的密碼體制, 本節(jié)在“分割-融合模型” 的基礎(chǔ)上, 提出算法隔離運(yùn)行的密碼體制工程實現(xiàn)方法. 其基本思想為在對密碼算法進(jìn)行分割后, 將部分子算法的執(zhí)行置于一個與用戶業(yè)務(wù)數(shù)據(jù)“隔離” 的環(huán)境下運(yùn)行, 即, 使之無法接觸用戶的密鑰、消息等關(guān)鍵信息.

關(guān)于如何實現(xiàn)算法隔離運(yùn)行, 較為簡單的思路之一為對相關(guān)算法進(jìn)行預(yù)先運(yùn)行, 即, 在用戶私鑰、明文產(chǎn)生之前, 先運(yùn)行被隔離的算法獲取其輸出, 此舉實際上避免了相關(guān)算法得到用戶敏感信息. 此外, 通過密碼系統(tǒng)內(nèi)部硬件隔離、控制被隔離算法可讀取的信息列表等方法也能夠?qū)崿F(xiàn)算法隔離運(yùn)行的效果, 相關(guān)具體工程實現(xiàn)手段超出了本文討論的范疇, 在此不做具體討論.

5 基于算法隔離運(yùn)行的抗顛覆安全保留的對稱密碼體制

本節(jié)基于算法隔離運(yùn)行思想, 通過引入偽隨機(jī)置換、計算強(qiáng)提取器等工具, 在第5.1節(jié)和第5.3節(jié)中分別在部分顛覆模型和完全顛覆模型下設(shè)計了抗顛覆安全保留的對稱加密體制, 并在第5.2節(jié)和第5.4節(jié)中給出了相應(yīng)的安全性分析.

5.1 部分顛覆模型下基于隔離運(yùn)行的對稱密碼體制設(shè)計

本節(jié)考慮部分顛覆模型下的對稱密碼體制設(shè)計. 其中假設(shè)密鑰生成算法可以被誠實執(zhí)行, 而加密算法和解密算法處于顛覆威脅下. 在本方案的設(shè)計中引入了第2.3 節(jié)中定義的偽隨機(jī)置換. 加密算法E 被分割為以下兩個部分:

- Rg:1λ→{0,1}?, 隨機(jī)數(shù)生成器, 其算法說明滿足定義1中的不可識別性.

圖5 算法隔離運(yùn)行Figure 5 Isolated operation of cryptographic scheme

- Per : {0,1}κ× {0,1}?→{0,1}?, 偽隨機(jī)置換算法, 其算法說明滿足定義2 中的安全性. 其中{0,1}κ為密鑰空間.

圖6 部分顛覆模型下基于隔離運(yùn)行的對稱加密算法和解密算法Figure 6 Symmetric encryption algorithm based on isolated operation in partial subversion

5.2 安全性分析

在隔離運(yùn)行假設(shè)的基礎(chǔ)上, 圖6 中的加密體制仍能在顛覆威脅下保證IND-CPA 安全性. 詳細(xì)定理描述如下.

定理3圖6 中的加密體制在部分顛覆模型下滿足抗顛覆-(IND-CPA,1/2)-安全保留性.

證明:假設(shè)定理3 不成立, 即, 存在PPT 敵手A, 對于任何的PPT 看門狗W, 使得

其與式(2) 矛盾, 命題得證.

5.3 完全顛覆模型下基于隔離運(yùn)行的對稱密碼體制設(shè)計

本節(jié)繼續(xù)討論在完全顛覆模型下基于隔離運(yùn)行的對稱密碼體制的構(gòu)造. 完全顛覆指密碼體制中包括密鑰生成算法在內(nèi)的所有算法均處于顛覆風(fēng)險下, 這給抗顛覆密碼體制的設(shè)計帶來了更大的難度.

為了在缺少可信隨機(jī)源的情況下獲取計算上均勻隨機(jī)的字符串, Russel 等人[11]設(shè)計了使用非常數(shù)個隨機(jī)單比特生成器產(chǎn)生隨機(jī)字符串的方法, 即, 無狀態(tài)的單比特隨機(jī)源每次僅輸出一個隨機(jī)比特, 將多次輸出串聯(lián), 可得到一個與均勻隨機(jī)字符串統(tǒng)計不可區(qū)分的隨機(jī)串. 詳細(xì)描述如引理1,

其中? 為λ 的可忽略函數(shù).

引理1 的證明詳見文獻(xiàn)[11] 附錄D, 本文中不再重復(fù). Russel 等人[11]基于引理1 中的方法獲取計算上均勻隨機(jī)的密鑰和隨機(jī)數(shù), 構(gòu)造了抗顛覆安全的加密體制. 本節(jié)設(shè)計的方法與Russel 等人設(shè)計的方案有類似之處, 但重要區(qū)別之一在于, 本節(jié)的方案不需要保證密鑰和加密過程中產(chǎn)生的隨機(jī)數(shù)二者同時計算上均勻隨機(jī), 而只需要保證其中一個與均勻隨機(jī)字串不可區(qū)分, 另一個滿足高熵值的條件即可. 相比于Russel 等人的設(shè)計, 這樣有效減少了單比特隨機(jī)源的使用數(shù)量, 降低了密碼體制的實現(xiàn)成本和運(yùn)行效率.

圖7 完全顛覆模型下基于隔離運(yùn)行的對稱加密算法和解密算法Figure 7 Symmetric encryption/decryption algorithm based on isolated operation in complete-subversion

由此, 基于定理3 和引理1, 能夠直接給出定理4.

定理4圖7 中的加密體制在完全顛覆模型下滿足抗顛覆-(IND-CPA,1/2)-安全保留性.

此外, 本節(jié)設(shè)計了另一種滿足抗顛覆安全保留性的對稱密鑰體制構(gòu)造方法, 其中用戶的對稱密鑰不再與均勻隨機(jī)字串計算上不可區(qū)分,而只能保證a-bit 的最小熵. 本節(jié)針對此情況下的設(shè)計,參考了Ateniese等人在文獻(xiàn)[12] 中引入計算提取器(computational extractor) 的思想.

定義6[12]如果對于所有最小熵為a 的隨機(jī)變量X ∈{0,1}n, 和所有運(yùn)行時間為t 的識別算法D,哈希族H:{hs:{0,1}n→{0,1}m}s∈{0,1}?滿足

其中? 為λ 的可忽略函數(shù), 則稱其為(n,m,a,t,?)-計算強(qiáng)提取器族.

Guruswami 等人[28]證明了計算強(qiáng)提取器族的存在性并給出了其具體構(gòu)造.

加密體制被分割為以下若干模塊:

- Kgen:1λ→{0,1}n/a, 密鑰生成子算法, 產(chǎn)生n/a-bit 的均勻隨機(jī)字符串.

- Rg:1λ→{0,1}, 單比特隨機(jī)數(shù)生成器, 其算法說明滿足第2.2 節(jié)中定義的不可識別性.

- hr:{0,1}n→{0,1}m, (r ∈{0,1}?), (n,m,a,t,?)-計算強(qiáng)提取器.

圖8 完全顛覆模型下基于隔離運(yùn)行的對稱加密體制Figure 8 Symmetric encryption algorithm based on isolated operation in complete-subversion

5.4 安全性分析

在隔離運(yùn)行假設(shè)的基礎(chǔ)上, 圖8 中的加密體制仍能在顛覆威脅下保證IND-CPA 安全性. 詳細(xì)定理描述如下.

定理5圖8 中的加密體制在部分顛覆模型下滿足抗顛覆-(IND-CPA,1/2)-安全保留性.

證明:假設(shè)定理5 不成立, 即, 存在PPT 敵手A, 對于任何PPT 的看門狗W, 使得

其與式(4) 矛盾, 命題得證.

采用第5.2 節(jié)中描述的基于“采樣-拒絕” 的攻擊方法, 同樣可以證明圖7 和圖8 中的加密方案并不滿足無隱寫性. 因此第5.3 節(jié)中兩種方案的安全性也介于抗顛覆安全保留性與無隱寫性之間.

6 結(jié)論

為了分析顛覆威脅下密碼體制的安全性, 本文提出了抗顛覆安全保留性的概念. 抗顛覆安全保留性要求所有能通過黑盒測試的顛覆執(zhí)行均能實現(xiàn)原定的目標(biāo)安全性. 相比于當(dāng)前普遍使用的用于分析顛覆攻擊的無隱寫性, 抗顛覆安全保留性從定義形式上更加直接地反映了現(xiàn)實需求.

一方面, 本文形式化證明了所有滿足無隱寫性的密碼體制均滿足抗顛覆安全保留性. 另一方面, 本文通過設(shè)計算法隔離運(yùn)行的防御策略, 構(gòu)造了安全性介于無隱寫性與安全保留性之間的密碼體制, 證明了無隱寫性集合是抗顛覆安全保留性集合的真子集. 綜合以上論據(jù), 可以得出如圖1 所示的邏輯關(guān)系.

在現(xiàn)有針對于大規(guī)模監(jiān)視的研究中, 研究人員始終試圖在A 區(qū)構(gòu)造密碼體制, 而忽略了B 區(qū)的存在.鑒于當(dāng)前針對A 區(qū)缺少可行性較高的防御方法, 而以算法隔離運(yùn)行為代表的針對B 區(qū)的防御方法具有較強(qiáng)的現(xiàn)實可操作性, 因此抗顛覆安全保留性的提出, 對于重新審視并調(diào)整顛覆威脅下的安全目標(biāo), 構(gòu)建更加實用的抗顛覆密碼體制, 具有重要的意義.