為什麼此 MAC 上的生日攻擊無效

我試圖理解為什麼下面的生日攻擊對於這個 MAC 結構是無效的。

讓 Mac ： $ {0, 1}^{128} \times {0, 1}^{256} \to {0, 1}^{128} $ 成為 MAC。考慮以下對手 $ A $ , 這意味著與 Expt 一起工作 $ Mac(A) $ :

1
Adversary A^Mac(k,·),Vrfyk(·,·)
Initialize an empty hash table Y .
For m ∈{0, 1}^256:
  Query y ←Mac(k, m)
  If y ∈Y :
    m′ ←Y [y]
    Query Vrfyk(m′, y) and halt
  Else:
    Y [y] ← m

根據我的教授的說法，到生日時，這種攻擊應該會在大約 $ 2^{64} $ 循環的迭代，這對於強大的對手來說是實用的。但這不是有效的攻擊。為什麼？

但這不是有效的攻擊。為什麼？

如果 m 和 m’ 不相等，這是一個有效的衝突，但它不是對 MAC 的成功攻擊。

要理解為什麼這不會被描述為“有效攻擊”，請考慮“現代密碼學簡介”中對成功攻擊的描述：

如果…（1）t 是消息 m… 上的有效標籤，並且（2）誠實方之前沒有驗證過 m…，則攻擊者“破壞”了該方案。

（引文：Katz, Jonathan；Lindell, Yehuda。現代密碼學導論；第三版/Kindle 版；第 110 頁。）

考慮此定義將幫助您了解攻擊是否“有效”。

$ 2^{64} $ 不是多項式，而是密鑰大小的指數（在您的情況下為 256）

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