寫給開發人員的實用密碼學（二）—— 哈希函數

2022 年 3 月 13 日
筆記
演算法

本文主要翻譯自 Practical-Cryptography-for-Developers-Book，但是筆者也補充了許多程式碼示例及演算法細節。

《寫給開發人員的實用密碼學》系列文章目錄：

一、什麼是哈希函數

哈希函數，或者叫散列函數，是一種從任何一種數據中創建一個數字指紋（摘要）的方法，散列函數把數據壓縮壓縮（或者放大）成一個長度固定的摘要。

哈希函數的輸入空間（文本或者二進位數據）是無限大，但是輸出空間（一個固定長度的摘要）卻是有限的。將「無限」映射到「有限」，不可避免的會有概率不同的輸入得到相同的輸出，這種情況我們稱為碰撞（collision）。

一個簡單的哈希函數是直接對輸入數據/文本的位元組求和。
它會導致大量的碰撞，例如 hello 和 ehllo 將具有相同的哈希值。

更好的哈希函數可以使用這樣的方案：它將第一個位元組作為狀態，然後轉換狀態（例如，將它乘以像 31 這樣的素數），然後將下一個位元組添加到狀態，然後再次轉換狀態並添加下一個位元組等。
這樣的操作可以顯著降低碰撞概率併產生更均勻的分布。

二、加密哈希函數

一個好的「加密哈希函數」必須滿足抗碰撞（collision-resistant）和不可逆（irreversible）這兩個條件。
抗碰撞是指通過統計學方法（彩虹表）很難或幾乎不可能猜出哈希值對應的原始數據，而不可逆則是說攻擊者很難或幾乎不可能從演算法層面通過哈希值逆向演算出原始數據。

一個理想的加密哈希函數，應當具有如下屬性：

快速：計算速度要足夠快
確定性：對同樣的輸入，應該總是產生同樣的輸出
難以分析：對輸入的任何微小改動，都應該使輸出完全發生變化
不可逆：從其哈希值逆向演算出輸入值應該是不可行的。這意味著沒有比暴力破解更好的破解方法
無碰撞：找到具有相同哈希值的兩條不同消息應該非常困難（或幾乎不可能）

現代加密哈希函數（如 SHA2 和 SHA3）都具有上述幾個屬性，並被廣泛應用在多個領域，各種現代程式語言和平台的標準庫中基本都包含這些常用的哈希函數。

量子安全性

現代密碼學哈希函數（如 SHA2, SHA3, BLAKE2）都被認為是量子安全的，無懼量子電腦的發展。

加密哈希函數的應用

1. 數據完整性校驗

加密哈希函數被廣泛用於文件完整性校驗。如果你從網上下載的文件計算出的 SHA256 校驗和（checksum）跟官方公布的一致，那就說明文件沒有損壞。

但是哈希函數自身不能保證文件的真實性，目前來講，真實性通常是 TLS 協議要保證的，它確保你在 openssl 網站上看到的「SHA256 校驗和」真實無誤（未被篡改）。

現代網路基本都很難遇到文件損壞的情況了，但是在古早的低速網路中，即使 TCP 跟底層協議已經有多種數據糾錯手段，下載完成的文件仍然是有可能損壞的。
這也是以前 rar 壓縮格式很流行的原因之一—— rar 壓縮文件擁有一定程度上的自我修復能力，傳輸過程中損壞少量數據，仍然能正常解壓。

2. 保存密碼

加密哈希函數還被用於密碼的安全存儲，現代系統使用專門設計的安全哈希演算法計算用戶密碼的哈希摘要，保存到資料庫中，這樣能確保密碼的安全性。除了用戶自己，沒有人清楚該密碼的原始數據，即使資料庫管理員也只能看到一個哈希摘要。

3. 生成唯一 ID

加密哈希函數也被用於為文檔或消息生成（絕大多數情況下）唯一的 ID，因此哈希值也被稱為數字指紋。

注意這裡說的是數字指紋，而非數字簽名。
數字簽名是與下一篇文章介紹的「MAC」碼比較類似的，用於驗證消息的真實、完整、作者身份的一段數據。

加密哈希函數計算出的哈希值理論上確實有碰撞的概率，但是這個概率實在太小了，因此絕大多數系統（如 Git）都假設哈希函數是無碰撞的（collistion free）。

文檔的哈希值可以被用於證明該文檔的存在性，或者被當成一個索引，用於從存儲系統中提取文檔。

使用哈希值作為唯一 ID 的典型例子，Git 版本控制系統（如 3c3be25bc1757ca99aba55d4157596a8ea217698）肯定算一個，比特幣地址（如 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2）也算。

4. 偽隨機數生成

哈希值可以被當作一個隨機數看待，生成一個偽隨機數的簡單流程如下：

通過隨機事件得到一個熵（例如鍵盤點擊或滑鼠移動），將它作為最初的隨機數種子（random seed）。
添加一個 1 到熵中，進行哈希計算得到第一個隨機數
再添加一個 2，進行哈希計算得到第二個隨機數
以此類推

當然為了確保安全性，實際的加密隨機數生成器會比這再複雜一些，我們會在後面的「隨機數生成器」一節學習其中細節。

安全的加密哈希演算法

1. SHA-2, SHA-256, SHA-512

SHA-2，即 Secure Hash Algorithm 2，是一組強密碼哈希函數：SHA-256（256位哈希）、SHA-384（384位哈希）、SHA-512（512位哈希）等。基於密碼概念「Merkle–Damgård construction」，目前被認為是高度安全。 SHA-2 是 SHA-1 的繼任者，於 2001 年在美國作為官方加密標準發布。

SHA-2 在軟體開發和密碼學中被廣泛使用，它被認為在密碼學上足夠強大，可用於現代商業應用。

SHA-256 被廣泛用於比特幣區塊鏈，例如用於識別交易哈希和礦工執行的工作證明挖掘。

Python 程式碼示例：

import hashlib, binascii

text = 'hello'
data = text.encode("utf8")

sha256hash = hashlib.sha256(data).digest()
print(f"SHA-256({text}) = ", binascii.hexlify(sha256hash).decode("utf8"))

sha384hash = hashlib.sha384(data).digest()
print(f"SHA-384({text}) = ", binascii.hexlify(sha384hash).decode("utf8"))

sha512hash = hashlib.sha512(data).digest()
print(f"SHA-512({text}) = ", binascii.hexlify(sha512hash).decode("utf8"))

輸出如下：

SHA-256('hello') = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-384('hello') = 59e1748777448c69de6b800d7a33bbfb9ff1b463e44354c3553bcdb9c666fa90125a3c79f90397bdf5f6a13de828684f
SHA-512('hello') = 9b71d224bd62f3785d96d46ad3ea3d73319bfbc2890caadae2dff72519673ca72323c3d99ba5c11d7c7acc6e14b8c5da0c4663475c2e5c3adef46f73bcdec043

2. 更長的哈希值 == 更高的抗碰撞能力

按照設計，哈希函數的輸出越長，就有望實現更高的安全性和抗碰撞能力（但也有一些例外）。
一般來說，128 位哈希演算法比 256 位哈希演算法弱，256 位哈希演算法比 512 位哈希演算法弱。

因此顯然 SHA-512 比 SHA-256 更強。我們可以預期，SHA-512 的碰撞概率要比 SHA-256 更低。

3. SHA-3, SHA3-256, SHA3-512, Keccak-256

在輸出的哈希長度相同時，SHA-3（及其變體 SHA3-224、SHA3-256、SHA3-384、SHA3-512）被認為擁有比 SHA-2（SHA-224、SHA-256、SHA-384、SHA-512）更高的加密強度。
例如，對於相同的哈希長度（256 位），SHA3-256 提供比 SHA-256 更高的加密強度。

SHA-3 系列函數是 Keccak 哈希家族的代表，它基於密碼學概念海綿函數。Keccak 是SHA3 NIST 比賽的冠軍。

與 SHA-2 不同，SHA-3 系列加密哈希函數不易受到長度拓展攻擊 Length extension attack.

SHA-3 被認為是高度安全的，並於 2015 年作為美國官方推薦的加密標準發布。

以太坊（Ethereum）區塊鏈中使用的哈希函數 Keccak-256 是 SHA3-256 的變體，在程式碼中更改了一些常量。

哈希函數 SHAKE128(msg, length) 和 SHAKE256(msg, length) 是 SHA3-256 和 SHA3-512 演算法的變體，它們輸出消息的長度可以變化。

SHA3 的 Python 程式碼示例：

import hashlib, binascii

text = 'hello'
data = text.encode("utf8")

sha3_256hash = hashlib.sha3_256(data).digest()
print(f"SHA3-256({text}) = ", binascii.hexlify(sha3_256hash).decode("utf8"))

sha3_512hash = hashlib.sha3_512(data).digest()
print(f"SHA3-512({text}) = ", binascii.hexlify(sha3_512hash).decode("utf8"))

輸出：

SHA3-256('hello') = 3338be694f50c5f338814986cdf0686453a888b84f424d792af4b9202398f392
Keccak-256('hello') = 1c8aff950685c2ed4bc3174f3472287b56d9517b9c948127319a09a7a36deac8
SHA3-512('hello') = 75d527c368f2efe848ecf6b073a36767800805e9eef2b1857d5f984f036eb6df891d75f72d9b154518c1cd58835286d1da9a38deba3de98b5a53e5ed78a84976

SHAKE-128('hello', 256) = 4a361de3a0e980a55388df742e9b314bd69d918260d9247768d0221df5262380
SHAKE-256('hello', 160) = 1234075ae4a1e77316cf2d8000974581a343b9eb

4. BLAKE2 / BLAKE2s / BLAKE2b

BLAKE / BLAKE2 / BLAKE2s / BLAKE2b 是一系列快速、高度安全的密碼學哈希函數，提供 160 位、224 位、256 位、384 位和 512 位摘要大小的計算，在現代密碼學中被廣泛應用。BLAKE 進入了SHA3 NIST 比賽的決賽。

BLAKE2 函數是 BLAKE 的改進版本。
BLAKE2s（通常為 256 位）是 BLAKE2 實現，針對 32 位微處理器進行了性能優化。
BLAKE2b（通常為 512 位）是 BLAKE2 實現，針對 64 位微處理器進行了性能優化。

BLAKE2 哈希函數具有與 SHA-3 類似的安全強度，但開發人員目前仍然更傾向於使用 SHA2 和 SHA3。

BLAKE 哈希值的 Python 示例：

import hashlib, binascii

text = 'hello'
data = text.encode("utf8")

blake2s = hashlib.new('blake2s', data).digest()
print("BLAKE2s({text}) = ", binascii.hexlify(blake2s).decode("utf-8"))

blake2b = hashlib.new('blake2b', data).digest()
print("BLAKE2b({text}) = ", binascii.hexlify(blake2b).decode("utf-8"))

輸出如下：

BLAKE2s('hello') = 19213bacc58dee6dbde3ceb9a47cbb330b3d86f8cca8997eb00be456f140ca25
BLAKE2b('hello') = e4cfa39a3d37be31c59609e807970799caa68a19bfaa15135f165085e01d41a65ba1e1b146aeb6bd0092b49eac214c103ccfa3a365954bbbe52f74a2b3620c94

5. RIPEMD-160

RIPEMD-160, RIPE Message Digest 是一種安全哈希函數，發佈於 1996 年，目前主要被應用在 PGP 和比特幣中。

RIPEMD 的 160 位變體在實踐中被廣泛使用，而 RIPEMD-128、RIPEMD-256 和 RIPEMD-320 等其他變體並不流行，並且它們的安全優勢具有爭議。

建議優先使用 SHA-2 和 SHA-3 而不是 RIPEMD，因為它們輸出的哈希值更長，抗碰撞能力更強。

Python 示例：

import hashlib, binascii

text = 'hello'
data = text.encode("utf8")

ripemd160 = hashlib.new('ripemd160', data).digest()
print("RIPEMD-160({text}) = ", binascii.hexlify(ripemd160).decode("utf-8"))

# => RIPEMD-160({text}) =  108f07b8382412612c048d07d13f814118445acd

6. 其他安全哈希演算法

以下是目前流行的強加密哈希函數，它們都可被用於替代 SHA-2、SHA-3 和 BLAKE2：

Whirlpool 發佈於 2000 年，此演算法輸出固定的 512 位哈希值。該演算法使用512位的密鑰，參考了分組密碼的思路，使用輪函數加迭代，演算法結構與 AES 相似。
SM3 是中國國密密碼雜湊演算法標準，由國家密碼管理局於 2010 年 12 月公布。它類似於 SHA-256（基於 Merkle-Damgård 結構），輸出為 256 位哈希值。
GOST（GOST R 34.11-94）哈希函數是俄羅斯的國家標準，它的輸出也是 256 位哈希值。

以下函數是 SHA-2、SHA-3 和 BLAKE 的不太受歡迎的替代品，它們是SHA3 NIST 比賽的決賽入圍者

Skein 能夠計算出 128、160、224、256、384、512 和 1024 位哈希值。
Grøstl 能夠計算出 224、256、384 和 512 位哈希值。
JH 能夠計算出 224、256、384 和 512 位哈希值。

不安全的加密哈希演算法

一些老一代的加密哈希演算法，如 MD5, SHA-0 和 SHA-1 被認為是不安全的，並且由於加密漏洞（發現碰撞）而被撤回。不要使用 MD5、SHA-0 和 SHA-1！這些哈希函數都被證明在密碼學上是不安全的。

使用這些不安全的哈希演算法，可能會導致數字簽名被偽造、密碼泄漏等嚴重問題！

另外也請避免使用以下被認為不安全或安全性有爭議的哈希演算法： MD2, MD4, MD5, SHA-0, SHA-1, Panama, HAVAL（有爭議的安全性，在 HAVAL-128 上發現了碰撞），Tiger（有爭議，已發現其弱點），SipHash（它屬於非加密哈希函數）。

PoW 工作量證明哈希函數

區塊鏈中的 Proof-of-Work 工作量證明挖礦演算法使用了一類特殊的哈希函數，這些函數是計算密集型和記憶體密集型的。
這些哈希函數被設計成需要消耗大量計算資源和大量記憶體，並且很難在硬體設備（例如積體電路或礦機）中實現，也就難以設計專用硬體來加速計算。這種哈希函數被稱為抗 ASIC，英文是 ASIC-resistant.

大部分工作量證明（Proof-of-Work）演算法，都是要求計算出一個比特定值（稱為挖掘難度）更大的哈希值。
因為哈希值是不可預測的，為了找出符合條件的哈希值，礦工需要計算數十億個不同的哈希值，再從中找出最大的那個。
比如，一個工作量證明問題可能會被定義成這樣：已有常數 x，要求找到一個數 p，使 hash(x + p) 的前十個比特都為 0.

有許多哈希函數是專為工作量證明挖掘演算法設計的，例如 ETHash、Equihash、CryptoNight 和 Cookoo Cycle.
這些哈希函數的計算速度很慢，通常使用 GPU 硬體（如 NVIDIA GTX 1080 等顯示卡）或強大的 CPU 硬體（如 Intel Core i7-8700K）和大量快速 RAM 記憶體（如 DDR4 晶片）來執行這類演算法。
這些挖礦演算法的目標是通過刺激小型礦工（家庭用戶和小型礦場）來最大限度地減少挖礦的集中化，並限制挖礦行業中高級玩家們（他們有能力建造巨型挖礦設施和數據中心）的力量。
與少數的高玩相比，大量小玩家意味著更好的去中心化。

目前大型虛擬貨幣挖礦公司手中的主要武器是 ASIC 礦機，因此，現代加密貨幣通常會要求使用「抗 ASIC 哈希演算法」或「權益證明（proof-of-stake）共識協議」進行「工作量證明挖礦」，以限制這部分高級玩家，達成更好的去中心化。

1. ETHash

這裡簡要說明下以太坊區塊鏈中使用的 ETHash 工作量證明挖掘哈希函數背後的思想。

ETHash 是以太坊區塊鏈中的工作量證明哈希函數。它是記憶體密集型哈希函數（需要大量 RAM 才能快速計算），因此它被認為是抗 ASIC 的。

ETHash 的工作流程：

基於直到當前區塊的整個鏈，為每個區塊計算一個「種子」
從種子中計算出一個 16 MB 的偽隨機快取
從快取中提取 1 GB 數據集以用於挖掘
挖掘涉及將數據集的隨機切片一起進行哈希

更多資訊參見 eth.wiki – ethash

2. Equihash

簡要解釋一下 Zcash、Bitcoin Gold 和其他一些區塊鏈中使用的 Equihash 工作量證明挖掘哈希函數背後的思想。

Equihash 是 Zcash 和 Bitcoin Gold 區塊鏈中的工作量證明哈希函數。它是記憶體密集型哈希函數（需要大量 RAM 才能進行快速計算），因此它被認為是抗 ASIC 的。

Equihash 的工作流程：

基於直到當前區塊的整個鏈，使用 BLAKE2b 計算出 50 MB 哈希數據集
在生成的哈希數據集上解決「廣義生日問題」（從 2097152 中挑選 512 個不同的字元串，使得它們的二進位 XOR 為零）。已知最佳的解決方案（瓦格納演算法）在指數時間內運行，因此它需要大量的記憶體密集型和計算密集型計算
對前面得到的結果，進行雙 SHA256 計算得到最終結果，即 SHA256(SHA256(solution))

更多資訊參見 //github.com/tromp/equihash

三、非加密哈希函數

加密哈希函數非常看重「加密」，為了實現更高的安全強度，費了非常多的心思、也付出了很多代價。

但是實際應用中很多場景是不需要這麼高的安全性的，相反可能會對速度、隨機均勻性等有更高的要求。
這就催生出了很多「非加密哈希函數」。

非加密哈希函數的應用場景有很多：

哈希表 Hash Table: 在很多語言中也被稱為 map/dict，它使用的演算法很簡單，通常就是把對象的各種屬性不斷乘個質數（比如 31）再相加，哈希空間會隨著表的變化而變化。這裡最希望的是數據的分布足夠均勻。
一致性哈希：目的是解決分散式快取的問題。在移除或者添加一個伺服器時，能夠儘可能小地改變已存在的服務請求與處理請求伺服器之間的映射關係。
高性能哈希演算法：SipHash MurMurHash3 等，使用它們的目的可能是對數據進行快速去重，要求就是足夠快。

有時我們甚至可能不太在意哈希碰撞的概率。
也有的場景輸入是有限的，這時我們可能會希望哈希函數具有可逆性。

總之非加密哈希函數也有非常多的應用，但不是本文的主題。
這裡就不詳細介紹了，有興趣的朋友們可以自行尋找其他資源。

參考

Tags: 演算法