證明 MAC 和雜湊組合是不安全的
讓 $ F $ 是一個安全的 PRF 和 $ H $ 一個通用的雜湊函式。
我怎樣才能展示一對 $ (F,H) $ 誰的組成
$$ S’((k_1, k_2), m) = F(k_2, H(k_1,m)) $$ 是不安全的 MAC（或不安全的 PRF，因為 MAC 可以定義為 PRF）？
我猜是為了找一對 $ (F,H) $ ，訣竅是創造一些 $ H $ 其圖像空間足夠短，可以輕鬆找到碰撞，但我不擅長找到此類函式的範例，我閱讀的書籍總是試圖抽像這些函式。
不破 $ F $ ，你不能： $ S’ $ 是一個具有幾乎相同安全性的 PRF $ F $ .
讓 $ k_1 $ 和 $ k_2 $ 是統一的隨機密鑰。讓 $ F $ 成為PRF，具有優勢$$ \operatorname{Adv}^{\operatorname{PRF}}F(A) = \lvert\Pr[A(F{k_2}) = 1] - \Pr[A(f) = 1]\rvert $$對於任何區分器 $ A $ ， 在哪裡 $ f $ 是一個均勻隨機函式，其域和余域為 $ F $ . 讓 $ H $ 豆 $ \varepsilon $ - 幾乎是通用的雜湊族，所以 $ \Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon $ 對於任何 $ x \ne y $ . （無資格， $ \varepsilon = 1/|T| $ 在哪裡 $ T $ 是的共域 $ H $ .)
定義$$ S’{k_1,k_2}(m) = F{k_2}(H_{k_1}(m)). $$
修復任何 PRF 辨識器 $ A’ $ 為了 $ S’ $ 製造 $ q $ 查詢，並讓 $ U $ 是具有域和余域的均勻隨機函式 $ S’ $ . 我們將綁定優勢 $ A’ $ 在區分 $ S’ $ 就另一種算法的優勢而言 $ A $ 在區分 $ F $ 和碰撞機率 $ \varepsilon $ 的 $ H $ : $$ \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}{S’}(A’) &= \lvert\Pr[A’(S’{k_1,k_2}) = 1] - \Pr[A’(U) = 1]\rvert \ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} $$ 在哪裡 $ A $ 是 PRF 的鑑別器 $ F $ . 只要 $ \operatorname{Adv}^{\operatorname{PRF}}F(A) $ 很小而且 $ q $ 不會太大， $ \operatorname{Adv}^{\operatorname{PRF}}{S’}(A’) $ 也很小。
我們將通過具有中間機率的三角不等式來做到這一點 $ \Pr[A’(f \circ H_{k_1}) = 1] $ 那 $ A’ $ 在變體上返回 1 $ f \circ H_{k_1} $ 的 $ S’{k_1,k_2} = F{k_2} \circ H_{k_1} $ ，其中均勻隨機 $ f $ 已被替換 $ F_{k_2} $ .
- 定義 PRF 鑑別器 $ A $ 為了 $ F $ 經過 $ A(\mathcal O) = A’(\mathcal O \circ H_{k_1}) $ . 然後 $$ \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}F(A) &= \lvert\Pr[A(F{k_2}) = 1] - \Pr[A(f) = 1]\rvert \ &= \lvert\Pr[A’(F_{k_2} \circ H_{k_1}) = 1]
- \Pr[A’(f \circ H_{k_1}) = 1]\rvert. \end{align*} $$ 如果 $ A’ $ 是一個很好的區分 $ S’ $ ，我們會發現 $ A $ 是一個很好的區分 $ F $ ， 除非 $ A’ $ 只是幸運地發現了碰撞 $ H $ .
- 現在考慮 $ q $ 查詢 $ x_1, x_2, \ldots, x_q $ 由…所送出 $ A’ $ 為神諭 $ f \circ H_{k_1} $ .
從查詢到 $ H_{k_1} $ 單獨，我們只假設兩個不同輸入上的碰撞機率的弱屬性，對手可以高機率地發現三個輸入之間的碰撞——例如，在多項式評估 MAC 中 $ M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^{|m| - i + 1} $ 對手可以輕鬆地恢復密鑰 $ r $ 和 $ s $ 從兩個不同的查詢中找到任意多的機率為 1 的碰撞。
但是由於 $ f $ 是均勻隨機函式，唯一的資訊 $ A’ $ 可以藉鑑oracle訪問 $ f \circ H_{k_1} $ 是查詢是否在其中一個中發生衝突 $ H_{k_1} $ 或者 $ f $ ，或者絕對不碰撞。只有在實際發生衝突時，攻擊者才能自適應地對查詢可能發生衝突的資訊採取行動。 $ H_{k_1} $ , 最多以機率發生 $ \varepsilon $ 對於送出的任何一對輸入。因此，要學習 $ \Pr[A’(f \circ H_{k_1}) = 1] $ ，只要對發生碰撞的機率設置一個界限就足夠了。
在查詢中 $ x_1, x_2, \ldots, x_q $ 由…所送出 $ A’ $ 至 $ f \circ H_{k_1} $ ， 事件 $ C $ 發生碰撞 $ H_{k_1} $ 有機率 $$ \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} $$ 在活動中 $ \lnot C $ 查詢不會發生衝突 $ H_{k_1} $ , 每個的分佈 $ f(H_{k_1}(x_i)) $ 是獨立均勻隨機的，與分佈相同 $ U(x_i) $ . 因此必然 $ \Pr[A’(f \circ H_{k_1}) = 1 \mid \lnot C] = \Pr[A’(U) = 1] $ ， 以便 $$ \begin{align*} \Pr[A’(f \circ H_{k_1}) = 1] &= \Pr[A’(f \circ H_{k_1}) = 1 \mid C],\Pr[C] \ &\quad + \Pr[A’(f \circ H_{k_1}) = 1 \mid \lnot C],\Pr[\lnot C] \ &\leq \Pr[C] + \Pr[A’(f \circ H_{k_1}) = 1 \mid \lnot C] \ &\leq \binom{q}{2} \varepsilon + \Pr[A’(U) = 1], \end{align*} $$ 因此 $ \Pr[A’(f \circ H_{k_1}) = 1] - \Pr[A’(U) = 1] \leq \binom{q}{2} \varepsilon $ . 3. 加起來， $$ \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}{S’}(A’) &= \lvert\Pr[A’(S’{k_1,k_2}) = 1] - \Pr[A’(U) = 1]\rvert \ &\leq \lvert\Pr[A’(F_{k_2} \circ H_{k_1}) = 1]
- \Pr[A’(f \circ H_{k_1}) = 1]\rvert \ &\quad + \lvert\Pr[A’(f \circ H_{k_1}) = 1] - \Pr[A’(U) = 1]\rvert \ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A)
- \binom{q}{2} \varepsilon, \end{align*} $$ QED。
這遵循引理 3.3 的證明結構：
該定理的變體出現在許多早期的論文中，包括創建 HMAC 之前的 MDx-MAC 論文和 HMAC/NMAC 安全論文。