“超越生日悖論的安全”的定義是什麼？
我正在閱讀一篇關於 MAC 的論文，我想確定生日悖論之外的安全性的含義。
有定義嗎？
對於被認為是好的 MAC 算法，攻擊 MAC 的最佳方法應該是碰撞（生日攻擊）
這意味著，對於具有 $ n $ 攻擊者在發布後將偽造比特標籤 $ q=O(2^{n/2}) $ 標籤查詢。
在文獻中這個界限被稱為生日結界。
現在，如果你能想出一個 MAC 結構，你可以證明對手需要更多的查詢，比如說 $ q=O(2^{2n/3}) $ 或者 $ q=O(2^{5n/6}) $ 如此處所示，如生日約束所給出的，您的 MAC 提供超越生日悖論的安全性。
“生日悖論”是指一種依賴於發現相關密碼原語內部的衝突（或可能缺少衝突）的攻擊；“超越生日悖論”是指避免這種攻擊的東西。
它最常用於分組密碼模式；在最常見的模式下，找到一個碰撞（你可以期待之後做 $ 2^{n/2} $ 加密塊，假設塊大小為 $ n $ 位）意味著明文塊之間的某種關係（這意味著資訊洩漏）。CTR 之後也會洩露資訊 $ 2^{n/2} $ 塊，但以不同的方式；這裡不可能發生碰撞，因此資訊洩漏是沒有兩個完全相同的 CTR 輸出塊（當您超出生日界限時，您會期望一個）；這也是一種資訊洩露（儘管更為微妙）。“超越生日悖論”指的是不會發生這種情況的分組密碼模式；它們是安全的，即使您保護的遠遠超過 $ 2^{n/2} $ 塊。
當您引用 MAC 時，碰撞攻擊的應用方式取決於 MAC 函式的內部結構。沒有通用的方法來使用 MAC 輸出中的衝突來生成偽造。可能有一些方法可以針對特定 MAC 使用衝突。
以下是容易受到衝突攻擊的兩個 MAC：
- CMAC; 如果您發現兩條長度相等的消息 $ A, B $ 和 $ CMAC(K, A) = CMAC(K, B) $ , 當我們知道 $ CMAC(K, A | X) = CMAC(K, B | X) $ ; 要違反 MAC 屬性，我們可以要求 $ CMAC(K, A | X) $ ，然後聲稱我們知道 $ CMAC(K, B | X) $ ，儘管我們從未向 Oracle 詢問過該確切值。
- HMAC（沒有截斷）；如果您發現兩條消息 $ HMAC(K, M_1) = HMAC(K, M_2) $ ，那麼可能發生的事情（至少，以非平凡的機率）是 $ Hash(K \oplus IPAD | M_1) = Hash(K \oplus IPAD | M_2) $ ，如果是這樣，那麼你可以構造一個消息擴展 $ N $ 和 $ HMAC(K, M_1 | N) = HMAC(K, M_2 | N) $ .
另一方面，有一些 MAC 對碰撞攻擊沒有幫助。一個明顯的例子是 $ SHA3( K | M) $ ; 如果我們找到兩條消息，這無關緊要 $ M_1, M_2 $ 和 $ SHA3( K | M_1) = SHA3( K | M_2) $ ; 因為 SHA3 具有如此龐大的內部狀態，我們不太可能在所有 1500 個內部位中都發現衝突，因此我們無法推斷出 $ SHA3( K | M_1 | X) = SHA3( K | M_2 | X) $