大規(guī)模監(jiān)視下安全性定義再分析*

李 耕, 劉建偉, 張宗洋

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

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

1 引言

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

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

新的安全威脅受到了密碼學(xué)理論界的持續(xù)關(guān)注, 研究人員對(duì)大規(guī)模監(jiān)視的攻擊手段進(jìn)行重新分析, 逐步建立了后斯諾密碼學(xué)框架. 與傳統(tǒng)密碼學(xué)的重要不同在于, 后斯諾密碼學(xué)刻畫了敵手對(duì)密碼算法進(jìn)行“顛覆” 的過(guò)程, 即, 敵手可根據(jù)算法說(shuō)明(specification), 通過(guò)嵌入后門等手段, 給出顛覆后的算法執(zhí)行(implementation). 而算法執(zhí)行對(duì)于使用者而言被建模為黑盒, 使用者無(wú)法獲取其內(nèi)部的運(yùn)算過(guò)程, 只能通過(guò)輸入輸出來(lái)判斷其是否誠(chéng)實(shí)地按照算法說(shuō)明執(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é)所定義的安全性外, 對(duì)于任何敵手給出的執(zhí)行, 要么從用戶角度能夠區(qū)分其輸出與算法說(shuō)明的輸出, 要么敵手自身也無(wú)法區(qū)分其輸出與算法說(shuō)明的輸出. Russel 等人[6]將這種思想形式化表示為無(wú)隱寫性(stego-freeness).

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

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

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

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

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

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

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

1.1 本文貢獻(xiàn)

1.1.1 抗顛覆職能安全

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

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

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

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

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

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

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

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

1.2 相關(guān)研究

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

早在“棱鏡門” 事件發(fā)生之前, Young 等人[5,15-17]就已對(duì)密碼體制執(zhí)行遭受敵手篡改的情況進(jìn)行過(guò)研究, 他們將此類攻擊方法概括為通用保護(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]又通過(guò)游戲的方式形式化定義了強(qiáng)SETUP. Young 等人[5,15]針對(duì)常用的密碼體制, 如RSA、El-Gamal、DSA、Kerberos 協(xié)議等設(shè)計(jì)了攻擊方法并證明了其有效性.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 預(yù)備知識(shí)

2.1 表示方法定義

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

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

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

則稱Rg 滿足不可識(shí)別性.

2.3 偽隨機(jī)置換

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

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

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

2.4 無(wú)隱寫性

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

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

其中

則稱Fspec滿足無(wú)隱寫性.

2.5 IND-CPA 安全

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

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

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

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

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

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

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

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

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

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

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

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

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

其中檢測(cè)游戲DET 如圖4 所示.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 部分顛覆模型下基于隔離運(yùn)行的對(duì)稱加密算法和解密算法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, 對(duì)于任何的PPT 看門狗W, 使得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖8 完全顛覆模型下基于隔離運(yùn)行的對(duì)稱加密體制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, 對(duì)于任何PPT 的看門狗W, 使得

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

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

6 結(jié)論

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

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

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