19
$\begingroup$

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];
}
$\endgroup$
  • 2
    $\begingroup$ Here's the thing about ChaCha. It's not a hash function. Well, technically it is, but it doesn't take a message and add it to an internal state to assign a unique value to a given message. Issues with preimage and collisions are not significant, as long as the the sender and recipient are both trusted parties. Rumba does take Salsa and uses it as a compression function, but has shown to be resistant to collision attacks after four rounds. The problem isn't really one. RC4 isn't a hash function either. $\endgroup$ – user3201068 Jun 21 '15 at 20:22
  • $\begingroup$ @user3201068: indeed. I have now emphasized the (pre-existing) observation that a collision or second preimage for the Chacha core would not be a defect. $\endgroup$ – fgrieu Jun 21 '15 at 20:56
  • 1
    $\begingroup$ …Bernstein notes… I've read something from Bernstein himself about that a few months ago. The “Bernstein hashing” confusion (at least, the one I had – which seems similar to yours) roots in the fact Bernstein thinks of “hashing” as mixing/shuffling. Years later he realized that it causes confusion as “hash” algos exist too. He still holds on to his “to hash means to mix” mantra (probably an ego thing), but meanwhile adds that he´s not talking about “hashes“ as we (crypto community) know them. Can´t remember title right now, but if it makes sense to you, I could try to dig up what I´ve read. $\endgroup$ – e-sushi Jul 24 '15 at 2:18
  • $\begingroup$ That was in the DJB paper responding to the "On the Salsa20 core function" paper. A scathing response. $\endgroup$ – Thomas M. DuBuisson Jul 24 '15 at 2:26
  • 1
    $\begingroup$ @ThomasM.DuBuisson Could well be the one… (I´m on mobile, enjoying the downsides of German train-transportation right now. I´ld hate to try checking PDFs with the wanky connection I´ve got atm.) Personally, I can only say that when reading Bernsteins publications, I tend to replace “hash” with “mixing function” in my brain and all starts to make sense. A scathing response. True. At least we can claim we always knew Bernstein isn´t what one could call an “easy character”. OTOH, I enjoyed reading his travel experiences. $\endgroup$ – e-sushi Jul 24 '15 at 2:30
6
+200
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nitpick: the final addition in the core makes it not easily invertible. We know how to make public, easily computable functions over a 512-bit domain that are demonstrably bijective, but quite computationally hard to invert for arbitrary output (admittedly, building such function using only ARX operations requires a lot of these). $\endgroup$ – fgrieu Jul 24 '15 at 6:37
  • $\begingroup$ @fgrieu, I was sloppily using "invertible" as a synonym for bijective there. Will fix. $\endgroup$ – otus Jul 24 '15 at 6:37
  • $\begingroup$ If we could demonstrate that the ChaCha core is not a bijection (other than for 0 rounds, where that result is trivial), it would be something. I conjecture that's feasible for few rounds (like 2), but becomes infeasible for enough rounds to reach security (like 8 or more). The final addition destroys the argument of bijection, but lack of argument for a proposition does not prove that it does not hold (much less provide a counterexample). $\endgroup$ – fgrieu Jul 24 '15 at 12:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, my question is not about ChaCha (the cipher). I have now stated that explicitly. $\;$ I agree a lot about your praise of ChaCha (the cipher), as should be apparent in the info for the ChaCha tag. $\endgroup$ – fgrieu Jun 22 '15 at 10:03
  • $\begingroup$ @fgrieu IC. In which case Blake uses a large table of constants to eliminate some properties of ChaCha. No one really uses ChaCha round function without minor modification for anything other than the hash. $\endgroup$ – user3201068 Jun 22 '15 at 18:26
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @fgrieu Sorry, I have a public slice of the presentation I ment to link github.com/TomMD/cryptol-slides. In that presentation and associated SAW code I show Cryptol/SAW proving the theorems from the 'On the Salsa20 Core Function' paper. $\endgroup$ – Thomas M. DuBuisson Jul 24 '15 at 1:51
  • $\begingroup$ @fgrieu The double round function is as defined by DJB in the specification and it does not have any collisions. To understand the theorems I suggest you read the related paper. Read further to see the collisions, especially see "theorem7". $\endgroup$ – Thomas M. DuBuisson Jul 24 '15 at 2:57
  • $\begingroup$ In case it needs stated explicitly: ChaChaTwoRounds is like "ChaCha2" to get ChaCha20 we run ChaChaTwoRounds 10 times, as you can see in the source. This is what we are doing with ChaCha _ 10, the proofs for which have yet to terminate but the result should be obvious corollary for the two round case - there are no collisions. $\endgroup$ – Thomas M. DuBuisson Jul 24 '15 at 3:00
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Thomas M. DuBuisson Jul 24 '15 at 4:24
  • 3
    $\begingroup$ Summarizing the discussion: the theorem prover proved that 2 rounds of ChaCha can't collide; this is not directly related to the ChaCha core with 2 rounds colliding. $\;$ It did not answer on if the ChaCha core with 10x2 rounds collides. In fact, if an automated tool could prove or disprove that the ChaCha core with only 2 rounds has collisions, that would be even more an achievement than proving that for the Salsa20 core. $\;$ There are strong heuristic arguments that there are collisions for the ChaCha core using enough rounds for security, we just do not know any (for now). $\endgroup$ – fgrieu Jul 24 '15 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.