宣布AES-GEM（带伽罗瓦扩展模式的AES） - The Trail of Bits博客

Scott Arciszewski
2024年7月12日
密码学

如今，AES-GCM是TLS 1.3使用的两种密码模式之一（另一种是ChaCha20-Poly1305），并且是FIPS验证模块中加密数据的首选方法。但尽管取得了巨大成功，AES-GCM却是一些灾难性故障的根本原因：例如，Hanno Böck和Sean Devlin利用nonce滥用将他们的Black Hat USA幻灯片注入MI5网站。

安全研究人员多年来一直在警告AES-GCM的弱点。十九年前，Niels Ferguson向NIST的一个分组密码模式项目提交了一篇论文，概述了AES-GCM的认证弱点（尽管NIST最终将其标准化）。今年早些时候，亚马逊发表了一篇论文，详细介绍了AES-GCM的实际挑战，并认为AES的128位分组大小不再足够，倾向于256位分组密码（即Rijndael-256）。

为了解决这些问题，我提出了一种新的分组密码模式，称为伽罗瓦扩展模式（简称GEM），我上个月在NIST关于手风琴模式密码需求的研讨会上介绍了它。AES-GEM以最小的性能开销在各个维度上提高了GCM的安全性。

重要提示： AES-GEM的当前设计尚未准备好用于生产，因为一些细节可能会在未来发生变化。要理解当前设计，让我们首先了解AES-GCM的不足之处，然后讨论如何用GEM做得更好。

AES的工作原理

在深入之前，对一些读者来说，解释本博客文章中使用的术语和概念可能会有所帮助。

AES（高级加密标准）是一种广泛用于加密信息的分组密码。它支持多种密钥大小（128位、192位和256位密钥），但始终在128位分组上操作。AES是Rijndael分组密码系列的标准化形式。Rijndael支持除128位以外的其他分组大小，但只有128位分组被NIST标准化。现代处理器提供了专用的硬件指令来加速AES操作，但AES密钥调度仍然可能对性能产生负面影响。

ECB（电子密码本）模式是没有分组密码操作模式的情况。它涉及直接对数据分组计算分组密码。ECB模式不是语义安全的，正如许多密码学家所证明的那样。为了提高安全性，像AES这样的分组密码通常与操作模式一起使用。（如果不是，几乎肯定应该这样做。如果您认为您正在使用ECB加密敏感数据，请联系我们的密码学团队。）

CTR（计数器模式）是一种分组密码的操作模式，其中递增的值序列用分组密码加密以产生伪随机密钥流。要加密数据，只需将每个明文字节与每个对应的密钥流字节进行XOR计算。

GCM（伽罗瓦/计数器模式）是一种提供认证加密的分组密码操作模式。它是密码学家称为AEAD模式的东西：带有关联数据的认证加密。GCM可以为敏感数据提供机密性，并为敏感和公共数据提供完整性。

AEAD模式对于设计密码系统非常重要，这些系统能够抵抗试图改变加密数据以研究系统行为，希望获得对密码分析有用的信息的攻击者。

GCM是用于加密明文的计数器模式（CTR）和用于认证密文（以及如果提供，额外的关联数据）的伽罗瓦域消息认证码（GMAC）的组合。GMAC用一个称为GHASH的函数定义，该函数是在认证数据上评估的多项式。GHASH的输出与加密分组的XOR产生最终的认证标签。称为H的认证密钥是通过加密一系列128位零位来计算的。

POLYVAL是GHASH的替代方案，用于AES-GCM-SIV。POLYVAL使用的不可约多项式是GHASH不可约多项式的反转。

许多密码模式（包括GCM和CTR）需要一个仅对每条消息使用一次的数字。这个永远不应重复的公共数字称为nonce。

最后，生日边界是概率论中的一个概念，表示一组随机值中碰撞的可能性。在密码学中，它意味着如果nonce是随机选择的，随着使用更多nonce，两个nonce碰撞的概率显著增加。对于具有96位nonce的AES-GCM，在大约2^32条消息之后，有1/2^32的机会发生nonce碰撞，这可能导致安全漏洞，例如伪造消息的能力。

当前AES-GCM的实际挑战

正如其他人所指出的，AES-GCM的最大挑战是AES只有128位的分组大小。这有两个主要后果：

1. 公共nonce和内部计数器的大小被限制在总共128位。实际上，nonce大小通常为96位，计数器为32位。如果选择更大的nonce，它会被哈希到适当的大小，这对安全性几乎没有改善。如果您曾经重用nonce，您会泄漏认证子密钥，因此可以无限期地伪造消息。
2. 在相同密钥下加密超过一定数量的分组后，攻击者可以以显著概率区分密文和随机字节。

当您理解我们处理的是2的幂时，96位的nonce空间可能听起来很多，但如果您随机选择nonce，您只能加密2^32条消息，然后有2^-32的碰撞概率。使用具有更大分组大小的密码可以缓解这个痛点，但这不是修复它的唯一方法。

AES分组大小并不是AES-GCM在实践中唯一的问题。正如Niels Ferguson在2005年指出的，对短标签的成功伪造揭示了认证子密钥。

此外，我们还了解到AES-GCM有一个意外的属性，即多个密钥可以解密相同的密文+认证标签。其发现者将这个问题称为“隐形蝾螈”，因为它允许他们从加密消息应用程序的滥用报告工具中隐藏蝾螈的图片。在使用AES-GCM的协议中缓解隐形蝾螈需要对使用的密钥进行某种单向承诺。

最后，AES-GCM中单条消息的最大明文长度相对较小：略低于64 GiB。为了应对这个最大长度，软件通常将更大的消息分解为适合此长度约束的较短帧。这导致生日边界前的有限nonce空间比如果容忍更长的消息时更快地被用完。

介绍AES-GEM

我们的提案，伽罗瓦扩展模式，是GCM（伽罗瓦/计数器模式）的修改，目前解决了大多数这些弱点。然而，关于我们想要采用哪种策略来缓解最后一个痛点，仍然有一个悬而未决的问题，我稍后会解释。

在高层次上，我们提出了两种变体：AES-128-GEM和AES-256-GEM。我们还使用标准AEAD接口指定了两种AEAD构造。

AES-128-GEM
密钥长度：128位
子密钥长度：128位
Nonce长度：192位
最大明文长度：2^61 – 1字节
最大AAD长度：2^61 – 1字节
标签长度：48字节（AEAD）或16字节（无承诺）

AES-256-GEM
密钥长度：256位
子密钥长度：256位
Nonce长度：256位
最大明文长度：2^61 – 1字节
最大AAD长度：2^61 – 1字节
标签长度：48字节（AEAD）或16字节（无承诺）

从GCM到GEM的道路

如果您从AES-GCM的现有设计开始并进行以下更改，您将到达GEM的当前草案。

Nonce扩展
首先，我们需要一个更长的nonce，我们将在下一步中用于子密钥派生。

对于256位密钥，256位nonce是一个很好的整数。对于128位密钥，我们最终需要192位。

在任何一种情况下，最右边的64位将保留用于实际的基础加密。剩余的位（对于AES-256为192位，对于AES-128为128位）将用于子密钥派生。

这使我们能够分摊密钥派生的成本，并在多条消息上设置AES密钥调度，前提是nonce和密钥的前（n – 64）位相同。

子密钥派生
使用AES进行密钥派生有多种策略。在Real World Cryptography 2024上，Shay Gueron介绍了DNDK-GCM，它使用了一个有趣的构造来实现子密钥派生。

我们希望保持简单和易于理解。因此，我们将密钥派生策略基于CBC-MAC，因为CMAC已经是FIPS批准的MAC（即用于AES-CCM）。

在AES-256的情况下，我们使用两个CBC-MAC输出来派生256位子密钥。然而，这种方法有一个微妙恼人的属性：两半永远不会产生相同的输出，因此严格来说，可能的输出少于2^256。

在GEM的两种变体中，我们借用了Salsa20设计中的一个技巧：将输出与输入密钥进行XOR，以确保子密钥对于任何不知道输入密钥的攻击者来说与均匀随机无法区分。如果您不知道这个密钥，输出与适当长度的随机密钥无法区分。

支持更长的消息
我们需要64位剩余nonce而不是GCM典型的96位的原因是我们的内部计数器大小不是32位长。相反，它是64位长。

否则，如当前所写，GEM的行为与您对GCM的期望相同：它使用计数器模式进行批量数据加密。让我们暂时搁置这一点，稍后再讨论。

改进的认证安全性
我们现有的设计AES-GCM以以下方式构建：

1. 通过用密钥加密全清零分组来派生认证子密钥H。
2. 计算密文、关联数据和包含两个段长度（以位为单位）的分组的GHASH()。
3. 将步骤2的输出与计数器分组的AES-CTR加密进行XOR。

我们的设计大致相同，但有一个重要的调整：

1. 通过用子密钥加密全置位分组来派生认证子密钥H。
2. 计算密文、关联数据和包含两个段长度（以位为单位）的分组的GHASH()。
3. 使用输入密钥通过AES-ECB加密步骤2的输出。
4. 将步骤3的输出与计数器分组的AES-CTR加密进行XOR。

步骤3直接解决了Niels Ferguson在2005年确定的AES-GCM的弱点。其他更改是实施细节。

这种调整为短标签提供了更好的安全性，因为原始GHASH输出位的AES加密是一种非线性变换，没有密钥无法反转。我们使用输入密钥而不是子密钥，因为唯一其他使用输入密钥加密数据的地方（即子密钥派生）从未直接揭示。

密钥承诺
在我们解决GEM对隐形蝾螈式攻击的保护之前，我们需要分析设计中的其他一些微妙之处。

GCM和GEM的最终分组中的组件长度都以位而不是字节表示，并且每个都限制在2^64。这意味着，即使GEM由于其内部计数器理论上允许每条消息最多2^64个分组（或2^68字节）的明文，我们也必须调整最终的GHASH步骤以适应这种额外的开销。

相反，内部计数器的不可达值保留用于密码的内部使用。具体来说，以0x02000000 00000000到0xFFFFFFFF FFFFFFFF结尾的内部计数器值在遵守明文2^61 – 1字节限制时无法达到。

全置位分组（0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF）已经在GEM中用于认证子密钥，而64位尾随nonce + 0xFFFFFFFF 0xFFFFFFFE用于计数器分组，用于最终认证标签计算。

为了提供密钥承诺，接下来的两个分组，nonce + 0xFFFFFFFF 0xFFFFFFFC和0xFFFFFFFF 0xFFFFFFFD将作为密钥和nonce的承诺值。

我们指定两个分组，因为在这里使用一个AES分组是不够的。考虑AES-256的情况，它有256位密钥和128位分组：根据鸽巢原理，我们期望有2^128个不同的密钥将给定的固定明文值映射到固定的密文值。因此，单个分组不足以进行承诺。然而，对于两个连续的分组，假设分组密码是安全的，不需要这样的鸽巢考虑。

通过这种方式，我们可以快速生成给定密钥和nonce的承诺值。

在AEAD接口中，承诺附加到认证标签。在解密消息时，两者都必须与它们的重新计算值进行比较，以恒定时间进行。

AES-GEM的性能特征

尽管我们已经解决了GCM的大多数痛点，但GEM的实际性能影响是最小的。

AES-256-GEM：
密钥派生：四个额外的AES加密分组，一些XOR，一个额外的密钥调度
认证：一个额外的AES加密分组
密钥承诺：两个额外的AES加密分组

AES-128-GEM：
密钥派生：两个额外的AES加密分组，一些XOR，一个额外的密钥调度
认证：一个额外的AES加密分组
密钥承诺：两个额外的AES加密分组

由于如今AES由于硬件加速非常快，这种性能影响在除最性能敏感的应用之外的所有应用中应该几乎不被注意。在这些情况下，如果派生子密钥被缓存，密钥派生性能成本可以在最多2^32条不同消息上分摊。

完善AES-GEM

当前GEM草案没有充分解决一个最终问题，但我们希望在NIST研讨会上讨论这个问题，并肯定会在最终设计中解决它。

尽管我们的草案GEM构造允许比GCM更长的消息，但AES分组大小使其按原样使用有风险。主要担忧是加密非常长的消息会给攻击者带来显著优势，以区分AES-GEM密文和随机字节序列。（这是亚马逊2024年论文中提出的担忧之一。）

有几种方法我们可以完善GEM以解决这个弱点，这些方法具有不同的性能特征和权衡。

宽分组PRP
多年来，许多密码设计使用宽分组PRP，例如XTS模式中的AES，以安全地加密超过AES分组大小通常允许的范围。由于XTS广泛用于磁盘加密，这种方法可能会被证明是安全的。

然而，XTS模式目前除了磁盘加密之外没有标准化用于其他用例。

分层密钥派生
如果我们不使用子密钥直接，而是使用内部计数器的高32位从保留的nonce空间中选择不同的值，加密它，并每2^36字节派生一个新的子密钥，会怎么样？然后，我们仅使用此子密钥加密计数器的剩余32位，这与AES-GCM几十年来所做的类似。

这种子子密钥派生可以类似于密钥承诺构建：

• 对于AES-256-GEM，加密从保留nonce空间派生的32字节，并将其用作实际的CTR密钥。
• 对于AES-128-GEM，加密从保留nonce空间派生的16字节（但与AES-256-GEM选择的不同的nonce空间），并将其用作实际的基础CTR密钥。

这是一个有吸引力的选项，原因有多种。最重要的是，这种策略将以非常直接的方式规避PRP区分器问题。它也不依赖于任何非标准设计（如XTS模式）。您可以用FIPS批准的组件构建整个东西，就像我们对AES-GEM的其余草案设计所做的那样。

缺点？这种方法确实每2^36字节明文产生另一个密钥调度。这可能仍然很好地分摊，但值得记住。

具有分层密钥派生的AES-GEM的总性能成本

AES-256-GEM：
密钥派生：四个额外的AES加密分组，一些XOR，一个额外的密钥调度
每2^36字节明文的额外密钥派生：两个额外的AES加密分组，一个额外的密钥调度
认证：一个额外的AES加密分组
密钥承诺：两个额外的AES加密分组
1 GB明文的额外总开销：七个AES-256分组，两个额外的AES-256密钥调度
1 TB明文的额外总开销：37个AES-256分组，17个额外的AES-256密钥调度

AES-128-GEM：
密钥派生：两个额外的AES加密分组，一些XOR，一个额外的密钥调度
每2^36字节明文的额外密钥派生：一个额外的AES加密分组，一个额外的密钥调度
认证：一个额外的AES加密分组
密钥承诺：两个额外的AES加密分组
1 GB明文的额外总开销：五个AES-128分组，两个额外的AES-128密钥调度
1 TB明文的额外总开销：21个AES-128分组，17个额外的AES-128密钥调度

其他想法
可能还有另一个我们尚未想象的选项。找到最佳权衡，特别是在考虑硬件设计时，是我们在NIST研讨会上介绍GEM的原因之一。

切割GEM

IETF的CFRG目前正在讨论一个RFC草案，用于AES-GCM的修改变体，该变体对短标签是安全的，称为GCM-SST。他们的设计出于性能原因使用POLYVAL而不是GHASH，并使用第二个认证密钥（Q）和第二个POLYVAL，所有这些都XOR在一起。

不出所料，这种额外的XOR并不能显著保护AES-GCM中短标签的弱点（尽管它确实使通常的攻击更昂贵）。

我们GEM的初始设计使用AES分组密码来置换GHASH输出，而不是简单地向多项式输出引入额外的线性操作（XOR）。

我们有兴趣与其他行业领导者合作，提供一种强调短标签用例（即WebRTC）的GEM变体。这种假设的变体（暂定CUT-GEM）可以使用POLYVAL代替GHASH，并使用基于时期的子密钥派生调度来减少每个数据包的性能损失。

我在哪里可以了解更多关于AES-GEM的信息？

关于AES-GEM的更多信息可在我们的GitHub上找到！

如果您喜欢这篇文章，请分享：
Twitter
LinkedIn
GitHub
Mastodon
Hacker News

页面内容

• AES的工作原理
• 当前AES-GCM的实际挑战
• 介绍AES-GEM
• 从GCM到GEM的道路
• AES-GEM的性能特征
• 完善AES-GEM
• 切割GEM
• 我在哪里可以了解更多关于AES-GEM的信息？

最近的帖子

• 使用Deptective调查您的依赖项
• 系好安全带，Buttercup，AIxCC的评分回合正在进行中！
• 使您的智能合约超越私钥风险
• Go解析器中意外的安全陷阱
• 我们从审查Silence Laboratories的首批DKLs23库中学到了什么

© 2025 Trail of Bits。
使用Hugo和Mainroad主题生成。