查找與 MAC 的衝突的執行時間是多少，…？
我最近讀到了這樣的說法，即如果攻擊者可以控制密鑰和消息，則在分組密碼上發現衝突可能不是一項艱鉅的任務。
所以，給定一個偽隨機函式 $ f:{0,1}^m \times {0,1}^{l_0} \times … \times {0,1}^{l_k}\rightarrow {0,1}^n $ ，發現碰撞的預期執行時間是多少？
$ f $ 可以是任何 MAC 或任何類似的東西。
為了 $ m>n $ 並且沒有任何其他輸入，答案很簡單 $ \mathcal O(\sqrt{n}) $ （標準雜湊函式），但是額外的輸入會改變什麼嗎？
對於塊密碼，這種情況通常是微不足道的，因為第二個原像安全性很容易被破壞。給定一對 $ (M_1,K_1) $ 一個可以計算 $ (D_{K_2}(E_{K_1}(M_1)),K_2) $ 輕鬆獲得碰撞。
查找與 MAC 的衝突的執行時間是多少…
嗯，MAC 的定義是“如果你不知道密鑰，那麼它是不可行的……”。如果您確實知道鍵（或能夠選擇它），則此定義不會斷言任何內容；因此它不提供任何重要的下限。
特別是，對於常見的 MAC（例如 CMAC、Carter-Wegman MAC），生成第二個原像是微不足道的。對於 CMAC，我們實際上可以生成原像；我們只需選擇一個任意前綴（塊長度的倍數），併計算生成目標圖像所需的最後一個塊。對於 Carter-Wegman MAC，我們可以通過查看幾乎通用的散列函式來生成第二個原像，並生成第二條消息，為給定的密鑰生成相同的散列（至少，對於我聽說過的每個 au 散列）。
另一方面，我們來到 HMAC。對於 HMAC，我們可以通過兩種方式在兩個不同的密鑰之間產生衝突：
- 如果給 HMAC 一個短密鑰（不超過散列塊大小），它會將其異或到 IPAD/OPAD 模式中。這意味著如果我們在鍵上附加一個零字節，比如說， $ K_2 = K_1 || 00 $ ，那麼異或的結果將是相同的，所以 $ HMAC(K_1, M) = HMAC(K_2, M) $ 對於任何 $ M $ .
- 利用這一點，如果密鑰長於雜湊塊大小，HMAC 首先對密鑰進行雜湊處理，然後使用該雜湊作為密鑰。因此，我們可以選擇兩個不同的鍵， $ K_1 $ （很長），和 $ K_2 = Hash(K_1) $ ，那麼我們有 $ HMAC(K_1, M) = HMAC(K_2, M) $ 對於任何消息 $ M $ .
如果我們不允許這些方法（並且可能說密鑰必須是相同的長度），那麼很容易看出發現與 HMAC 的衝突並不比在底層雜湊函式中發現衝突（作為 HMAC 中的衝突）更容易將意味著 HMAC 的上或下散列或預處理長密鑰的散列中的衝突）。
因此，底線：MAC 的定義並不能確保發現衝突（假設攻擊者知道密鑰）變得困難；我們可以在認為很難的地方找到 MAC（例如具有固定長度密鑰的 HMAC）；我們還可以在容易找到的地方找到 MAC。