抗大規(guī)模監(jiān)視密碼學研究綜述*

李 耕, 劉建偉, 張宗洋,2

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

2.中國科學院信息工程研究所信息安全國家重點實驗室, 北京100093

1 引言

2013年6月, 美國國家安全局(National Security Agency, NSA)爆發(fā)“棱鏡門” 事件, 前中央情報局職員愛德華· 斯諾登(Edward Snowden)爆料美國國家安全局和聯(lián)邦調(diào)查局(Federal Bureau of Investigation, FBI)通過潛入各大網(wǎng)絡巨頭的服務器, 監(jiān)控美國公民的個人信息[1].后續(xù)爆料揭露NSA一直嘗試對全球通信網(wǎng)絡進行攻擊, 對世界各國重要領(lǐng)域的通信內(nèi)容進行竊聽[2].斯諾登的爆料震驚了世界, 使得人們對當前信息安全技術(shù)的可靠性產(chǎn)生了質(zhì)疑.

“棱鏡門” 及相關(guān)事件所涉及的竊密方法有部分與密碼學直接相關(guān).當前并沒有公開證據(jù)表明美國情報機構(gòu)能夠有效破解各種常用密碼體制所基于的數(shù)學難題[3], 但是卻有證據(jù)顯示這些機構(gòu)能通過一些非正常手段攻破密碼系統(tǒng).例如, NSA 操縱標準化組織強行通過隱含后門的標準: Dual_EC_DRBG[4].Dual_EC_DRBG 在密碼學中起著偽隨機數(shù)生成器的作用, 它由NSA 內(nèi)部員工設計, 跳過了形式化證明[5], NSA 通過不正當手段使其被國家標準技術(shù)研究所(National Institute of Standards and Technology, NIST)、美國國家標準學會(American National Standard Institute, ANSI)和國際標準化組織(International Organization for Standardization, ISO)等組織推薦成相關(guān)標準, 在這些標準所推薦的參數(shù)里, Dual_EC_DRBG 的設計者可以嵌入后門, 使得在獲取隨機數(shù)生成器足夠長的輸出后, 后門擁有者可以預測后續(xù)輸出結(jié)果, 這就使得偽隨機數(shù)生成器的安全性不復存在.Bernstein 等人[6]回顧了Dual_EC_DRBG 的設計歷史和標準化過程, 解釋了其后門在實際中是如何運行的, 并對NSA 所起的不光彩作用進行了深刻的揭露和批判.這種在大規(guī)模監(jiān)視(mass-surveillance)的背景下, 對密碼體制進行篡改和惡意設計、對算法的執(zhí)行過程加入非安全因素的攻擊方法跳脫了傳統(tǒng)密碼學的考慮范疇, 使得一些在傳統(tǒng)密碼學分析方法下被認為是安全的密碼體制不再安全.

針對這些新問題, 抗大規(guī)模監(jiān)視密碼學成為密碼學理論研究的一個新方向, 逐漸受到國內(nèi)外學者的廣泛關(guān)注.總體來說, 當前電子設備使用快速普及, 重要領(lǐng)域以及個人數(shù)據(jù)信息價值凸顯, 各國對網(wǎng)絡情報搜集需求上升, 密碼體制應用日趨復雜化, 閉源模塊與器件的廣泛使用, 以及以“棱鏡門” 為代表的一系列信息安全事件構(gòu)成的導火索, 共同推動了這一新方向的產(chǎn)生.抗大規(guī)模監(jiān)視密碼學是傳統(tǒng)密碼學的延伸, 是密碼學對新的實際情況所做的適應, 其產(chǎn)生和發(fā)展具有一定的合理性.

本文結(jié)合該領(lǐng)域當前主要成果, 對抗大規(guī)模監(jiān)視密碼學做了較為全面的介紹, 具體貢獻如下:

(1)提煉了抗大規(guī)模監(jiān)視密碼學的一般特征, 總結(jié)了諸如IV 替換攻擊、偏密文攻擊、輸入觸發(fā)攻擊等各種攻擊方法, 基于監(jiān)視-檢測、watchdog 等安全模型, 以及分割-融合、自防御、密碼反向防火墻等各種安全防御方法;

(2)從單向函數(shù)、偽隨機數(shù)生成器、加密體制、簽名體制、密碼協(xié)議等方面介紹了該領(lǐng)域主要結(jié)論及相關(guān)最新進展, 理清了發(fā)展脈絡, 并對研究動向做了一定的展望.

本文組織結(jié)構(gòu)如下: 第2 節(jié)介紹了抗大規(guī)模監(jiān)視密碼學的基本特征與當前研究布局; 第3 節(jié)介紹了抗大規(guī)模監(jiān)視的加密和簽名體制研究; 第4 節(jié)介紹了抗大規(guī)模監(jiān)視的密碼學原語研究; 第5 節(jié)介紹了抗大規(guī)模監(jiān)視的密碼協(xié)議研究; 第6 節(jié)介紹了抗大規(guī)模監(jiān)視密碼學其他研究方向; 第7 節(jié)對當前抗大規(guī)模監(jiān)視密碼學的研究工作做了總結(jié)和展望.

2 抗大規(guī)模監(jiān)視密碼學基本特征與研究布局

傳統(tǒng)密碼學針對密碼體制的安全性分析, 一般默認目標算法能夠正確地被執(zhí)行, 在此基礎(chǔ)上進行形式化分析.然而在大規(guī)模監(jiān)視密碼學中, 為了更準確地反映實際情況, 不再無條件保證算法的正確執(zhí)行, 將密碼算法的執(zhí)行階段視作博弈的一個環(huán)節(jié).這是因為實際中大量的密碼相關(guān)單元屬于閉源模塊.另外, 由于密碼算法的復雜度日益增大, 通過代碼本身來分析算法安全性的難度也迅速增大(例如心臟滴血漏洞在程序源代碼公開近兩年后才被發(fā)現(xiàn)[7]).安全防御一方僅能通過分析算法的輸入與輸出判斷其執(zhí)行的正確性.

Schneier 等人[8]在分析惡意弱化密碼體制的行為時, 將新環(huán)境下各個實體概括如下:

(1)破壞者(Saboteur): 通過惡意篡改等各種方式對密碼體制本身進行弱化的一方;

(2)受害者(Victim): 被弱化的密碼體制的使用者;

(3)攻擊者(Attacker): 試圖利用弱點攻擊受害者的一方;

(4)防御者(Defender): 基于安全目的設計密碼體制的一方.

這種概括在一定程度上可以代表大規(guī)模監(jiān)視背景下圍繞密碼體制的博弈形式.

由于上述基礎(chǔ)假設的變更, 抗大規(guī)模監(jiān)視密碼學與傳統(tǒng)密碼學在安全性的定義上產(chǎn)生了分歧.在大規(guī)模監(jiān)視密碼學中出現(xiàn)了諸如算法替換攻擊、參數(shù)替換攻擊等一系列新型攻擊方式.密碼學體系的各個組成部分, 如密碼學原語(單向函數(shù)、偽隨機數(shù)生成器等)、加密、數(shù)字簽名和密碼協(xié)議等等, 其安全性需要重新進行分析.面對新的威脅, 一方面, 可以對這些密碼學構(gòu)件重新設計, 如采用分割-融合技術(shù)等對密碼算法進行重新設計, 以保證在新威脅下的安全性; 另一方面, 也有部分研究提出引入一些新的方式和機制, 如密碼反向防火墻等, 保證密碼體制的安全性.鑒于抗大規(guī)模監(jiān)視背景下, 攻擊與防御的形式和方式更為復雜, 如何對實際情況進行抽象, 總結(jié)出合理的形式化安全模型, 用以分析上述所有攻擊和防御方法的有效性, 也是該領(lǐng)域當前核心研究內(nèi)容之一.以上內(nèi)容構(gòu)成了抗大規(guī)模監(jiān)視密碼學總體研究布局, 如圖1 所示.

圖1 抗大規(guī)模監(jiān)視密碼學Figure 1 Cryptography against mass surveillance

3 抗大規(guī)模監(jiān)視加密和簽名體制研究

相關(guān)方面的研究最早可追溯到1983年, Simons[9]指出惡意修改密碼體制的實現(xiàn)方式會弱化其安全性.攻擊者在密碼體制中, 利用公鑰加密、數(shù)字簽名等密碼技術(shù)建立起一種隱蔽信道, 除指定接收者外, 其他人都無從知曉通信信息是否嵌入隱藏消息.按著這一思路發(fā)展, Young 等人[10–13], Bellare 等人[14]分別從攻擊方法、防御方法和安全模型等方面對大規(guī)模監(jiān)視下的加密和簽名體制展開了一系列研究.

3.1 攻擊方法研究

攻擊方法的研究對整個研究體系的建立起著重要的牽引作用.目前在抗大規(guī)模監(jiān)視背景下, 算法替換攻擊(algorithm subversion attacks, ASAs)是攻擊加密體制的重要手段之一.ASAs 指攻擊者使用自身特有的權(quán)力和能力, 使用某種經(jīng)過篡改的算法去替換被攻擊者使用的純凈算法, 并結(jié)合各種后續(xù)具體方法,達到獲取信息的目的.以下是迄今為止提出的幾種主要的具體攻擊方式, 總結(jié)見表1.

SETUP:Young 等人[15]于1996年針對黑盒密碼體制提出了一種名為通用保護的內(nèi)嵌后門(secretly embedded trapdoor with universal protection, SETUP)的攻擊機制.其主要攻擊思路基于公鑰密碼體制, 由攻擊者設計替換算法C′, 用以代替用戶器件中的純凈密碼算法C, C′中含有一個公鑰, 而竊取秘密的攻擊者持有此公鑰所對應的私鑰(為表述方便, 此處將之稱作后門信息).C′與C 在不掌握后門信息的使用者看來具有相同的輸入輸出特征, 在概率多項式時間內(nèi)計算上無法區(qū)分.但是攻擊者可以使用后門信息, 通過C′所產(chǎn)生的輸出獲取相應敏感信息, 如使用者的明文、密鑰等等.此過程具有一定反追溯性.Young 等人根據(jù)強度的不同定義了強SETUP 和弱SETUP, 并將這種對密碼體制進行攻擊和安全分析的思路概括為kleptography.在該框架下, Young 等人針對常用密碼體制, 包括Diffie-Hellman 密鑰協(xié)商體制[16]、RSA 加密體制、ElGamal 加密體制[17]、ElGamal 簽名體制和Kerberos 協(xié)議[18]等, 設計了一系列具體攻擊方法[10–13].

Teseleanu[19]在SETUP 機制中引入了門限體制, 提出了針對ElGamal 簽名體制的(?,n)-門限SETUP 攻擊方案.其中, n 個惡意實體中如有? 個參與攻擊, 則可獲取受害者的相應私鑰.此種攻擊方式更有利于保護攻擊者的身份.

IV 替換攻擊(IV-replacement attack):此攻擊由Bellare 等人[14]針對對稱密碼體制提出.攻擊者對密碼算法進行惡意顛覆, 其與顛覆算法之間享有一個密鑰(稱顛覆密鑰), 顛覆后的密碼算法在實現(xiàn)過程中, 將本應具有隨機性的初始向量IV, 由對用戶密鑰加密所得密文代替, 此過程加密密鑰為顛覆密鑰.當存在有效算法利用密文恢復IV 時, 攻擊者可以使用所掌握的顛覆密鑰對IV 進行解密獲取用戶密鑰.

偏密文攻擊(Biased-ciphertext attack):此攻擊由Bellare 等人[14]提出, 適用于隨機化加密體制.被顛覆的加密算法在某一明文所對應的密文集合中, 帶有特定偏向性而非隨機均勻選取密文, 通過這種偏向性將加密密鑰逐比特按序泄露.掌握后門(顛覆密鑰)的攻擊者能夠識別這種偏向性, 獲取關(guān)鍵信息, 并攻破加密體制; 而不掌握后門的用戶則無法識別此偏向性.偏密文攻擊是一種強大的攻擊方式, 理論上對所有隨機化、無狀態(tài)、隨機數(shù)單射(coin injective)1隨機數(shù)單射(coin injective): 對所有密鑰、消息以及關(guān)聯(lián)數(shù)據(jù), 加密過程中所使用的隨機數(shù)到密文的映射是單射.的對稱加密體制都具有有效性.

改進的偏密文攻擊:Bellare 等人[20]提出了改進的偏密文攻擊方式.之前的偏密文攻擊需要逐比特按序泄露密鑰, 因此顛覆算法必須是有狀態(tài)的; 改進的攻擊方式則實現(xiàn)了一次密文泄露密鑰一個隨機的比特位, 這樣顛覆算法本身可以具有無狀態(tài)的特性, 攻擊適用范圍更廣.

輸入觸發(fā)顛覆(Input-triggered subversions)攻擊:Degabriele 等人[21]針對文獻[14]所提出的安全分析模型(詳見3.2節(jié))的局限性, 提出了輸入觸發(fā)顛覆攻擊, 即顛覆算法僅在輸入為特定信息時才采取一定機制泄露密鑰等關(guān)鍵信息, 其余情況下均執(zhí)行與純凈算法一樣的操作, 且此特定信息僅有攻擊者知曉.簡言之, 即顛覆算法在僅由攻擊者掌握的特定的輸入下才發(fā)動攻擊.

定時炸彈(Time bombs)攻擊:文獻[22]和文獻[23]分別討論了木馬與硬件后門中的定時炸彈攻擊.該攻擊與輸入觸發(fā)替換攻擊在思路上相類似, 只是觸發(fā)攻擊的因素是特定時間, 可逃避離線看門狗(offline watchdog)(詳見3.2節(jié))的審查.

偏隨機數(shù)攻擊(Biased randomness attack):該攻擊由Ateniese 等人[24]針對簽名體制提出, 基本構(gòu)造思路與偏密文攻擊類似, 在隨機化簽名體制中, 顛覆算法使用一個偽隨機函數(shù)以及與攻擊者共享的顛覆密鑰, 偏向性地選擇簽名所用的隨機數(shù), 實現(xiàn)每一次簽名泄露簽名者私鑰的一個比特.攻擊者在獲取若干簽名后, 可以恢復出簽名密鑰.

非對稱顛覆攻擊(Asymmetric subversion attacks):Liu 等人[25]針對當前一系列常用的簽名體制設計了非對稱顛覆攻擊.該方法具有反追溯特性, 監(jiān)視者所掌握的后門并不嵌入顛覆算法中.

此外, Auerbach 等人[26]還針對加密體制提出了參數(shù)顛覆攻擊(parameter substitute attack, PSA)方法, 詳細將在6.2 節(jié)中介紹.

表1 主要ASAs 方式總結(jié)Table 1 Summary of ASAs

3.2 抗大規(guī)模監(jiān)視安全模型研究

安全模型研究是抗大規(guī)模監(jiān)視加密和簽名體制研究的主線之一.其主要針對新背景下的現(xiàn)實情況, 包括攻擊方與防御方所能掌握的信息、影響的環(huán)節(jié)等, 以形式化的語言, 設計相應游戲, 建立起大規(guī)模監(jiān)視背景下對密碼體制進行安全性分析的標準.抗大規(guī)模監(jiān)視下密碼學的安全模型相比于傳統(tǒng)模型如CPA 模型、CCA 模型等[27–29]有較大的發(fā)展.

Young 等人[12,13]在對SETUP 具體攻擊方式進行廣泛探索后, 明確定義了基于游戲的SETUP 攻擊,并將算法執(zhí)行可顛覆的密碼學稱為kleptography.Bellare 等人[14]第一次對大規(guī)模監(jiān)視下的算法替換攻擊作出了一系列形式化定義, 首次建立了基于監(jiān)視-檢測的安全模型思路, 提出了針對ASAs 的較為完整的安全模型(BPR14), 并對攻擊與防御方法的有效性給出了形式化判斷方法.BPR14 模型的基本思路為, 在ASAs 環(huán)境下, 攻擊者一方面需要保證攻擊的有用性, 即能夠從所設計的顛覆算法產(chǎn)生的密文中得到敏感信息; 另一方面, 需要保證攻擊的隱蔽性, 即不掌握后門信息的普通用戶無法覺察到攻擊的存在, 否則攻擊理論上無法持續(xù)下去.基于這種思想, Bellare 等人設計了代表攻擊方執(zhí)行的監(jiān)視游戲(surveillance game), 與代表防御方(用戶, 密碼體制設計者)執(zhí)行的檢測游戲(detection game), 在游戲的基礎(chǔ)上定義了刻畫某種替換算法(攻擊方法)的抗檢測性與刻畫某種密鑰體制的抗監(jiān)視性.

然而, BPR14 模型存在一定局限性.為了保證內(nèi)部邏輯的嚴謹, BPR14 模型對所分析的顛覆算法做了嚴格的限制, 要求顛覆的加密算法與純凈的解密算法之間能滿足完美的加解密正確性.Degabriele 等人[21]對這種限制提出了質(zhì)疑, 并通過設計輸入觸發(fā)顛覆攻擊, 否定了原模型在放寬對顛覆算法的限制時的實用性.他們針對BPR14 模型的局限提出了改進的安全模型(DFP15).DFP15 模型適用于分析范圍更廣的顛覆算法, 其關(guān)注的是一個在線過程, 即檢測者并不意在判斷密碼體制是否被顛覆, 而關(guān)注攻擊者是否通過顛覆達到了獲取了相應信息的目的.該模型將檢測游戲設計為檢測方審閱監(jiān)視游戲的在線交互記錄, 從而體現(xiàn)出監(jiān)視與檢測是一對針對同一對象、基于不同目的的競爭過程, 通過雙方的優(yōu)勢對比來定義密碼體制的抗顛覆性.

DFP15 模型雖然具有更大的適用范圍和更完備的內(nèi)部邏輯, 但其與現(xiàn)實情況的符合程度值得商榷.Bellare 等人[20]提出了新的安全模型(BJK17), 相較于之前模型, 此安全模型主要特點在于, 檢測方的能力更強, 在詢問中可以自主提交密鑰, 并可獲取算法的更新狀態(tài)σ; 并對攻擊者提出了更高的要求, 監(jiān)視游戲最終提交的不是一個判斷比特b, 而是完整的用戶密鑰.此模型是在Degabriele 等人的質(zhì)疑下對安全模型發(fā)展所做的又一次改進.

數(shù)字簽名在身份認證、數(shù)據(jù)完整性、不可否認性以及匿名性等信息安全領(lǐng)域中有著重要的作用[30].Ateniese 等人[24]在算法替換背景下, 對簽名體制的安全性做了相對完整的研究, 指出一大類隨機化數(shù)字簽名方案不能避免替換攻擊.對抗ASAs 的簽名體制的研究在一定程度上借鑒了上述加密體制的研究思路, 并結(jié)合了數(shù)字簽名的特點以及其傳統(tǒng)形式化安全定義方式.出于在ASAs 下對數(shù)字簽名體制分析的需要,定義了簽名體制的唯一簽名性(unique signatures)、正確性(correctness)、可驗證性(verifiability)、寬松可驗證性(relaxed verifiability)等具體性質(zhì).在新環(huán)境, 即存在算法替換者和攻擊者的情況下, Ateniese等人設計了針對原體制代表攻擊者參加的不可識別性游戲、針對顛覆體制代表使用者或監(jiān)管方參加的公共/私有不可檢測性游戲、針對顛覆體制代表攻擊者參加的選擇明文攻擊下的冒充性游戲.以上工作所建立的形式化分析模型是分析抗ASAs 的數(shù)字簽名體制安全性的依據(jù).

Russell 等人[31]提出了基于看門狗(watchdog)的安全模型, 基本思想為基于檢測的安全.該模型引入一個正面第三方(實際中可視為網(wǎng)絡管理者), 將所有的檢測能力集成為一個身份——看門狗(watchdog).模型由看門狗、敵手與挑戰(zhàn)者(用戶)之間的三方交互規(guī)則來定義, 三者之間交互方式如圖2 所示.根據(jù)權(quán)限的不同, 看門狗被分為離線看門狗(offline watchdog)、在線看門狗(online watchdog)、以及全知看門狗(omniscient watchdog)三類.看門狗可獲取標準算法(純凈算法)與被視為黑盒的實際運行算法; 此外, 在線看門狗和全知看門狗還可以獲取敵手與挑戰(zhàn)者之間運行游戲的在線交互副本, 全知看門狗甚至可獲取挑戰(zhàn)者的私有狀態(tài).另外, 敵手與挑戰(zhàn)者之間運行傳統(tǒng)的安全游戲.針對一個密碼體制, 如果所有的顛覆攻擊, 要么無法削弱安全性, 要么能大概率地被看門狗檢測出來, 則稱這樣的密碼體制是安全的.該模型理論上可分析所有kleptography 環(huán)境下的密碼算法安全性.

圖2 Watchdog 防御模型Figure 2 Defense system based on watchdog

Horel 等人[32]提出了一種較為特殊的安全模型, 其中挑戰(zhàn)者必須使用敵手所提供的加密算法, 而且敵手有能力解密此算法產(chǎn)生的密文.挑戰(zhàn)者可以采取特殊的調(diào)用方式, 以期在通信雙方之間建立一條隱蔽信道, 而使得敵手無法通過所傳輸?shù)男畔⑴袛嗤ㄐ烹p方是否在信道中隱藏了秘密信息.該安全模型與隱寫體制有很大相似, 但嚴格意義上來講存在明確的區(qū)別.主要區(qū)別在于, 其一, 雙方事先沒有共享秘密信息;其二, 雙方無法自主選擇明文.

筆者[33]考察了現(xiàn)實中存在多個獨立監(jiān)視者的場景并定義了一種新的安全模型, 在該場景中, 用戶只能使用監(jiān)視者提供的算法來構(gòu)建密碼系統(tǒng)并傳遞消息, 但是這些算法可以來自多個不同的監(jiān)視者, 并且這些監(jiān)視者之間相互獨立.如果所有的監(jiān)視者, 要么認為用戶誠實地執(zhí)行了其給出的顛覆算法(對用戶之間真實消息的傳遞毫無察覺), 要么認為用戶執(zhí)行的是未經(jīng)顛覆的純凈算法, 則稱該系統(tǒng)是安全的.

以上是當前對于抗大規(guī)模監(jiān)視背景下建立的安全模型所做的主要探索.相關(guān)研究在一定程度上形成了大規(guī)模監(jiān)視背景下, 密碼設備本身不可信時分析算法安全性的研究思路, 為后續(xù)具體的密碼體制研究提供了框架.然而, 由于新背景下攻擊的形式, 以及攻擊方的權(quán)力和能力等情況極其復雜, 現(xiàn)有模型與實際情況的吻合度值得商榷, 尚未有一種公認模型能夠完美地刻畫現(xiàn)實環(huán)境, 相關(guān)研究仍在繼續(xù)中.

3.3 大規(guī)模監(jiān)視防御方法研究

對抗顛覆攻擊的一種較為直觀的防御方法是在一個密碼體制的實現(xiàn)中采用多個不同來源的設備.此時攻擊者只有在同一時間顛覆所有設備才能成功獲取敏感信息.但此種方法顯然帶來了額外的成本開銷.

偏密文攻擊(詳見3.1 節(jié))的提出, 從理論上證明了在沒有進一步防護機制(如外加可信設備等)的情況下, 所有隨機化加密體制(有狀態(tài)、無狀態(tài))都不能抵抗ASAs.因此, 如果從算法本身的層面上來進行安全防護, 則所設計的加密體制必須滿足唯一密文(unique ciphertext)的性質(zhì), 即在純凈的解密算法下,任一明文所對應的密文集合的元素個數(shù)不大于1.文獻[14,20,21,34]等都通過嚴格的數(shù)學方法, 證明了在各自所提出的安全模型下, 唯一密文體制具有抗顛覆的性質(zhì).

在簽名體制防護方面, Ateniese 等人[24]證明了滿足唯一簽名性等特定性質(zhì)的簽名體制, 在攻擊者所使用顛覆體制具有一定限制(如保留正常功能)的情況下, 具有不可識別性.這為設計在ASAs 下安全的數(shù)字簽名體制提供了方向性的建議.另外, 他們還將密碼反向防火墻(CRF)的概念應用于簽名體制, 定義了帶CRF 的安全模型, 并給出了具體構(gòu)造.Chow 等人[35]結(jié)合watchdog 模型與分割-融合(decomposition and amalgamation)技術(shù)(詳見下段)對簽名體制提出了一種通用性的顛覆防御方法; 并引入全域哈希, 設計了完全顛覆模型下安全的簽名體制.另外, 在攻擊者能力有限的情況下, 門限簽名對于ASAs 具有較強的防護能力, 至少目前尚沒有文獻提出對于門限簽名體制的此類攻擊方案[19].

Russell 等人[36]對隨機化密碼算法提出了一種防御方法.此方法基于分割-融合(decomposition and amalgamation)技術(shù).此技術(shù)將密碼算法進行分割, 分割后的算法一部分為隨機性算法RG, 如隨機字符串生成算法、密鑰生成算法等, 另一部分為確定性算法DG.所有的算法構(gòu)件重新組合后能夠?qū)崿F(xiàn)與原算法相同的功能.分割后的算法都能夠被廣泛測試.由于DG 的確定性的性質(zhì), 使得攻擊者只能對RG 進行攻擊.為了使針對RG 的后門不產(chǎn)生作用, 此模型又將所有RG 進一步分割為兩個相互獨立的隨機算法和一個基于隨機預言的可信整合算法, 以此達到防護密碼體制的目的.

以上對加密和簽名等密碼體制的分析, 都需要一定程度地限制攻擊者所使用的顛覆算法.然而, 在防御方(檢測者)能力較弱時, 不排除存在顛覆算法無限制的ASAs, 這種攻擊的危害則更為直接.基于密碼協(xié)議的分析框架, Mironov 等人[37]首次引入密碼反向防火墻(cryptographic reverse firewall, CRF)的概念.CRF 是部署于信息系統(tǒng)與外部之間的安全模塊, 區(qū)別于傳統(tǒng)的抵抗外來攻擊的防火墻概念, CRF存在的目的是為了防御由內(nèi)部攻擊所造成的對外泄露關(guān)鍵信息的安全威脅.CRF 具有特殊的信任狀態(tài),一方面其具有執(zhí)行的可信性, 即不可顛覆性; 另一方面, 其身份本身又具有不可信性, 即僅允許其掌握原本可公開的數(shù)據(jù), 如公鑰、密文等等.Mironov 等人沿用傳統(tǒng)的密碼協(xié)議形式化框架, 給出了CRF 運行方式的形式化定義, 即協(xié)議中每個實體對外發(fā)送與接收的信息均經(jīng)過CRF 的處理(如圖3 所示).CRF 需要滿足以下三個基本性質(zhì):

(1)功能保留性(Functionality–maintaining): 引入CRF 后仍保留原協(xié)議的功能;

(2)安全保留性(Security-preserving): 引入CRF 后仍保留原協(xié)議的安全性;

(3)抗泄露性(Exfiltration-resistance): 引入CRF 后, 任何內(nèi)部攻擊無法對外泄露額外信息.

圖3 CRF 運行示意圖Figure 3 Operation of CRF

CRF 的安全保留性與抗泄露性有著緊密的關(guān)聯(lián), 但二者互不蘊含.筆者[38]對其二者在消息傳輸協(xié)議框架下的相互關(guān)系進行了詳細的形式化分析, 并對Mironov 等人提出的CRF 抗泄露性定義做了一定程度的完善, 考慮了游戲定義中敵手能力更強的情況.

Fischlin 等人[39]提出了自防御密碼協(xié)議的防御方法, 它區(qū)別于密碼反向防火墻與基于檢測的看門狗(watchdog)的防御機制.該類體制假設存在“安全錨(security anchor)”, 以確保一個安全的啟動階段2在安全的啟動階段中, 使用者可獲取算法的一個純凈版本..當把部分密碼算法建模成可顛覆黑盒時, 基于安全啟動階段, 特殊設計的密碼協(xié)議可以使得攻擊者的優(yōu)勢可忽略.根據(jù)這一思路, Fischlin 等人為具有同態(tài)性質(zhì)的公鑰加密體制和隨機化單鑰加密體制設計了相應安全防護方法.

4 抗大規(guī)模監(jiān)視密碼學原語研究

4.1 顛覆環(huán)境下的單向函數(shù)及哈希函數(shù)研究

作為密碼學基本原語之一, 單向函數(shù)對密碼體制的構(gòu)建起著重要的作用.Russell 等人[31]構(gòu)造了一個在傳統(tǒng)模型下安全, 但無法抵抗kleptography 環(huán)境下攻擊的單向函數(shù)實例, 指出在新情況下有必要重新分析單向函數(shù)的安全性并給出構(gòu)造.Russell 等人在其所定義的watchdog 模型(詳見3.2 節(jié))下, 定義了單向置換(one-way permutation, OWP)的三種安全性質(zhì), 分別為: (1)OWPC, 敵手可以選擇OWP 的參數(shù)生成函數(shù); (2)OWPA, 敵手可以直接提供OWP 的公共參數(shù); (3)OWPSP, 其定義基于分離程序模型(split program model).在合適哈希函數(shù)假設下, Russell 等人給出了利用傳統(tǒng)OWP 構(gòu)造滿足OWPA和OWPSP安全的OWP 的方法.

Russell 等人[40]在kleptography 環(huán)境下形式化分析了隨機喻言機的安全性, 對被顛覆的隨機喻言提出了糾正方法, 使得在顛覆攻擊下仍然能夠可信地黑盒調(diào)用隨機喻言, 而無需關(guān)心隨機喻言的具體實現(xiàn).當哈希函數(shù)被顛覆時, 通過對一系列哈希輸出值進行異或, 并再次運行哈希函數(shù)的方法, 利用顛覆算法仍需要滿足黑盒測試下無法被檢測識別的限制, 可以實現(xiàn)最終的輸出能夠滿足隨機喻言下的安全要求.Russell 等人在無差別(indifferentiability)模型下證明了糾正方法的安全性.

4.2 帶有后門的偽隨機數(shù)生成器研究

偽隨機數(shù)生成器(pseudorandom number generator, PRG)在密碼體制中扮演著十分重要的角色, 其本身的安全性對于密碼體制的安全起著十分重要的作用[41].

在抗大規(guī)模監(jiān)視密碼學產(chǎn)生之前, 就有包括Barak 等人[42]在內(nèi)的學者對PRG 的安全性進行了形式化定義.受斯諾登事件的影響以及文獻[14]等對算法替換攻擊形式化分析思路的啟發(fā), 研究人員還嚴格分析了一系列PRG 相關(guān)標準[43–46], 并開始研究在內(nèi)部攻擊安全威脅下的帶有后門的偽隨機生成器(backdoored pseudorandom generators, BPRG).

Dodis 等人[47]形式化定義了BPRG 的安全性質(zhì).其在傳統(tǒng)的PRG 安全性定義的基礎(chǔ)上, 加入了后門信息sk 并允許攻擊者掌握sk.BPRG 的定義基于兩個游戲: 挑戰(zhàn)者與普通敵手A(不持有后門信息sk)的游戲, 和挑戰(zhàn)者與持有后門信息sk 的敵手B 的游戲.BPRG 需要在第一個游戲中表現(xiàn)出傳統(tǒng)PRG的安全性質(zhì), 并在第二個游戲中使敵手B 可以憑借后門sk 獲取特殊的優(yōu)勢.根據(jù)敵手B 可獲取的不同特殊優(yōu)勢, 可以將BPRG 的強度分為3 類:

(1)敵手可以區(qū)分BPRG 的多步輸出和等長的均勻隨機分布字符串.

(2)敵手可以根據(jù)BPRG 的多步輸出恢復出BPRG 的最后狀態(tài).

(3)敵手可以根據(jù)BPRG 的多步輸出中任意一步輸出恢復出其余任意一步輸出.

Dodis 等人給出了BPRG 的構(gòu)造方法, 并通過BPRG 與公鑰密碼體制之間的相互構(gòu)造證明了其二者之間等價.Dodis 等人還研究了對BPRG 的免疫方法, 討論了使用一種作用于BPRG 輸出端的“非平凡函數(shù)” 來保證輸出結(jié)果對于敵手B 的隨機性的方法, 由此定義了公共免疫、半私有免疫、以及私有免疫三種免疫的強度, 證明了公共免疫的不可能性, 并給出了后兩種免疫的具體方法.

Degabriele 等人[48]在Dodis 等人工作的基礎(chǔ)上, 給出了兩種新的BPRG 安全性定義.新安全性定義對敵手B 的要求更高, 要求其在得到單步輸出后可以恢復BPRG 的狀態(tài)以及BPRG 的所有可能輸出.隨后, 他們考察了帶輸入的偽隨機數(shù)生成器(pseudorandom number generator with input, PRNG with input)模型[42], 研究其存在后門(backdoored PRNGs with input, BPRNG with input)時的形式化定義, 規(guī)定敵手可以獲取泄露的輸入信息、獲取或設置BPRNG 的狀態(tài)并在其輸入累計熵達到一定值后獲取挑戰(zhàn)消息.Degabriele 等人基于可再隨機化加密體制[49]具體構(gòu)造了帶輸入的BPRNG, 并給出了BPRNG 狀態(tài)長度與攻擊者成功嵌入后門機會之間的關(guān)系.

Russell 等人[31]基于經(jīng)典的Blum-Micali PRG 構(gòu)造方法[50]和OWPA(詳見4.1 節(jié)), 設計了抗顛覆攻擊的PRG.考慮到Dodis 等人已給出的相關(guān)否定結(jié)論, 即不可能通過將“非平凡函數(shù)”作用于BPRG的輸出實現(xiàn)BPRG 公共免疫, Russell 等人則采取不同思路繞開了這一點, 其設計基于對PRG 公共參數(shù)的隨機化處理.

5 抗大規(guī)模監(jiān)視密碼協(xié)議研究

5.1 零知識協(xié)議相關(guān)研究

在交互式證明協(xié)議中, 如果惡意的驗證者只知道輸入命題正確與否, 卻獲取不到其他一切有用信息,則稱此協(xié)議為零知識協(xié)議[51].Ben-Sasson 等人[52]分析了零知識協(xié)議中共同參考字符串(common reference string, CRS)被顛覆時的安全威脅, 提出了分布式CRS 生成方案, 使得只要其中一個實體誠實,則協(xié)議安全.Bellare 等人[53]分析了惡意共同參考字符串模型下非交互式零知識(non-interactive zeroknowledge,NIZK)協(xié)議[54]和非交互式證據(jù)不可區(qū)分(non-interactive witness indistinguishable,NIWI)協(xié)議的安全性, 形式化定義了顛覆可靠性、顛覆不可區(qū)分和顛覆零知識性質(zhì), 并考察這三種性質(zhì)與傳統(tǒng)可靠性、不可區(qū)分性和零知識性的各種組合性質(zhì), 給出一系列肯定或者否定結(jié)果.針對NP 語言, 主要結(jié)果包括4 點:

(1)在文獻[55]所提供范例的基礎(chǔ)上, 通過構(gòu)造能破壞可靠性的模擬者, 證明了不存在顛覆可靠的NIZK;

(2)通過借助NP 關(guān)系與雙線性群生成器構(gòu)造的NIZK 框架, 基于computational Diffie-Hellman(CDH)、decision linear (DLin)和knowledge-of-exponent (KEA)變種假設, 證明了存在滿足顛覆零知識的NIZK;

(3)借助于文獻[56]構(gòu)造的非交互式系統(tǒng), 基于DLin 假設, 證明了存在顛覆可靠和顛覆不可區(qū)分的NIWI;

(4)借助偽隨機數(shù)生成器和ZAP (即兩輪的NIWI 協(xié)議[57])構(gòu)造的NIZK, 證明了存在顛覆不可區(qū)分的NIWI 協(xié)議.

Abdolmaleki 等人[58]在文獻[53]的基礎(chǔ)上, 要求CRS 陷門可提取以及CRS 公共可驗證, 實現(xiàn)了計算可靠和完美可組合的抗顛覆零知識系統(tǒng).

5.2 基于密碼反向防火墻的抗大規(guī)模監(jiān)視安全協(xié)議

密碼反向防火墻(CRF)是部署于信息系統(tǒng)和外部之間, 防止因內(nèi)部攻擊造成對外信息泄露的器件(詳見3.3 節(jié)).在密碼協(xié)議中, CRF 通過對協(xié)議中傳輸?shù)男畔嵤霸匐S機化” 以及其他相應操作, 實現(xiàn)在保留原協(xié)議功能和安全要求的基礎(chǔ)上, 防止被顛覆的實體對外泄露信息.

Mironov 等人[37]針對由Naor 等人[59]、Aiello 等人[60]各自獨立提出的基于DDH 難題的不經(jīng)意傳輸協(xié)議, 為協(xié)議雙方都設計了CRF.所設計的CRF 基于內(nèi)部生成的隨機數(shù), 在滿足原協(xié)議功能的前提下對消息收發(fā)雙方發(fā)出的消息都進行了再隨機化.可以證明即使在協(xié)議實體遭到顛覆的情況下, 經(jīng)隨機化后的消息仍然可以與完全隨機均勻產(chǎn)生的消息不可區(qū)分.Mironov 等人還給出了一種方法, 能夠?qū)⑷我鈪f(xié)議轉(zhuǎn)化成一個實現(xiàn)相同功能的新協(xié)議, 在新協(xié)議中所有實體都可以配備一個具有強抗泄露性(詳見3.3 節(jié))的CRF, 以此來保護實體在顛覆風險下的安全性.

Dodis 等人[61]在文獻[37]建立的框架下, 繼續(xù)定義了CRF 可檢測失敗(detectable failure)的性質(zhì), 并對消息傳輸協(xié)議環(huán)境下的CRF 進行了較為全面的研究.針對消息傳輸協(xié)議, 他們借助于再隨機化加密體制, 提出了協(xié)議雙方的CRF 的通用構(gòu)造方法.并且, 他們構(gòu)造了一種抗選擇密文攻擊的安全密鑰協(xié)商協(xié)議的CRF.

國內(nèi)學者陳等人[62]在平滑映射哈希系統(tǒng)[63,64]的基礎(chǔ)上, 通過引入密鑰可延展性和元素可再隨機化性, 提出了可延展平滑映射哈希系統(tǒng)的概念, 并給出了一個相應實例.基于可延展平滑映射哈希系統(tǒng), 他們?yōu)榘ㄏ鬏攨f(xié)議、不經(jīng)意信封協(xié)議、不經(jīng)意傳輸協(xié)議在內(nèi)的多種協(xié)議構(gòu)造了CRF.

6 抗大規(guī)模監(jiān)視密碼學研究其他方向

6.1 算法替換攻擊與隱寫體制相關(guān)研究

算法替換攻擊的思想與隱寫體制(steganography)聯(lián)系緊密.Berndt 等人[65]重新分析了現(xiàn)有算法替換攻擊的本質(zhì), 認為針對對稱加密體制的顛覆其本質(zhì)就是構(gòu)造一種隱寫體制.他們對對稱加密算法的顛覆體制與隱寫體制實現(xiàn)相互構(gòu)造, 嚴格證明了其二者實際上是等價的, 這也為設計算法替換攻擊提供了一種實際可行的方法.Russell 等人[36]從隱寫的角度討論了針對隨機化加密體制的抗顛覆防御方法, 提出了無隱寫(stego-free)體制的概念.

6.2 參數(shù)顛覆攻擊相關(guān)研究

參數(shù)顛覆的概念首次由Bellare 等人[53]提出.他們分析了非交互式零知識協(xié)議在共同參考字符串在遭到惡意顛覆時的安全性(詳見5.1 節(jié)).另外Dodis 等人[47]和Degabriele 等人[48]在研究偽隨機數(shù)生成器時也采用了參數(shù)顛覆的思想(詳見4.2 節(jié)).文獻[66–69]分別考察了公共參數(shù)在非可信環(huán)境下生成時密碼體制的安全性.

Auerbach 等人[26]在參數(shù)顛覆攻擊下形式化定義了公鑰加密體制和密鑰封裝體制的安全模型, 其中,敵手可以完全控制公共參數(shù)的生成過程.他們提出了相較于傳統(tǒng)密文不可識別性、公鑰隱藏性更強的密文偽隨機性(ciphertext pseudo-randomness, CPR)的概念, 以及高效可嵌入群族(efficiently-embeddable group, EEG)概念, 構(gòu)造了具有CPR 性質(zhì)的密鑰封裝體制, 又基于橢圓曲線密碼學, 給出了EEG 實例的構(gòu)造方法.

6.3 抗泄露密碼學相關(guān)研究

抗算法替換攻擊、抗公開參數(shù)替換攻擊等攻擊的密碼體制并不能夠保證一定可避免其他潛在攻擊.在當前背景下, 攻擊的手段日趨多樣, 如側(cè)信道攻擊就是一種強大攻擊方法.側(cè)信道攻擊指當加載密碼體制的電子設備運行時, 通過測量其運行過程中的時間消耗、功率消耗或電磁輻射等側(cè)信道信息, 進而獲取密鑰部分或全部信息.針對于此, Dziembowski 等人[70]正式提出了抗泄露密碼學(leakage-resilient cryptography), 抗泄露密碼學將物理泄漏方式抽象為信息論意義上的泄漏函數(shù), 在此基礎(chǔ)上設計可證明安全的密碼算法和協(xié)議, 使得算法和協(xié)議的安全性獨立于底層的硬件實現(xiàn)工藝和敵手的側(cè)信道攻擊手段, 因此具有更廣的安全性.當前, 研究人員已設計了抗泄露攻擊的單向函數(shù)[71]、偽隨機函數(shù)[72,73]、對稱加密體制[74,75]、公鑰加密體制[76–79]、消息認證碼[74,75]和零知識證明協(xié)議[80,81]等.筆者在抗泄露的公鑰加密領(lǐng)域進行了相關(guān)研究, 利用零知識協(xié)議構(gòu)造了后挑戰(zhàn)泄露情況下選擇密文攻擊安全的公鑰加密體制[82].

抗泄露密碼學與抗大規(guī)模監(jiān)視密碼學有著緊密的關(guān)聯(lián), 在產(chǎn)生背景、前提假設、關(guān)注對象、分析方法等方面存在廣泛的共通性.在某些情況下, 二者所產(chǎn)生的密碼體制也具有相互借鑒意義, 二者研究存在著結(jié)合的趨勢.

7 展望與結(jié)束語

從目前學術(shù)界的研究來看, 抗大規(guī)模監(jiān)視密碼學實際上是在新背景下對傳統(tǒng)密碼學所做的一種推進和延伸.結(jié)合學者們在各方面所做工作, 此領(lǐng)域研究現(xiàn)已完成了從發(fā)現(xiàn)問題(設計攻擊方法)、定義問題(建立安全模型等)到解決問題(設計防御體制)的一個較為完整的框架, 然而仍存在諸多不足之處, 很多現(xiàn)實問題未能得到很好的解決, 主要包括:

(1)現(xiàn)有抗大規(guī)模監(jiān)視安全模型與現(xiàn)實情況存在偏差.迄今為止發(fā)表的公開文獻中, 對于抗大規(guī)模監(jiān)視的威脅的建模各有優(yōu)缺點, 但核心思想都較為相似, 且都不能十分全面地刻畫現(xiàn)實情況.

(2)現(xiàn)有的防御策略在實際中較難實現(xiàn).當前所設計的針對大規(guī)模監(jiān)視的防御策略, 一方面集中在放棄隨機化體制, 回歸確定性加密, 這顯然無法滿足相當大一部分現(xiàn)實需求; 另一方面則使用CRF、分割-融合技術(shù)、可靠偽隨機數(shù)生成器等方法保證隨機化密碼算法的安全, 這些方法都需要較強的假設或較高的實現(xiàn)成本.

如何解決上述問題將是此領(lǐng)域下一步的重要研究方向.本文介紹了當前在該領(lǐng)域各個方面的主要研究成果.由于實際所面對問題的復雜性, 抗大規(guī)模監(jiān)視密碼學的發(fā)展也是一個曲折的過程, 此方面的研究目前還處在一個較為初步的階段.抗大規(guī)模監(jiān)視密碼學的研究對于突破與豐富當前密碼學理論, 探索新的密碼應用技術(shù), 解決新形勢下現(xiàn)實信息安全問題, 都具有重要的理論和現(xiàn)實意義.