AES-GCM 是使用最廣的鑑別式密碼。它當然基於 AES 演算法，而 Galois 計數器模式（GCM，Galois counter mode）本質上是 CTR 模式的一個調整版，加進了一個小而有效率的元件來計算鑑別標籤。

本書寫作時，AES-GCM 是唯一一個 NIST 標準的鑑別式密碼（SP 800-38D）。

它也是 NSA Suite B 的一部分，並被 IETF 用於 IPSec、SSH 與 TLS 1.2 這些安全網路協定。

雖然 GCM 可以搭配任何區塊密碼，你大概只會看到它與 AES 搭配。

有些人因為 AES 是美國的而不想用它，但基於同樣的理由他們也不會用 GCM——因此 GCM 很少與其他密碼配對。

內部結構：CTR + GHASH#

AES-GCM 的運作可以拆成兩件事：

  1. 以 CTR 模式加密
  2. 對密文區塊做 MAC

因此 AES-GCM 本質上是一個 encrypt-then-MAC 建構。

加密層#

以秘密金鑰 K 參數化的 AES 實例，變換一個由 nonce N 串接計數器組成的區塊（計數器從 1 開始，接著遞增為 2、3……），再把結果與明文區塊 XOR 得到密文區塊。

這與 CTR 模式相比沒什麼新意，唯一的小差別是計數器從 1 而非 0 開始——就安全性而言這無關緊要。

AES-CTR 使用 128 位元金鑰 K 與 96 位元 nonce N。

鑑別層#

要鑑別密文，GCM 使用一個 Wegman–Carter MAC（見第 7 章），把 AES(K, N ‖ 0) 的值與一個稱為 GHASH 的通用雜湊函式的輸出 XOR 起來：

T = GHASH(H, C) ⊕ AES(K, N ‖ 0)

其中 C 是密文，H 是雜湊金鑰（或稱鑑別金鑰），由下式決定：

H = AES(K, 0)

也就是對一個全為空位元組之區塊的加密。

GCM 中 GHASH 不直接使用 K，是為了確保「即使 GHASH 的金鑰被攻破，主金鑰 K 仍保持秘密」。

給定 K 你可以算出 H = AES(K, 0)，但你無法從 H 反推 K——因為 K 在這裡扮演 AES 的金鑰。

GHASH 用多項式記法把每個密文區塊與鑑別金鑰 H 相乘。

圖 8-2：AES-GCM 模式：套用於一個關聯資料區塊與兩個明文區塊

使用多項式乘法讓 GHASH 在硬體與軟體中都很快，這要歸功於許多常見微處理器上都有的特殊多項式乘法指令 CLMUL（carry-less multiplication，無進位乘法）。

延伸：多項式乘法

多項式乘法對我們來說顯然比古典整數算術複雜，但對電腦而言更簡單，因為沒有進位。

例如要計算 (1 + X + X²) 與 (X + X³) 的乘積，先照一般多項式乘法展開（兩個 X³ 項互相抵銷）：

(1 + X + X²)(X + X³) = X + X² + X³ + X³ + X⁴ + X⁵
                      = X + X² + X⁴ + X⁵

接著做模歸約，把 X + X² + X⁴ + X⁵ 對 1 + X³ + X⁴ 取模，得到 X²——因為：

X + X² + X⁴ + X⁵ = X ⊗ (1 + X³ + X⁴) + X²

更一般地說，依模歸約的定義，A + BC 對 B 取模等於 A。

GHASH 的缺點#

可惜 GHASH 遠稱不上理想：

  • 速度並非最佳：即使使用 CLMUL 指令，加密明文的 AES-CTR 層仍然比 GHASH MAC 更快。
  • 難以正確實作：事實上，連全世界使用最廣之密碼學軟體 OpenSSL 專案的資深開發者都把 AES-GCM 的 GHASH 寫錯了。一個 commit 在 gcm_ghash_clmul 函式中有 bug，允許攻擊者為 AES-GCM 偽造有效的 MAC。（所幸該錯誤在進入下個 OpenSSL 發行版之前被 Intel 工程師發現。）

GCM 的安全性#

若同一個 nonce N 在 AES-GCM 實作中被用了兩次，攻擊者就能取得鑑別金鑰 H，並用它為任何密文、關聯資料或其組合偽造標籤。

為什麼#

標籤的計算是 T = GHASH(H, A, C) ⊕ AES(K, N ‖ 0)，而 GHASH 是一個輸入輸出呈線性關係的通用雜湊函式。

若你拿到用同一個 nonce N 計算的兩個標籤 T₁ 與 T₂，把它們 XOR 起來，AES 的部分就會消失：

T₁ ⊕ T₂
 = [GHASH(H, A₁, C₁) ⊕ AES(K, N‖0)] ⊕ [GHASH(H, A₂, C₂) ⊕ AES(K, N‖0)]
 = GHASH(H, A₁, C₁) ⊕ GHASH(H, A₂, C₂) ⊕ [AES(K, N‖0) ⊕ AES(K, N‖0)]
 = GHASH(H, A₁, C₁) ⊕ GHASH(H, A₂, C₂)

攻擊者因此能對已知的 A₁, C₁, A₂, C₂ 還原出 GHASH(H, A₁, C₁) ⊕ GHASH(H, A₂, C₂)。GHASH 的線性性接著讓攻擊者能輕易求出 H。

若 GHASH 使用了與加密部分相同的金鑰 K，情況會更糟。但因為 H = AES(K, 0)，沒有辦法從 H 找到 K。

這在現實中發生過#

2016 年，研究人員掃描網際網路上透過 HTTPS 伺服器暴露的 AES-GCM 實例，尋找 nonce 重複的系統。

他們找到 184 台 nonce 重複的伺服器，其中 23 台永遠使用全零字串當 nonce。

GCM 的效率#

GCM 模式的一個優點是加密與解密都可平行化，讓你能獨立加解密不同的明文區塊。

但 AES-GCM 的 MAC 計算不可平行化：GHASH 處理完任何關聯資料後，它必須從密文的開頭一路算到結尾。

這意味著任何「先收到明文、再收到關聯資料」的系統，都必須等到所有關聯資料被讀取並雜湊完畢，才能開始雜湊第一個密文區塊。

不過 GCM 是可串流的：由於兩層的計算可以管線化，不需要在計算 GHASH 之前先存下所有密文區塊——GHASH 會在每個區塊被加密的當下就處理它。

P₁ 加密成 C₁ → GHASH 處理 C₁（同時 P₂ 加密成 C₂）→ P₁ 與 C₁ 不再需要 → ...
Backward 鑑別式密碼 OCB Forward