鑑別式加密 • 嚴謹密碼學：現代加密實務入門

本章談的是一類不只保護訊息機密性、還保護其真確性的演算法。

回想第 7 章：訊息鑑別碼（MAC）藉由產生一個標籤（某種簽名）來保護訊息的真確性。與 MAC 一樣，本章討論的鑑別式加密（AE，authenticated encryption）演算法也產生鑑別標籤，但它們同時還加密訊息。

換句話說：單一個 AE 演算法同時提供了一般密碼與 MAC 的功能。

本章脈絡#

用 MAC 做鑑別式加密——encrypt-and-MAC、MAC-then-encrypt、encrypt-then-MAC 三種組合。
鑑別式密碼——AEAD、nonce 的角色，以及評估準則。
AES-GCM——標準的鑑別式密碼，及其 nonce 重用的致命弱點。
OCB——比 GCM 更快、更簡單的單層設計。
SIV——最安全但不可串流。
基於置換的 AEAD——完全不同的取徑。

常見錯誤#

鑑別式密碼的攻擊面比雜湊函式或區塊密碼更大，因為它們同時追求機密性與真確性。它們接收數個不同的輸入值，且必須在任何輸入下都保持安全——無論輸入只含關聯資料而無加密資料、含極大的明文、或不同的金鑰大小。

它們還必須對所有 nonce 值都安全，能抵抗蒐集大量「訊息／標籤」對的攻擊者，並在某種程度上抵抗 nonce 的意外重複。

這要求很高——如你所見，連 AES-GCM 都有數個不完美之處。

AES-GCM 與弱雜湊金鑰#

AES-GCM 的一個弱點藏在它的鑑別演算法 GHASH 中：某些雜湊金鑰 H 的值會大幅簡化針對 GCM 鑑別機制的攻擊。

具體來說，若 H 屬於全體 128 位元字串中某些數學上定義的特定子群，攻擊者可能只要把前一則訊息的區塊重新洗牌，就能猜出某則訊息的有效鑑別標籤。

GHASH 內部：從 H = AES(K, 0) 與 X₀ = 0 出發，反覆計算：

Xᵢ = (X(i−1) ⊕ Cᵢ) ⊗ H

處理密文區塊 C₁, C₂, ...，最後的 Xᵢ 被 GHASH 回傳用來計算最終標籤。

延伸：推導 GHASH 的展開式

為了簡化，先假設所有 Cᵢ 都等於 1，於是對任意 i 有 Cᵢ ⊗ H = 1 ⊗ H = H。

從 GHASH 的遞迴式出發，代入 X₀ = 0、C₁ = 1：

X₁ = (X₀ ⊕ C₁) ⊗ H = (0 ⊕ 1) ⊗ H = H

利用 ⊗ 對 ⊕ 的分配律，代入 X₁ = H、C₂ = 1：

X₂ = (X₁ ⊕ C₂) ⊗ H = (H ⊕ 1) ⊗ H = H² ⊕ H

再代入 X₂：

X₃ = (X₂ ⊕ C₃) ⊗ H = (H² ⊕ H ⊕ 1) ⊗ H = H³ ⊕ H² ⊕ H

接著 X₄ = H⁴ ⊕ H³ ⊕ H² ⊕ H，依此類推，最後得到：

Xn = Hⁿ ⊕ Hⁿ⁻¹ ⊕ Hⁿ⁻² ⊕ ... ⊕ H² ⊕ H

若那些 Cᵢ 不是 1 而是任意值，我們會得到：

Xn = C₁Hⁿ ⊕ C₂Hⁿ⁻¹ ⊕ C₃Hⁿ⁻² ⊕ ... ⊕ C(n−1)H² ⊕ CnH

GHASH 接著把訊息長度 XOR 進最後這個 Xn，把結果乘上 H，再與 AES(K, N ‖ 0) XOR，產生最終的鑑別標籤 T。

哪裡會出問題：先看兩個最簡單的情況：

若 H = 0：無論 Cᵢ 的值為何、也就是無論訊息為何，Xn = 0。所有訊息都會有相同的鑑別標籤。
若 H = 1：標籤就只是密文區塊的 XOR，把密文區塊重新排序會得到相同的鑑別標籤。

0 與 1 只是 H 的 2^128 個可能值中的兩個，出現機率只有 2/2^128 = 1/2^127。但還有其他弱值——所有「取 i 次方時屬於短循環」的 H 值。

例如 H = 10d04d25f93556e69f58ce2f8d035a4 屬於一個長度為 5 的循環，因為它滿足 H⁵ = H，因此對任何 5 的倍數 e 都有 Hᵉ = H。
於是在 Xn 的展開式中，交換區塊 Cn（乘上 H）與區塊 C(n−4)（乘上 H⁵）會讓鑑別標籤保持不變——這等同於一次偽造。
攻擊者可以利用這個性質，在不知道金鑰的情況下構造出一則新訊息與其有效標籤——而這對安全的鑑別式密碼本該是不可能的。

上例基於長度為 5 的循環，但還有許多更長的循環，因此有許多 H 值比它們應有的更弱。
結論：在 H 恰好屬於短循環的不太可能情況下，攻擊者能偽造任意數量的鑑別標籤——但除非他們知道 H 或 K，否則無法判定 H 的循環長度。所以雖然這個漏洞無法被利用，它本來只要更審慎地選擇模歸約所用的多項式就能避免。
細節見 Markku-Juhani O. Saarinen 的〈Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes〉：https://eprint.iacr.org/2011/202/ ^↗。

AES-GCM 與短標籤#

實務上 AES-GCM 通常回傳 128 位元標籤，但它能產生任意長度的標籤。

使用 128 位元標籤時，嘗試偽造的攻擊者成功機率應該是 1/2^128（一般而言，n 位元標籤的成功機率應為 1/2^n）。但使用較短的標籤時，由於 GCM 結構上的弱點，偽造機率遠高於 1/2^n。

實際公式是 2^m / 2^n，其中 2^m 是「成功攻擊者曾觀察到其標籤的最長訊息」的區塊數：

標籤長度	訊息大小	偽造機率
32 位元	2 MB	`1/2^16`（而非 `1/2^32`）
48 位元	4 GB（`2^28` 個 16 位元組區塊）	`2^28 / 2^48 = 1/2^20`，約百萬分之一

以密碼學的標準而言，百萬分之一是相當高的機率。
更多資訊見 Niels Ferguson 2005 年的論文〈Authentication Weaknesses in GCM〉。

本章脈絡#

常見錯誤#

AES-GCM 與弱雜湊金鑰#

AES-GCM 與短標籤#

延伸閱讀#