Can reduced-round ChaCha be used as non-cryptographic fast PRNG to produce output indistinguishable from random data?

Question

The fastest known attack against the Salsa20 family of stream ciphers requires 2¹³⁷ simple operations against Salsa20/7, or 2²⁴⁴ 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 2³² operations on Salsa20/6 instead takes 2^127.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?

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:

After two rounds:

After three rounds:

After four rounds:

…

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:

0x00000000,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000

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

0x80040001,0x00000000,0x00000000,0x00000000
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00000000,0x00000000,0x00000000
0x0000e000,0x00000000,0x00000000,0x00000000

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:

0xedc5e0a9,0x020000c0,0x381f830c,0x304888dc
0x00000000,0x00000000,0x00000000,0x00000000
0x00000001,0x00006000,0x800c0001,0x00000000
0x0000e000,0x01c00000,0x040000d8,0x01200f00

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

0x39545d5e,0x0cc160d8,0x301fb030,0xa05208dc
0xa240cc8b,0x24e0120c,0x2a030dc7,0xabeeb94e
0x39ea409b,0x0000000f,0xcf3bb828,0x1c205f6d
0xc6612ba5,0x01c06a00,0x02000018,0x6745c36b

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:

0xf5eebb6a,0x79a3e194,0x52e3644f,0x28fc33dd
0xcbfe2c2e,0xa0ce9f57,0xfa23cf02,0x2f549d35
0x2b1af315,0x7af4976b,0xa100a15f,0x86f420f1
0x2900cc14,0x8dcbf124,0x90611242,0x61fdabbe

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.