可證明安全理論的發展

張曼君

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

1 可證明安全含義

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

對密碼系統的有效攻擊絕大多數是由于密碼方案或協議存在很大的漏洞。假設好的密碼原語存在，如何設計密碼方案正是可證明安全性要解決的問題，它是一種將好的密碼原語轉化為好的密碼方案的方法。

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

確定密碼協議的安全目標；

給出密碼協議的形式化安全定義；

將攻擊者完成攻擊目標的方法歸約為破譯或者解決極微本原，從而達到證明協議安全的目的。

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

馮登國在可證明安全理論與方法研究一文中指出了目前多數安全協議的設計現狀：

（1）傳統方式：一種安全協議被提出后，在某種假定之下做出其安全性判斷。如果在很長一段時間內都不能被破譯，就接受其安全性；如果一段時間后發現該協議可能存在安全漏洞，于是對協議進行必要改動，再繼續使用；這一過程可能周而復始。

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

設計安全協議是非常容易出錯的，因此有必要對協議進行安全性分析。傳統上通過試錯法來分析協議，但是該方法僅僅對于已知攻擊具有檢測能力，卻無法檢測未知攻擊，因此經該方法檢測為正確的協議，在一段時間后往往被發現存在安全漏洞。因此，學者們提出了多種安全協議的證明技術，以提供安全性準確可信的分析。目前，協議安全性證明方法基本分為兩大類：形式化證明方法和可證安全法。

2 形式化方法

形式化方法又稱作計算機安全方法。該方法源于計算機安全團體，強調對安全協議的自動化分析和描述。形式化方法最初來自Delov和Yao的安全威脅模型，在模型中，安全協議被劃分成兩個層面：協議技術層面和密碼算法層面，密碼算法被當作黑盒處理，模型將協議的運行用形式化方法進行分析。形式化方法根據設計思想可分為三類：邏輯推導法、模型檢測法和定理證明法。

（1）邏輯推導法

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

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

（2）模型檢測方法

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

（3）定理證明方法

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

形式化方法是對于人類智慧和經驗模型化了的專家系統，該方法在論證協議不安全方面是有效的，它能夠查找協議中的安全漏洞。但是該方法對于攻擊者的模型定義不夠全面，主要考慮被動攻擊；而且該方法將密碼算法作為黑盒處理，因此無法發現因為密碼算法的不合理帶來的安全漏洞。

3 可證明安全方法

可證明安全方法起源于密碼學團體，最初來自Goldwasser和Micali的研究。在公鑰簽名體制的可證明安全的發展過程中，Goldwasser等人在80年代中期提出了最重要的成果，攻擊者獲得適應性所選擇消息的簽名后，仍然不能以不可忽略優勢偽造一個新消息的簽名。該方法應用計算復雜性理論，通過對敵手攻擊成功概率和計算代價的評估來判斷協議的安全性。

可證明安全方法包括以下三個方面：

困難問題：公認在多項式時間內得到解決的概率是可忽略的問題。

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

歸約方法：歸約方法是可證安全理論中最常用到的工具，可證安全的主要技巧在于從攻擊能力到困難問題的歸約。對協議進行證明時，首先要構建安全模型，為攻擊者提供一種虛擬環境，使其發揮攻擊能力；還要建立挑戰算法，將安全問題歸約為數學難題，并且在模擬過程中將數學難題暗中嵌入，引導攻擊者解決該難題。目前的主流方法包括標準模型和隨機預言機模型。

4 隨機預言機模型下的可證明安全

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

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

1993年，Bellare和Rogaway兩位學者正式提出了ROM方法論，自此，可證明安全方法從理論研究走向實際應用，隨之產生了多個安全方案，同時，具體安全性的概念得以提出，安全性的漸進度已經滿足不了人們對于安全性的衡量，取而代之是得到確切的安全性度量。

5 標準模型下的可證明安全

標準模型將密碼學原語視為基礎部件，通過某種方式利用這些基礎部件構造更強大的原語。在ROM中證明了的方案安全并不能保障該方案在現實生活中的安全性。目前有許多安全方案可在ROM中證明安全，但是在實際應用中卻不能構造出與方案對應的實例。與之相比較，可證安全性在標準模型中更具現實意義。標準模型雖然也是通過預言機對于詢問進行應答，但與ROM不同，預言機內部映射要符合方案中的具體函數關系，因此，增加了設計難度。

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