對消息身份驗證的生日攻擊如何工作？
在密碼學工程中：
2.7.1 生日攻擊
生日攻擊以生日悖論命名。如果你有 23 個人在一個房間裡，其中兩個人生日相同的可能性超過 50%。這是一個驚人的大機率，因為有 365 個可能的生日。
那麼什麼是生日攻擊呢？這是一種攻擊，取決於重複值（也稱為衝突）出現的速度比您預期的要快得多這一事實。假設一個用於安全金融交易的系統對每筆交易使用一個新的 64 位身份驗證密鑰。（為簡單起見，我們假設沒有使用加密。）有 $ 2^{64} $ ( $ =18\cdot 10^{18} $ ，或 180 億）可能的關鍵值，所以這應該很難破解，對吧？錯誤的！看過之後 $ 2^{32} $ ( $ =4\cdot 10^9 $ ，或 40 億）個交易，攻擊者可以預期兩個交易使用相同的密鑰。假設第一個經過身份驗證的消息總是相同的“你準備好接收交易了嗎？” 資訊。如果兩個事務使用相同的驗證密鑰，那麼它們的第一條消息上的 MAC 值也將相同，這很容易被攻擊者檢測到。通過知道這兩個密鑰是相同的，攻擊者現在可以將舊事務中的消息插入到新事務中。 由於它們通過正確的密鑰進行身份驗證，這些虛假消息將被接受，這顯然是對金融交易系統的破壞。
這有什麼壞處：
通過知道這兩個密鑰是相同的，攻擊者現在可以將舊事務中的消息插入到新事務中。
?
假設兩個事務具有相同的 MAC，這意味著相同的身份驗證密鑰。
舊事務中的消息與新事務中的消息不一樣嗎？所以更換不改變？
在這種情況下，交易 $ t_i $ 包含許多消息 $ m_i^t $ 其中每條消息都使用事務密鑰進行 MAC 化 $ k_i $ .
現在假設每筆交易的MAC密鑰是統一隨機生成的
$$ 1 $$. 然後繞了一圈 $ 2^{32} $ 交易，我們預計一個密鑰再次發生的機率為 50% 的生日悖論。這是碰撞部分。認為 $ t_i $ 和 $ t_j $ 具有相同的 MAC 密鑰 $ k_i $ . 如段落中所述，如果交易的第一條消息相同，那麼儲存交易的攻擊者可以看到密鑰被重用 - 來自交易的密鑰 $ t_i $ 用於交易 $ t_j $ .
Attacker stores | (m10,MAC(m10) |(m11,MAC(m11) | ... | (m1N1,MAC(m1N1)| | (m20,MAC(m20) |(m21,MAC(m21) | ... | (m2N1,MAC(m2N2)| .... | (mi0,MAC(mi0) |(mi1,MAC(mi1) | ... | (miNi,MAC(miNi)| .... | (mj0,MAC(mj0) |(mj1,MAC(mj1) | ... | (mjNi,MAC(mjNi)| and observes : MAC(mi0) = MAC(mj0) and may send | (mj0,MAC(mj0) |(mi1,MAC(mi1) | ... | (miNi,MAC(miNi)|現在，他們只是接收消息 $ m_i^t $ 來自 $ t_i $ ，並將它們插入到使用相同密鑰的目前事務中。所以新交易包含 $ m_j^t $ 消息和插入 $ m_i^t $ 關於攻擊者的優勢的消息。攻擊者可能會刪除所有 $ m_j^t $ 交易的消息，可以發送 $ m_i^t $ 的，也取決於他們的優勢。
結果，替換更改了事務上的消息。
$$ 1 $$這也是碰撞部分和安全性的重要組成部分。
正如 kelalaka 所指出的，似乎有一個隱含的假設，即“事務”包含多個單獨經過身份驗證的消息，並且這些消息沒有以任何方式連結（例如，通過在下一條消息的 MAC 的輸入中包含上一條消息的 MAC 令牌）計算）。
值得注意的是，這種方案無論如何都不能保護事務的完整性——MITM 攻擊者可以在單個事務中重新排序、刪除或重放消息，而不會被 MAC 擷取。如上所述，生日攻擊只給了攻擊者額外的自由，可以使用相同的 MAC 密鑰將消息從一個事務重播到另一個事務，這並不是該方案對 MITM 攻擊的（已經非常糟糕的）漏洞的擴展。甚至有更長的 MAC 密鑰。
原則上，如果 MAC 密鑰和/或令牌太短，生日攻擊甚至*會影響設計良好的多消息身份驗證方案。*然而，細節在很大程度上取決於方案，通常這種攻擊需要的不僅僅是一個短密鑰。
例如，讓我們假設 $ i $ - 交易中的消息 $ t $ 由標籤認證$$ \tau_{i,t} = \operatorname{MAC}{K_t}(\tau{i-1,t} \mathbin| i \mathbin| m_{i,t}), $$在哪裡 $ K_t $ 是每筆交易的 MAC 密鑰， $ \tau_{i-1,t} $ 是交易中前一條消息的 MAC 標籤， $ i $ 是消息號（填充到固定長度或以其他方式明確地與其他 MAC 輸入分開）和 $ m_{i,t} $ 是要認證的消息。
然後，能夠替換標記的消息 $ (m_{i,t}, \tau_{i,t}) $ 與先前截獲的 $ (m_{i’,t’}, \tau_{i’,t’}) $ 來自另一筆交易 $ t’ $ 並讓它通過 MAC 驗證，攻擊者不僅需要 $ K_t = K_{t’} $ ， 但是也 $ i = i’ $ 和 $ \tau_{i-1,t} = \tau_{i-1,t’} $ . 這可能是偶然發生的，如果鍵、標籤和消息計數器（的典型值）的組合長度足夠低，但它比兩個鍵衝突的可能性要小得多。在實踐中，它還需要標籤（或密鑰！）足夠短，以至於即使不利用生日效應，它也會直接受到暴力偽造攻擊。
因此，雖然本書試圖傳達的總體觀點——密鑰應該足夠長以避免生日沖突——是一個總體上應該遵循的好原則，但我不相信他們提出的實際攻擊是實際攻擊，至少不反對任何已經不容易受到更嚴重攻擊的方案。