為什麼這種蠻力攻擊不會將所有加密雜湊函式的安全位減少到 N/3？
傳統的暴力碰撞攻擊是生成 $ 2^{N/2} $ （唯一的）隨機字元串，對它們進行雜湊處理，這會導致約 50% 的碰撞機會。問題標題中談到的攻擊是按序列生成雜湊 $ H_0 = F(S), H_n = F(S||H_{n-1}) $ ， 在哪裡 $ S $ 是一個與之發生碰撞的字元串， $ F $ 是雜湊函式，序列在 $ 2^{N/3} $ .
上述攻擊需要較少的散列函式呼叫，因為它依賴於每個順序散列減少可能散列的數量這一事實。雜湊時 $ 2^N $ 隨機字元串，會有 $ (1-(1-\frac{1}{2^N})^{2^N})2^N $ 由於所有的衝突，可能的雜湊值。
告訴序列中每個散列的可能散列分數的序列是 $ P_0 = 1, P_n = 1 - (1-\frac{1}{2^N})^{2^NP_{n-1}} $ ，大致近似於 $ P_n = P_{n-1} - \frac{P_{n-1}^2}{2} $ 作為 $ \lim_{P_{n-1}\to 0} $ , 可以近似為一個函式 $ P(n) = \frac{2}{n + 2} $ . （這些精度的降低使將來的計算更容易）
序列中的雜湊與所有後續雜湊之間不會發生衝突的機會是 $ C_n = (1 - \frac{1}{P_n2^N})^{M - n - 1} $ 在哪裡 $ M $ 是序列的長度，因為分數非常接近 $ 1 $ , 可以近似為 $ C_n = 1 - \frac{M - n}{P_n2^N} = 1 - \frac{Mn - n^2}{2^{N + 1}} $ . 現在來近似所有的乘法 $ C $ 小號 ( $ C_0C_1…C_M) $ 為了獲得所有雜湊組合的碰撞機會，我們可以丟棄乘法（因為再次， $ C_n $ 非常接近 $ 1 $ ) 並添加所有減去的部分並從中減去 $ 1 $ ，這導致 $ 1 - \frac{M^3/2-M^3/4}{2^{N+1}} = 1 - \frac{M^3/4}{2^{N+1}} $ , 並達到約 50% 的碰撞率 $ M = 2^{(N+3)/3-1} $ ，這只是 $ 2^{N/3} $ .
有沒有理由為什麼這不起作用？
讓 $ M $ 是對統一隨機函式的查詢次數 $ F $ 在不同的點 $ X_1, X_2, \dots, X_M $ . 重複值的機率 $ F(X_i) = F(X_j) $ 為了 $ i \ne j $ 最多是 $ M^2!\big/2^N $ 由生日悖論。為了 $ M = 2^{N/3} $ ， 這是 $ 2^{2N/3}!\big/2^N = 1\big/2^{N - 2N/3} = 1\big/2^{N/3} $ . 如果您的計算不符合此界限，則您的計算中有錯誤。
‘但是如果我們遇到一個短週期怎麼辦 $ H \mapsto F(S \mathbin| H) $ ？’， 你問。在域上的均勻隨機函式中重複之前的預期點數 $ 2^N $ 元素是 $ \frac12\sqrt{2\pi,2^N} - 1 \approx 2^{N/2} $ （Harris 1960 Eqs. 3.4 & 3.11，有關分發的更多詳細資訊，請參閱論文；免費）。所以不，這種方法不會提高預期成本。
使用聰明的烏龜追逐野兔算法來尋找循環，而不是製作一個大表並檢查重複項，可以減少攻擊的記憶體或區域*時間成本，就像在van Oorschot-Wiener 並行碰撞搜尋機中一樣，但它並沒有逃脫生日的束縛！