MAC函數的安全性是怎樣的？


當使用加密演算法加密消息時，**無論採用對稱加密還是公鑰加密，其安全性一般依賴於密鑰的長度。**排除加密演算法可能有的弱點，攻擊者可以使用窮舉攻擊來嘗試所有可能的密鑰。一般情況下，對k比特長的密鑰，窮舉攻擊需要2^(k-1)次嘗試。

**對於MAC，情況則完全不同。**MAC函數一般是一個多對一的函數。攻擊者如何用窮舉攻擊法獲得密鑰呢？MAC函數域由任意長度的消息組成，其中域值由所有可能的MAC和所有可能的密鑰組成。如果使用一個長度為n比特的MAC，那麼將有2n個可能的MAC，**而可能有N個消息，其中N>>2^n。**

如果不考慮保密性，即假設對手已獲得消息的明文和相應的MAC。假定k>n，即密鑰長度大於MAC長度，那麼如果已知M1和MAC1，MAC1=Ck1( M1)。密碼分析者必須對所有可能的密鑰值ki執行MACi=Cki( Mi)。當MACi= MAC1時，則至少說明找到一個密鑰。但攻擊者此時並無法確定真正的密鑰。因為，由於總共將產生2^k個MAC，但只有2^n個不同的MAC值。因此，許多密鑰會產生同一個正確的MAC。因此，此時攻擊者必須重複這樣的攻擊，直到可以確認正確的密鑰。

**一般來說，對消息認證碼的窮舉搜索攻擊比對使用相同長度密鑰的加密演算法的窮舉搜索更困難，然而也存在一些攻擊方法卻不需要尋找產生MAC所使用的密鑰。**

考慮能遇到的攻擊的類型，MAC函數必須滿足以下要求，其中假定對手知道MAC函數C但不知道k：

- 如果攻擊者得到M和Ck(M)，構造一個消息Mˊ，使得Ck(M)= Ck(Mˊ)，在計算上是不可行的。

- Ck(M)應該在以下意義下均勻分布。隨機選擇消息M和Mˊ， Ck(M)= Ck(Mˊ)的概率為2^-n，其中n為MAC的長度。

- 若Mˊ為M的某種已知變換，即Mˊ=f(M)，那麼Ck(M)= Ck(Mˊ)的概率為2^-n。

**所以mac是很難攻擊的，其安全性足矣保障我們的安全需求。**

---

推薦閱讀：