How should I interpret this note on diffusion of the internal state of a PRNG?

Question

This question is about Tyche, a non-cryptographic PRNG. While the PRNG is not cryptographic the analysis and this question surely is heavily involved with cryptography, so I think it's on-topic here.

In short, Tyche is a nonlinear PRNG based on the ChaCha quarter-round function. The state (4 words $a, b, c, d$) gets mixed using the $MIX$ function (which is basically the ChaCha quarter-round), and then a part of the state gets returned. This is the $MIX$ function in pseudocode:

MIX(a, b, c, d):
    a = a + b
    d = (d ^ a) <<< 16
    c = c + d
    b = (b ^ c) <<< 12
    a = a + b
    d = (d ^ a) <<< 8
    c = c + d
    b = (b ^ c) <<< 7

Later the authors propose a faster variant (due to instruction level parallelism), where the inverse of $MIX$ is used, $\textit{MIX-i}$:

MIX-i(a, b, c, d):
    b = (b >>>  7) ^ c; c = c - d
    d = (d >>>  8) ^ a; a = a - b
    b = (b >>> 12) ^ c; c = c - d
    d = (d >>> 16) ^ a; a = a - b

Then the authors note the following (emphasis mine):

The downside, however, is that $\textit{MIX-i}$ diffuses bits slower than $MIX$ does: for 1-bit differences in the internal state, 1 $MIX$ call averages 26 bit flipped bits, while $\textit{MIX-i}$ averages 8.

I don't exactly know how to interpret this note.

1. Why is this a downside?
2. Does this mean the quality of the PRNG is less?
3. By default the initial constant state (in $c$ and $d$) gets mixed with the seed (in $a$ and $b$) using 20 calls to $MIX$. Does it need more iterations to initialize the PRNG when using $\textit{MIX-i}$?
4. It surely can't affect period length since it's the inverse, right?

Answer 1

An ideal random permutation should flip 64 (out of 128) bits on average for each iteration, regardless of what the previous state was. So one thing you can take from this is that neither of those functions is (close to) ideal. That is not to say they can't still be useful; a non-cryptographic generator only needs to look good statistically, not withstand a powerful attacker. There are two things that help the generator have decent output:

• The mode of operation. We work in feedback mode, i.e., $x_{i+1} = f(x_i)$. This means that, on average, much more than 26 bits flip from one state to the other if one starts from an arbitrary state. Compare this with, for example, counter mode, where only one or two bits flip on average between iterations. My measurements indicate that in the counter mode case you need at least 5 iterations of MIX until you achieve comparable statistical quality that 1 iteration achieves in feedback mode. The downside is, of course, that feedback mode is not as parallelizable as counter mode.

• We only output 1 out of 4 words per iteration (the one with the best diffusion). This eliminates some of the possible intrastate correlations that may be left by the non-ideal permutation. This is similar to the approach LEX used to get away with producing 4 bytes of stream at every AES round. You can also look at it as a keyed sponge with 96 bits of capacity.

The initialization step, with 20 iterations, is probably overkill for either generator. It is only meant to ensure the starting point looks more or less random even if the seed has very low hamming weight.

The period (and cycle structure) is the same in both the MIX permutation and its inverse. MIX-i does a poorer job at diffusion, but it still compares fairly well with other similar non-cryptographic generators. I prefer MIX.

Answer 2

I see no issue here about bit diffusion; if $\textit{MIX-i}$ has a problem, so does $\textit{MIX}$.

The reason is simple, $\textit{MIX-i}$ is precisely $\textit{MIX}$, but backwards. Hence, if $\textit{MIX}$ starting at initial state $S_0$ and ending at final state $S_n$, would generate the output:

$B_0, B_1, B_2, ..., B_{n-2}, B_{n-1}, B_n$

then $\textit{MIX-i}$, starting at initial state $S_n$, would generate the output:

$B_n, B_{n-1}, B_{n-2}, ..., B_2, B_1, B_0$

If the sequence $B_n, B_{n-1}, B_{n-2}, ..., B_2, B_1, B_0$ has a problem (either against a statistical analysis, or against a cryptographical attack), then $B_0, B_1, B_2, ..., B_{n-2}, B_{n-1}, B_n$ should have the same problem.

Now, is $\textit{MIX}$ (or $\textit{MIX-i}$) a good random number generator – either statistically, or as a cryptographically secure random number generator? Well, I don't know if it's a good statistical rng (it does have an obvious state recovery attack that takes $O(2^{64})$ time, hence I believe it is disqualified from being considered a CSRNG); however the fact that hidden bits from $A, C, D$ are not mixed in as well as they may be are not an automatic disqualification.

Answer 3

According to the text you quoted — yes, it's less quality and you should (following math logic) loop the $\textit{MIX-i}$ at least (26/8=) 3 times to achieve the same amount of flipped bits as the "slower" $MIX$.

In fact, I'm not really sure if $\textit{MIX-i}$ is indeed faster than $MIX$. Sure, $MIX_i$ is faster by itself, but having to loop it 3 times to achieve the 26 flipped bits $MIX$ achieves, it could well be that it's more logic to stick with $MIX$ in the first place.

I don't have time to create one, but a benchmark would be able to show if 3 * $\textit{MIX-i}$ is indeed faster than 1 * $MIX$ when practically implemented. Chances are, that it'll turn out $MIX$ is the better choice.

As for the period length, I don't see it being affected either… but when your goal is to achieve more flipped bits (to have a more random range of what the rng returns), $MIX$ will do a better job than $\textit{MIX-i}$, which is bound to return numbers in a close range of previous ones. Exagerated example: if you're fine with 1,3,5,4,2,…,251,254,253,255 instead of 1,123,16,204,…,51,17,164,3, you can opt-in for $\textit{MIX-i}$;. Otherwise, you'll probably want to use $MIX$.