Ensuring CSRNG integrity in reduced range

Question

I recently answered a question on Code Review: Resizing a discrete uniform CSRNG distribution and I was challenged to offer a proof for one of my suggestions, and I can't find one, possibly because I don't know how best to describe my suggestion.

As background, there is an (assumed) CSRNG RNGCryptoServiceProvider available that returns random bytes in the range [0, 256).

The objective is to return random values in a limited range [0, limit) where limit <= 256.

My suggestion is to:

- allocate a variable to store the previous value generated
- add a random value to it (from the CSRNG)
- modulo the result by the limit
- store the result to be used in the next request
- return the result

In my words, this returns a series of integer values where the differences between each is guaranteed (to the limits of the base CSRNG) to be uniformly distributed. Any modulo bias in the result is only relative to the previous result (not relative to 0).

In code (C#), I proposed:

private static IEnumerable<int> RandomWrap(int chunkSize, int limit)
{
    int prev = 0;
    foreach (byte b in RandomBytes(chunkSize))
    {
        prev = (prev + b) % limit;
        yield return prev;
    }

}

Does this code preserve the integrity of the CSRNG source? Can I prove it? Is there a reference I can use?

Answer 1

There are two cases to distinguish:

• Either the limit (let me call it $\ell$) divides 256. In this case, your method gives indeed random numbers in the appropriate range, but one can do better: simply pick a random byte $b$ and return $b\bmod \ell$.
• Either $\ell$ does not divide 256, and you have an issue.

Let me develop a bit on this issue. Your assumption was that using your method, each value would be biased, but with a bias depending of the previous value, which you assumed to be uniform. However, this does not quite work, for two reasons. First, your previous value is not uniform, as your first value is 0, so you cannot assume that the bias will be "uniformly spread". But even more, assume your previous value is uniform; then it does not solve the issue at all. Indeed, what you want from your random-looking sequence is that each value looks random even given the previous values. This is very important, it is fairly trivial to generate a long sequence of integers so that each integer taken independently look random, but the sequence is clearly not a random-looking sequence.

So, by adding the previous value to your byte before reducing modulo $\ell$, you do not solve the problem: there is a bias, which depends on the previous value, which you should assume is available to the adversary.

Let me restate the classical solutions that provably work:

• You can take $b$, and if it is lower than $\ell$, keep it, otherwise drop it and take the next byte. This is the rejection sampling.
• You can take a sequence of, say, 9 random bytes, parse them as a random 72-bit integer $n$, and compute your output as $n \bmod \ell$. This gives you a distribution statistically close to uniform over $[0, \ell-1]$, with a bias bounded by $2^{-64}$, as $\ell$ is lower than $2^8$.