Hash
有沒有辦法使用迭代來減緩碰撞攻擊？
迭代雜湊函式的簡單方法 $ H(H(m)) $ 僅使蠻力原像查找速度變慢，但由於內部散列函式中的衝突是整個函式中的衝突，因此使碰撞攻擊速度更快。
是否有一種迭代算法也可以減慢蠻力碰撞攻擊？不擴大輸出規模？
我正在尋找可以簡化為散列函式的標準屬性的東西，而不是僅適用於理想的散列或隨機預言。
案例是使用短散列，例如 128 位和 64 位抗衝突性。碰撞發現攻擊應該被減慢到不可行的程度，例如 $ 2^{100} $ 雜湊函式呼叫。
正如其他人在評論中指出的那樣，在雜湊迭代中使用消息可以再次解決內部雜湊中的衝突。此外，也可以使用輪數，以防您在不同輪次發生碰撞。但是連接只是將這些值組合為輸入的一種可能方式。
如果你的假設只是一個一般的雜湊函式，你應該有一個函式 $ f $ ，然後設置：
- $ h_1 = H(m) $
- $ h_{i+1} = H(f(h_i,m,i)) $
串聯可能是一種可能性 $ f $ ，但在 Merkle-Damgard 構造中可能存在問題。您還可以使用雜湊函式 $ f $ ，但這並不能解決這個問題。或者，您可以改用 MAC，在其中使用上一輪的散列和 $ i $ 派生密鑰，您可以從各種 MAC 算法中進行選擇。或者，您也可以直接使用分組密碼作為 $ f $ ，就像 MAC 算法一樣（嗯，一些 MAC 是基於分組密碼的）。但你必須記住， $ m $ 本身可能會更長。更一般的方法可能是 PRF 的假設。
在類似的註釋上：或者，您可以使用基於雜湊函式的 CSPRNG，使用消息為其播種，然後迭代“足夠遠”，使其與您想要的迭代次數相匹配，並將其用作輸出。
為了您考慮 128 位，我會說可以使用帶有 AES 的 CMAC/OMAC，例如 $ f:= CMAC_{h_i}(m||i) $