被收買的騎士：保密不等於不可竄改

講義 p. 18 問：除了保密性之外，我們還想要什麼安全性質？ 設想騎士被收買，竄改羊皮紙上的密文。他不知道金鑰也不知道訊息，但他仍然可以重排、增加或刪除字元。Henry 解密之後會得到什麼？一團亂碼嗎？如果不是亂碼呢？

一次性密碼本（one-time pad）是完美保密的：\(c = m \oplus \sk\)。但考慮 Francis 傳送 \[m = \texttt{PAY\ 100\ GOLD}\] 騎士雖然讀不懂 \(c\)，卻知道（或猜到）訊息的格式。他把 \(c\) 中對應「1」的那個位元組 \(c_i\) 改成 \(c_i' = c_i \oplus (\texttt{1} \oplus \texttt{9})\)。Henry 解密得到 \[c_i' \oplus \sk_i = m_i \oplus (\texttt{1} \oplus \texttt{9}) = \texttt{1} \oplus \texttt{1} \oplus \texttt{9} = \texttt{9},\] 也就是 \(\texttt{PAY\ 900\ GOLD}\)——完全「有意義」，而且 Henry 毫無察覺。 這個性質稱為可延展性（malleability）：敵手不必知道明文，就能對明文做可預測的修改。 所有以 XOR 為基礎的串流加密（包括現代的 CTR 模式、ChaCha20）都有同樣性質；KL-IMC §4.1.2 另外指出，ECB 模式可以藉由重排密文區塊來重排明文區塊、刪除區塊來截短訊息。

  • 保密性 \(\not\Rightarrow\) 完整性：一次性密碼本完美保密，卻任人竄改（上例）。

  • 完整性 \(\not\Rightarrow\) 保密性：把訊息明文連同一個鑑別標籤一起送出，任何人都讀得到訊息，但沒人改得動它。

因此，「收到的訊息或密文就是對方送出的那一個」是一個獨立且新的安全性質，稱為。它必須用不同的手段達成——這正是 Problem Set 1 第一題的主題。

達成完整性的兩條路：工程 vs. 密碼學

講義 p. 19 列出 Francis 可以怎麼做：

  • 工程方法（engineering approach）：用擦不掉的墨水、填滿羊皮紙所有空白、使用防竄改（tamper-resistant）的羊皮紙…… 現代對應：防拆封裝、硬體安全模組（HSM）、Secure Enclave。這些有用，但每一種都是「針對特定竄改手法」的防禦，難以窮舉。

  • 密碼學方法（cryptographic approach）：

    1. 用另一把共享的秘密完整性金鑰 \(\ik\)，對密文計算一個標籤（tag）\(\tau\)；

    2. 把密文與標籤一起寫在羊皮紙上；

    3. Henry 先用 \(\ik\) 檢查標籤是否正確，通過之後才解密。

講義的「密碼學方法」：先加密、再對密文貼標籤；收件端先驗證、通過才解密。這就是 Encrypt-then-MAC。

訊息鑑別碼（MAC）的語法（講義 p. 20）

一個是三個演算法的三元組 \(\MAC = (\KGen, \Tag, \Vf)\)：

  • \(\KGen\)：輸出一把完整性金鑰 \(\ik \in \calK\)：\(\ \ik \gets \KGen\)。

  • \(\Tag\)：輸入完整性金鑰 \(\ik\) 與訊息 \(m \in \calM\)，輸出標籤 \(\tau \in \calT\)：\(\ \tau = \Tag(\ik, m)\)（可隨機化：\(\tau \gets \Tag(\ik,m)\)）。

  • \(\Vf\)（verify）：輸入 \(\ik\)、訊息 \(m\) 與標籤 \(\tau\)，輸出 \(0\) 或 \(1\)：\(\ b = \Vf(\ik, m, \tau)\)。輸出 \(1\) 時稱 \(\tau\) 是 \(m\) 在 \(\ik\) 下的合法標籤（valid tag），否則為不合法。

講義再度提醒：「同樣地，這裡沒有談正確性或安全性，只有語法。」——這兩者正是 Problem 1 (i) 與 (iv)–(viii) 要你補上的。

講義明確寫「another shared secret integrity key」。原則上，一把金鑰只做一件事（key separation）。 若加密與 MAC 共用同一把金鑰，兩個演算法之間可能產生意想不到的交互作用（例如用 CBC 加密、又用同一金鑰做 CBC-MAC，標籤會等於最後一個密文區塊，整個方案被瞬間攻破）。 使用獨立金鑰 \((\sk, \ik)\) 可以讓我們模組化地論證安全：只要 \(\SKE\) 保密、\(\MAC\) 不可偽造，組合就安全（Bellare–Namprempre 2000）。 實務上通常由一把主金鑰透過金鑰衍生函數（KDF）衍生出 \(\sk\) 與 \(\ik\)。

延伸補充：MAC 在現實中的樣貌

  • 確定性 MAC 與典範驗證（canonical verification）：實務上幾乎所有 MAC（HMAC、CMAC、GMAC、Poly1305）都是確定性的，而 \(\Vf\) 就是「重新計算 \(\tau' = \Tag(\ik, m)\)，比較是否等於 \(\tau\)」。KL-IMC 稱之為典範驗證；Problem 1 (viii) 會證明在這種情況下，給敵手驗證預言機並不會讓它更強。

  • 不只用於通訊：KL-IMC §4.2 指出 MAC 的另一個典型場景是「自己與未來的自己」通訊——伺服器在使用者瀏覽器中存放的 cookie、存在不可信儲存裝置上的資料，都可用 MAC 防止被竄改（不一定需要加密）。

  • 與數位簽章的差別：MAC 是對稱的，驗證者也能產生標籤，所以 MAC 不能向第三方證明「這是 Alice 寫的」（Bob 也能偽造）。需要「不可否認性」時要用數位簽章（公鑰密碼學，課程後半）。

  • 能舉例說明「保密不蘊含完整性」（一次性密碼本的位元翻轉）與「完整性不蘊含保密性」（明文加標籤）。

  • 能默寫 MAC 的語法；能畫出或描述 Encrypt-then-MAC 的傳送／接收流程，並強調「先驗證、後解密」。

  • 知道為何加密與 MAC 要使用獨立的金鑰。