Hash
找到原像、弱碰撞或強碰撞的“成本”是多少？
對於一個安全的 n 位散列函式，找到原像、弱碰撞或強碰撞的“成本”是多少？
定義：
- 在原像攻擊中，給定一個雜湊函式 $ H $ 和一個雜湊值 $ h $ ，我們試圖找到 $ x $ 這樣 $ h = H(x) $ . 這 $ x $ 不必是用於計算雜湊的原始輸入值 $ h $ .
- 在第二次原像攻擊中（弱碰撞）；我們被給予 $ H,x,h $ 和 $ h = H(x) $ 我們需要找到另一個 $ x’ $ 這樣 $ h = H(x’) $ .
- 碰撞攻擊（強碰撞）；我們正在尋找兩種不同的輸入 $ a $ 和 $ b $ 這樣使得這樣 $ H(a)=H(b) $ .
費用：
- 原像和二次原像的成本為 $ \mathcal{O}(2^n) $
通常對原像和次要原像的搜尋是從 0 迭代到 $ c\cdot2^n $ 或隨機測試 $ c\cdot2^n $ 然後來自更大空間的值 $ 2^n $ .
- 碰撞的代價是 $ \mathcal{O}(2^{n/2}) $ 有 50% 的機率，這是由於生日攻擊。
天真的方式是生成 $ 2^{n/2} $ 輸入雜湊對並根據雜湊值對其進行排序。這花費大約 $ \mathcal{O}(2^{n/2}) $ 空間。
更好的方法是使用Pollard 的 Rho *；
- 選擇一個隨機雜湊值 $ h_1 $ 並設置 $ h_1’ = h_1 $
- 計算 $ h_2 = H(h_1) $ 和 $ h_2’ = H(H(h_1’)) $ . 一個是慢一個是快。
- 繼續這個過程 $ h_{i+1} = H(h_i) $ 和 $ h_{i+1}’ = H(H(h_i’)) $ 直到我們達到一個索引 $ j $ 這樣 $ h_{j+1} = h_{j+1}’ $我們可以將這個算法視覺化如下；算法最終進入一個循環（Rho-Shape）
通往的道路 $ h_5 $ 是碰撞。循環長度和碰撞點可以通過Floyds 算法求出。
這需要 $ \mathcal{O}(2^{n/2}) $ 尋找碰撞的操作。
如果我們問，平均週期長度是多少？如果我們將散列函式建模為均勻隨機，那麼Harris 在 1960 年就證明了這一點。對於散列函式 $ \ell $ 位輸出，平均週期長度為 $ \frac{1}{ 2} \sqrt{2 \pi \ell} $ 對於 SHA256，這使得 $ 2^{127} \sqrt{\pi} $ . 這使得具有 256 位輸出的雜湊函式無法執行循環以查找衝突
*在其他情況下，這也稱為弗洛伊德循環檢測算法（弗洛伊德龜兔賽跑）。Knuth 將其歸因於弗洛伊德，但沒有引用。起源未知。
