重用密鑰和隨機數時對Poly1305的偽造攻擊

**簡介：**我試圖找出重用一次性密鑰是如何危害自身的，但只發現它完全破壞了加密的資訊，它到處都寫著。但是由於沒有指定重用或恢復密鑰的方法，我不太明白它是如何完成的，即使給出了明文和標籤。

**問題：**我們有幾條消息及其標籤，使用純 Poly1305 加密，使用相同的密鑰（使用 python 的Poly1305from chacha20poly1305，實現程式碼生成）沒有 AES 和 ChaCha，從程式碼和規範中看起來。

Poly1305 的輸入是： 256 位一次性密鑰；任意長度的消息

我想重用 Poly1305 密鑰來簽署自定義消息並因此偽造它。我應該怎麼做才能在我的自定義消息中重複使用相同的密鑰而不知道它，或者如果可能的話，找到密鑰？

**例如，**您有以下數據，相同的密鑰被使用了 3 次（十六進制數據：十六進制標記）：

Data: e8962f8dada53f589eada744bf3f9bb298be47ebd3416a59a13a709d1bf6fb4d
Tag:  825f51bb7b0f05990f03998c63a51f08

Data: 6e05652fe6a6985c1fed6604f95b133fe7a4a9f95313a8ad15d995195528efad
Tag:  53cc694570e89ec66350b4d7877ea58a

Data: 46a683f0a164bf6e19ee0b05f4c65f1f7b1d6ec454fe0e79ec4debfb22da36c1
Tag:  cba1048b9ee15929a16f0cfe5f4547b1

在Poly1305

• 16 字節 AES 密鑰 k
• 16 字節附加密鑰 r
• 16 字節 $ n $ 隨機數

是必須的。使用者的義務

• 任何使用 Poly1305-AES 的協議都必須確保密鑰的不可預測性 $ (k, r) $ .
• 發件人絕不能對兩條不同的消息使用相同的隨機數

明顯的攻擊是破壞機密性的拖拽，這並不意味著加密密鑰被洩露。事實並非如此。

Poly1305 的隨機數計算為 $ nonce = \operatorname{AES}_k(n) $

$$ \operatorname{Poly1305}( r, m, \operatorname{AES}_k(n)) $$

這 $ r $ 實際上 $ \in { 2^{106} } $ 不是完整的 128 位。

Poly1305 認證可以簡化為

$$ (((c_1 r^q + c_2 r^{ q−1} + \cdots + c_q r^1 ) \bmod 2^{130} - 5) + \operatorname{AES}_k(n)) \bmod 2^{128} $$在哪裡 $ c_i $ 是編碼的消息 $ m $ , $ r_i $ 是個 $ r $ 以字節為單位。

操作案例

如果我們省略 $ \operatorname{AES}_k(n) $ 對於純Poly1305，則方程變為

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

現在，為了簡單起見，只考慮一個 16 字節的小消息，使用相同的密鑰和隨機數。那麼while循環中的for循環只會工作一次。

void poly1305_gmpxx(unsigned char *out,
   const unsigned char *r,
   const unsigned char *s,
   const unsigned char *m,unsigned int l)
 {
   unsigned int j;
   mpz_class rbar = 0;

   for (j = 0;j < 16;++j)
       rbar += ((mpz_class) r[j]) << (8 * j);

   mpz_class h = 0;
   mpz_class p = (((mpz_class) 1) << 130) - 5
   
   while (l > 0) {
       mpz_class c = 0;
       for (j = 0;(j < 16) && (j < l);++j)
           c += ((mpz_class) m[j]) << (8 * j);
       c += ((mpz_class) 1) << (8 * j);
       m += j; l -= j;
       h = ((h + c) * rbar) % p;
   }   
   //Omitted since Pure Poly!
   //for (j = 0;j < 16;++j)
   //    h += ((mpz_class) s[j]) << (8 * j);

   for (j = 0;j < 16;++j) {
       mpz_class c = h % 256;
       h >>= 8;
       out[j] = c.get_ui();
   }
}

那麼我們有

mpz_class h = 0;
mpz_class c = 0;
for (j = 0; j < 16 ;++j)
   c += ((mpz_class) m[j]) << (8 * j);

h = (c * rbar) % p;

for (j = 0;j < 16;++j) {
   mpz_class c = h % 256;
   h >>= 8;
   out[j] = c.get_ui();
}

最後一個循環實際上輸出了 16 個字節的 $ h $ ， 自從 $ p = 2^{130}-5 $ 略小於模數。

**提示：**玩弄資訊，尤其是上半部分。

注意：rfc8439取代了 RFC 7539

本文件的前身 RFC 7539 旨在作為穩定的參考和實施指南。它是加密論壇研究小組 (CFRG) 的產品。本文件合併了針對 RFC 7539 送出的勘誤表，並在“安全注意事項”部分添加了一些文本。

我想重用 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 $ 是編碼的消息 $ m $ , $ r_i $ 是個 $ r $ 以字節為單位（和 $ c_0 $ 作為隨機數和密鑰的函式，可能使用 AES 或 ChaCha20）。

我們沒有關於價值的資訊 $ c_0 $ ，所以標籤沒有給我們任何關於內部多項式可能評估的資訊。但是，如果我們有兩條帶有相同標籤和密鑰的 MAC 消息，它們將共享 $ 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 $ 其中一個為零。

那麼問題是：我們能否有效地在有限域上找到多項式的零點。答案是肯定的；有關已知方法的調查，請參閱此 Wikipedia 文章（Cantor-Zassenhaus 算法在這種情況下看起來是最實用的）。

從我的回答中，應該很容易看出為什麼省略 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 $ 值，因此不需要第二條消息來消除它。攻擊可以直接使用這個多項式進行。

引用自：https://crypto.stackexchange.com/questions/83629