密钥和当前重用时对Poly1305的伪造攻击

Question

我试图找到重用一次性密钥的方法，但是只发现了它完全破坏了加密的信息，它到处写。但是，由于没有指定重用或恢复密钥的方法，所以我不太清楚它是如何实现的，即使提供了明文和标记。

问题:我们有几条消息及其标记，使用纯Poly1305加密，密钥相同(使用python的Poly1305从chacha20poly1305、实施代码生成)，而没有AES和ChaCha，正如代码和规范所显示的那样。

Poly1305的输入是:一个256位的一次性密钥；任意长度的消息。

我希望重用Poly1305密钥来签署自定义消息，从而伪造它。我应该做什么来重用相同的密钥，而不知道它在我的自定义消息或，如果可能的话，找到密钥？

例如，您获得了以下数据，相同的键被使用了3次(十六进制中的数据:十六进制中的标记)：

Data: e8962f8dada53f589eada744bf3f9bb298be47ebd3416a59a13a709d1bf6fb4d
Tag:  825f51bb7b0f05990f03998c63a51f08

Data: 6e05652fe6a6985c1fed6604f95b133fe7a4a9f95313a8ad15d995195528efad
Tag:  53cc694570e89ec66350b4d7877ea58a

Data: 46a683f0a164bf6e19ee0b05f4c65f1f7b1d6ec454fe0e79ec4debfb22da36c1
Tag:  cba1048b9ee15929a16f0cfe5f4547b1

Answer 1

我希望重用Poly1305密钥来签署自定义消息，从而伪造它。我应该做什么来重用相同的密钥，而不知道它在我的自定义消息或，如果可能的话，找到密钥？

我将直接告诉你，而不是给你一个提示。我还将告诉您，为什么没有AES/ChaCha20的Poly1305是不安全的，即使只使用了一次密钥。

正确的Poly1305被定义为(从kelaka的答案中窃取的文本)：

在tag = (((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + c_0) \bmod 2^{128}中，c_i's被编码为消息m，r_i是以字节为单位的r ( c_0是当前和密钥的函数，可能使用AES或ChaCha20)。

我们没有关于c_0值的信息，因此标签没有给我们任何关于内部多项式的计算结果的信息。Hoewver，如果我们有两个带有相同标签和密钥的消息，它们将共享c_0值。在这种情况下，我们可以做的是减去(模2^{128}两个标记值，这将给我们：

tag - tag' =

((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130}-5) \bmod 2^{128}

-((c'_1 r^q + c'_2 r^{ q−1} + \cdots + c'_q r^1 ) \bmod 2^{130}-5) \bmod 2^{128}

我们可以将其改写为：

tag - tag' + 2^{128}k =

(((c_1-c'_1) r^q + (c_2-c'_2) r^{ q−1} + \cdots + (c_q-c'_q) r^1 ) \bmod 2^{130}-5)

为了k \in \{-4,..., 4\}。

这给了我们9个多项式(对于k的各种可能值)，对于这些多项式，我们知道系数，并且我们知道，对于其中一个多项式，q的正确值是零。

问题是:我们能有效地找到有限域上多项式的零点吗？答案是肯定的；有关已知方法的调查，请参见这篇维基百科文章 (Cantor算法在此场景中看起来最实用)。

从我的回答中可以很容易地看出为什么省略AES/ChaCha20步骤是不安全的，因为攻击者可以用一条消息恢复q。

这种改进的Poly1305算法是：

tag = (((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5)) \bmod 2^{128}

正如您所看到的，我们已经删除了c_0值，因此不需要第二条消息来消除它。攻击可以直接进行这个多项式。