伽羅瓦/計數器模式

在密碼學中，伽羅瓦/計數器模式（GCM）^[1]是一種對稱分組加密算法的工作模式，因其良好的性能而被廣泛採用。最快速的GCM通信信道可以用便宜的硬件來實現^[2]。

GCM算法提供數據真實性（與完整性）和機密性的驗證，基於關聯數據認證加密（AEAD）方法。這表示它需要密鑰K、明文P和一些附加數據（associated data，以下簡稱AD）作為輸入；然後使用密鑰對明文 P 加密得到密文 C，並根據密文和AD（未加密）的計算來得到認證標籤 T。知道K（密鑰）的接收者在收到AD、C（密文）和T（認證標籤）後可以解密密文以得到P（明文），並且可以檢查T（認證標籤）以確保密文和AD都沒有被篡改。

GCM使用塊大小為128位的塊密碼（通常為AES-128）的計數器模式進行加密，並使用伽羅瓦域GF（${\displaystyle 2^{128}}$）中的算術來計算認證標籤；因此得名。

伽羅瓦消息認證碼（GMAC）是GCM的一種僅用於認證的變體，可以形成增量消息認證碼。GCM和GMAC都可以接受任意長度的初始化向量。

即使是與相同的分組密碼一起使用，不同的分組密碼的操作模式也可能具有顯著的不同性能和效率特徵。GCM可以充分利用並行處理，實現GCM可以有效地利用指令流水線或硬件流水線。相比之下，密碼塊鏈接（CBC）模式會導致流水線停滯，從而影響其效率和性能。

基本操作

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

密文塊被認為是一個多項式的係數，然後在密鑰相關點H處使用有限域算術求值。隨後再對結果進行加密，生成可用於驗證數據完整性的身份驗證標籤。加密後的內容包含 IV、密文和身份驗證標籤。

數學基礎

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

${\displaystyle x^{128}+x^{7}+x^{2}+x+1}$

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

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

其中H = E _k (0 ¹²⁸ ) 是哈希密鑰，使用分組密碼加密的 128 個零位的字符串， A是僅經過身份驗證（未加密）的數據， C是密文， m是 128- A 中的位塊（向上取整）， n是 C中 128 位塊的數量（向上取整），對於i = 0, ..., m + n + 1的變量 X _i定義如下。 ^[3]

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

${\displaystyle 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的最後一個塊的位長，並且${\displaystyle \parallel }$表示位串的串聯。

${\displaystyle 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次來完成：

${\displaystyle {\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 ：

${\displaystyle {\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標準、 ^{[4] [5]} SSH ， ^[6] TLS 1.2 ^{[7] [8]}和 TLS 1.3。 ^[9] AES-GCM 包含在NSA Suite B 密碼學及其 2018 年商業國家安全算法 (CNSA)套件中的最新替代品中。 ^[10] GCM 模式用於SoftEther VPN服務器和客戶端， ^[11]以及自 2.4 版以來的OpenVPN。

性能

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

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

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

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

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

專利

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

安全性

GCM 在具體的安全模型中被證明是安全的。 ^[19]當它與與隨機排列無法區分的分組密碼一起使用時，它是安全的；然而，安全性取決於為使用相同密鑰執行的每個加密選擇唯一的初始化向量（參見流密碼攻擊）。對於任何給定的密鑰和初始化向量組合，GCM 僅限於加密2³⁹−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可能會被完全破壞，並且完全失去認證保證。 ^[20]

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

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

參見

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

參考文獻

1. RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS
2. Lemsitzer, S.; Wolkerstorfer, J.; Felber, N.; Braendli, M. Multi-gigabit GCM-AES Architecture Optimized for FPGAs. Paillier, P.; Verbauwhede, I. (編). Cryptographic Hardware and Embedded Systems - CHES 2007. Lecture Notes in Computer Science 4727. Springer. 2007: 227–238. ISBN 978-3-540-74734-5. doi:10.1007/978-3-540-74735-2_16.
3. McGrew, David A. The Galois/Counter Mode of Operation (GCM) (PDF). 2005 [20 July 2013]. （原始內容存檔 (PDF)於2016-03-03）. Note that there is a typo in the formulas in the article.
4. RFC 4106 The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
5. RFC 4543 The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
6. RFC 5647 AES Galois Counter Mode for the Secure Shell Transport Layer Protocol
7. RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS
8. RFC 6367 Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
9. RFC 8446 The Transport Layer Security protocol version 1.3
10. Algorithm Registration - Computer Security Objects Register | CSRC | CSRC. 24 May 2016 [2022-01-03]. （原始內容存檔於2020-04-16）.
11. Why SoftEther VPN – SoftEther VPN Project. [2022-01-03]. （原始內容存檔於2013-03-11）.
12. Gueron, Shay. Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode (Revision 2.02). April 2014 [2018-04-29]. （原始內容存檔於2010-02-18）.
13. Käsper, E.; Schwabe, P. Clavier, C.; Gaj, K. , 編. Cryptographic Hardware and Embedded Systems – CHES 2009. Lecture Notes in Computer Science 5747. Springer. 2009: 1–17. ISBN 978-3-642-04138-9. doi:10.1007/978-3-642-04138-9_1.
14. Gueron, Shay. AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1? (PDF). Workshop on Real-World Cryptography. [8 February 2013]. （原始內容存檔 (PDF)於2014-03-10）.
15. Gopal, V., Feghali, W., Guilford, J., Ozturk, E., Wolrich, G., Dixon, M., Locktyukhin, M., Perminov, M. "Fast Cryptographic Computation on Intel Architecture via Function Stitching" （頁面存檔備份，存於網際網路檔案館） Intel Corp. (2010)
16. Manley, Raymond; Gregg, David. Gong, G.; Gupta, K.C. , 編. Progress in Cryptology – INDOCRYPT 2010. Lecture Notes in Computer Science 6498. Springer. 2010: 311–327. ISBN 978-3-642-17400-1. doi:10.1007/978-3-642-17401-8_22.
17. IoT Security Part 6: Galois Counter Mode. 2016-05-06 [2018-04-29]. （原始內容存檔於2016-05-11）.
18. McGrew, David A. The Galois/Counter Mode of Operation (GCM) Intellectual Property Statement (PDF). Computer Security Resource Center, NIST. [2022-01-03]. （原始內容存檔 (PDF)於2008-08-29）.
19. McGrew, David A.; Viega, John. Proceedings of INDOCRYPT 2004. Lecture Notes in Computer Science 3348. Springer. 2004. Bibcode:10.1.1.1.4591 請檢查|bibcode=值 (幫助). ISBN 978-3-540-30556-9. doi:10.1007/978-3-540-30556-9_27.
20. Niels Ferguson, Authentication Weaknesses in GCM （頁面存檔備份，存於網際網路檔案館）, 2005-05-20
21. Markku-Juhani O. Saarinen. Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes. FSE 2012. 2011-04-20 [2022-01-03]. （原始內容存檔於2020-11-23）.