将数据附加到使用流密码加密的认证密码中

Question

假设我们使用xSalsa20进行了Poly1305身份验证。如果X 是密文，则N是当前值，而H是身份验证标记，因此最终的密文是N || X || H ，然后给定密钥K，是否可以使用更多的数据扩展X ，而不对其进行解密，根据需要更新N和Y？(我不确定是否需要更改N。)

更清楚的说，X_m 是原始认证的密文。我想把纯文本数据A 附加到上面。我正在寻找一个实现X_n = Append(X_m, A, K) 这样的Decrypt(X_n, K) = Decrypt(X_m, K) \| A 的方案。

Salsa20是一个流密码，所以它产生一个CSPR密钥流，S ，然后密文变成X = S \oplus P ，其中P是明文。因此，我直觉地感觉，这应该比使用分组密码要容易得多。也许通过生成相同的密钥流，直到密文的大小，然后用密钥流的一部分加密新的数据。如果身份验证标记是从密文生成的，那么解密也是不必要的。另外，据我所见，在这样的方案中，现在并不是真正的重用。

这将如何转换成其他流密码，如XChaCha20-Poly1305？

Answer 1

如果X 是密文，则N是当前值，而H是身份验证标记，因此最终的密文是N \| X \| H ，然后给定密钥K，是否可以使用更多的数据扩展X ，而不对其进行解密，根据需要更新N和H？

对大多数计划来说，这是非常可能的，是的。

这包括两个部分:CPA安全加密功能和消息认证代码。

首先用于加密功能：

• 如果它是基于CTR的，这是没有问题的，因为一个简单的跳过计数器前的最后一个块的索引，以获得必要的关键流。AES-CTR包括在内，也包括(X)ChaCha和(X)Salsa，它们都是CTR模式下的PRF.
• 对于CBC，Aleksander已经有了答案:您解密最后一个块，继续在使用填充的地方填充它，并使用第二个到最后一个块作为IV。
• 对于CFB来说，这个故事应该和CBC差不多，但是由于它很少被使用，所以我没有研究细节。
• 对于OFB来说，由于它本质上计算S_i=E_k(S_{i-1})并使用S_i作为密钥流，如果您知道相应的明文，如果您不知道相应的明文，那么您也可以从最后一个充分使用的块中恢复状态，如果您不知道，那么您就不走运了，并且必须从开始时开始使用“现在”。

至于安全性方面的考虑:至少对于流模式，您永远不会重复使用密钥流，这样消息的保密性就会得到保护，但是当然，对手可以知道消息已经扩展了。

至于身份验证代码，这里是事情变得非常混乱的地方：

• 对于HMAC来说，这似乎不可能重新计算完整的MAC，即使知道密钥作为HMAC的最后一步是运行密钥，并通过一个不可逆的PRF减少整个消息的结果，这不允许从输出中恢复内部状态。
• 对于CCM的CBC-MAC，图像也同样严峻，因为它包含了起始的精确消息长度和依赖于此值的每个内部状态。
• 对于使用不可逆PRF (所以不是分组密码)的CBC，图像类似于HMAC，无法从输出恢复状态。

然而，这给我们留下了两类广泛使用的MAC:基于分组密码CBC的MAC和卡特-韦格曼的MAC，如Poly1305和GHASH。

• 对于基于CBC的方案，如果使用块密码而不对消息进行预处理，通常会对最后一个块进行特殊处理，无论是将一个特殊值XORing到最后一个消息块，还是使用不同的密钥再次加密密文。但是，如果您知道关键，这些转换都是可逆的。因此，您可以在最后一个块之前有效地恢复内部状态，并为最后一个块和更新重新计算MAC。
• 对于Carter来说，正如波乔所解释的那样，这有点复杂，并且可能与特殊的非危险的实现处理一起工作，但在原则上，这是可能的(尤其是GCM使用的GHASH )，当然，如果对手能够看到这两种密文，这是非常危险的。

请注意，在使用基于CBC的方案(如EAX)时，可以安全地执行此扩展，因为所使用的变量有适当的PRF，因此相关输入的输出与无键对手没有明显的关系。

Answer 2

嗯，不，你不能(不重新扫描整个密文)，而且你可能无论如何都不应该。

xSalsa20是简单的一半--它实际上处于计数器模式，因此很容易从xSalsa20中生成更多的比特，用于加密所附加的附加数据(而这些附加比特不会更改为以前的密文位)。

问题在于Poly1305一半；它将密文作为多项式系数(在GF(2^{130}-5)上)，然后计算该多项式对x的一个秘密值(然后添加一个秘密的非依赖因子)--如果它所做的就是这样的话，那么就很容易调整多项式结果以考虑额外的比特(方法是减去秘密常数项，必要时乘以x的幂，然后添加新位并返回秘密常量项)。然而，它做了一个进一步的步骤；它接受多项式的输出(这是0和2^{130}-6之间的一个值)，并取mod 2^{128}。这意味着，对于(几乎)任何标记值，多项式将计算出4个可能的值，这意味着扩展的多项式将需要4个可能的标记(因为这两个较高的位在乘以x后会修改较低的位)，而且您不知道它可能是哪一个(如果不从头开始重新计算多项式)。

现在，可以修改初始的Poly1305实现，以保存\bmod 2^{128}操作丢弃的两个上层位(泄漏这些位将不会给攻击者带来任何好处)；这将允许高效的增量更新。另一方面，这样做可能不是个好主意--如果对手同时看到两种密文(即原始版本和扩展版本，它们都使用相同的nonce)，那么他可以计算一个显式多项式，其中的秘密值x作为根--这使他能够很好地猜测x的值，这将允许他随意修改密文，而不会被检测到。

因为有了这个威胁，我相信每当你修改密文的时候，你真的想要改变现在的状态；这涉及到完全的解密和重新加密。