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];
}
…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:18A 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