雜湊演算法現狀——原因、方法及未來

新手在瞭解區塊鏈的時候經常會接觸到雜湊（hash）和雜湊演算法（hashing algorithm）這樣的概念，它們在安全方面可以說是無處不在。透過P2P執行像BTC/" target="_blank"">比特幣，以太坊之類有眾多節點的去中心化網路需要去信任機制和驗證的高效性。

這就是說，這些系統需要想辦法將資訊以一種高效而簡潔的方式編碼，並允許其參與者能夠安全而快速的進行驗證。

比特幣和以太坊所涉及的主要概念是“區塊”，這是一種包含交易記錄，時間戳以及其他後設資料的資料結構。這種資料結構安全性的關鍵在於：它能夠將大量關於全球網路狀態的資訊壓縮成一小段資訊標準，並使這一小段資訊能被高效的驗證，這一小段資訊被稱為雜湊。

即使僅僅改變輸入資訊的一個字元也會產生一個完全不同的雜湊值！

加密學上的雜湊被用於各行各業，從密碼儲存到檔案驗證系統。基本思想是使用一種確定性的演算法(deterministicalgorithm)，這種演算法能夠接受一個輸入並每次都產生一個長度固定的字串。也就是說，一個相同的輸入得到的永遠都是相同的輸出。

除了這種確定性，雜湊演算法還有一個特性：輸入中的任何一點點的改變都會導致輸出變得完全不同。

雜湊演算法有一個問題，就是衝突必然性（inevitability of collisions）。它的意思是：由於雜湊函式輸出的字串長度一定，不同的輸入有可能會產生相同的雜湊值。衝突是不好的，如果一個攻擊者能夠故意產生衝突，他便能夠把惡意的檔案或者資料偽裝成正確的雜湊值並將其傳遞下去。一個好的雜湊函式的目標是讓衝突的發生變得幾乎不可能。

計算一個雜湊值不應該太過高效，因為這會讓衝突的實現變得太過容易。雜湊演算法應該能夠抵禦“原像攻擊（pre-image attack）”。也就是說，根據已知的雜湊值找到輸入值應該是極其困難的（輸入值被稱作原像，比如s = hash(x)，根據s找到x應該是幾乎不可能的）。

總結起來，一個好的雜湊演算法應該具備以下特徵：

·改變輸入的任意一點都會產生一個完全不同的輸出

·發生衝突的可能性非常低

·在不犧牲抵禦衝突的情況下有一定的效率

攻擊雜湊

最初的雜湊演算法標準之一是MD5雜湊，它被廣泛的應用於檔案完整性驗證（校驗和），同時在網路應用的資料庫中用於儲存雜湊密碼。那時它的功能還十分簡單，因為不論輸入如何，輸出是一個固定的128位的字串，並且它使用並不有效的多輪單向操作（one-wayoperations across several rounds）來計算確定性輸出。

由於輸出字串長度較短以及操作較為簡單，MD5很容易被破解並易受生日攻擊（Birthday Attack）的侵擾。

什麼是“生日攻擊”？

你可能聽說過：如果一個房間裡有23個人，那麼兩兩生日重疊的可能性就有50%，而在一個房間內如果提高到70人，那麼這個概率就變成了99.9%。這就是鴿子洞原則（pigeonhole principle），如果有100只鴿子只有99個洞，那麼必然有一個洞中有兩隻鴿子。

放在雜湊演算法的案例中就變成了，一個固定長度的字串意味著一個固定的排列組合數量，因此當輸入值達到一定的數量時，衝突必然會發生。

太多鴿子了！至少有一隻鴿子會與另一隻共用一個洞

MD5抵禦衝突的能力如此之弱，以至於一個2.4GHz的奔騰處理器都能在數秒之內製造一次雜湊衝突。事實上，由於MD5在較早年代的廣泛應用，已經有大量的原像線上上洩漏，你甚至可以用簡單的谷歌搜尋來找到它們。

多樣性和雜湊演算法的進化

開端：SHA1 & SHA2

美國國家安全域性（NSA）一直都是雜湊演算法標準方面的先驅，他們最早提出安全雜湊演算法，也就是SHA1，這個演算法輸出的是160位固定長度的字串。

然而，SHA1僅僅在MD5的基礎上提高了輸出的長度，單向操作的數量以及單向操作的複雜性，但未做任何根本改進來使其能夠抵禦更強大的機器，這些機器嘗試不同的攻擊向量。

那麼我們該如何提高呢？

SHA3

在2006年，美國國家標準與技術研究所（NIST）發起了一場尋找一個與SHA2從根本上不同的替代品，讓它成為新的演算法標準。因此，SHA3的誕生是雜湊演算法偉大機制的一部分，它被稱為KECCAK。

雖然名字看上去差不多，SHA3內部與之前的演算法完全不同，因為它擁有海綿結構（Sponge Construct）機制。這種結構使用隨機的排列組合來吸收和輸出資料，同時還能為未來輸入值提供隨機源。

KECCAK256海綿結構作用於輸入值

SHA3維持一個內部狀態，使得輸出資訊比字串長度長（依然能夠做到對於資訊的壓縮），這使它克服了先前演算法的侷限性。它也在2015年成為了NIST的標準演算法。

雜湊和PoW

當雜湊演算法被整合到區塊鏈協議中的時候，更老一些的比特幣選擇了SHA256演算法，而以太坊選擇了改良版的SHA3（KECCAK256）作為PoW的演算法。一個在區塊鏈PoW協議中選擇雜湊函式的重要標準是計算雜湊值的效率。

對比特幣SHA256演算法的執行效率可以透過製造諸如ASICs礦機之類的專門硬體來進一步提高。這表現在礦池中ASICs的使用，並使協議趨向於計算中心化。

也就是說，PoW鼓勵高效的計算群體聚合成更大的群體（礦池）從而提高我們所說的雜湊算力（也就是一個機器在固定的時間間隔能夠計算的雜湊數量）。

以太坊，選擇了改良後的SHA3，也被稱作KECCAK256。此外，以太坊的PoW演算法（Dagger-Hashimoto）設計成硬體記憶體難以計算，這從一定程度上避免了ASICs礦機的使用。

為什麼比特幣要使用雙重SHA256？

比特幣使用SHA256來轉換資料的方式很有趣，它將演算法在協議中連續執行了兩次。注意，這並不是為了抵禦生日攻擊，顯然如果hash(x) = hash(y) 那麼也有hash(hash(x)) = hash(hash(y))，而是為了緩解長度擴充套件（length-extension）攻擊。

從本質上說，這種攻擊需要惡意攻擊者知道雜湊輸入值的長度，在這個已知的長度上再加上一個秘密的字串，就可以發動雜湊函式內部的一部分，從而擾亂雜湊函式。由於SHA256是SHA2演算法家族的成員，它有這一類的短板，而比特幣透過將雜湊函式連續執行兩次來緩解這個缺陷。

以太坊2.0和BLAKE

SHA3並不是NIST在2006年發起的那場競賽中唯一的突破。雖然SHA3最終獲勝，一個叫做BLAKE的演算法緊隨其後位居第二。對於以太坊2.0分片的執行，更高效的雜湊演算法可以說是必不可少的。

BLAKE2b雜湊演算法是一個在競賽之後被高度升級最佳化過的版本，由於在保持高度安全性的同時擁有極高的效率（跟KECCAK256相比），這個演算法也經歷了較為徹底的測試。

在一個現代CPU上計算BLAKE2b實際上比KECCAK要快3倍。

雜湊演算法的未來

看起來無論我們做什麼，要麼是在（1）提高雜湊函式內部操作的複雜性，要麼是在（2）提高雜湊輸出的長度，寄希望於攻擊者的計算機由於速度不夠快而無法有效產生計算衝突。

我們網路的安全性目前依賴著單向操作原像的模糊性。也就是說一個雜湊演算法的安全目標是讓任何人找到具有兩個相同輸出的值變得越難越好，從而使得雜湊衝突的可能性儘可能的小，雖然依舊存在無限數量的可能的衝突。

那麼量子計算呢？在量子計算面前雜湊演算法足夠安全嗎？

根據目前的理解，簡單的回答是：安全。雜湊演算法將能夠經受量子計算的挑戰。量子計算能夠破解那些諸如RSA加密問題，這些問題具有嚴格的底層數學結構，它們由巧妙的技巧和理論構建。而雜湊演算法內部構造中並沒有那麼正式的結構。

量子計算機確實可以加快計算非結構化問題（如雜湊）的速度，但是到最後，量子計算機發起攻擊的方式依然是暴力破解，和傳統的計算機並沒有什麼不同。

不論我們選擇什麼演算法，顯然我們都在駛向一個計算更高效的未來，我們必須盡全力挑選最好的工具並經得起時間的考驗。

------

風險警示：藍狐筆記所有文章都不構成投資推薦，投資有風險，投資應該考慮個人風險承受能力，建議對專案進行深入考察，慎重做好自己的投資決策。

本文已加入“POB.Network腦力挖礦”內容天使合夥人計劃。

通往區塊鏈的新世界：關注“藍狐筆記”區塊鏈公眾號：lanhubiji 

或加入藍狐筆記的知識星球：https://t.zsxq.com/iaQNnIq