Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

If I have a good random number generator that gives me a byte of data at a time, and I want to extract a random decimal digit of 0 to 9 from that byte stream, what is the correct way to do that?

At first I naively assumed that a simple (randomByte mod 10) calculation would be sufficient, but since 256 is not evenly divisible by 10, that results in a clear bias in the "random" digits:

0: 101323 #################################
1: 101261 #################################
2: 101473 #################################
3: 101389 #################################
4: 101551 #################################
5: 101587 #################################
6: 97831  ###############################
7: 97893  ###############################
8: 97843  ###############################
9: 97849  ###############################
(histogram from 1 million 'random' digits)

One method that appears to work is to discard any value above 249 and divide by 25. Is that cryptographically correct? Is there a better method that doesn't involve discarding (potentially expensive) bytes of randomness?

(this question is prompted by reading about a CryptoCat vulnerability, where one of the discovered flaws was that they discarded random values above 250 instead of above 249, giving a slight bias in their "random" numbers... so I was curious what the "right" way to do it is)

share|improve this question
2  
Discarding isn't expensive on average. Especially if you generate multiple digits from multiple bytes at a time. Btw. good stream ciphers(and thus PRNGs) are pretty fast, so the modulo operation is probably more expensive than generating a byte. –  CodesInChaos Jul 20 '13 at 20:26
add comment

2 Answers

up vote 13 down vote accepted

There are two generic ways to produce a "sufficiently unbiased" random digit.

First method is to loop if the byte was not in the right range. I.e.:

  • Get next random byte b.
  • If b is in the 0..249 range, return b mod 10.
  • Loop.

This method may consume an unbounded number of random bytes, but it is perfectly unbiased and it is very unlikely to require looping many times. That's what Java's Random.nextInt(int) standard method applies (albeit with 32-bit words instead of bytes).

Second method is to use as source value not one byte but a big enough word. Say, use 20 bytes, interpret these as an integer x in the 0..2160-1 range, and return x mod 10. This way, the bias is still there, but can be made arbitrarily small, to the point that it no longer matters. This is computationally expensive (more than the first method) but has the advantage of always requiring the same number of input bytes, which can be handy in some specific situations (e.g. side-channel leaks).

share|improve this answer
1  
With the first method one could simply include an upper bound for the number of iterations. Hitting it becomes exponentially rate and the bias exponentially small when the underlying generator is good. The advantage of such an upper bound is that you can prove that the generator will terminate. –  CodesInChaos Jul 20 '13 at 20:31
4  
Concerning side-channels, if the underlying PRNG is secure and properly seeded the side-channel shouldn't leak anything useful. It only gives the attacker information about discarded bytes, which shouldn't allow prediction of other bytes. The control flow of the first method isn't secret, even if the output is. –  CodesInChaos Jul 20 '13 at 20:34
add comment

As random generator may be something expensive, the more efficient way is to cut each byte (0-255) in two part (0-15), before dropping out of limit values:

There is a little sample using :

unset random cnt
while [ ! "$random" ] ;do
    ((cnt++))
    i=$(dd if=/dev/random bs=1 count=1 2>/dev/null | od -A n -t u1)
    for val in $((i&15)) $((i>>4)) ;do
        [ $val -lt 10 ] && [ ! "$random" ] && random=$val
    done
done
printf "%d bytes read, random value: %d\n" $cnt $random
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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