The fastest known attack against the Salsa20 family of stream ciphers requires 2137 simple operations against Salsa20/7, or 2244 against Salsa20/8. The 8-round version encrypts data at 1.88 cycles-per-byte on a Core2Duo, which is already extremely fast. As there's no real key schedule, cutting this down to two rounds should bring the speed up to 0.47 cycles-per-byte.

ChaCha is based on the Salsa core, but improves diffusion per round (quite significantly, as an attack taking 232 operations on Salsa20/6 instead takes 2127.5 operations on ChaCha6). The speed on the same CPU is equivalent. This is as fast as XorShift128+ (0.48 cycles-per-byte on Kaby Lake). Even worse for XorShift128+, the lowest bit is an LFSR, which may not be ideal for certain use cases such as Monte Carlo simulations.

This leads me to wonder, in situations where cryptographic security is not needed, could two-round ChaCha be used in place of another, fast PRNG? Would the output be indistinguishable from random data, sans cryptographic attacks?


1 Answer 1


As cypherfox had correctly pointed out during our chat, two rounds is not enough to reliably diffuse a single changed bit throughout the entire output.

My question appears to have been answered directly by Bernstein's page on diffusion for Salsa20 (note that ChaCha has better diffusion).

Quoting https://cr.yp.to/snuffle/diffusion.html

The following pictures show how quickly changes in one byte of Salsa20 input spread through the entire Salsa20 array. Here's a typical Salsa20 input array, with a superposition of 256 possibilities for the first byte in the third row:


After one round:

First round

After two rounds:

Second round

After three rounds:

Third round

After four rounds:

Fourth round

Additionally, the paper on Salsa20's security gives an example of diffusion:

Consider computing the second block of the Salsa20 stream cipher with nonce 0 and key (1,2,3,...,32). Rather than displaying the arrays produced by the second-block computation, this section displays the xor between those arrays and the corresponding first-block arrays, to emphasize the "active" bits—the bits where the computations differ.

The Salsa20 hash function starts with a 4×4 input array who's only difference from the first block is the different block counter, as shown by the following xor:


By the end of the first round, the difference has propagated to two other entries in the same column:


At this point there are still just a few active bits. The difference depends on a few carries but is still highly predictable.

The second round then propagates the difference across columns:


By the end of the third round, every word has been affected:


A substantial fraction of the bits are now active, although two words still have stretches of bits that were not (and were unlikely to be) active.

By the end of the fourth round, those last two stretches of inactivity have been eliminated:


That's just 4 out of the 20 rounds in Salsa20. In every subsequent round, there are hundreds of active bits, for a total of more than 4000 active bits. Each of those 4000 active bits interacts with carries in a random-looking way, producing random-looking differences, not shown here.

Clearly, no less than 4 rounds can be used to safely achieve full diffusion. At this point, Salsa20/4 is no longer competitive with other fast PRNG alternatives. I'll additionally update my answer with the results from Dieharder tests later, when I have time. I will also test ChaCha.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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