Collision or second preimage for the ChaCha core?

Question

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 <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];
}

Answer 1

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) <<< 7;
c ^= (b+a) <<< 9;
d ^= (c+b) <<< 13;
a ^= (d+c) <<< 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 <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 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.

Answer 2

I think I understand what you're asking now.

ChaCha is essentially a block cipher with no key schedule. This has an advantage, less SRAM required for constrained devices, and even for desktops, less cache calls ( https://stackoverflow.com/questions/10274355/cycles-cost-for-l1-cache-hit-vs-register-on-x86 ). Part of the reason why ChaCha manages to be as fast as the AES instruction set.

This does cause a minor issue though, key bits would theoretically be leaked out through a slide attack. Except to generate a slide pair, one needs to monitor essentially 2^256 (birthday bound) ChaCha encryptions and have a known plaintext for each one. Not feasible.

Even if ChaCha was a hypothetical ideal pseudorandom function, in which one initial state maps to a random final state of the same size, there's a substantial problem: a small fraction of final states map to two or more initial states because of the birthday problem, and the pigeonhole problem.

Obviously there would be a distinguishing attack against ChaCha. But for the reason why 128-bit block ciphers in counter mode aren't distinguished, one would need to observe 2^256 outputs to notice any bias.

While there are outputs that aren't possible for ChaCha, the vast number of outputs that are possible are difficult to guess.

I am not sure I covered everything, and so I would edit this post to include any suggestions from the comments if I think it is necessary.

Answer 3

The easiest, zero thought, way to get an answer to this question is to ask the computer. Using Dylan's cryptol implementation it is straight-forward to ask a question:

m1 != m2 ==> ChaChaCore m1 != ChaChaCore m2

That is, if inputs m1 and m2 are not equal then the ChaCha core function will not be equal either.

Cryptol doesn't (well, didn't) have an implication arrow so we just phrase the same question a little differently.

My original post asked the vastly easier question that omits the final 32-bit addition for a doubleround:

ChaCha20> :prove \m1 m2 -> m1 == m2 || ChaChaTwoRounds m1 != ChaChaTwoRounds m2
Q.E.D.

The real question, which includes this final add, doesn't terminate quickly:

:prove \m1 m2 -> m1 == m2 || ChaCha m1 10 + m1 != ChaCha m2 10 + m2

I'm still waiting on this one. Perhaps if I used SAW and added the first result as a lemma then the solution would go faster.