ChaCha核心的碰撞或第二個原像？

Daniel J. Bernstein 的ChaCha核心是Salsa20核心的演變。兩者都是 512 位位串集上的函式，被劃分為 16 個 32 位字。

我們可以為 ChaCha核心展示碰撞或第二原像（暗示前者）嗎？

澄清：我使用ChaCha核心（伯恩斯坦沒有正式定義）作為ChaCha的Salsa20核心（他在這裡定義）是Salsa20；因此包括使用 32 位加法組合多輪的輸入和輸出。我不是在詢問與 ChaCha 流密碼（哪個密鑰流生成器使用 ChaCha 核心）的輸出的衝突。

---

Salsa20 核心具有易於驗證的特性，即如果我們切換輸入的每個 32 位字的最左邊位，則輸出不會改變，這使得展示第二個原像（因此發生衝突）變得微不足道。這些碰撞或第二個原像在 Bernstein 提出的 Salsa20（或 ChaCha）核心的使用中不是問題，因為核心函式的足夠輸入被固定為任意值，它可以防止（據我們所知）出現碰撞和第二個-與這些添加的約束匹配的原像。因此，這個問題更多是出於好奇。

ChaCha 和 Salsa20 核心表現出一些其他隨機函式不會的特性，比如在零處靜止，或者當所有輸入詞都相同時，輸出詞之間具有顯著的同一性。這些也不是問題，只是故意設計決定的結果，即把“ nothing-up-my-sleeves numbers ”排除在核心功能之外，以便於對其進行分析。

更新：也許我的一些好奇心真的來自於短暫地製造（在scrypt中使用 Salsa20 核心的背景下）非常混亂的罪魁禍首 Bernstein 指出：

我最初將 Salsa20 核心介紹為“Salsa20 雜湊函式”，但這個術語讓那些認為“雜湊函式”意味著“抗碰撞壓縮函式”的人感到困惑。Salsa20 芯不壓縮，也不抗碰撞。如果您想要抗碰撞壓縮功能，請查看 Rumba20。（我不知道同一個人對 FNV 雜湊函式、完美雜湊函式、通用雜湊函式等有何看法）

---

以下是 C99 中的兩個核心功能；我們正在尋找不同的值，in以使對應out的值相同。

#define CHACHA  1   // 1 for ChaCha, 0 for Salsa20
#define ROUNDS  8   // number of rounds, must be even; standard values are 20, 12, 8

#include <stdint.h> // for uint32_t

// 32-bit left rotation of v by n bits, with n in range [1..31]
#define ROTL(v,n) ((uint32_t)(v)<<(n) | (uint32_t)(v)>>(32-n))

// ChaCha or Salsa20 core, parameterized by CHACHA and ROUNDS
void djbcore(uint32_t out[16], const uint32_t in[16]) {
  int i;
  uint32_t x[16];
  for (i = 0; i<16; ++i) x[i] = in[i];
  for (i = 0; i<ROUNDS/2; ++i) { // each loop does 2 rounds
       uint32_t t;
#if CHACHA // compiled for ChaCha
#define DJBQ(a,b,c,d) /* quarter round for ChaCha */ \
 t=(x[a]+=x[b])^x[d]; x[d]=ROTL(t,16); t=(x[c]+=x[d])^x[b]; x[b]=ROTL(t,12); \
 t=(x[a]+=x[b])^x[d]; x[d]=ROTL(t, 8); t=(x[c]+=x[d])^x[b]; x[b]=ROTL(t, 7);
       DJBQ( 0, 4, 8,12) DJBQ( 1, 5, 9,13) DJBQ( 2, 6,10,14) DJBQ( 3, 7,11,15)   
       DJBQ( 0, 5,10,15) DJBQ( 1, 6,11,12) DJBQ( 2, 7, 8,13) DJBQ( 3, 4, 9,14)
#else // compiled for Salsa20
#define DJBQ(a,b,c,d) /* quarter round for Salsa20 */ \
 t=x[a]+x[d]; x[b]^=ROTL(t, 7); t=x[b]+x[a]; x[c]^=ROTL(t, 9); \
 t=x[c]+x[b]; x[d]^=ROTL(t,13); t=x[d]+x[c]; x[a]^=ROTL(t,18);
       DJBQ( 0, 4, 8,12) DJBQ( 5, 9,13, 1) DJBQ(10,14, 2, 6) DJBQ(15, 3, 7,11)
       DJBQ( 0, 1, 2, 3) DJBQ( 5, 6, 7, 4) DJBQ(10,11, 8, 9) DJBQ(15,12,13,14)
#endif
  }
  for (i = 0;i < 16;++i) out[i] = x[i] + in[i];
}

我們能否為 ChaCha 核心展示碰撞或第二原像（暗示前者）？

不，可能不會。

Salsa20 和 ChaCha 核心都包含大量的“四分之一回合”，每個回合都是可逆的和雙射的。兩個核心都不是雙射（因此可能發生衝突）的唯一原因是最終將輸入元素添加到狀態中。

使用 Salsa20 翻轉高位有效，因為它不會影響四分之一輪方程的右側：

b ^= (a+d) <<< 7;
c ^= (b+a) <<< 9;
d ^= (c+b) <<< 13;
a ^= (d+c) <<< 18;

因此，翻轉所有高位會在所有輪次中翻轉它們，並通過添加輸入數據來抵消。

ChaCha 四分之一回合沒有那麼簡單的對稱性：

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

不同的單詞受到位翻轉和不同類型操作的影響的次數不同，因此沒有一個簡單的變化會在四分之一輪中保持不變。發現碰撞可能很難。

我意識到這不是證據，只是一種揮手的理由。

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