哪些數據認證結構會受到生日悖論的影響？
$ H(m\mathbin\Vert k) $ 作為一種身份驗證算法，其中 $ H: {0, 1}^* \rightarrow {0, 1}^{n} $ , 至多具有相當於 $ \frac{n}{2} $ 位。 $ H((k^\prime \oplus \mathrm{opad})\mathbin\Vert H((k^\prime \oplus \mathrm{ipad})\mathbin\Vert m)) $ , HMAC 的定義, 具有上強度 $ n $ . 分組密碼模式和提供身份驗證的分組密碼的安全性對我來說不太清楚。MAC 算法結構的哪些部分決定了它是否具有強度 $ n $ 位而不是那個數字的一半？
事實證明，生日悖論同時出現在後綴-MAC中 $ H(m \mathbin\Vert k) $ 和HMAC $ H((k \oplus \mathrm{opad}) \mathbin\Vert H((k \oplus \mathrm{ipad}) \mathbin\Vert m)) $ ，但方式不同。而且，奇怪的是，“可證明的安全性”領域沒有關於它在後綴 MAC 中的方式的理論形式主義，正如您所觀察到的那樣，它實際上是相關的。
快速總結是，對於一個 $ b $ 位散列函式 $ H $ ， 什麼時候 $ k $ 攻擊者不知道，對於後綴 MAC $ H(m \mathbin\Vert k) $ ，攻擊者可以花費 $ 2^{b/2} $ *離線工作以查找消息 $ m_a \ne m_b $ 碰撞下 $ H $ ，而對於 HMAC，攻擊者必須與您的系統線上互動 $ 2^{b/2} $* 在他們被期望偶然發現消息之前的消息 $ m_a \ne m_b $ 碰撞下 $ \operatorname{HMAC-}!H_k $ .
因為 $ 2^{b/2} $ 離線工作有時是可行的，例如，如果 $ b = 128 $ 就像在 MD5 中一樣（它也有非泛型的碰撞攻擊，可以將工作減少到可以忽略的程度），而 $ 2^{b/2} $ 與單個應用程序的線上互動幾乎是不可想像的，在總結 MAC 安全性時，我們通常將其覆蓋並說後綴 MAC 具有 $ b/2 $ 位安全而 HMAC 有 $ b $ 一些安全性——但你會在分析任何 MAC 的“可證明安全性”的論文中找到血淋淋的細節。
更詳細一點：
- 後綴-MAC結構 $ H(m \mathbin\Vert k) $ 對於迭代雜湊函式 $ H $ ，即大致在哪裡 $ H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = f(\cdots(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1}) $ , 容易受到碰撞 $ f $ : 如果你能找到初始消息塊 $ m_a \ne m_b $ 這樣 $ f(\mathit{IV}, m_a) = f(\mathit{IV}, m_b) = h $ ，然後消息 $ m_a $ 和 $ m_b $ 始終具有相同的身份驗證器
$$ H(m_a \mathbin\Vert k) = f(f(\mathit{IV}, m_a), k) = f(h, k) = f(f(\mathit{IV}, m_b), k) = H(m_b \mathbin\Vert k), $$任何以_ $ m_a $ 或者 $ m_b $ 並共享一個共同的前綴， $ m_a \mathbin\Vert m’ $ 和 $ m_b \mathbin\Vert m’ $ . 一個知道的對手 $ f $ 和 $ \mathit{IV} $ ——在像 SHA-256 這樣的情況下，它們分別是一個公共函式和常量——可以離線工作以嘗試找到這樣的衝突。一旦他們找到了一個，並且他們會知道什麼時候找到了，因為他們可以測試它，他們可能能夠以機率 1立即破壞您的應用程序，而無需事先互動。
這實際上是相關的：基於 MD5 和 SHA-1 的密碼系統在實踐中因發現此類衝突而被破解，在美國和以色列針對伊朗的國際工業破壞事件中，MD5 甚至被用於偽造 HTTPS 證書（儘管使用 RSASSA-PSS 簽名，而不是使用對稱身份驗證器）。
令人好奇的是，在可證明的安全領域中並沒有關於此的理論形式主義。 每個像 SHA-256 這樣的固定壓縮函式都有衝突。我們只是還不知道。在對這些結構進行一定量的攻擊後，我們不能正式地談論攻擊者的成功機率，因為它們沒有任何隨機性。攻擊者要麼知道碰撞（當然存在碰撞），要麼不知道，雖然我們可以非正式地推測他們在密碼分析方面的專業知識，但密碼學中的任何形式主義都不能幫助量化關於該知識的機率。 2. $ \operatorname{HMAC-}!H_k $ 容易受到內部碰撞的影響 $ H((k \oplus \mathrm{ipad}) \mathbin\Vert m) $ : 對於每個 $ k $ , 保證有很多對消息 $ m_a \ne m_b $ 這樣
$$ H((k \oplus \mathrm{ipad}) \mathbin\Vert m_a) = H((k \oplus \mathrm{ipad}) \mathbin\Vert m_b). $$ 在這種情況下，兩條消息在密鑰下共享一個共同的身份驗證標籤 $ k $ ，所以如果發件人提供了一個身份驗證標籤 $ m_a $ ，攻擊者可以將消息替換為 $ m_b $ 並保持標籤完好無損，接收者將不會更聰明。（外部也可能發生碰撞 $ H $ ， 當然。） 但攻擊者無法嘗試離線測試是否 $ m_a $ 和 $ m_b $ 相撞 $ \operatorname{HMAC-}!H_k $ ，因為他們不知道 $ k $ ，在可證明安全的形式主義中。因此，攻擊者的最佳策略（在我們確實降低了安全性的情況下）只是嘗試在不更改其身份驗證標籤的情況下替換消息，並且在碰撞之前的預期偽造嘗試次數約為 $ 2^{b/2} $ .
這同樣適用於其他構造，例如 CMAC，這就是為什麼如果您仔細查看其中許多構造的安全性降低，您會發現對生日界限的引用，以及查詢數量方面的偽造機率 $ q $ 只要 $ q \lll 2^{b/2} $ . 一個值得注意的例外是多項式評估一次性 MAC，它們的工作方式不同，但這必須是另一個晚上的睡前故事。
您可以找到某種方法使碰撞對您的攻擊有用的部分。
有了第一個 MAC， $ H(m\parallel k) $ 有一個簡單的偽造攻擊：生成 $ (m,m’) $ 直到 $ H(m)=H(m’) $ 和 $ m\neq m’ $ （但長度相同），然後送出 $ m $ 到簽署預言機並使用 $ m’ $ 作為您創建偽造品的消息。因為之後的內部狀態是一樣的 $ m $ 或者 $ m’ $ 處理後，將生成相同的 MAC。總的來說，這讓你遠離 $ n/2 $ 離線雜湊評估。請注意，這假設 $ m,m’ $ 具有相同的長度，是Merkle-Damgård雜湊 H的塊長度的倍數。
但是，使用 HMAC，首先您不能對雜湊進行離線評估，因為您不知道前綴，其次要發現衝突，您必須向 oracle 查詢兩個衝突字元串，此時您不能使用它們不再送出為偽造。
有關安全遊戲的入門知識，請參閱此問答。