AES-GCM-SIV中的隐形火蜥蜴

到目前为止，许多人已经阅读了关于AES-GCM有趣特性的Insible Salamander论文，该特性允许攻击者构造一个密文，该密文将在两个不同的密钥下使用有效标签进行解密，前提是攻击者知道这两个密钥。在某种程度上，找到这样的属性并不太令人惊讶：AES-GCM被设计为一个AEAD，在AEAD定义中没有任何地方说明有权访问密钥的攻击者可以做什么，因为通常假设攻击者没有这种访问权限，因为任何Alice-Bob-message模型在这种情况下都是没有意义的。

我感兴趣的是，这个属性出现的次数比人们想象的要多，我现在在审查密码设计的工作中遇到过它好几次，对于现实世界的系统来说，它远不是一个鲜为人知的属性。这些系统的共同之处在于它们涉及三方：爱丽丝、鲍勃和特伦特。特伦特是鲍勃信任的第三方，他被允许读取消息并扫描它们，细节如何时和为什么取决于所讨论的密码系统。虽然特伦特和鲍勃在密文上达成了一致--比如因为特伦特把密文交给鲍勃，或者因为爱丽丝在密文上签了特伦特的签名--但爱丽丝可以选择给特伦特和博格不同的密钥。爱丽丝面临的挑战是拿出一个具有有效身份验证标签的密文，并且仍然可以解密为特伦特和鲍勃的不同消息。

在我深入研究如何为AES-GCM和AES-GCM-SIV构建看不见的火蜥蜴之前，先简单介绍一下如何防御这些问题。这里最简单的选择是将密钥的散列添加到密文中。这在技术上违反了不可区分性，因为密钥的身份被泄露，即攻击者现在知道消息使用了哪个密钥。如果需要不可区分，则使用IV作为散列的盐可以很好地工作，像HMAC-SHA-2(KEY=IV，MESSAGE=KEY)(也就是HKDF-EXPAND)这样的结构在这里工作得很好，只要注意这个密钥散列是否可以在任何其他上下文中使用即可。一般来说，它不应该这样做，因为密钥应该只用于AES-GCM/AES-GCM-SIV，但是现实世界中的系统有时会有奇怪的属性。

在缓解障碍的情况下，让我们来看看有趣的部分：构建信息。为了了解这些攻击的原因和方式，我们首先必须讨论\mathbb{F}_{2^{128}}以及AES-GCM和AES-GCM-SIV使用此字段构造各自标记的方式。作为有限域\mathbb{F}_{2^{128}}遵循通常的域公理，支持加法、乘法和除法。该字段的特征为2，这意味着加法只是XOR运算符，减法与加法的运算完全相同。乘法和除法稍微复杂一些，不在本文的讨论范围内，只要硬件支持某些指令集(无进位乘法)，就可以用非常快的算法实现乘法。除法算法使用欧几里得算法，在一个朴素的实现中最多需要256次乘法，所以虽然比其他操作慢，但仍然非常快。我将使用+进行加法运算，使用\cot进行乘法运算。最重要的警告是不要将这些运算与整数算术混淆。

接下来，转到AES-GCM。该AEAD是使用基于UHF的MAC进行认证的AEAD的相对简单的实现。我们的IV是12字节长，我们使用4字节计数器和CTR模式来加密消息。有点奇怪的特点是我们从2开始计数器，原因我们将在后面看到。对于身份验证，我们首先通过加密零块导出身份验证密钥H(这就是为什么我们不从零开始计数器的原因，否则零IV将是无效的)。现在，使用密文块、附加数据块(根据最后一个块需要用零填充)，并添加包含附加数据和密文大小的特殊长度块，我们得到一个块集合，我将所有这些块称为C_i。为了计算标签，我们现在计算多项式。

GHash(H，C，T)=C0\CDOT H^{n+1}+C1\CDOT H^{n}+\dots+C_{n-1}\CDOT H^2+C_n\CDOT H+T常量项，T是与计数器变量1相关的加密计数器块(这就是为什么我们在CTR模式中从2开始)。记住，在特征2+是异或，所以我们可以等价地说，我们计算不带常数项的多项式，然后用CTR模式加密它作为第一个块。

现在，我们如何让两个不同的明文在密文和标签上达成一致，我们首先选择两个密钥并产生相应的密钥流，选择明文以使密文一致(如果您想要两个有意义的明文，这部分是最困难的一步，您首先暴力破解前几个字节，以便

AES-GCM-SIV的实际IV主要用于导出每消息密钥。这意味着如果两条消息的IV不同，则加密和验证密钥都将是无关的，不能用来推断彼此的情况。

其中明文块P_i再次包含额外的数据和长度，并且为清楚起见已经剥离了一些额外的硬化和效率技巧。

我们以前的方法，首先创建密文，然后平衡以使标签清楚地一致，在这里不再起作用。密钥流和密文依赖于标签，所以如果我们想要找到火蜥蜴的机会，我们必须在进行任何计算之前修复标签。因此，在选择了T之后，我们在每个密钥下对其进行解密，以得到我们的多项式S_i=\Operatorname{AES}^{-1}(K_{E，I}，T)的结果。剩下的就是找到明文P_1，P_2，使得。

S_i=\sum_{j=0}^n P_{j，i}H_i^{n+1-j}给出了一个2n个未知数的线性方程组。但这并不是我们需要满足的所有约束，因为一旦我们平衡了标记，我们仍然需要加密这些明文。在这里，我们很幸运，一切都超过了特征2：CTR加密只是明文和加密计数器块C_i=\Operatorname{AES}(K_E，CB_i)+P_i的相加。说两个明文在两个不同的密钥下产生相同的密文正好满足了等式。

这就像标签的两个方程一样，是一个线性方程。最后，对于一个大小为n个块的明文，我们得到了2n个变量的n+2个线性方程。这意味着，在几乎所有的情况下，我们只需添加两个牺牲块，就可以构建一个看不见的火蜥蜴，但同样的警告是，这两个明文需要部分暴力强制。

我已经对此进行了测试，并编写了生成AES-GCM(Java)和AES-GCM-SIV(C++)火蜥蜴的代码。