2
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ The way to prove such a claim usually is to construct a bijection from your output to the RNG output. Alternatively the strategy is to proof that distinguishing your output from random can be used to distinguish the RNG's output from random. $\endgroup$
    – SEJPM
    Mar 6 '17 at 16:55
  • $\begingroup$ And the standard cryptographer's way to go about this problem is to assume that all bits are equally distributed, find the smallest bitmask that allows for the full range, sample this bit-range (by sampling your larger range und using bitwise AND with the mask) and return the first result that satisfies your constraints. $\endgroup$
    – SEJPM
    Mar 6 '17 at 16:57
  • $\begingroup$ What is the reason why you store the previous output and add it to the current pseudorandom byte? Once I understand your design choice, I can probably answer your question. $\endgroup$ Mar 6 '17 at 17:56
  • $\begingroup$ @GeoffroyCouteau - by using the previous random result to add the new byte (which is not pseudorandom, but "true" random) I avoid having a Modulo Bias - (for example, see crypto.stackexchange.com/a/21010/11006 ) $\endgroup$
    – rolfl
    Mar 6 '17 at 17:59
  • $\begingroup$ Ok, now I'm confused. Didn't you say that the bytes come from a CSPRNG? How comes they are truly random? If they are, where do you use the CSPRNG? A "cryptographically secure random number" is a pseudorandom number, not a truly random number, right? Moreover, the link you give states the two usual ways of avoiding a bias: statistical masking with a very large integer, and rejection sampling. You are using neither of them, and I do not think your method avoids the modulo bias. $\endgroup$ Mar 6 '17 at 18:06
4
$\begingroup$

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$.
$\endgroup$
5
  • $\begingroup$ One small nit to this excellent answer: for the second method, to get a bias bound bounded by $2^{-64}$, you need 8 random bytes in addition to the size of $\ell$; for example, if you use 8 bytes to generate a value in the range $[0, 2^{32}-2]$, you get a bias of $2^{-32}$... (oh, and the range should be $[0, \ell-1]$...) $\endgroup$
    – poncho
    Mar 6 '17 at 18:43
  • $\begingroup$ Corrected the range and the statement, thanks for pointing this out :) $\endgroup$ Mar 6 '17 at 18:48
  • $\begingroup$ I agree with your assessment here. Where I failed in my logic is that it's possible to make inferences of a value if you know the previous value. While I agree that this breaks the integrity of a source/base CSRNG (as I asked in the question) I wonder whether the code is still useful in some circumstances (perhaps the original usecase from the OP in Code Review). Regardless, this answer is correct. $\endgroup$
    – rolfl
    Mar 6 '17 at 19:27
  • $\begingroup$ This I cannot tell, and it will be up to you to find out :) $\endgroup$ Mar 6 '17 at 19:38
  • $\begingroup$ Edit: so, from what I saw on Code Review, the OP seems to want a sequence of uniform looking numbers between 0 and limit, so I cannot see how this method would help. But the first proposal you made should work right. $\endgroup$ Mar 6 '17 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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