伽罗瓦/计数器模式

在密码学中，伽罗瓦/计数器模式（GCM）是一种对称分组加密算法的工作模式，因其良好的性能而被广泛采用。最快速的GCM通信信道可以用便宜的硬件来实现。

GCM算法提供数据真实性（与完整性）和机密性的验证，基于关联数据认证加密（AEAD）方法。这表示它需要密钥K、明文P和一些附加数据（associated data，以下简称AD）作为输入；然后使用密钥对明文 P 加密得到密文 C，并根据密文和AD（未加密）的计算来得到认证标签 T。知道K（密钥）的接收者在收到AD、C（密文）和T（认证标签）后可以解密密文以得到P（明文），并且可以检查T（认证标签）以确保密文和AD都没有被篡改。

GCM使用块大小为128位的块密码（通常为AES-128）的计数器模式进行加密，并使用伽罗瓦域GF（$2^{128}$）中的算术来计算认证标签；因此得名。

伽罗瓦消息认证码（GMAC）是GCM的一种仅用于认证的变体，可以形成增量消息认证码。GCM和GMAC都可以接受任意长度的初始化向量。

即使是与相同的分组密码一起使用，不同的分组密码的操作模式也可能具有显著的不同性能和效率特征。GCM可以充分利用并行处理，实现GCM可以有效地利用指令流水线或硬件流水线。相比之下，密码块链接（CBC）模式会导致流水线停滞，从而影响其效率和性能。

## 基本操作

与一般计数器模式一样，每个块按顺序编号，然后该块编号与初始化向量（Initialization Vector，IV）组合并使用块密码算法（E）加密（通常是AES）。然后将此加密的结果与明文进行异或以产生密文。与所有计数器模式一样它本质上是一个流密码，因此必须对于每个加密流使用不同的 IV。

密文块被认为是一个多项式的系数，然后在密钥相关点H处使用有限域算术求值。随后再对结果进行加密，生成可用于验证数据完整性的身份验证标签。加密后的内容包含 IV、密文和身份验证标签。

<image>

## 数学基础

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} <pre> 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 </pre> \end{cases}$$

其中 len( A ) 和 len( C ) 分别是 A和C的位长的 64 位表示， v = 连（一）模组 128 是 A的最后一个块的位长， u = 长度( C ) 模组 128 是 C的最后一个块的位长，并且$\parallel$表示位串的串联。

$$<pre> 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 </pre> \end{cases}$$

第二种形式是一种有效的迭代算法（每个X i取决于X i -1），它是通过将霍纳的方法应用于第一种而产生的。只有最后的X m + n +1仍然是输出。

如果需要并行化哈希计算，可以通过交错k次来完成：

$$\begin{align} <pre> 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} </pre> \end{align}$$

如果 IV 的长度不是 96，则使用 GHASH 函数计算Counter 0：

$$\begin{align} Counter 0 = \begin{cases} IV \parallel 0^{31} \parallel 1 & \text{for } len(IV) = 96 \\ <pre> \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{align}$$

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)。