可證明安全理論的發(fā)展

張曼君

（西安郵電大學(xué) 通信與信息工程學(xué)院 陜西 710000）

1 可證明安全含義

可證明安全是指密碼協(xié)議可以從數(shù)學(xué)上被規(guī)約證明是安全的，能抵抗某些攻擊。最早在這一領(lǐng)域做出貢獻(xiàn)的是C.E.Shannon，他在信息論中首先提到了信息量的完善保密（Perfectly secret）概念。完善是指密碼協(xié)議能抵抗所有的唯密文攻擊，而不會(huì)透露密文所對(duì)應(yīng)的任何明文消息。

對(duì)密碼系統(tǒng)的有效攻擊絕大多數(shù)是由于密碼方案或協(xié)議存在很大的漏洞。假設(shè)好的密碼原語存在，如何設(shè)計(jì)密碼方案正是可證明安全性要解決的問題，它是一種將好的密碼原語轉(zhuǎn)化為好的密碼方案的方法。

可證明安全的一般性方法如下：

確定密碼協(xié)議的安全目標(biāo)；

給出密碼協(xié)議的形式化安全定義；

將攻擊者完成攻擊目標(biāo)的方法歸約為破譯或者解決極微本原，從而達(dá)到證明協(xié)議安全的目的。

這一過程并沒有直接證明密碼方案或協(xié)議的安全性，如果發(fā)現(xiàn)了方案或協(xié)議的漏洞，就相當(dāng)于發(fā)現(xiàn)了其中困難問題的解。如果我們相信后者是安全的，那么不用分析該方案或協(xié)議我們就證明了其安全性。有時(shí)也將“可證明安全”稱為“歸約安全”。

馮登國在可證明安全理論與方法研究一文中指出了目前多數(shù)安全協(xié)議的設(shè)計(jì)現(xiàn)狀：

（1）傳統(tǒng)方式：一種安全協(xié)議被提出后，在某種假定之下做出其安全性判斷。如果在很長一段時(shí)間內(nèi)都不能被破譯，就接受其安全性；如果一段時(shí)間后發(fā)現(xiàn)該協(xié)議可能存在安全漏洞，于是對(duì)協(xié)議進(jìn)行必要改動(dòng)，再繼續(xù)使用；這一過程可能周而復(fù)始。

（2）可證明安全：是一種歸約方法。首先，確定協(xié)議的安全方案和安全目標(biāo)，其次，構(gòu)建攻擊模型，再次，將攻擊者的目標(biāo)歸約到解決某類密碼學(xué)上的難題，最后，推翻原始假設(shè)，證明協(xié)議的安全性。

設(shè)計(jì)安全協(xié)議是非常容易出錯(cuò)的，因此有必要對(duì)協(xié)議進(jìn)行安全性分析。傳統(tǒng)上通過試錯(cuò)法來分析協(xié)議，但是該方法僅僅對(duì)于已知攻擊具有檢測(cè)能力，卻無法檢測(cè)未知攻擊，因此經(jīng)該方法檢測(cè)為正確的協(xié)議，在一段時(shí)間后往往被發(fā)現(xiàn)存在安全漏洞。因此，學(xué)者們提出了多種安全協(xié)議的證明技術(shù)，以提供安全性準(zhǔn)確可信的分析。目前，協(xié)議安全性證明方法基本分為兩大類：形式化證明方法和可證安全法。

2 形式化方法

形式化方法又稱作計(jì)算機(jī)安全方法。該方法源于計(jì)算機(jī)安全團(tuán)體，強(qiáng)調(diào)對(duì)安全協(xié)議的自動(dòng)化分析和描述。形式化方法最初來自Delov和Yao的安全威脅模型，在模型中，安全協(xié)議被劃分成兩個(gè)層面：協(xié)議技術(shù)層面和密碼算法層面，密碼算法被當(dāng)作黑盒處理，模型將協(xié)議的運(yùn)行用形式化方法進(jìn)行分析。形式化方法根據(jù)設(shè)計(jì)思想可分為三類：邏輯推導(dǎo)法、模型檢測(cè)法和定理證明法。

（1）邏輯推導(dǎo)法

牛奶燕麥粥。先把牛奶放微波爐里加熱半分鐘，然后把即食燕麥片倒進(jìn)去攪拌，讓它泡十幾分鐘就可以吃了。配雞蛋、榨菜吃咸的，還是配葡萄干吃甜的，大家可以根據(jù)個(gè)人口味選擇。

在邏輯推導(dǎo)法中定義一個(gè)邏輯公理集，通過可操作的抽像符號(hào)來表述協(xié)議的安全特性，并利用邏輯公理對(duì)協(xié)議各方的知識(shí)信仰進(jìn)行推理，以期推出新的關(guān)于協(xié)議安全性的知識(shí)信仰。最著名的邏輯推導(dǎo)法是Burrows、Abadi和Needham提出的BAN邏輯。BAN邏輯的優(yōu)點(diǎn)是概念清晰、簡單，對(duì)于協(xié)議中的潛在安全漏洞能夠有效地發(fā)現(xiàn)。但是，BAN邏輯中的假設(shè)以及理想化過程具有非形式化的特點(diǎn)，在推理的過程中可能會(huì)導(dǎo)致協(xié)議信息的丟失或不嚴(yán)格的重構(gòu)，影響協(xié)議的安全性和可信度。隨著BAN邏輯的推廣，在此基礎(chǔ)上出現(xiàn)了多種擴(kuò)展協(xié)議，其中有GNY邏輯、AT邏輯、VO邏輯和SVO邏輯，他們被稱作類BAN邏輯。除此之外，還有用于協(xié)議非否認(rèn)性證明的Kailar邏輯。

（2）模型檢測(cè)方法

模型檢測(cè)方法主要考察協(xié)議狀態(tài)之間的轉(zhuǎn)換，將其以路徑形式表達(dá)，從初始狀態(tài)開始，搜索協(xié)議參與方或攻擊者的可能路徑。主要包括一般目的驗(yàn)證語言、單一代數(shù)理論模型以及特別目的專家系統(tǒng)。典型的一般目的驗(yàn)證語言包括Murá描述語言和通信順序進(jìn)程語言，這類語言把安全協(xié)議當(dāng)作一般性的描述目標(biāo)，遍歷所有狀態(tài)，對(duì)協(xié)議進(jìn)行驗(yàn)證。單一代數(shù)理論模型包括Meadows模型和Woo-Lam模型等，這類方法對(duì)于安全協(xié)議的分析更有針對(duì)性，通過將協(xié)議轉(zhuǎn)換為代數(shù)系統(tǒng)來描述參與方的狀態(tài)，證明某一狀態(tài)式不可達(dá)。特別目的專家系統(tǒng)為了證明協(xié)議的漏洞，從不安全狀態(tài)出發(fā)，以證明初始狀態(tài)到此不安全狀態(tài)是有效路徑。其中有代表性的方法包括NRL分析器和Interrogator詢問器。

（3）定理證明方法

定理證明法先對(duì)協(xié)議進(jìn)行形式化，在此基礎(chǔ)上對(duì)其進(jìn)行模型化和歸約，為了證明協(xié)議滿足某種安全屬性，需要證明歸約在模型中成立。主要包括Paulson歸納法、Schneider秩函數(shù)、串空間模型和Spi-演算等。定理證明與模型檢測(cè)的區(qū)別在于，前者是從協(xié)議的正面入手，而后者試圖針對(duì)反面，尋找各種可能的攻擊。定理證明無需檢測(cè)工具，且過程簡單明了。

形式化方法是對(duì)于人類智慧和經(jīng)驗(yàn)?zāi)Ｐ突说膶＜蚁到y(tǒng)，該方法在論證協(xié)議不安全方面是有效的，它能夠查找協(xié)議中的安全漏洞。但是該方法對(duì)于攻擊者的模型定義不夠全面，主要考慮被動(dòng)攻擊；而且該方法將密碼算法作為黑盒處理，因此無法發(fā)現(xiàn)因?yàn)槊艽a算法的不合理帶來的安全漏洞。

3 可證明安全方法

可證明安全方法起源于密碼學(xué)團(tuán)體，最初來自Goldwasser和Micali的研究。在公鑰簽名體制的可證明安全的發(fā)展過程中，Goldwasser等人在80年代中期提出了最重要的成果，攻擊者獲得適應(yīng)性所選擇消息的簽名后，仍然不能以不可忽略優(yōu)勢(shì)偽造一個(gè)新消息的簽名。該方法應(yīng)用計(jì)算復(fù)雜性理論，通過對(duì)敵手攻擊成功概率和計(jì)算代價(jià)的評(píng)估來判斷協(xié)議的安全性。

可證明安全方法包括以下三個(gè)方面：

困難問題：公認(rèn)在多項(xiàng)式時(shí)間內(nèi)得到解決的概率是可忽略的問題。

安全性定義：是可證明安全方法的關(guān)鍵。其中定義了攻擊者的行為和目的。對(duì)攻擊者的行為，即可能的攻擊方法進(jìn)行形式化描述；攻擊者的目的即攻擊協(xié)議要達(dá)到的目標(biāo)。當(dāng)協(xié)議中的攻擊者具有最強(qiáng)的攻擊行為且目的最簡單，就稱協(xié)議具有最好的安全性。其中包括BR模型、基于BR的擴(kuò)展模型BR95、WJM97，和基于組合以及模塊思想的模型，例如CK模型、UC模型等。

歸約方法：歸約方法是可證安全理論中最常用到的工具，可證安全的主要技巧在于從攻擊能力到困難問題的歸約。對(duì)協(xié)議進(jìn)行證明時(shí)，首先要構(gòu)建安全模型，為攻擊者提供一種虛擬環(huán)境，使其發(fā)揮攻擊能力；還要建立挑戰(zhàn)算法，將安全問題歸約為數(shù)學(xué)難題，并且在模擬過程中將數(shù)學(xué)難題暗中嵌入，引導(dǎo)攻擊者解決該難題。目前的主流方法包括標(biāo)準(zhǔn)模型和隨機(jī)預(yù)言機(jī)模型。

4 隨機(jī)預(yù)言機(jī)模型下的可證明安全

在隨機(jī)預(yù)言機(jī)模型(Random Oracle Model：ROM)中，允許協(xié)議各方對(duì)其進(jìn)行問詢，證明者首先完成在這個(gè)模型中方案的安全性證明，利用哈希函數(shù)模擬隨機(jī)預(yù)言機(jī)，在哈西函數(shù)沒有缺點(diǎn)的安全論斷下，隨機(jī)預(yù)言機(jī)的證明保證了協(xié)議的安全性。

在隨機(jī)預(yù)言機(jī)模型中，歸約論斷如下進(jìn)行：首先對(duì)方案滿足的安全性進(jìn)行形式化定義，假設(shè)在概率多項(xiàng)式算法中，攻擊者能夠以不可忽略概率成功攻擊方案；其次，為攻擊者提供其所需的模擬環(huán)境，即隨機(jī)預(yù)言機(jī)，對(duì)攻擊者的詢問予以回答；最后，將數(shù)學(xué)上的困難問題嵌入模型中，利用攻擊結(jié)果解決數(shù)學(xué)難題。在模型證明過程中，用哈希函數(shù)模擬隨機(jī)預(yù)言機(jī)，協(xié)議參與者都能對(duì)其進(jìn)行訪問，通過利用攻擊者的攻擊行為來求解困難問題。利用上述證明過程得到的模型即隨機(jī)預(yù)言機(jī)模型。

1993年，Bellare和Rogaway兩位學(xué)者正式提出了ROM方法論，自此，可證明安全方法從理論研究走向?qū)嶋H應(yīng)用，隨之產(chǎn)生了多個(gè)安全方案，同時(shí)，具體安全性的概念得以提出，安全性的漸進(jìn)度已經(jīng)滿足不了人們對(duì)于安全性的衡量，取而代之是得到確切的安全性度量。

5 標(biāo)準(zhǔn)模型下的可證明安全

標(biāo)準(zhǔn)模型將密碼學(xué)原語視為基礎(chǔ)部件，通過某種方式利用這些基礎(chǔ)部件構(gòu)造更強(qiáng)大的原語。在ROM中證明了的方案安全并不能保障該方案在現(xiàn)實(shí)生活中的安全性。目前有許多安全方案可在ROM中證明安全，但是在實(shí)際應(yīng)用中卻不能構(gòu)造出與方案對(duì)應(yīng)的實(shí)例。與之相比較，可證安全性在標(biāo)準(zhǔn)模型中更具現(xiàn)實(shí)意義。標(biāo)準(zhǔn)模型雖然也是通過預(yù)言機(jī)對(duì)于詢問進(jìn)行應(yīng)答，但與ROM不同，預(yù)言機(jī)內(nèi)部映射要符合方案中的具體函數(shù)關(guān)系，因此，增加了設(shè)計(jì)難度。

雖然隨機(jī)預(yù)言機(jī)模型不能成為方案安全性的絕對(duì)證明，但是，作為方案安全性的一種必要測(cè)試工具，ROM可以排除多項(xiàng)安全隱患。在ROM下設(shè)計(jì)簡單有效的可證明安全協(xié)議，能夠抵抗多種未知攻擊。但是仍有一些學(xué)者堅(jiān)持使用標(biāo)準(zhǔn)模型來證明協(xié)議的安全性，他們認(rèn)為，在ROM中將哈希函數(shù)當(dāng)做理想的隨機(jī)模型是強(qiáng)假設(shè)，而且，ROM中證明的協(xié)議安全性和通過哈希函數(shù)獲得的安全性沒有必然的因果關(guān)系。事實(shí)上，所有標(biāo)準(zhǔn)模型下的可證安全協(xié)議在設(shè)計(jì)上都過于復(fù)雜，ROM設(shè)計(jì)上較為簡單，實(shí)用性更強(qiáng)。因此，客觀上來說，目前的安全方案至少要能夠達(dá)到ROM下證明的安全性。而設(shè)計(jì)安全協(xié)議的目標(biāo)應(yīng)放在具有標(biāo)準(zhǔn)模型下可證明的安全性，以及ROM下的簡單高效性。