更有效的迭代雜湊方法
這是一種執行迭代加密散列的可能方法，其速度是普通方法的兩倍。
給定一個壓縮函式 $ f: {0,1}^{a+b} \rightarrow {0,1}^b $ . 假設消息有長度 $ 4a $ 填充後的位。通常四個消息塊是一個接一個地註入到一個數據塊中 $ x_i \in {0,1}^b $ :
$$ m = m_0 | m_1 | m_2 | m_3; ; |m_i| = a $$ $$ x_{i+1} = f(x_i | m_i); ; i=0,1,2,3; ; x_0 = IV $$ $$ h = x_4 $$ 更快散列的第一個想法是簡化壓縮函式，例如替換 $ f $ 通過函式 $ g $ 類似地建構但僅使用 $ \frac 1 4 $ 的內部回合。計算 $ x_4 $ 像上面一樣使用 $ g $ 代替 $ f $ 並最終確定 $ h=p(x_4) $ ， 在哪裡 $ p $ 是一個不允許計算的偽隨機函式 $ x_4 $ 從雜湊 $ h $ .
我認為這可能對原像而不是碰撞攻擊是安全的，因為兩者之間存在太多相關性 $ x_i $ 和 $ x_{i+1} $ , 允許構造消息塊 $ m_i, \overline m_i, m_{i+1}, \overline m_{i+1} $ 以便 $$ g(g(x_i|m_i)|m_{i+1})=g(g(x_i|\overline m_i)|\overline m_{i+1}) $$ 現在的想法是將每個消息塊插入兩次：
$$ x_{i+1} = g(x_i | m_{i \bmod 4}); ; i=0,…,7 $$ $$ h = x_8 $$ 現在至少有五個電話 $ g $ 在兩個不同塊的注射之間 $ m_i, m_j $ . 例如 $ m_2 $ 雜湊時 $ i=2 $ 和 $ m_3 $ 什麼時候 $ i=7 $ ，因此之間不應該存在可利用的相關性 $ x_2 $ 和 $ x_7 $ . 然而這個方案只使用 $ \frac 1 2 $ 總輪數，與普通方法相比。
考慮到整數的整數，這是否安全？ $ f $ 是否足以使普通方法安全？
這是嘗試找到衝突的一種明顯方法：
- 搜尋一對 $ m_1, \overline{m_1} $ 與財產 $ g(x | m_1) = g(x | \overline{m_1}) $ 對於非平凡的分數 $ x $ . 鑑於 $ g $ 輪數減少，這可能是可行的。
- 現在，從一個固定的 $ x_i $ （對應於一個已知的消息前綴），並蒐索一個 $ m_0 $ 英石 $ g(x_i | m_0) $ 是碰撞原像之一 $ m_1, \overline{m_1} $ .
- 稱呼 $ g(g(x_0 | m_0) | m_1) $ 價值 $ x_2 $ ; 搜尋一個 $ m_2, m_3 $ 配對這樣 $ g(g(g(x_2 | m_2) | m_3) | m_0) $ 也是一個碰撞對。
如果我們能找到，那麼消息會阻塞 $ (m_0, m_1, m_2, m_3) $ 和 $ (m_0, \overline{m_1}, m_2, m_3 $ ) 添加到消息前綴時發生衝突。
這有多可行？這取決於第一步的可行性（以及隨機 $ x $ value 是一個碰撞原像) - 如果我們可以得到一個碰撞原像的機率高達 $ 2^{-N} $ ，那麼剩餘步驟使用的工作量是預期的 $ 2^{N+1} $ 工作…