這是關于隨機預言模型系列文章的第五部分。 點擊如下鏈接查看之前的文章:
第一部分: 介紹
第二部分: ROM 的形式化，方案和證明簡介
第三部分: 我們?nèi)绾螢E用 ROM 來使我們的安全證明工作
第四部分：ROM 使用案例
大約八年前，我開始寫一篇特別不夠正式的文章，討論一種特定的密碼建模技術，稱為“隨機預言模型”。 這要追溯到2011年的美好時光，那是一個密碼學更加天真和溫和的時代。 當時沒有人預見到我們所有的標準密碼學最終都將被弄的漏洞百出; 你不需要被提醒“加密就是密碼學”的意思。 人們甚至用比特幣來購物。
第一篇隨機預言的文章不知怎地就出現(xiàn)了三個結(jié)局，并且一個比一個更荒謬。 我想，在某種程度上，我對整件事感到很尷尬——說實話，這件事挺俗氣的——所以我有點半途而廢打算放棄了。 這是我后悔的主要原因之一，因為我一直計劃要發(fā)表第五篇文章，也是最后一篇文章，來結(jié)束這一團糟的事情。這篇文章將是本系列文章中最好的一篇，也是我一直想寫的一篇。
為了給你提供一些上下文，我會簡要地說明隨機預言模型是什么，以及你為什么應該關心它。 (當然你最好還是讀讀這個系列的前幾篇文章。)
隨機預言模型是一種對哈希函數(shù)進行建模的瘋狂方法，我們假設這些函數(shù)實際上是隨機函數(shù)，并利用這一假設來證明密碼協(xié)議中的一些事情，如果沒有這樣一個模型，這些事情是很難證明的。 幾乎所有我們今天使用的“可證明的”密碼學都依賴于這個模型，這意味著如果這些證明是“錯誤的” ，那么這些證明中的許多東西將會受到質(zhì)疑。
為了梳理這篇文章的其余部分，我將引用第四部分的最后一段話，以下面的內(nèi)容結(jié)束:
你看，我們一直都知道這次旅行不會永遠持續(xù)下去，我們只是覺得我們還有更多的時間。不幸的是，末日即將來臨。就像萊昂納多·德·卡普里奧在《盜夢空間》無聊的情節(jié)中探索的那個虛構(gòu)的城市一樣，隨機預言模型在自身矛盾的壓力下崩潰了。
正如我之前所承諾的那樣，這篇文章會講述那次“崩潰”，以及它對密碼學家、安全專家和我們其他人意味著什么。
首先，為了使這篇文章更加自成一體，我想回顧一下我在本系列文章前面討論過的一些基本內(nèi)容。 如果你讀過前面的幾篇文章，你可以跳過這一部分。
我們將(很快)提醒讀者什么是哈希函數(shù)，什么是隨機函數(shù)，什么是隨機預言
正如在本系列的前幾篇文章中所討論的，哈希函數(shù)(或哈希算法)是計算機科學的許多領域中使用的標準原語。 它們接受一些輸入，通常是一個可變長度的字符串，并可重復地輸出一個短的、固定長度的“摘要”。 我們經(jīng)常這樣表示這些函數(shù):
加密哈希使用這個基本模板并利用加密應用程序所需的一些重要安全屬性。 最著名的是，它們提供了一些眾所周知的屬性，比如抗碰撞性，這是數(shù)字簽名等應用程序所需要的。但哈希函數(shù)在密碼學中到處都會出現(xiàn)，有時出現(xiàn)在意想不到的地方，從加密到零知識協(xié)議，有時這些系統(tǒng)需要更強的特性。 這些有時很難用形式化的術語表示: 例如，許多協(xié)議需要一個哈希函數(shù)來產(chǎn)生極其“隨機”的輸出。
在可證明安全性的早期，密碼學家意識到理想的哈希函數(shù)的行為類似于“隨機函數(shù)”。 這個術語指的是從所有可能的函數(shù)集中均勻采樣的函數(shù)，這些函數(shù)具有適當?shù)妮斎?/ 輸出規(guī)范(域和范圍)。 在一個完美的世界里，你的協(xié)議可以，例如，在設置時隨機抽取大量可能的函數(shù)中的一個，將該函數(shù)的標識符放入一個公鑰或其他什么東西中，然后你就可以開始工作了。
不幸的是，在實際協(xié)議中不可能真正使用隨機函數(shù)(適當規(guī)模的域和范圍)。 這是因為抽樣和評估這些函數(shù)的工作量太大了。
例如，使用很少的256位輸入并生成256位摘要的不同函數(shù)的數(shù)量是令人難以置信的(2 ^ ) ^ 。簡單地“寫下”你所選擇的函數(shù)的恒等式將需要在函數(shù)輸入長度中呈指數(shù)級的內(nèi)存。由于我們希望我們的加密算法是有效的(意思是，稍微正式一點，它們在多項式時間內(nèi)運行)，使用隨機函數(shù)幾乎是不可用的。
所以我們不使用隨機函數(shù)來實現(xiàn)哈希。 在“現(xiàn)實世界”中，我們使用比利時人或國家安全局開發(fā)的奇怪函數(shù)，比如 SHA256、 SHA3和 Blake2。 這些函數(shù)具有極快的運算速度和微小的算法來執(zhí)行計算，其中大多數(shù)只占用幾十行或更少的代碼。 它們當然不是隨機的，但據(jù)我們所知，輸出看起來相當混亂。
盡管如此，協(xié)議設計者仍然渴望使用真正的隨機函數(shù)能夠給他們的協(xié)議帶來安全性。 他們會問，如果我們折中一下，結(jié)果會怎樣?如果我們使用隨機函數(shù)來建模我們的哈希函數(shù)——只是為了編寫我們的安全證明——然后當我們實現(xiàn)(或“實例化”)我們的協(xié)議時，我們將使用高效的哈希函數(shù)，比如SHA3，會怎么樣呢?當然，這些證明并不完全適用于實例化的實際協(xié)議，但它們可能仍然很好。
使用這種范式的證明被稱為隨機預言模型(ROM)中的證明。 關于 ROM 如何工作的完整機制，可以翻閱我之前發(fā)表的該系列文章。 你現(xiàn)在需要知道的是，在這個模型中的證明必須以某種方式繞過，即計算一個隨機函數(shù)需要花費大量指數(shù)級的時間。 這個模型處理這個問題的方法很簡單: 它沒有給每個協(xié)議參與者一個關于哈希函數(shù)本身的描述(哈希函數(shù)對任何人來說都太大了) ，而是給每個參與者(包括對手)一個神奇的“預言” ，這個預言可以有效地評估隨機函數(shù) H，并將結(jié)果返回給他們。
這意味著任何時候其中一方想要計算函數(shù)，他們自己并不能獨自完成。 相反，它們會調(diào)用第三方，即“隨機預言”，“隨機預言”擁有一個巨大的隨機函數(shù)輸入和輸出表。 在高層次上，這個模型看起來有點像下面這樣:
因為系統(tǒng)中的所有參與方都與同一個預言在“對話” ，所以當他們要求預言對給定的消息進行哈希時，都會得到相同的哈希結(jié)果。 對于真正的哈希函數(shù)來說，這是一個相當好的替代函數(shù)。 使用外部的預言可以讓我們“掩蓋”評估隨機函數(shù)的成本，這樣就沒有人需要花費一個指數(shù)級的時間來評估一個函數(shù)。 在這個人工模型中，我們得到了理想的哈希函數(shù)，而且沒有任何麻煩。
這看起來已經(jīng)很可笑了……
絕對是這樣！
然而，我認為在你認為隨機預言模型是個空洞的事物之前，你應該知道幾件非常重要的事情:
1. 當然，每個人都知道隨機的預言證明不是“真的”。 大多數(shù)認真的協(xié)議設計者都會承認，在隨機預言模型中證明某些東西是安全的，并不意味著它在“現(xiàn)實世界”是安全的。 換句話說，隨機的預言模型證明是偽造的這一事實，這并不是我想讓你們知道的秘密。。
2. 總之: ROM 證明通常被認為是一種有用的啟發(fā)式方法。 對于那些不熟悉“啟發(fā)式”這個術語的人來說，“啟發(fā)式”是一個成年人用來保護你畢生積蓄的詞，因為他們使用的密碼學無法證明任何事情。
OK，開個玩笑！ 事實上，隨機預言證明仍然是很有價值的。 這主要是因為它可以經(jīng)常幫助我們檢測方案中的缺陷。 也就是說，雖然隨機預言證明在現(xiàn)實世界中并不意味著安全性，但不能編寫這樣的證明通常是協(xié)議的危險信號。 此外，ROM證明的存在有希望表明協(xié)議的“核心”是正常的，并且任何現(xiàn)實世界中出現(xiàn)的問題都與哈希函數(shù)有關。
3. 經(jīng)過ROM驗證的方案在實踐中有著相當不錯的記錄。 如果 ROM 驗證每隔一天就會提出一些荒謬而被破壞的方案，我們很可能就已經(jīng)放棄了這種技術。 然而，我們使用的密碼學幾乎每天都在 ROM 中得到驗證(僅僅是驗證) ，而且大多數(shù)情況下它確實奏效。
這并不是說，當用特定的哈希函數(shù)實例化時，經(jīng)過 ROM 證明的方案從未被破壞。 但通常情況下，這些破壞是因為哈希函數(shù)本身明顯存在缺陷(正如 MD4和 MD5不久前都break 掉時所發(fā)生的情況) ，盡管如此，這些缺陷通?？梢酝ㄟ^簡單地切換到一個更好的函數(shù)來進行修復。 此外，從歷史上看，實際攻擊更可能來自明顯的缺陷，比如發(fā)現(xiàn)哈希碰撞破壞了簽名方案，而不是來自某種奇特的數(shù)學缺陷。 這就讓我們注意到了最后一個關鍵的點..。
4. 多年以來，許多人相信只讀存儲器實際上是可以被保存的。 這種希望是由這樣一個事實驅(qū)動的：即 ROM 方案在實現(xiàn)了強哈希函數(shù)時似乎工作得很好，所以也許我們所需要做的就是找到一個哈希函數(shù)，使 ROM 證明變得有意義。 一些理論家希望像密碼混淆這樣的奇特技術能夠以某種方式使具體的哈希算法運行良好，使(某些) ROM 證明可以實例化。
所以這就是 ROM 的狀態(tài)，或者至少是直到20世紀90年代末的狀態(tài)。 我們知道這個模型是人造的，但它固執(zhí)地拒絕爆炸或產(chǎn)生完全無意義的結(jié)果。
然后，在1998年，一切都變糟了。
CGH98: 一個“不可實例化”的方案
對于理論密碼學家來說，隨機預言模型的真正破裂點來自于 Canetti，Goldreich 和 Halevi (以下簡稱 CGH)在1998年發(fā)表的一篇 STOC 論文。 我打算把剩下的時間來解釋他們發(fā)現(xiàn)的要點。
CGH 所證明的是，實際上，有一些加密方案可以在隨機預言模型中被證明是完全安全的，但是，當你用任何具體函數(shù)實例化哈希函數(shù)時，這種安全性就會變得非常危險。
這是一個非常可怕的結(jié)果，至少從可證明的安全社區(qū)的角度來看是這樣。 從理論上來說，你的證明可能不夠有力，這是一回事。 而另一回事則是，你要知道，在實踐中，有些方案可以直接通過你的證據(jù)，就像終結(jié)者滲透到抵抗組織，然后以最嚴重的方式在你身上爆發(fā)。
在我們詳細介紹CGH及其相關結(jié)果之前，有幾點需要注意。
首先， CGH很大程度上是一個理論結(jié)果。解決這個問題的密碼“反例”方案通?？雌饋聿幌裎覀儗⒃趯嵺`中使用的真正的密碼系統(tǒng)，盡管后來的作者提供了一些更“現(xiàn)實”的變體。事實上，這些變體是被設計用來做一些“真實的”方案不會做的但卻是非常“人為的”事情。這可能會導致讀者會以“人為的”這一理由對它們不屑一顧。
這種觀點的問題在于，外表并不是判斷一個方案的特別科學的方法。 如果證明是正確的，那么“真實的”和“人為的”方案都是有效的密碼系統(tǒng)。 這些具體的反例的要點是故意做“人為的”事情，以突出問題的 ROM。 但這并不意味著“現(xiàn)實的”方案不能解決這些問題。
這些“人為”的方案的另一個優(yōu)點是，它們使基本概念相對容易解釋。 作為對這一點的進一步說明:而不是解釋CGH本身，我將使用一個由Maurer, Renner和Holenstein (MRH)提出的相同基本結(jié)果的公式。
一個簽名方案
CGH-style 的反例的基本思想是構(gòu)造一個“人為的”方案，這個方案在 ROM 中是安全的，但是當我們使用任何具體的函數(shù)“實例化”哈希函數(shù)時，它就完全崩潰了。
雖然 CGH 可以應用于許多不同類型的密碼系統(tǒng)，在這個解釋中，我們將使用一個相對簡單的系統(tǒng)類型開始我們的例子: 一個數(shù)字簽名方案。
你可能還記得本系列的前幾章內(nèi)容，一個普通的簽名方案由三個算法組成: 密鑰生成、簽名和驗證。 密鑰生成算法輸出一個公鑰和私鑰。 簽名使用秘鑰對消息進行簽名，并輸出簽名。 驗證采用結(jié)果簽名、公鑰和消息，并確定簽名是否有效: 如果簽名檢查出來，則輸出“True” ，否則輸出“False”。
傳統(tǒng)上，我們要求簽名方案(至少)在選擇消息攻擊(UF-CMA)下是不可偽造的。 這意味著我們可以考慮一個高效的(多項式時間有限的)攻擊者，他可以在選擇的消息上要求簽名，這些消息是由包含私鑰簽名密鑰的“簽名預言”生成的。 我們對安全方案的期望是，即使給出了這種訪問權限，也沒有攻擊者能夠在一些他沒有要求簽名的新消息上簽名，除非有極小的可能性。
在解釋了這些基本知識之后，讓我們來討論一下我們將如何使用簽名。 這將涉及以下幾個步驟:
第一步: 從一些現(xiàn)有的安全簽名方案入手。 我們從哪個簽名方案開始并不重要，只要我們可以假設它是安全的(根據(jù)上面描述的 UF-CMA 定義) ，這個現(xiàn)有的簽名方案將用作我們要構(gòu)建的新方案的構(gòu)建塊。 我們將這個方案命名為 S。
步驟2: 我們將使用現(xiàn)有的方案 S 作為構(gòu)建塊來構(gòu)建一個“新的”簽名方案，我們將調(diào)用這個方案。 構(gòu)建這個新方案主要是將奇怪的花哨功能嫁接到原方案 S 的算法上。
步驟3: 接下來是詳細的工作描述，我們認為它是完全安全的ROM。自從我們開始(假定)安全的簽名方案后，這個論點主要歸結(jié)為我們在上一步中的隨機預言模型附加功能中添加的功能并不是可攻擊的。
步驟4: 最后，我們將證明，當你使用任何具體的哈希函數(shù)實例化隨機預言時，無論它看起來多么“安全” ，這種情況都是完全不存在的。 簡而言之，我們將展示如何用真正的哈希函數(shù)替換隨機的預言，這里有一個簡單的攻擊方式，這種攻擊總是能夠成功地偽造簽名。
欲知后事如何，請聽下回分解！
