這種結構是安全的 MAC 嗎？

讓 $ F:{ 0,1 }^n \times { 0,1 }^ n \rightarrow Z^*_q $ 是 PRF，並且 $ H:{ 0,1 }^{2n} \rightarrow { 0,1}^n $ 是一個安全的散列函式。是以下構造 $ \Pi=(Gen,Mac,Vrfy) $ 是安全的 MAC 嗎？

（請注意，我們為pair重新定義了攻擊者成功的條件 $ (m=a_1|a_2,~T) $ ， 以便 $ Vrfy_K(m,T)=1 $ ，並且 $ a_1|a_2 $ 或者 $ a_2|a_1 $ 沒有問它的神諭）。

$ K \leftarrow Gen(1^n):\

~~~~~~~~~K=(k_1,k_2,k_3)
$ 
$ ----------------------------------- $ 
$ 
T \leftarrow Mac_K(m)\\
~~~~~~~~~parse~m~as~~a_1|a_2 ~~where~ a_1,a_2 \in \{ 0,1 \}^n \\
~~~~~~~~~parse~K~as~(k_1,k_2,k_3)\\
~~~~~~~~~r \leftarrow F_{k_3}(H(a_1 | a_2) \oplus H(a_2 | a_1))\\
~~~~~~~~~a \leftarrow F_{k_1}(a_1),~~~~s \leftarrow F_{k_2}(a_1)\\
~~~~~~~~~b \leftarrow F_{k_1}(a_2),~~~~z \leftarrow F_{k_2}(a_2)\\
~~~~~~~~~t_1 \leftarrow a \cdot (s+r),~~~~t_2 \leftarrow b \cdot (z-r)\\
~~~~~~~~~T=(t_1,t_2)
$ 
$ ----------------------------------- $ 
$ 
b:=Vrfy_K(m,T)\\
~~~~~~~~~parse~m~as~~a_1|a_2 ~~where~ a_1,a_2 \in \{ 0,1 \}^n \\
~~~~~~~~~parse~K~as~(k_1,k_2,k_3)\\
~~~~~~~~~parse~T~as~(t_1,t_2)\\
~~~~~~~~~a \leftarrow F_{k_1}(a_1),~~~~s \leftarrow F_{k_2}(a_1)\\
~~~~~~~~~b \leftarrow F_{k_1}(a_2),~~~~z \leftarrow F_{k_2}(a_2)\\
~~~~~~~~~if ~(a^{-1}\cdot t_1 + b^{-1}\cdot t_2 =s+z) ~then\\
~~~~~~~~~~~~b=1\\
~~~~~~~~~else\\
~~~~~~~~~~~~b=0\\
$

不，它不必是安全 MAC，因為可以設計一個符合標準雜湊函式屬性（抗原像性、抗碰撞性）的雜湊函式，但在此模式下使用時會使該 MAC 不安全。

如果我們採取 $ H’ $ 作為標準的安全散列函式，我們可以定義散列函式：

$$ H(a | b) = \begin{cases} 0 || H’(a | b) & \text{if } a \ge b \ 1 || H’(b | a) & \text{if } a < b \end{cases} $$ 請注意，如果我們發現，比如說，原像或碰撞 $ H $ ，這立即給了我們一個原像或碰撞 $ H’ $

並且，使用這個散列函式，值 $ r $ MAC 生成過程中定義的關鍵相關常數；以外 $ r $ ，標籤的前半部分是消息前半部分的函式，標籤的後半部分是消息後半部分的函式。因此，給定兩條消息的 MAC $ (x, y) $ ， 和 $ (z, w) $ ，對手可以很容易地預測有效生成器將產生的 MAC $ (x, w) $ （當然可以接受）

引用自：https://crypto.stackexchange.com/questions/60799