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