伽罗瓦/计数器模式

在密碼學中，**伽羅瓦 / 計數器模式**( **GCM** ) 是對稱密鑰加密分組密碼的一種操作模式，因其性能而被廣泛採用。可以使用廉價的硬體資源實現最先進的高速通信通道的 GCM 吞吐率。 該操作是一種經過身份驗證的加密算法，旨在提供數據真實性（完整性）和保密性。 GCM 是為塊大小為 128 位的塊密碼定義的。 伽羅瓦消息認證碼（**Galois Message Authentication Code** ，**GMAC** ) 是 GCM 的僅認證變體，可以形成增量消息認證代碼。 GCM 和 GMAC 都可以接受任意長度的初始化向量。

不同的分組密碼操作模式可能具有明顯不同的性能和效率特性，即使使用相同的分組密碼也是如此。 GCM 可以充分利用並行處理，實現 GCM 可以有效利用指令流水線或硬體流水線。相比之下，密碼塊連結（CBC）操作模式會導致流水線停頓，從而影響其效率和性能。

## 基本操作

與普通計數器模式一樣，塊按順序編號，然後該塊編號與初始化向量（Initialization Vector，IV） 組合併使用塊密碼 E 加密，通常為 AES 。然後將此加密的結果與明文進行異或以產生密文。與所有計數器模式一樣，這本質上是一個流密碼，因此對於每個加密的流使用不同的 IV 是必不可少的。

密文塊被視為多項式的係數，然後在依賴於密鑰的點 H 使用有限域算術對其進行評估。然後對結果進行加密，生成可用於驗證數據完整性的身份驗證標籤。然後，加密文本包含 IV、密文和身份驗證標籤。

## 數學基礎

GCM 將眾所周知的計數器加密模式與新的 Galois 身份驗證模式相結合。關鍵特徵是用於驗證的伽羅瓦域乘法易於並行計算。此功能允許比使用連結模式的加密算法（如 CBC ）更高的吞吐量。使用的 GF (2 128 ) 欄位由多項式定義

　
: $x^{128}+x^{7}+x^{2}+x+1$

身份驗證標籤是通過將數據塊輸入 GHASH 函數並對結果進行加密來構建的。這個 GHASH 函數定義為

　
: ${\text{GHASH}}(H,A,C)=X_{m+n+1}$

其中 _H_ = _E k_ (0 128 ) 是哈希密鑰，使用分組密碼加密的 128 個零位的字符串， _A_ 是僅經過身份驗證（未加密）的數據， _C_ 是密文， _m_ 是 128- _A 中的_位塊（向上取整）， _n 是 C_ 中 128 位塊的數量（向上取整），對於 _i_ = 0, ..., _m_ + _n_ + 1 _的變量 X i_ 定義如下。 

首先，經過驗證的文本和密文分別用零填充到 128 位的倍數，並組合成單個消息 _S i_ ：

　
: $S_{i}={\begin{cases}A_{i}&{\text{for }}i=1,\ldots ,m-1\\A_{m}^{*}\parallel 0^{128-v}&{\text{for }}i=m\\C_{i-m}&{\text{for }}i=m+1,\ldots ,m+n-1\\C_{n}^{*}\parallel 0^{128-u}&{\text{for }}i=m+n\\\operatorname {len} (A)\parallel \operatorname {len} (C)&{\text{for }}i=m+n+1\end{cases}}$

其中 len ( _A_ ) 和 len ( _C_ _) 分別是 A_ 和 _C_ 的位長的 64 位表示， _v_= 連（_一_） 模組 _128 是 A_ 的最後一個塊的位長， _u_= 長度 ( _C_ ) 模組 _128 是 C_ 的最後一個塊的位長，並且 $\parallel $ 表示位串的串聯。

　
: $X_{i}=\sum _{j=1}^{i}S_{j}\cdot H^{i-j+1}={\begin{cases}0&{\text{for }}i=0\\\left(X_{i-1}\oplus S_{i}\right)\cdot H&{\text{for }}i=1,\ldots ,m+n+1\end{cases}}$

第二種形式是一種有效的迭代算法（每個 _X i_ 取決於 _X_ i -1 ），它是通過將霍納的方法應用於第一種而產生的。只有最後的 _X_ m + _n_ +1 仍然是輸出。

如果需要並行化哈希計算，可以通過交錯 _k_ 次來完成：

　
: ${\begin{aligned}X_{i}^{'}&={\begin{cases}0&{\text{for }}i\leq 0\\\left(X_{i-k}^{'}\oplus S_{i}\right)\cdot H^{k}&{\text{for }}i=1,\ldots ,m+n+1-k\\\end{cases}}\\[6pt]X_{i}&=\sum _{j=1}^{k}\left(X_{i+j-2k}^{'}\oplus S_{i+j-k}\right)\cdot H^{k-j+1}\end{aligned}}$

如果 IV 的長度不是 96，則使用 GHASH 函數計算 _Counter 0_ ：

　
: ${\begin{aligned}Counter0={\begin{cases}IV\parallel 0^{31}\parallel 1&{\text{for }}len(IV)=96\\{\text{GHASH}}(\ IV\parallel 0^{s}\ \parallel \ 0^{64}\parallel len_{64}(IV)\ ){\text{ with }}s=(128-(len(IV)\mod 128))\mod 128&{\text{otherwise}}\end{cases}}\end{aligned}}$

GCM 由 John Viega 和 David A. McGrew 設計，是對 Carter-Wegman 計數器模式（CWC 模式）的改進。

2007 年 11 月， NIST 宣布發布 NIST 特別出版物 800-38D _對塊密碼操作模式的建議：伽羅瓦 / 計數器模式 (GCM) 和 伽羅瓦消息驗證碼（GMAC），_使 GCM 和 GMAC 成為官方標準。

## 利用

GCM 模式用於 IEEE 802.1AE (MACsec) 乙太網安全、 IEEE 802.11ad （也稱為 WiGig ）、ANSI (INCITS) 光纖通道安全協議 (FC-SP)、 IEEE P1619 .1 磁帶存儲、 IETF IPsec 標準、 SSH ， TLS 1.2 和 TLS 1.3。 AES-GCM 包含在 NSA Suite B 密碼學及其 2018 年商業國家安全算法 (CNSA) 套件中的最新替代品中。 GCM 模式用於 SoftEther VPN 伺服器和客戶端， 以及自 2.4 版以來的 OpenVPN。

## 表現

GCM 要求對每個加密和驗證數據塊（128 位）在 Galois 欄位中進行一次分組密碼操作和一次 128 位乘法。分組密碼操作很容易流水線化或並行化；乘法運算很容易流水線化，並且可以通過一些適度的努力進行並行化（通過並行化實際操作，通過根據原始 NIST 提交調整 Horner 的方法，或兩者兼而有之）。

英特爾添加了 PCLMULQDQ 指令，突出了它對 GCM 的使用。 2011 年，SPARC 添加了 XMULX 和 XMULXHI 指令，它們也執行 64 × 64 位無進位乘法。 2015 年，SPARC 添加了 XMPMUL 指令，該指令對更大的值執行 XOR 乘法，高達 2048 × 2048 位的輸入值產生 4096 位的結果。這些指令支持 GF (2 n ) 上的快速乘法，並且可以與任何欄位表示一起使用。

GCM 在許多平台上發布了令人印象深刻的性能結果。 Käsper 和 Schwabe 描述了一種「更快且抗時間攻擊的 AES-GCM」 ，它在 64 位英特爾處理器上實現了每字節 10.68 個周期的 AES-GCM 認證加密。Dai 等人。使用 Intel 的 AES-NI 和 PCLMULQDQ 指令時，對於相同的算法，每字節報告 3.5 個周期。 Shay Gueron 和 Vlad Krasnov 在第三代英特爾處理器上實現了每字節 2.47 個周期。為 OpenSSL 和 NSS 庫準備了適當的補丁。 

當需要對消息執行身份驗證和加密時，軟體實現可以通過重疊這些操作的執行來實現速度提升。通過交錯操作利用指令級並行性來提高性能。這個過程稱為函數拼接， ，雖然原則上它可以應用於密碼算法的任何組合，但 GCM 特別適合。 Manley 和 Gregg 展示了在 GCM 中使用函數拼接時優化的簡易性。他們提出了一個程序生成器，它採用加密算法的帶注釋的 C 版本，並生成在目標處理器上運行良好的代碼。

例如，GCM 在嵌入式領域受到 Silicon Labs 的批評，因為並行處理不適合加密硬體引擎的高性能使用，因此降低了一些對性能最敏感的設備的加密性能。 

## 專利

根據作者的聲明，GCM 不受專利保護。 

## 安全性

GCM 在具體的安全模型中被證明是安全的。 當它與與隨機排列無法區分的分組密碼一起使用時，它是安全的；然而，安全性取決於為使用相同密鑰執行的每個加密選擇唯一的初始化向量 _（參見_流密碼攻擊）。對於任何給定的密鑰和初始化向量組合，GCM 僅限於加密 239−256 位純文本 (64 GiB)。 NIST 特別出版物 800-38D 包括初始化向量選擇指南。

身份驗證強度取決於身份驗證標籤的長度，就像所有對稱消息身份驗證代碼一樣。不鼓勵在 GCM 中使用較短的身份驗證標籤。標記的位長，用 t 表示，是一個安全參數。一般來說，t 可以是以下五個值中的任意一個：128、120、112、104 或 96。對於某些應用，t 可能是 64 或 32，但這兩個標籤長度的使用限制了輸入的長度數據和密鑰的生命周期。 NIST SP 800-38D 中的附錄 C 為這些約束提供了指導（例如，如果 t = 32 且最大數據包大小為 210 字節，則應調用身份驗證解密函數不超過 211 次；如果 t = 64 且最大數據包大小為數據包大小為 215 字節，認證解密函數調用不超過 232 次）。

與任何消息認證代碼一樣，如果對手_隨機選擇一個 t_ 位標籤，則對於概率度量為 2 - _t 的_給定數據，它預計是正確的。然而，使用 GCM，對手可以通過選擇帶有 n 個單詞的標籤 —— 密文的總長度加上任何額外的認證數據 (AAD)—— 以概率度量 2 - _t_ 乘以 n 來增加成功的可能性。儘管如此，必須記住，對於任意大的 _t_ ，這些最佳標籤仍然由算法的生存度量 1 − _n_⋅2−_t_ 主導。此外，GCM 既不適合用於非常短的標籤長度，也不適合用於非常長的消息。

Ferguson 和 Saarinen 分別描述了攻擊者如何針對 GCM 身份驗證執行最優攻擊，滿足其安全性的下限。 Ferguson 表明，如果 _n_ 表示編碼中的塊總數（GHASH 函數的輸入），那麼有一種方法可以構建目標密文偽造，預計成功的概率約為 _n_ ⋅2 − _t_ . 如果標籤長度 _t_ 小於 128，那麼這次攻擊中的每一次成功偽造都會增加後續有針對性的偽造成功的概率，並泄漏有關哈希子密鑰的信息，_H_ . 最終， _H_ 可能會被完全破壞，並且完全失去認證保證。 

除了這種攻擊，攻擊者可能會嘗試系統地猜測給定輸入的許多不同標籤以進行身份驗證解密，從而增加其中一個（或多個）最終被視為有效的可能性。因此，實現 GCM 的系統或協議應監控並在必要時限制每個密鑰的不成功驗證嘗試次數。

Saarinen 描述了 GCM 弱密鑰。 這項工作為基於多項式哈希的身份驗證的工作原理提供了一些有價值的見解。更準確地說，這項工作描述了一種在給定有效 GCM 消息的情況下偽造 GCM 消息的特定方法，對於 _n_ × 128 位長的 _n_⋅2−128 然而，這項工作並沒有表現出比以前已知的更有效的攻擊；本文觀察 1 中的成功概率與 INDOCRYPT 2004 分析中引理 2 的成功概率相匹配（設置 _w_ = 128 和 _l_ = _n_ × 128 ）。 Saarinen 還描述了基於 Sophie Germain primes 的 GCM 變體 Sophie Germain Counter Mode (SGCM)。

## 參見

* 認證加密
* 分組密碼操作模式
* AES-GCM-SIV

## 參考文獻