伽罗瓦/计数器模式

在密码学中，伽罗瓦/计数器模式( GCM ) 是对称密钥加密分组密码的一种操作模式，因其性能而被广泛采用。可以使用廉价的硬件资源实现最先进的高速通信通道的 GCM 吞吐率。 ^[1]该操作是一种经过身份验证的加密算法，旨在提供数据真实性（完整性）和保密性。 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 ¹²⁸ ) 字段由多项式定义

${\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定义如下。 ^[2]

首先，经过验证的文本和密文分别用零填充到 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标准、 ^{[3] [4]} SSH ， ^[5] TLS 1.2 ^{[6] [7]}和 TLS 1.3。 ^[8] AES-GCM 包含在NSA Suite B 密码学及其 2018 年商业国家安全算法 (CNSA)套件中的最新替代品中。 ^[9] GCM 模式用于SoftEther VPN服务器和客户端， ^[10]以及自 2.4 版以来的OpenVPN。

表现

GCM 要求对每个加密和验证数据块（128 位）在 Galois 字段中进行一次分组密码操作和一次 128 位乘法。分组密码操作很容易流水线化或并行化；乘法运算很容易流水线化，并且可以通过一些适度的努力进行并行化（通过并行化实际操作，通过根据原始 NIST 提交调整 Horner 的方法，或两者兼而有之）。

英特尔添加了PCLMULQDQ指令，突出了它对 GCM 的使用。 ^[11] 2011 年，SPARC 添加了 XMULX 和 XMULXHI 指令，它们也执行 64 × 64 位无进位乘法。 2015 年，SPARC 添加了 XMPMUL 指令，该指令对更大的值执行 XOR 乘法，高达 2048 × 2048 位的输入值产生 4096 位的结果。这些指令支持 GF(2 ⁿ ) 上的快速乘法，并且可以与任何字段表示一起使用。

GCM 在许多平台上发布了令人印象深刻的性能结果。 Käsper 和 Schwabe 描述了一种“更快且抗时间攻击的AES-GCM” ^[12] ，它在 64 位英特尔处理器上实现了每字节 10.68 个周期的 AES-GCM 认证加密。Dai等人。使用 Intel 的 AES-NI 和 PCLMULQDQ 指令时，对于相同的算法，每字节报告 3.5 个周期。 Shay Gueron 和 Vlad Krasnov 在第三代英特尔处理器上实现了每字节 2.47 个周期。为 OpenSSL和NSS库准备了适当的补丁。 ^[13]

当需要对消息执行身份验证和加密时，软件实现可以通过重叠这些操作的执行来实现速度提升。通过交错操作利用指令级并行性来提高性能。这个过程称为函数拼接， ^[14] ，虽然原则上它可以应用于密码算法的任何组合，但 GCM 特别适合。 Manley 和 Gregg ^[15]展示了在 GCM 中使用函数拼接时优化的简易性。他们提出了一个程序生成器，它采用加密算法的带注释的 C 版本，并生成在目标处理器上运行良好的代码。

例如，GCM 在嵌入式领域受到 Silicon Labs 的批评，因为并行处理不适合加密硬件引擎的高性能使用，因此降低了一些对性能最敏感的设备的加密性能。 ^[16]

专利

根据作者的声明，GCM 不受专利保护。 ^[17]

安全性

GCM 在具体的安全模型中被证明是安全的。 ^[18]当它与与随机排列无法区分的分组密码一起使用时，它是安全的；然而，安全性取决于为使用相同密钥执行的每个加密选择唯一的初始化向量（参见流密码攻击）。对于任何给定的密钥和初始化向量组合，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可能会被完全破坏，并且完全失去认证保证。 ^[19]

除了这种攻击，攻击者可能会尝试系统地猜测给定输入的许多不同标签以进行身份验证解密，从而增加其中一个（或多个）最终被视为有效的可能性。因此，实现 GCM 的系统或协议应监控并在必要时限制每个密钥的不成功验证尝试次数。

Saarinen 描述了 GCM弱密钥。 ^[20]这项工作为基于多项式哈希的身份验证的工作原理提供了一些有价值的见解。更准确地说，这项工作描述了一种在给定有效 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. Lemsitzer, S.; Wolkerstorfer, J.; Felber, N.; Braendli, M. 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. 
2. 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.
3. RFC 4106 The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
4. RFC 4543 The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
5. RFC 5647 AES Galois Counter Mode for the Secure Shell Transport Layer Protocol
6. RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS
7. RFC 6367 Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
8. RFC 8446 The Transport Layer Security protocol version 1.3
9. Algorithm Registration - Computer Security Objects Register | CSRC | CSRC. 24 May 2016 [2022-01-03]. （原始内容于2020-04-16）. 
10. Why SoftEther VPN – SoftEther VPN Project. [2022-01-03]. （原始内容于2013-03-11）. 
11. 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）. 
12. 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. 
13. 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）. 
14. 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)
15. 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. 
16. IoT Security Part 6: Galois Counter Mode. 2016-05-06 [2018-04-29]. （原始内容于2016-05-11）. 
17. 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）. 
18. 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. 
19. Niels Ferguson, Authentication Weaknesses in GCM （页面存档备份，存于互联网档案馆）, 2005-05-20
20. 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）.