Problem 2：On encryption（論加密）

核心問題。確定性加密把「加密」變成一個固定的查表：\(m \mapsto c\) 是一個固定的函數。於是

1. 相等性洩漏：\(c_i = c_j \iff m_i = m_j\)。敵手不需金鑰就知道哪些密文對應同一則訊息、每則訊息出現幾次（講義迭代 (iii) 的「字母頻率」反例，在訊息層級重演）。

2. 字典攻擊：若敵手有 \(\Enc(\sk,\cdot)\) 的存取權，它可以把所有「可能的」訊息都拿去加密、建一本密文–明文對照字典，之後看到任何密文就直接查表「解密」——完全不需要知道金鑰。當訊息空間小、或訊息高度公式化時，這本字典很容易建完。

場景一：公式化的軍事／商業訊息。 戰場上的回報往往只有少數幾種：「NOTHING TO REPORT」、「ATTACK AT DAWN」、「RETREAT」。 敵手（有加密預言機時）把這幾句都加密一遍；之後攔到的每一封密文，一比對就知道內容。 即使沒有預言機，光是「今天的密文與過去 30 天某一天相同」也足以推論「今天沒事」。 二戰時盟軍破解 Enigma 的「crib」正是利用德軍每日固定的「Keine besonderen Ereignisse」（無特殊事件）與氣象報告格式；中途島的「AF 缺水」則是主動誘導對方加密指定明文（見第 [sec:iterations] 節）。

場景二：投票或是／否回覆。 電子投票系統把每張選票 \(m \in \{\texttt{YES}, \texttt{NO}\}\) 加密後公布。 敵手自己投一票 YES（這就是一次加密預言機查詢！），看到自己的密文 \(c_{\texttt{YES}}\)； 從此所有與 \(c_{\texttt{YES}}\) 相同的選票都是贊成票，其餘都是反對票——全部選票被解密，金鑰仍然安全無虞。

場景三：金融交易。 「TRANSFER £100 FROM A TO B」這類訊息格式固定、欄位值範圍小。敵手開一個帳戶、對自己做幾筆轉帳（取得密文），就能辨識出其他人的交易類型與金額級距；再配合重放（Problem 2 (ii)），後果更嚴重。

場景四：資料庫欄位加密。 為了能用 查詢，有些系統對欄位採確定性加密。 2015 年 Naveed、Kamara 與 Wright 對這類系統（如 CryptDB 式設計）的研究顯示：只靠公開的統計資料（例如人口的姓氏分布、病歷中診斷碼的頻率）配合密文的頻率，就能還原大部分欄位內容——這正是「頻率洩漏」在現代的具體代價。

形式化的說法。任何確定性且無狀態的加密方案都不可能是 CPA 安全的（第 [sec:ind-preview] 節的遊戲）：敵手先向預言機查詢 \(m_0\) 得到 \(c_0\)，再以 \((m_0, m_1)\) 挑戰；若挑戰密文 \(c^\ast = c_0\) 就猜 \(b = 0\)、否則猜 \(b = 1\)，必勝。 這也是為什麼講義在迭代 (v) 中要給敵手「讓選定訊息被加密」的能力——它立刻排除掉所有確定性方案。

解法。加密必須是隨機化（每次加密抽一個新的隨機值／IV）或有狀態（使用計數器作為 nonce）的，使同一訊息每次都產生不同的密文；KL-IMC §3.4 稱此為「加密必須是機率性的」。 附註：確定性加密在少數場合仍被刻意使用（金鑰包裝、可搜尋加密、SIV 模式的「nonce 誤用抵抗」），但使用者必須清楚它一定洩漏相等性，並確認在該場景中可以接受。

先弄清楚敵手還剩下什麼能力。MAC 完美，表示敵手無法送出任何「不是由 Alice 或 Bob 誠實產生」的 \(\tilde c\)——它改不了任何一個位元。它剩下的只有對整個 \(\tilde c\) 的操作：重複送（重放）、調換順序（重排）、送回原發送者（反射）、扣住（延遲）、丟掉（拒絕）。 前三者的共通點是：每一個 \(\tilde c\) 本身都是真的，錯的是它出現的「時間」、「位置」或「方向」。 所以對策也很清楚：把「這則訊息應該在什麼時候、什麼位置、往哪個方向出現」寫進訊息裡，讓接收端能檢查。因為這些資訊是 \(m\) 的一部分，它們會被 \(\Enc\) 加密、再被 \(\Tag\)（透過 \(c\)）保護——敵手無法竄改它們。

把三者合在一起，就是 KL-IMC §5.4 的「安全通訊 session」構造：

逐一驗證三種攻擊都失效。

• 重放：敵手重送 \(\tilde c_1\)。\(B\) 驗證通過、解密得 \(\ctr = 0\)，但 \(B\) 已把 \(\ctr_{A\to B}\) 推進到 \(1\)（或更大），\(0 \neq\) 期望值 \(\Rightarrow\) 拒絕。

• 重排：敵手先送 \(\tilde c_2\)（\(\ctr = 1\)）。\(B\) 期望 \(0\) \(\Rightarrow\) 拒絕。（若之後 \(\tilde c_1\) 送達則被接受，再來 \(\tilde c_2\) 也會被接受——順序被強制了。）

• 反射：敵手把 \(\tilde c_1\) 送回 \(A\)。因為雙方共用 \((\sk,\ik)\)，\(A\) 的 \(\Vf\) 會通過、\(\Dec\) 會成功——但解析出 \(b = b_{A\to B} = 0\)，而 \(A\) 只接受 \(b_{B\to A} = 1\) \(\Rightarrow\) 拒絕。

幾個設計上的補充。

1. 為什麼放進 \(m\) 而不是明文附在旁邊？ 只要這些欄位受到 MAC 保護即可；放進 \(m\) 是最省事的做法（\(\tau\) 透過 \(c\) 覆蓋了一切），而且順便隱藏了序號這類中繼資料。現代的 AEAD 介面另有「關聯資料」（associated data）欄位，可以把序號以明文但受鑑別的方式附上。 絕對不能做的是把序號放在 MAC 範圍之外——那敵手改一改就能繞過檢查。

2. 隱含序號：TLS 1.3 甚至不傳送序號，雙方各自計數，並把序號混入加密的 nonce；序號不對時解密／驗證會直接失敗。省頻寬，效果相同。

3. 另一種擋反射的方法：兩個方向使用不同的金鑰（\(\sk_{A\to B}, \ik_{A\to B}\) 與 \(\sk_{B\to A}, \ik_{B\to A}\)，TLS 1.3 的 ／ 即是）。反射回來的訊息會直接驗證失敗，不需要方向位元。KL-IMC 註腳指出這是實務上更常見的做法。

4. 跨 session 的重放：計數器每次 session 都從 \(0\) 開始，若兩次 session 用同一組金鑰，上一次的 \(\tilde c\) 就能在這一次重放。解法：每個 session 使用新鮮的金鑰（金鑰協商），或把一個隨機的 session 識別碼也放進 \(m'\)。

5. 時間戳 vs. 計數器：時間戳不需雙方同步「狀態」，但需要同步「時鐘」，且在容許視窗 \(\Delta\) 內仍可重放（除非接收端額外記住視窗內看過的訊息）。計數器精確，但雙方必須保持同步——這正是 (iii) 要討論的脆弱點。

一句話：敵手仍然無法讓 \(B\) 接受任何不該接受的訊息（保密性、完整性、防重放／重排／反射全都保持），但它獲得了對可用性（availability）的強大槓桿，而且某些「遺失」會變得與「惡意刪除」無法區分。具體影響取決於 (ii) 中接收端對計數器採取的政策。

1. 嚴格計數器政策（只接受 \(\ctr =\) 期望值）。

• 放大的阻斷服務：敵手只要丟掉一則 \(\tilde c_i\)，之後的 \(\tilde c_{i+1}, \tilde c_{i+2}, \ldots\) 全部因為「\(\ctr\) 跳號」而被拒絕——雙方計數器失去同步（desynchronisation），整個 session 停擺，直到重新協商。丟一封訊息的成本，換來癱瘓整條連線的效果。

• 好消息：遺失會被偵測。KL-IMC 把「message-dropping attack」列為第三種攻擊，並說「我們至少希望這種行為能被偵測」。嚴格計數器恰好做到這點：\(B\) 看到 \(\ctr\) 跳號，就知道中間少了東西。密碼學不能阻止丟包，但能讓丟包不會悄悄地發生。

• 安全性不受影響：敵手丟掉 \(\tilde c_i\) 後，仍然無法讓 \(B\) 接受 \(\tilde c_{i+1}\) 當作第 \(i\) 則、也無法補送任何偽造的訊息。

2. 寬鬆政策（滑動視窗／「只要比上次大就接受」）。 為了容忍自然的封包遺失（UDP、無線網路），DTLS 與 IPsec 採用滑動視窗：接受視窗內未見過的序號。此時：

• 選擇性刪除變得「合法」：敵手丟掉 \(\tilde c_1\)、放行 \(\tilde c_2\)，\(B\) 接受 \(\tilde c_2\) 並把視窗推進；\(\tilde c_1\) 之後即使送達也可能落在視窗之外而被丟棄。對 \(B\) 而言，這與「網路剛好掉了一個封包」無法區分——敵手得到了一個「精準刪掉特定訊息」的能力（例如刪掉「取消交易」那一封）。

• 視窗內的重排被容忍：這是設計上的取捨，上層應用必須自行處理順序。

• 重放仍被擋住：視窗內的序號必須「未見過」，所以同一則訊息仍只會被接受一次。

3. 若 (ii) 使用時間戳。 拒絕傳遞的近親是延遲：敵手扣住 \(\tilde c\)，在容許視窗 \(\Delta\) 的最後一刻才放行——訊息仍「新鮮」、會被接受，但時效可能已過（「現在賣出」在崩盤後才到）。視窗越大越容易出事，越小越容易誤拒合法訊息；這是時間戳方案的固有張力。

4. 截斷攻擊（truncation）：連嚴格計數器也偵測不到的事。 計數器能偵測中間的缺口，卻偵測不到結尾的缺失：若敵手丟掉 session 的最後 \(k\) 則訊息，\(B\) 只會以為「對方還沒說完」或「對話結束了」。 SSL 2.0 就有這個問題；後來的 TLS 加入了受鑑別的 訊息——沒有收到它就表示連線被截斷。一般原則：需要一則受鑑別的「結束」訊息（或回條／心跳），拒絕傳遞才會變成可偵測的事件。

總結：這就是講義為何把「延遲」與「拒絕傳遞」劃入網路工程。 密碼學控制的是訊息的內容與身分，不是通道的行為。在 (ii) 的設計下，敵手能做的「壞事」被壓縮到只剩不送與晚送——而這兩件事任何密碼學都無法阻止（敵手只要剪斷電纜即可）。我們能做的是：(a) 讓它可被偵測（計數器缺口、結束訊息、逾時）；(b) 讓系統優雅地恢復（重傳、重新協商、改走別的路徑）；(c) 用冗餘與網路層防護提高敵手的成本。這些都是協定與系統設計的工作，而不是加密或 MAC 的工作。