Collision or second preimage for the ChaCha core? Daniel J. Bernstein's ChaCha core is an evolution of the Salsa20 core. Both are functions over the set of 512-bit bitstrings, partitioned as sixteen 32-bit words.

Can we exhibit collisions, or second-preimages (with implies the former), for the ChaCha core?

Clarifications: I'm using ChaCha core (which is not formally defined by Bernstein) as being to ChaCha what Salsa20 core (that he defines here) is to Salsa20; thus including combining input and output of a number of rounds using 32-bit additions. I'm not asking about collisions with the output of the ChaCha stream cipher (which keystream generator uses the ChaCha core).



The Salsa20 core has the easily verified property that if we toggle the leftmost bit of each 32-bit word of the input, the output does not change, making it trivial to exhibit second-preimages (thus collisions). These collisions or second preimages are not an issue in the uses of the Salsa20 (or ChaCha) core proposed by Bernstein, because enough input of the core function is fixed to arbitrary values that it prevents (as far as we know) exhibiting collisions and second-preimages matching these added constraints. The question is thus more out of curiosity than anything else.

ChaCha and Salsa20 cores exhibit some other properties that a random function would not, like being stationary at zero, or having remarkable identities between output words when all input words are identical. These are not an issue either, only a consequence of the deliberate design decision of putting the nothing-up-my-sleeves numbers out of the core function, in order to facilitate its analysis.

Update: Perhaps some of my curiosity really comes from briefly being culprit of making (in the context of the use of the Salsa20 core in scrypt) the very confusion Bernstein notes:


  I originally introduced the Salsa20 core as the "Salsa20 hash function," but this terminology turns out to confuse people who think that "hash function" means "collision-resistant compression function." The Salsa20 core does not compress and is not collision-resistant. If you want a collision-resistant compression function, look at Rumba20. (I wonder what the same people think of the FNV hash function, perfect hash functions, universal hash functions, etc.)




Here are both core functions in C99; we are seeking distinct values for in such that the corresponding out are identical.

#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 &lt;stdint.h&gt; // 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)&lt;&lt;(n) | (uint32_t)(v)&gt;&gt;(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&lt;16; ++i) x[i] = in[i];
   for (i = 0; i&lt;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 &lt; 16;++i) out[i] = x[i] + in[i];
}
Can we exhibit collisions, or second-preimages (with implies the former), for the ChaCha core? 


No, likely not.

The Salsa20 and ChaCha cores both consist of a large number of "quarter-rounds" each of which is invertible and bijective. The only reason neither core is a bijection (and thus can have collisions) is the final addition of the input elements into the state.

With Salsa20 flipping the high bits works because it doesn't affect the right side of the quarter-round equations:

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


Thus, flipping all the high bits flips them all the way through the rounds and is canceled out by the addition of the input data.

The ChaCha quarter-round doesn't have as simple symmetry:

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


Different words get affected a different number of times by a bit flip and by a different kind of operation at first, so there is no simple change that would be left untouched by a quarter-round. Finding collisions is probably hard.

I realize this isn't proof, just a sort of handwaving justification.