抗碰撞的雜湊函數真的不會有碰撞嗎？

使用 hash function (雜湊函數) 前，必須了解一個很重要的問題: 對兩個不同的數 x、y 來說，hash(x) 等於 hash(y) 的機率有多少？若應用情境是資料結構的 hash table，那麼 hash(x) 和 hash(y) 相等並不嚴重，可以用 chaining 或 open addressing 解。不過這並非本篇想討論的點。

另一方面，像是檢查下載檔案正確性 (例如 Subresource Integrity)，或帳戶位置 (例如 Bitcoin address 和 Ethereum address )， 無法容許 hash function 接受兩個不同輸入卻產生一樣的輸出。具有這種「很難找到兩個不同輸入產生相同輸出」的 hash function，我們說它具有 collision resistance (抗碰撞) 的性質。

違反直覺的性質

目前常用的 hash function 像是 SHA-256、SHA-3 是 “被相信” 有 collision resistance ，而不是有數學證明擔保。另一方面，雖然存在可用數學證明有有此性質的函數，但它們效率太差，並不實用。

以 SHA3 -256 為例，輸入可以是任意大小的資料，輸出固定是 256 bit。直覺來看，將無窮大的空間投影到一個固定大小的空間，怎麼可能沒有碰撞？所以，我們真正關心的是: 資料量多大時，才比較容易發生碰撞？或著說，資料量多少內，幾乎不用擔心碰撞？

生日悖論 (Birthday Paradox)

我們可以用生日悖論來回答此問題。

問題: 一年有 365 天，一個房間裡有多少人後，有過半的機率會有兩人生日一樣？聽起來應該要很多人，但答案卻是 23 人。因為和直觀印象差距很大，所以說是悖論。

由此推廣的一般性問題，就是具 collision resistance 的 hash function 能處理多少筆輸入，而不用擔心有 collision？比方說 SHA-256 的輸入最大可到 2⁶⁴-1 bits，輸出是 256 bits。那麼，SHA-256 處理多少組數字後，會有 collision？

假設攻擊者無法破解 SHA-256，只能從 [0, 2²⁵⁶-1] 裡隨機選 n 個數字亂猜。那麼，差不多要 2¹²⁸ 次才會有 collision。

計算方法

Wikipedia 提供幾種算法，這裡我想說的是另一種直觀解析。

假設從數量為 s 的集合抽樣 n 次，n 個取樣都不重覆，可看成有 (a, b), (a, c), … 共 C(n, 2) 個數對，數對裡兩數相等的機率是 1/s。

C(n, 2) 差不多是 n²，期望 n² * 1/s 差不多是 1 的話，得出

  n² / s = 1
→ n²     = s
→ n      = s^(1/2)

所以長度為 256-bit 的字串，共有 2²⁵⁶ 種字串，差不多取樣 2¹²⁸ 個數後，會出現重覆數。

可以代些數字粗估數量級，感覺一下有多可靠。若期望 n² / 2²⁵⁶ = 1/10¹⁸。計算後得出 n 差不多是 2¹²⁸ / 10⁹，仍然是極大的數字 (比 10²⁹ 大)，但估計相撞的機率接近 1/10¹⁸，相當於中獎率百萬分之一的樂透連中三次。

推廣到多個重覆數

同樣問題，求 n 多大時，三個取樣很可能是同一個數。

用同樣思路，共有 C(n, 3) = O(n³) 個數對 (x1, x2, x3)，三者一樣的機率是 1/s²。

  n³ / s² = 1
→ n³      = s²
→ n       = s^(2/3)

由此類推，抽樣 n = s^( (k-1) / k ) 時，有 k 個取樣很可能是同一個數。

值域大小和安全性

由以上的分析可知，n bit 的字串，雖然可表示 2^n 個數，卻只有「 2^(n/2)」 的安全性。像是 32 bit 的字串，只要 2¹⁶ = 65536 個字串就能產生 collision。即使用了有 collision resistance 的 hash function，仍需要足夠的 bits 數才安全。