為什麼是米一個Cķ(米1||米2)=⟨Fķ(米1),Fķ(米1⊕米2¯¯¯¯¯¯¯)⟩米一個Cķ(米1||米2)=⟨Fķ(米1),Fķ(米1⊕米2¯)⟩Mac_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 oplus o…
我正在準備考試並嘗試解決我在網際網路上找到的以下問題：
讓 $ F_k $ 是一個偽隨機函式。顯示以下 MAC 用於長度的消息 $ 2n $ 是不安全的。共享密鑰是隨機密鑰 $ k \in {0, 1}^n $ .
$ \operatorname{Mac}_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩ $
在哪裡 $ m_1, m_2 $ 是長度的二進製字元串 $ n $ 和 $ \overline{m_2} $ 是 $ m_2 $ 其所有位反轉。攻擊者必須向 MAC-oracle 進行查詢以偽造 MAC 的最少查詢次數是多少？
為了解決這兩個問題，我嘗試建構攻擊者為其請求標籤的兩條消息，然後以提供有效消息和標籤的方式組合消息和相應的標籤。遺憾的是，這沒有成功，因為標籤的第二部分結合了原始消息的兩個部分。我的方法是否走錯了路？
我們想偽造標籤 $ m = m_1 || m_2 $ . 我們需要生成的標籤是：
$$ \operatorname{Mac}_k(m_1||m_2)=⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩ $$
我們將使用消息查詢 oracle $ m_1^\prime || m_2^\prime $ , 這需要不同於 $ m_1||m_2 $ 算作贗品。考慮 $ m_1^\prime || m_2^\prime = (m_1 \oplus \overline{m_2}) || m_2 $ , 這不同於 $ m_1||m_2 $ 當且當 $ \overline{m_2} \neq 0 $ .
此消息具有以下標籤：
$$ \begin{align} \operatorname{Mac_k(m_1^\prime||m_2^\prime)} &=⟨F_k(m_1^\prime),F_k(m_1^\prime \oplus \overline{m_2^\prime})⟩ \ &=⟨F_k(m_1 \oplus \overline{m_2}),F_k((m_1 \oplus \overline{m_2})\oplus \overline{m_2})⟩ \ &=⟨F_k(m_1 \oplus \overline{m_2}),F_k(m_1)⟩ \end{align} $$
交換兩個輸出會產生標籤 $ m=m_1||m_2 $ .
因此，我們可以只使用對 MAC 預言機的一次查詢來製造偽造品。