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

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?
-

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.

-

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.

-
Nice to see the author respond ;) I'm currently doing more research into the tradeoffs using SIMD and seeing if that's worth it/whether MIX-i still performs better there. –  orlp Oct 4 '13 at 0:02

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$.

-
$\textit{MIX-i}$ is exactly 2 times as fast as $MIX$. –  orlp Oct 3 '13 at 16:26
@nightcracker Haven't dived into that paper yet, but if $\textit{MIX-i}$ 's step is 2 times faster, $\textit{MIX-i}$ will "practically" be slower as it needs 3 loops to achieve a "good" random distribution, compared to $MIX$. (See my edit 4 minutes ago; I added the bottom paragraph with an exagerated example of the bit-flip downside .) –  e-sushi Oct 3 '13 at 16:37
@nightcracker Hmmm, found some C source at gamedev.net/topic/… of Tyche-i with someone saying "speed varies between 5-12 times as fast than rand()". Darn, knowing myself — I'll be benchmarking and analyzing both Tyche and Tyche-i next week just to satisfy my curiosity. Thanks for that… ;) –  e-sushi Oct 3 '13 at 16:49
You might want to check out the username of the poster of that code ;) I'm currently working on a more complete implementation (mostly boilerplate for generating bytes, shorts, doubles, properly distributed random ranges, etc). Also, if you're interested I can write a version using SIMD that, if my previous numbers of 5-12 were correct, would be somewhere between 20-140 times as fast as rand() - however this would require more memory as it would mean calculating 4-12 RNG's in parallel. –  orlp Oct 3 '13 at 16:55
And to get back on-topic, if I understand correctly the Tyche-i PRNG is "weaker" against analysis, but if both do not show noticable biases then Tyche-i would be the preferred PRNG for simulation purposes, seeing it's twice as fast? –  orlp Oct 3 '13 at 16:57