雜湊函式的過去、現在與未來

買賣虛擬貨幣
雜湊值和雜湊函式的概念是初次入門區塊鏈的人常聽到的兩個關鍵詞,而且似乎對安全性來說特別關鍵。(實際上也確實是。)對於像比特幣和以太坊這樣由成千上萬的節點透過 P2P 方法組成的去中心化網路來說,“免信任性” 和驗證效率無疑是關鍵。也就是說,這些系統需要找到方法把資訊編碼成緊湊的形式,同時讓參與者能夠安全快速地進行驗證。

比特幣和以太坊網路所處理的主要內容叫做 “區塊”,指的是由交易、時間戳和其他重要後設資料所組成的資料結構。比特幣和以太坊網路的安全性的關鍵一環是:它能將表達網路全域性狀態的大塊資訊壓縮成一個簡短的訊息。在有需要之時,我們可以高效地驗證這個訊息的真實性。這個過程就是用雜湊函式來完成的,而得到的結果(訊息)就是雜湊值。

- 即使只更改輸入中的一個字元,最後得出的雜湊值也會完全不同 -
密碼學雜湊廣泛應用於口令儲存和檔案驗證系統。簡單來說,密碼學雜湊函式是一種確定性的演算法,不論輸入什麼值,都能得到一個固定長度的字串。也就是說,同一個輸入值始終對應同一個輸出值。對雜湊函式來說,重要的不僅是確定性(還有結果的隨機性):即使只更改輸入中的一個位元位,也會導致最終得到的雜湊值截然不同。
雜湊演算法有一個無可迴避的問題叫碰撞可能性。因為雜湊值是固定長度的字串,同一個雜湊有可能對應多個輸入。碰撞會造成很嚴重的後果。如果有人能夠按需要發起碰撞攻擊,他就可以用恰當的雜湊值將惡意檔案或資料偽裝成合法的、能夠透過驗證的檔案。好的雜湊函式的設計目標是讓攻擊者極難找到方法來找出對應同一個雜湊的不同輸入。雜湊計算的效率不應過高,以免讓攻擊者可以更簡單地人為計算出碰撞。雜湊演算法必須能夠抵禦“原像攻擊(pre-image attack)”。也就是說,對於特定雜湊值,攻擊者很難透過確定性計算步驟倒推出輸入值(即,原像)。假設 s = hash(x),倒推 x 應該是近乎不可能的。總的來說,“好的” 雜湊演算法需要具備以下 3 個特性:· 更改輸入中的一個位元位會產生雪崩效應,導致最後得出的雜湊值截然不同· 出現雜湊碰撞的概率非常低
· 在無需犧牲抗碰撞性的前提下計算效率過得去破解雜湊演算法雜湊演算法的初始標準之一是 MD5 雜湊。MD5 雜湊廣泛應用於檔案完整性驗證(校驗和),以及在網路應用資料庫中儲存經過雜湊計算的賬號口令。MD5 的功能非常簡單,因為它會將每個輸入轉換成一個固定的 128 位字串輸出,並透過多輪簡單的單向操作來計算確定性輸出。由於輸出值長度較短,操作又較為簡單,MD5 很容易被破解,一種常見的攻擊方法叫生日攻擊。“生日攻擊” 是啥玩意?你有沒有聽說過這樣一個事實?如果你將 23 個人放到一個房間裡,其中兩個人生日相同的概率為 50% 。如果將 70 個人放到一個房間裡,其中兩個人生日相同的概率高達 99.9% 。這就是我們所說的鴿籠原理(pigeonhole principle),即,將 100 只鴿子裝進 99 個鴿籠,必然有兩隻鴿子分享同一個鴿籠。也就是說,固定長度的輸出意味著所有輸入輸出組合中一定存在碰撞。

事實上,MD5 的抗碰撞性太差,以至於一臺家用 2.4 GHz 奔騰處理器都能在幾秒內計算出雜湊碰撞。此外,由於 MD5 在網際網路早期階段得到了廣泛應用,網路上有大量 MD5 原像遭到洩漏,透過谷歌搜尋它們的雜湊值就能找到。

雜湊演算法的多樣性發展

源起:SHA1 和 SHA2

NSA (沒錯,就是美國國家安全保障局)是雜湊演算法標準的先驅。安全雜湊演算法(Secure Hashing Algorithm,SHA1)是最早提出的標準,將輸出值的長度固定在 160 位。遺憾的是,SHA1 只是在 MD5 的基礎上增加了輸出值長度、單向操作的次數和複雜度,但是並沒有作出能夠抵禦更強大機器攻擊的根本性改進。

我們如何才能做得更好?

SHA3 興起

在 2006 年,美國國家標準技術研究所(NIST)舉辦了一場競賽,旨在找到一個本質上不同於 SHA2 的替代標準。因此,SHA3 應運而生,它是 KECCAK 雜湊演算法的一種方案。

雖然 SHA 3 在名稱上與 SHA1 和 SHA2 一脈相承,但是在本質上差異很大,因為它採用了一種名為海綿結構(sponge construct)的機制。該機制使用隨機排列來吸收並輸出資料,同時為將來用於雜湊演算法的輸入值提供隨機性。

SHA3 的內部狀態相較於輸出值擁有更多資訊,突破了以往演算法的侷限性。NIST 於 2015 年正式認可了 SHA3 標準。

雜湊計算和工作量證明

就整合進區塊鏈協議的雜湊演算法而言,比較早的比特幣選擇了 SHA256 ,而以太坊採用了改進後的 SHA3 (KECCAK256)作為工作量證明演算法。對於採用工作量證明的區塊鏈來說,選擇雜湊函式的一大重要標準是雜湊運算效率。

使用一類名為專用積體電路(ASIC)的硬體,我們可以大幅提高比特幣 SHA256 演算法的雜湊運算的效率。有很多文章已經闡述了礦池是如何利用 ASIC 的,以及 ASIC 是如何讓協議趨向於計算中心化的。也就是說,工作量證明會激勵計算效率較高的機器聚整合礦池,從而形成較大的雜湊算力(算力大小的衡量標準就是礦機在每個時間間隔內可以完成多少次雜湊運算)。

以太坊選擇的是改進後的 SHA3 演算法(叫做 KECCAK256 )。此外,以太坊的工作量證明演算法 Dagger-Hashimoto 被設計成了記憶體密集型模式,計算硬體需要加大記憶體才能提高計算效率。

為什麼比特幣採用雙重 SHA256 ?

有趣的是,比特幣協議(的工作量證明)需要重複執行兩遍 SHA256 演算法。請注意,這不是為了抵禦生日攻擊,畢竟在 hash(x) = hash(y) 的情況下,hash(hash(x)) = hash(hash(y)) 。雙重 SHA256 旨在抵禦長度擴充套件攻擊。

從本質上來說,所謂的長度擴充套件攻擊,指的是如果惡意攻擊者知道了某個雜湊輸入的長度,就可以在雜湊值上新增一個秘密的字串、欺騙雜湊函式從其內部狀態的一個特定部分開始計算。作為 SHA2 演算法家族的一員,SHA256 也存在這一缺陷。因此,比特幣採取執行兩遍雜湊計算的方式來解決這一缺陷。

Ethereum 2.0 和 BLAKE

SHA3 並非雜湊演算法競賽取得的唯一突破。雖然最終勝出的是 SHA3 ,但是 BLAKE 演算法緊隨其後,位居第二。對於以太坊 2.0 的分片實現來說,更高效的雜湊演算法可以說是一項功能性要求,研究團隊對此非常重視。BLAKE2b 雜湊演算法是 BLAKE 演算法的高度升級版本。與 KECCAK256 相比,BLAKE2b 雜湊演算法在保持高度安全性的同時,在提升效率方面也進行了深入探索。

使用一臺現代 CPU 計算 BLAKE2b 的速度比計算 KECCAK 快了 3 倍。

雜湊演算法的前景展望

這麼看來,無論我們做了什麼,無非就是(1)增加內部雜湊操作的複雜度,或者(2)增加雜湊輸出值的長度,讓攻擊者的計算機無法足夠快地有效計算出碰撞。

我們依靠單向操作的原像模糊性來保護網路的安全性。也就是說,雜湊演算法的安全性目標是在有無限多可能的衝突的情況下,讓找出雜湊碰撞的難度儘可能高。

如果量子計算時代到來,雜湊演算法依然安全嗎?

就目前來看,答案是肯定的,雜湊演算法將經受時間的考驗,抵禦量子計算。量子計算能夠解決的是那些嚴格按照某些小技巧或 RSA 加密理論打造底層結構的數學問題。另一方面,雜湊演算法的內部構造沒那麼形式化。

量子計算機確實能夠提高雜湊等非結構化問題的計算速度,但它們最終還是會像如今的計算機一樣採取暴力破解手段。
無論我們為協議選擇了哪種演算法,我們顯然都在邁向計算高效化的未來。為此,我們必須慎重選擇最合適的工具,使之經受住時間的檢驗。

參考文獻

[1]: https://bitcoin.stackexchange.com/questions/6037/why-are-hashes-in-the-bitcoin-protocol-typically-computed-twice-double-computed
[2]: https://en.wikibooks.org/wiki/Cryptography/Breaking_Hash_Algorithms
[3]: https://learncryptography.com/hash-functions/hash-collision-attack
[4]: https://github.com/zcash/zcash/issues/2233
[5]: https://crypto.stackexchange.com/questions/18612/how-is-sha1-different-from-md5
[6]: https://en.wikipedia.org/wiki/Birthday_attack
[7]: https://keccak.team/
[8]: https://en.wikipedia.org/wiki/Cryptographic_hash_function
[9]: https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;