我們要把第一堂課中「以密碼學方法達成完整性」的草圖形式化。回憶：一個訊息鑑別碼（MAC）是三個演算法 \(\MAC = (\KGen, \Tag, \Vf)\)：
\(\KGen\) 輸出完整性金鑰 \(\secret{\ik}\)；
\(\Tag(\ik, m)\) 輸入 \(\ik\) 與訊息 \(m\)，輸出標籤 \(\tau\)；
\(\Vf(\ik, m, \tau)\) 輸入 \(\ik\)、\(m\)、\(\tau\)，輸出 \(0\) 或 \(1\)。
直覺：Alice 與 Bob 共享 \(\ik\)。Alice 要送 \(m\) 時計算 \(\tau = \Tag(\ik, m)\) 並送出 \((m, \tau)\)；Bob 檢查 \(\Vf(\ik, m, \tau) = 1\)。若 \(\Vf\) 輸出 \(1\)，稱 \(\tau\) 是 \(m\) 在 \(\ik\) 下的合法（valid）標籤，否則為不合法。
(i) MAC 的正確性應該是什麼意思？
What should correctness mean for a MAC? （可參考第一堂課對 SKE 正確性的定義。）
仿照 SKE 的正確性「用 \(\sk\) 加密 \(m\) 得到 \(c\)，則用同一把 \(\sk\) 解密 \(c\) 會得到 \(m\)」，MAC 的正確性應該是：
誠實產生的標籤，一定會被（持有同一把金鑰的）驗證者接受。
形式化敘述。對每一把可能由 \(\KGen\) 輸出的金鑰 \(\ik\)，以及每一個訊息 \(m \in \calM\)： \[\text{若 } \tau = \Tag(\ik, m)\ \text{（或 } \tau \gets \Tag(\ik,m)\text{）}, \quad \text{則 } \Vf(\ik, m, \tau) = 1 .\] 用一行寫： \[\forall\, \ik \gets \KGen,\ \forall\, m \in \calM:\qquad \Vf\bigl(\ik,\, m,\, \Tag(\ik, m)\bigr) = 1 .\]
幾點說明。
若 \(\Tag\) 是隨機化的（同一個 \(m\) 可能有多個合法標籤），上式要求對 \(\Tag\) 的每一種隨機選擇都成立；即 \(\Prob\bigl[\Vf(\ik, m, \Tag(\ik,m)) = 1\bigr] = 1\)，機率取自 \(\KGen\) 與 \(\Tag\) 的隨機性。較寬鬆的版本只要求此機率「壓倒性地接近 \(1\)」。
正確性只談「合法的標籤被接受」，完全沒有說「不合法的標籤會被拒絕」。 後者是安全性（不可偽造性）的範疇，正是本題 (iv)–(viii) 要處理的。 一個 \(\Vf\) 永遠輸出 \(1\) 的 MAC 是完全正確的——也完全沒用。
與 SKE 的對照：SKE 的正確性是「\(\Dec \circ \Enc = \mathrm{id}\)」；MAC 的正確性是「\(\Vf(\cdot,\cdot,\Tag(\cdot,\cdot)) \equiv 1\)」。兩者都只保證功能（持有金鑰的合法使用者能正常運作），不保證安全。
(ii) 設計一個正確（但不必安全）的 MAC
Design a correct MAC. It does not have to satisfy any security properties.
由 (i) 可知，只要「\(\Vf\) 接受 \(\Tag\) 的輸出」即可。以下給三個由淺入深的例子（任何一個都是完整的答案）。
構造 A：常數標籤 MAC（「什麼都不做」的 MAC）。
\(\KGen\)：輸出任意 \(\ik\)（例如均勻隨機的 \(\ik \in \bits^n\)，或乾脆 \(\ik = \bot\)）。
\(\Tag(\ik, m) = 0\)（不論 \(\ik\)、\(m\) 為何都輸出常數 \(0\)）。
\(\Vf(\ik, m, \tau) = 1\) 若且唯若 \(\tau = 0\)。
正確性：對任何 \(\ik\)、\(m\)，\(\Tag(\ik, m) = 0\)，而 \(\Vf(\ik, m, 0) = 1\)。\(\checkmark\)
安全性：毫無。任何人對任何訊息都能「偽造」合法標籤 \(0\)。這是講義 p. 12「do nothing」加密方案在 MAC 世界的翻版；它在 (v) 會派上用場，因為它滿足 （金鑰根本沒被用到，當然無法被恢復）卻完全不滿足 。
構造 B：回聲 MAC。 \(\Tag(\ik, m) = m\)，\(\Vf(\ik, m, \tau) = 1 \iff \tau = m\)。正確；但敵手把訊息抄一遍就是合法標籤。
構造 C：一次性密碼本式 MAC（看起來有用到金鑰，但一樣不安全）。 令 \(\calM = \calT = \calK = \bits^n\)。
\(\KGen\)：\(\ik \gets \bits^n\) 均勻隨機。
\(\Tag(\ik, m) = \ik \oplus m\)。
\(\Vf(\ik, m, \tau) = 1 \iff \tau = \ik \oplus m\)（典範驗證）。
正確性：\(\Vf(\ik, m, \ik \oplus m)\) 檢查 \(\ik \oplus m \overset{?}{=} \ik \oplus m\)，恆為 \(1\)。\(\checkmark\)
安全性：敵手只要看到一對 \((m_1, \tau_1)\) 就能算出 \(\ik = \tau_1 \oplus m_1\)，之後對任何 \(m\) 都能偽造 \(\tau = \ik \oplus m\)。它連最弱的 都不滿足。
L2.6cmC1.6cmC1.6cmC1.6cmL5.6cm 構造 & 正確？ & 滿足 ？ & 滿足 ？ & 備註
A：常數標籤 & & & & 金鑰未使用 \(\Rightarrow\) 無法恢復，但人人可偽造
B：回聲 & & & & 同上
C：\(\ik \oplus m\) & & & & 一對訊息–標籤即洩漏金鑰
(iii) 用 MAC 保護密文的完整性：Encrypt-then-MAC
In the first recorded lecture we informally used a MAC to ensure the integrity of ciphertexts. How would we achieve this in the syntax of \(\MAC = (\KGen, \Tag, \Vf)\) given above?
給定一個 SKE \(= (\KGen_E, \Enc, \Dec)\) 與一個 MAC \(= (\KGen_M, \Tag, \Vf)\)，其中 MAC 的訊息空間必須包含 SKE 的密文空間（\(\calC \subseteq \calM_{\MAC}\)，因為我們要對密文貼標籤）。組合方案如下：
金鑰產生。獨立執行 \(\sk \gets \KGen_E\) 與 \(\ik \gets \KGen_M\)；雙方共享 \((\sk, \ik)\)。
傳送訊息 \(m\)。
\(c = \Enc(\sk, m)\)；（先加密）
\(\tau = \Tag(\ik, c)\)；（再對密文貼標籤）
送出 \(\tilde c = (c, \tau)\)。
接收 \(\tilde c = (c, \tau)\)。
若 \(\Vf(\ik, c, \tau) \neq 1\)，立即中止（輸出 \(\bot\)，不做任何其他事）；（先驗證）
否則輸出 \(m = \Dec(\sk, c)\)。（通過才解密）
這恰好就是 Problem 2 題幹所給的流程，也是圖 [fig:etm] 畫的東西。 若要把它寫成「一個新的 SKE」，令 \(\SKE' = (\KGen', \Enc', \Dec')\)：\(\KGen'\) 輸出 \((\sk,\ik)\)；\(\Enc'((\sk,\ik), m) = (\Enc(\sk,m), \Tag(\ik, c))\)；\(\Dec'((\sk,\ik),(c,\tau))\) 在 \(\Vf\) 失敗時輸出 \(\bot\)、否則輸出 \(\Dec(\sk,c)\)。這種同時提供保密與完整性的 SKE 稱為鑑別加密（authenticated encryption, AE）。
三個設計要點。
標籤算在密文上，不是明文上。這樣接收端可以在碰觸任何未經鑑別的資料之前就把竄改過的密文丟掉；同時 \(\tau\) 是密文的函數，不會額外洩漏明文資訊。
兩把獨立的金鑰。\(\sk\) 與 \(\ik\) 分開產生（或由主金鑰以 KDF 衍生），遵守金鑰分離原則（見第 [sec:integrity] 節）。
先驗證、後解密；失敗就中止。任何「解密後再看看對不對」的做法都會把解密結果（或錯誤訊息、時間差）暴露給敵手，成為解密預言機。
延伸：為什麼是「Encrypt-then-MAC」，而不是其他順序？ 把一個加密方案與一個 MAC「黏」在一起有三種自然方式。Bellare 與 Namprempre（ASIACRYPT 2000）在「\(\Enc\) 是 CPA 安全、\(\MAC\) 不可偽造」的通用假設下，逐一分析：
L2.3cmL3.3cmL4.8cmL3.2cm 組合 & 做法 & 通用結論（B–N 2000） & 實務例子
Encrypt-and-MAC（E&M） & \(c = \Enc(\sk,m)\)，\(\tau = \Tag(\ik, m)\)，送 \((c,\tau)\) & 連保密性都不保證：MAC 不必隱藏輸入，確定性 MAC 會洩漏「兩則訊息是否相同」；且須先解密才能驗證 & SSH（原始設計；後來加上對策）
MAC-then-Encrypt（MtE） & \(\tau = \Tag(\ik,m)\)，\(c = \Enc(\sk, m\concat\tau)\) & 有 CPA 保密與明文完整性，但不通用地保證密文完整性／CCA 安全；必須先解密再驗證 & SSL/TLS \(\le\) 1.2——導致 padding oracle、Lucky 13、POODLE 等攻擊
Encrypt-then-MAC（EtM） & \(c = \Enc(\sk,m)\)，\(\tau = \Tag(\ik, c)\) & 只要 MAC 是強不可偽造（見 (vii)），就通用地得到密文完整性與 CCA 安全 & IPsec ESP；TLS 1.3 的 AEAD（GCM、ChaCha20-Poly1305 內部即為此結構）
Krawczyk（CRYPTO 2001）進一步指出 MtE 在特定加密方式（如 CBC、串流加密）下可以安全，但 EtM 是唯一不需看底層細節就安全的做法——這正是「通用組合」的價值。
(iv) 三個候選定義的（\(\ast\)）與（\(\dagger\)）
假設 MAC 正確，且某把 \(\ik\) 已由 \(\KGen\) 產生。稱敵手能「對訊息 \(m\) 偽造標籤」，若它能在不知道 \(\ik\) 的情況下產生某個 \(\tau\) 使 \(\Vf(\ik, m, \tau) = 1\)。
敵手不應能藉由觀察 \((m_i, \tau_i)\)（其中 \(\tau_i = \Tag(\ik, m_i)\)）來恢復 \(\ik\)。
讓敵手能存取 \(\Tag(\ik, \cdot)\)。敵手不應能對任何訊息 \(m\) 偽造標籤。
讓敵手能存取 \(\Tag(\ik, \cdot)\)，令 \(\calQ\) 為敵手輸入過 \(\Tag(\ik,\cdot)\) 的訊息集合。敵手不應能對任何不在 \(\calQ\) 中的訊息偽造標籤。
\(\Tag(\ik, \cdot)\) 表示敵手擁有一個黑盒函數：輸入 \(m\)、輸出 \(\Tag(\ik, m)\)，但看不到內部、不知道 \(\ik\)。 回憶：安全定義由兩個元素組成——敵手不應能做到的事（\(\ast\)），以及敵手能力的描述（\(\dagger\)）。
(iv) What are (\(\ast\)) and (\(\dagger\)) for each of –?
L1.3cmL6.0cmL6.8cm & （\(\ast\)）不應該可能的事（敵手的目標） & （\(\dagger\)）敵手的能力（攻擊模型）
& 輸出完整性金鑰 \(\ik\)（金鑰恢復，key recovery）。 & 被動觀察若干訊息–標籤對 \((m_i, \tau_i)\)，\(\tau_i = \Tag(\ik, m_i)\)。題目寫的是「observing」，最自然的解讀是訊息由誠實雙方決定、敵手只能看（已知訊息攻擊，known-message attack）；若把它加強成敵手可選 \(m_i\)，則與 / 的能力相同。
& 輸出任一對 \((m, \tau)\) 使 \(\Vf(\ik, m, \tau) = 1\)——對任何 \(m\) 偽造，包括曾經查詢過的訊息。 & 適應性選擇訊息攻擊（adaptive chosen-message attack）：可任意次、依先前結果適應性地查詢黑盒 \(\Tag(\ik,\cdot)\)。
& 輸出 \((m, \tau)\) 使 \(\Vf(\ik, m, \tau) = 1\) 且 \(m \notin \calQ\)——對一個新的（未查詢過的）訊息偽造。 & 同 ：適應性選擇訊息攻擊，並記錄查詢集合 \(\calQ\)。
觀察。
與 的（\(\dagger\)）完全相同，只差在（\(\ast\)）： 的獲勝條件比 寬鬆（少了 \(m \notin \calQ\) 的限制），所以敵手在 中更容易贏， 對方案的要求更嚴。
的（\(\ast\)）是三者中對敵手最苛刻的目標（要拿到整把金鑰），（\(\dagger\)）也最弱（只能看）。兩個面向都偏向「對方案寬鬆」，預示它是最弱的定義。
這正是第 [sec:two-facets] 節的原則：（\(\dagger\)）越強或（\(\ast\)）越容易達成，定義就越強。
(v) 哪一個最強？能達成嗎？
要「達成」一個定義，必須證明存在滿足它的物件（這裡是 MAC）；要證明一個定義「無法達成」，必須證明不存在這樣的物件。 至少與 一樣強（at least as strong），若每一個滿足 的 MAC 也滿足 。 嚴格比 強（stronger），若 至少與 一樣強，且存在一個滿足 但不滿足 的 MAC。
(v) What is the strongest definition of –? Can it be achieved?
結論先行： 是最強的定義；但它無法被任何正確的 MAC 達成。三者的強弱關係是 \[\D{2}\ \succ\ \D{3}\ \succ\ \D{1},\] 其中 \(\succ\) 表示「嚴格比…強」。以下逐步證明。
每個滿足 的 MAC 都滿足 。
Proof. 兩者的敵手能力相同。若 MAC 滿足 ，則沒有敵手能對任何訊息偽造標籤；特別地，沒有敵手能對 \(\calQ\) 之外的訊息偽造標籤，即滿足 。（ 的獲勝條件是 獲勝條件的子集。） ◻
每個滿足 的 MAC 都滿足 。
Proof. 採對換證明（contrapositive）：假設 MAC 不滿足 ，即存在敵手 \(\adv\) 能從觀察到的 \((m_1,\tau_1), \ldots, (m_q, \tau_q)\) 恢復出 \(\ik\)。我們用 \(\adv\) 建造一個攻破 的敵手 \(\bdv\)：
\(\bdv\) 向黑盒 \(\Tag(\ik,\cdot)\) 查詢 \(m_1, \ldots, m_q\)（若 的訊息由誠實方依某分布產生，\(\bdv\) 就依同一分布抽樣；黑盒存取涵蓋了被動觀察的能力），把 \((m_i, \tau_i)\) 交給 \(\adv\)。
\(\adv\) 輸出 \(\ik'\)（若 \(\adv\) 成功則 \(\ik' = \ik\)）。
\(\bdv\) 任選一個 \(m^\ast \notin \calQ = \{m_1,\ldots,m_q\}\)，自行計算 \(\tau^\ast = \Tag(\ik', m^\ast)\)（演算法 \(\Tag\) 是公開的——Kerckhoffs 原則），輸出 \((m^\ast, \tau^\ast)\)。
只要 \(\adv\) 成功，\(\ik' = \ik\)，由正確性得 \(\Vf(\ik, m^\ast, \tau^\ast) = 1\)，且 \(m^\ast \notin \calQ\)，故 \(\bdv\) 攻破 。因此 \(\Prob[\bdv \text{ 攻破 } \D{3}] \ge \Prob[\adv \text{ 攻破 } \D{1}]\)：若 成立， 必成立。 ◻
至少與 一樣強（由引理 [lem:d2d3]、[lem:d3d1] 傳遞）。
存在一個滿足 但不滿足 的 MAC。
Proof. 取 (ii) 的構造 A（常數標籤 MAC），其中 \(\KGen\) 輸出均勻隨機的 \(\ik \in \bits^n\)。 滿足 ：\(\Tag\) 與 \(\Vf\) 完全不使用 \(\ik\)，敵手看到的一切都與 \(\ik\) 統計獨立，猜中 \(\ik\) 的機率是 \(2^{-n}\)，可忽略。 不滿足 ：敵手不做任何查詢（\(\calQ = \emptyset\)），直接輸出 \((m, 0)\)，\(\Vf(\ik, m, 0) = 1\)，必勝。 ◻
沒有任何正確的 MAC 滿足 。
Proof. 令 \(\MAC\) 為任一正確的 MAC。考慮以下敵手 \(\adv\)：任選一個訊息 \(m \in \calM\)，向黑盒查詢得到 \(\tau = \Tag(\ik, m)\)，然後輸出 \((m, \tau)\)。 由正確性（(i)），\(\Vf(\ik, m, \tau) = 1\)。依題目對「偽造」的定義——「在不知道 \(\ik\) 的情況下產生某個 \(\tau\) 使 \(\Vf(\ik,m,\tau) = 1\)」——\(\adv\) 確實不知道 \(\ik\)，卻對 \(m\) 產生了合法標籤。 要求對任何 \(m\) 都不可能偽造，故 \(\MAC\) 不滿足 。因為 \(\MAC\) 是任意的，結論對所有正確的 MAC 成立。 ◻
至少與 一樣強（引理 [lem:d2d3]），且存在滿足 而不滿足 的 MAC。
Proof. 由定理 [thm:d2impossible]，任何滿足 的 MAC 都自動是「滿足 但不滿足 」的例子。因此只需知道滿足 的 MAC 存在：在標準假設下（偽隨機函數存在，等價於單向函數存在），\(\Tag(\ik, m) = F_{\ik}(m)\)（\(F\) 為偽隨機函數，實務上如 HMAC、CMAC）即滿足 （KL-IMC Construction 4.5／Theorem 4.6，課程稍後會證明）；在「只用一次」的情境下甚至有不依賴任何假設的資訊理論式 MAC（KL-IMC §4.6）。 ◻
所以 (v) 的答案：最強的是 ，但無法達成——不是因為我們不夠聰明，而是正確性本身就保證了「把黑盒的輸出照抄」是一次成功的偽造。這給我們一個重要教訓：
一個定義若強到沒有任何物件能滿足它，就毫無用處。好的定義必須在「夠強（排除所有我們在意的攻擊）」與「可達成（存在滿足它的方案）」之間取得平衡。 把「重放黑盒的輸出」也算成攻擊，但重放是任何無狀態 MAC 都無法阻止的，所以必須由定義明確排除（ 的 \(m \notin \calQ\)），並交給更高層的協定處理（Problem 2 (ii)）。
(vi) 應該選哪一個作為 MAC 的安全定義？
Which definition from – should we select as a security definition of a MAC? Why?
選 。理由分三層：
太弱，而且瞄準錯了目標。 MAC 的任務是防止偽造，不是保護金鑰本身；金鑰只是達成目標的手段。命題 [prop:d3d1strict] 的常數標籤 MAC 完美滿足 ，卻讓任何人都能偽造任何訊息——一個被 認證為「安全」的方案在實際使用中毫無防護，這表示 沒有捕捉到我們真正在意的事。這與講義迭代 (i)「無法恢復金鑰 \(\Rightarrow\) 什麼都不做的方案也算安全」是同一個教訓。
無法達成（定理 [thm:d2impossible]）。選一個沒有任何方案能滿足的定義，等於什麼都沒選。
是三者中最強的可達成定義，而且它的兩個面向都「合理地悲觀」：
（\(\dagger\)）給敵手適應性選擇訊息的能力是現實的：敵手往往能影響誠實方要鑑別的內容（網頁 cookie、協定中由對方指定的欄位、中途島式的誘導），而且允許過強的能力不會有壞處——只會讓證明出來的安全性更通用。
（\(\ast\)）要求對任何新訊息都不可偽造（存在性不可偽造），而不只是「有意義的」訊息：什麼叫有意義是應用層才知道的事，定義若依賴它就無法通用（KL-IMC §4.2 的論證）。
它恰好排除了唯一無法避免的「攻擊」——重放黑盒輸出。
正是教科書的標準定義：存在性不可偽造、適應性選擇訊息攻擊（existential unforgeability under adaptive chosen-message attack，EUF-CMA；KL-IMC Definition 4.2；見第 [sec:game-template] 節的實驗寫法）。
刻意沒有涵蓋的兩件事（這不是缺陷，而是邊界）：
重放：\(\Vf\) 無狀態，同一個合法的 \((m,\tau)\) 永遠被接受。要防重放需要狀態（計數器、時間戳），由上層協定負責——Problem 2 (ii)。
對已查詢訊息產生新的標籤： 不禁止敵手在看過 \((m_1, \tau_1)\) 後造出另一個 \(\tau_1' \neq \tau_1\) 也能通過驗證。這在多數應用無害，但在某些組合（例如 Encrypt-then-MAC 要達到 CCA 安全）會成為漏洞——這就是 (vii) 的主題。
(vii) 至少與 一樣強、但仍可達成的定義：強不可偽造性
Can you think of a definition that is at least as strong as your answer to (vi.) but still achievable? （提示：\(\Tag\) 可以是隨機化的，即對同一個訊息可能輸出多個合法標籤。考慮 。）
提示點出關鍵：若 \(\Tag\) 隨機化，同一個 \(m\) 可能有很多合法標籤。 只禁止敵手對新訊息偽造，卻允許敵手對舊訊息造出新標籤。把這個漏洞補起來，就得到：
讓敵手存取 \(\Tag(\ik,\cdot)\)，並令 \(\calQ^{+}\) 為敵手得到的所有訊息–標籤對 \((m_i, \tau_i)\) 的集合（而不只是訊息）。敵手不應能輸出任何 \((m, \tau)\) 使得 \[\Vf(\ik, m, \tau) = 1 \quad\text{且}\quad (m, \tau) \notin \calQ^{+}.\] 也就是：敵手不應能產生任何新的合法訊息–標籤對——包括對舊訊息的新標籤。
我們需要驗證三件事：它至少與 一樣強、它嚴格更強、它可達成。
Proof. 若 \((m,\tau)\) 是 意義下的偽造（\(\Vf = 1\) 且 \(m \notin \calQ\)），則 \((m,\tau)\) 顯然也不在 \(\calQ^{+}\) 中（\(\calQ^{+}\) 裡的訊息都在 \(\calQ\) 中），所以它也是 \(^{+}\) 意義下的偽造。因此任何攻破 的敵手都攻破 \(^{+}\)；對換即得「滿足 \(^{+}\) \(\Rightarrow\) 滿足 」。 ◻
存在滿足 但不滿足 \(^{+}\) 的 MAC。
Proof. 取任一滿足 的 MAC \((\KGen, \Tag, \Vf)\)，定義 \(\MAC'\)： \[\begin{align*} \Tag'(\ik, m) &= \Tag(\ik, m) \concat b, \qquad b \gets \bits \text{ 均勻隨機；}\\ \Vf'(\ik, m, \tau\concat b) &= \Vf(\ik, m, \tau) \qquad \text{（忽略最後一個位元）}. \end{align*}\] \(\MAC'\) 仍滿足 ：任何對 \(\MAC'\) 的新訊息偽造 \((m, \tau\concat b)\)，去掉 \(b\) 就是對 \(\MAC\) 的新訊息偽造。 但 \(\MAC'\) 不滿足 \(^{+}\)：敵手查詢一次得到 \((m_1, \tau_1 \concat b)\)，輸出 \((m_1, \tau_1 \concat \bar b)\)（翻轉最後一位）。它通過驗證，且 \((m_1, \tau_1\concat\bar b) \notin \calQ^{+}\)，必勝。 ◻
若一個確定性的 MAC 使用典範驗證（\(\Vf(\ik,m,\tau) = 1 \iff \tau = \Tag(\ik,m)\)）且滿足 ，則它也滿足 \(^{+}\)。
Proof. 在典範驗證下，每個訊息 \(m\) 恰有唯一的合法標籤 \(\Tag(\ik, m)\)。 設敵手輸出 \(^{+}\) 意義下的偽造 \((m,\tau)\)：\(\Vf(\ik,m,\tau) = 1\) 且 \((m,\tau) \notin \calQ^{+}\)。分兩種情況：
若 \(m \notin \calQ\)：這已是 意義下的偽造。
若 \(m \in \calQ\)：敵手曾查詢 \(m\) 並得到 \(\tau_m = \Tag(\ik,m)\)，故 \((m, \tau_m) \in \calQ^{+}\)。由唯一性，\(\Vf(\ik,m,\tau) = 1\) 蘊含 \(\tau = \Tag(\ik,m) = \tau_m\)，於是 \((m,\tau) = (m,\tau_m) \in \calQ^{+}\)，矛盾。此情況不可能發生。
所以每個 \(^{+}\) 偽造都是 偽造，兩者的攻破機率相等； 成立則 \(^{+}\) 成立。 ◻
因為滿足 的確定性典範驗證 MAC 存在（HMAC、CMAC、基於 PRF 的 MAC），\(^{+}\) 是可達成的。實務上幾乎所有 MAC 都是確定性的，所以「免費」得到強不可偽造性。
在 Encrypt-then-MAC 中，若 MAC 只滿足 而不滿足 \(^{+}\)，敵手可以把合法的 \((c, \tau)\) 改成 \((c, \tau')\)，收件端仍會接受並解密出同一個明文。這對完整性看似無害，卻破壞了密文完整性（INT-CTXT）與 CCA 安全：敵手得到了一個「與挑戰密文不同、卻解密成相同明文」的密文，可以合法地拿去問解密預言機。Bellare–Namprempre（2000）正是因此要求 EtM 的 MAC 必須強不可偽造；KL-IMC 習題 5.4 要你構造這個反例。
(viii) 給敵手驗證預言機，會讓它更強嗎？
我們在所有候選定義中都沒有給敵手 \(\Vf\) 的存取權。假設
\(\Vf(\ik, m, \tau)\) 計算 \(\tau' = \Tag(\ik, m)\)，若 \(\tau = \tau'\) 回傳 \(1\)、否則回傳 \(0\)；且
\(\Tag(\ik, \cdot)\) 是確定性的。
這稱為確定性 MAC 的典範驗證（canonical verification for a deterministic MAC）。 在這些假設下，一個能存取 \(\Tag(\ik,\cdot)\) 的敵手，若再給它 \(\Vf(\ik,\cdot,\cdot)\) 的存取權，會變得更強大嗎？（提示：用敵手對 \(\Tag(\ik,\cdot)\) 的存取權「建造」典範驗證。）
結論：不會（在可忽略的差距內）。在典範驗證 \(+\) 確定性 \(\Tag\) 的假設下，\(\Vf\) 預言機能告訴敵手的每一件事，敵手都能用 \(\Tag\) 預言機自己算出來。
核心論證（依提示）。 設 \(\adv\) 是一個同時使用 \(\Tag(\ik,\cdot)\) 與 \(\Vf(\ik,\cdot,\cdot)\) 的敵手。我們建造一個只使用 \(\Tag(\ik,\cdot)\) 的敵手 \(\bdv\)，它在內部執行 \(\adv\)，並「模擬」\(\Vf\) 預言機：
當 \(\adv\) 查詢 \(\Tag(\ik, m)\)：\(\bdv\) 轉送給自己的黑盒，把答案回給 \(\adv\)（並記下 \((m, \tau_m)\)）。
當 \(\adv\) 查詢 \(\Vf(\ik, m, \tau)\)：\(\bdv\) 用黑盒取得 \(\tau' = \Tag(\ik, m)\)，回答 \(1\) 若 \(\tau = \tau'\)、否則回答 \(0\)。
因為 \(\Tag\) 是確定性的，黑盒回傳的 \(\tau'\) 就是真正的 \(\Tag(\ik,m)\)；因為驗證是典範的，真正的 \(\Vf\) 做的也只是「算 \(\Tag(\ik,m)\)、比對」。所以 \(\bdv\) 的回答與真正的 \(\Vf\) 預言機一模一樣——\(\adv\) 無法分辨自己是在和真的 \(\Vf\) 互動，還是和 \(\bdv\) 的模擬互動。於是 \(\adv\) 能做到的任何事，\(\bdv\) 不用 \(\Vf\) 也能做到：\(\Vf\) 預言機沒有提供任何新的資訊。
一個需要小心的細節（進階）。 上面的論證有一個記帳上的微妙之處：\(\bdv\) 為了模擬 \(\Vf(\ik, m, \tau)\) 而向黑盒查詢了 \(m\)，於是 \(m\) 進入了\(\bdv\) 的查詢集合 \(\calQ_{\bdv}\)。如果 \(\adv\) 最後偽造的訊息 \(m^\ast\) 恰好是它先前只拿去驗證、從未拿去貼標籤的訊息（\(m^\ast \notin \calQ_{\adv}\) 但 \(m^\ast \in \calQ_{\bdv}\)），那麼 \(\adv\) 的偽造在 的規則下對 \(\bdv\) 就「不算數」了。
解法：\(\bdv\) 不需要為「新訊息」上的驗證查詢真的去問黑盒。精確的歸約如下。令 \(\adv\) 最多做 \(q_v\) 次驗證查詢。\(\bdv\) 事先均勻選一個指標 \(j^\ast \in \{0, 1, \ldots, q_v\}\)，然後執行 \(\adv\)：
\(\Tag\) 查詢照常轉送並記錄 \((m, \tau_m)\)。
對 \(\Vf(\ik, m, \tau)\) 查詢：
若 \(m\) 已被 \(\adv\) 查詢過 \(\Tag\)（\(\bdv\) 知道 \(\tau_m\)）：直接回答 \([\tau = \tau_m]\)，不碰黑盒。由典範驗證與確定性，這個回答是正確的。
若 \(m\) 是新訊息：這是第 \(i\) 個「新訊息驗證查詢」。若 \(i = j^\ast\)，\(\bdv\) 立即停止並輸出 \((m, \tau)\) 作為自己的偽造；否則回答 \(0\)。
若 \(\adv\) 結束並輸出 \((m^\ast, \tau^\ast)\)，\(\bdv\) 也輸出 \((m^\ast, \tau^\ast)\)。
分析：令 \(F\) 為「\(\adv\) 在真實實驗中某次對新訊息的驗證查詢得到答案 \(1\)」的事件，\(j_0\) 為第一次發生的指標。
若 \(\neg F\)：\(\bdv\) 對所有新訊息驗證查詢回答 \(0\) 都是正確的，模擬完美；當 \(j^\ast = 0\) 時 \(\bdv\) 跑完全程並輸出 \(\adv\) 的偽造，而 \(\calQ_{\bdv} = \calQ_{\adv}\)，所以 \(\adv\) 贏 \(\Rightarrow\) \(\bdv\) 贏。
若 \(F\) 且 \(j_0 = j\)：在第 \(j\) 次新訊息驗證查詢之前模擬完美；當 \(j^\ast = j\) 時 \(\bdv\) 輸出的 \((m, \tau)\) 正是一個通過驗證、且 \(m \notin \calQ_{\bdv}\) 的偽造。
因此 \[\Prob[\bdv \text{ 贏}] \;\ge\; \frac{1}{q_v + 1}\Bigl(\Prob[\adv \text{ 贏} \wedge \neg F] + \Prob[F]\Bigr) \;\ge\; \frac{\Prob[\adv \text{ 贏}]}{q_v + 1}.\] \(q_v\) 是多項式，所以若 \(\bdv\) 的成功機率可忽略，\(\adv\) 的也可忽略：有無 \(\Vf\) 預言機， 的安全性等價（只差一個多項式因子）。\(\bdv\) 的黑盒查詢次數甚至不比 \(\adv\) 多。 同樣的論證對 \(^{+}\) 也成立（KL-IMC p. 113：「任何強安全的 MAC 在允許驗證查詢時仍然強安全」）。
兩個重要的附註。
假設是必要的。若 \(\Tag\) 是隨機化的、或 \(\Vf\) 不是典範的（例如 \(\Vf\) 會接受一些 \(\Tag\) 不會輸出的標籤），\(\Vf\) 預言機就可能洩漏 \(\Tag\) 預言機給不了的資訊，驗證查詢可以造成差別。Bellare、Goldreich 與 Mityagin（2004，The Power of Verification Queries in Message Authentication and Authenticated Encryption）系統性地研究了這個問題。KL-IMC 坦言「含驗證預言機的定義或許才是『正確』的定義」，只是因為實務上的 MAC 幾乎都是典範的，才採用較簡單的版本。
現實中的驗證預言機洩漏的不只一個位元。收件端就是一個活生生的 \(\Vf\) 預言機。若 \(\Vf\) 的實作用一般的位元組比較（如 C 的 ／，遇到第一個不同的位元組就提早返回），敵手可以從拒絕所花的時間逐位元組猜出正確標籤（KL-IMC §4.2「A potential timing attack」）：對每個位置試 256 種值，花最久才被拒絕的那個就是對的。這類側通道攻擊不在我們的定義之內（定義假設敵手只看到預言機的輸出），卻真實存在——所以 MAC 比對一定要用常數時間（constant-time）的實作。
MAC 正確性：\(\forall \ik, m:\ \Vf(\ik, m, \Tag(\ik,m)) = 1\)；它不談不合法標籤。
常數標籤 MAC 是「正確但不安全」與「滿足 但不滿足 」的萬用反例。
\(\succ\) \(\succ\) ； 因正確性而不可達成；選 （EUF-CMA）。
強不可偽造性 \(^{+}\)：禁止任何新的 \((m,\tau)\) 對；確定性典範驗證 MAC 自動滿足；EtM 的 CCA 安全需要它。
典範驗證 \(+\) 確定性 \(\Rightarrow\) \(\Vf\) 預言機可被 \(\Tag\) 預言機模擬（損失因子 \(q_v+1\)）；但時間側通道是另一回事。