一個人怎麼能建2c/22C/22^{c/2}攻擊海綿雜湊？
讓 $ H $ 做一個有速率的海綿雜湊 $ r $ 和容量 $ c $ , 由排列建構 $ \pi: {0, 1}^n \rightarrow {0, 1}^n $ ， 在哪裡 $ n = r + c $ .
假設 $ r \ge 2c $ ，我怎樣才能找到至少有機率的碰撞 $ 0.5 $ 及時 $ O(2^{c/2}) $ . 衝突消息可以是 $ 2r $ 每個位。
我很確定我必須使用生日悖論，但我仍然不知道如何應用它。
根據 rate 的定義，散列函式在 $ r $ 有點長的塊。生成關於 $ 2^{c/2} $ ( $ r $ 位）消息塊，直到你有一對消息，說 $ m $ 和 $ m’ $ 這樣你就會在 $ c $ 與容量相關的位。那是 $ T_c(\pi(iv \oplus (0^c | m)) = T_c(\pi(iv \oplus (0^c | m’)) $ 在哪裡 $ T_c $ 是一個截斷* $ n $ 位輸出 $ \pi $ 至 $ c $ 位， $ iv $ 是雜湊函式在吸收任何消息之前的內部狀態， $ 0^c $ 是一串 c 個零位，並且 $ | $ 是連接運算符。
一個吸收後兩個雜湊函式實例的內部狀態 $ m $ 和另一個 $ m’ $ 現在有相同的容量位，但是 $ \pi(iv \oplus (0^c | m)) \neq \pi(iv \oplus (0^c | m’)) $ 因為 $ m \neq m’ $ 和 $ \pi $ 是一個排列。選擇任何值 $ m_2 $ 對於散列函式的第一個實例的第二個消息塊。然後選擇 $ m_2’ $ 對於第二個雜湊的第二個塊，使得 $ m_2 \oplus m_2’ = \pi(iv \oplus (0^c | m)) \oplus \pi(iv \oplus (0^c | m’)) $ .
在吸收第二個消息塊之前，兩個實例的容量位相同。您選擇第二個消息塊以取消剩餘的 $ r $ 第二次之前的位不相等 $ \pi $ 被應用。由於輸入到 $ \pi $ 是一樣的，輸出也是一樣的。現在你有一個完整的內部碰撞。因此，此時僅請求雜湊函式的輸出將產生輸出衝突。但是雜湊函式內部狀態的衝突比輸出之間的衝突更強大。您可以通過選擇不同的 $ m_2 $ 或者通過使用新的相同消息塊將輸入擴展到兩個散列函式。
您（可能）需要的原因 $ 2r $ 位輸入是這樣您就可以消除海綿狀態的非容量部分的差異。可以定義基於海綿的雜湊，這樣就不需要最後一步。請注意，一旦容量位發生衝突，選擇下一個消息塊值以使您發生衝突是微不足道的。
該算法可以這樣定義，而不是記住所有 $ n $ 輸出位 $ \pi $ 它只儲存容量位。這改變了算法。僅在這個細節上不同的兩個雜湊函式的輸出會有所不同，但兩者的抗碰撞性是相同的。
它可以被定義為執行狀態更新，如 $ h_{i} = \pi(h_{i-1} \oplus (0^c | m_i)) $ . 在哪裡 $ h $ 是個 $ n $ 雜湊函式的位狀態， $ m_i $ 是個 $ i $ 第 r 位長消息塊，以及 $ 0^c | m_i $ 是 n 位，因為 $ |0^c| + |m_i| = c + r = n $ .
或者也可以定義為進行更新，如 $ h_i = T_c(\pi((h_{i-1} | m_i)) $ . 在哪裡 $ h_i $ 而是 $ c $ 位長。
直覺上的區別在於，後一個定義將新的消息塊位覆蓋到海綿狀態，而前一個 XOR 位覆蓋到海綿狀態。基於海綿的散列函式是否以一種方式定義或另一種方式對其抗碰撞性沒有影響。
TLDR：只需暴力破解第一個消息塊，以使容量位匹配。然後只需選擇第二個消息塊以抵消剩餘的 r 位差異。
- 在這種情況下，丟棄最後一個 $ r $ 位。我選擇在這個答案中假設散列函式被定義為使得海綿的速率位是最後一個 $ r $ 位和容量位是第一個 $ c $ 位）