Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm writing a small script that generates random non-signed decimal integers within a certain range of values. I'm using GNU od, with the following command:

od /dev/hwrng --address-radix=n --read-bytes=4 --format=u4

/dev/hwrng is linked to a SoC thermal noise sensor (bcm2708 on Raspberry Pi), so it would return pure random bits. Once obtained a pure random integer from od, I would use the modulo operator (eg: % in C/C++) to restrict the range of values (eg: 96-127). I have some doubts:

  1. Does modulo affect the quality of randomness, faking in some way the distribution of values?
  2. I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon
  3. Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo
  4. Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG.
share|improve this question
1  
Read this. Forget about /dev/hwrng, that's none of your business as an application writer: just use /dev/urandom. (And don't use PHP's rand anywhere near cryptography.) –  Gilles Feb 5 at 22:44

1 Answer 1

up vote 10 down vote accepted

Let me begin by saying that if you have a hardware source of randomness, you don't need to be stingy with it.

1) Does modulo affect the quality of randomness, faking in some way the distribution of values?

Yes, it does. Or at any rate, it can --- see my answer to (3) below for more details. (I'm assuming by "quality of randomness", you specifically mean that each possible output should be equally likely, and every output should be independent of the others.)

For example, let's say that you wanted to generate a random integer between zero and three. If you did this by rolling a fair six-sided die (with sides labeled zero through five) and taking the result modulo four, what would the resulting distribution look like? Well, rolling either a 0 or a 4 would cause you to output 0, so the probability of outputting a 0 would be 2/6. On the other hand, the only way you'd output a 3 would be if you actually rolled a 3. So the probability of outputting a 3 would be 1/6. This means that you'd output a 0 twice as often as you'd output a 3.

2) I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon.

The term "truly random" usually means by definition based on some physical source of randomness. But truly random doesn't imply uniformly random. In the example above, the output of a dice roll modulo four was truly random, but some outputs were more likely than others. Physical processes rarely produce a uniform distribution. They have biases -- for example, they might produce a normal distribution -- and often have state (leading to correlations).

It's possible to transform true randomnes into uniform randomness using so-called randomness extractors (aka entropy extractors). It's possible that an extractor is already built in to the bcm2708. But I'm not aware of any documentation that establishes this.

Various /dev/random implementations include (attempts at) randomness extractors internally. If you trust these algorithms, you can always read bits from /dev/hwrng into /dev/urandom, and then read from /dev/urandom.

3) Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo

Your intuition is correct here; if you're taking the result modulo some small number, then you can reduce bias to an acceptably small amount by using a really large range of numbers to begin with.

Concretely, if you start with a (uniform) random number in {0, 1, ..., N - 1} and take the result modulo n, the result will differ from a uniform distribution by statistical distance of less than (N mod n)/N. This is a useful measure because statistical distance is in turn an upperbound on how much you're increasing an attacker's probability of mounting a successful attack. So if you're protecting nuclear launch codes, you'd probably want to keep (N mod n)/N < 2^(-80). If you're protecting against SSH access to your media server, (N mod n)/N < 2^(-30) is probably a comfortable security margin.

Note than if N is divisible by n, there's no bias whatsoever introduced during this step. In your context, N will be a power of two (either N = 2^16 if you use two bytes, or N = 2^32 if you use four). So if n is a smaller power of two, you're good.

4) Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG

From the PHP documentation:

This function [rand()] does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using openssl_random_pseudo_bytes() instead.

To answer your more general question, though: No. Given a 128-bit seed, it's mathematically impossible to generate more than 128 bits of "true" randomness (as measured by, e.g., min-entropy). But: Given a 128-bit seed and a cryptographically secure PRNG, this doesn't really matter. A 128 bit seed is plenty for all practical purposes. "True randomness" doesn't really gain you anything after that point.

share|improve this answer
    
Minor correction at 1): In the last sentence is should be "output a 0 twice as often as a 3" (probability 1/6 and 2/6) –  tylo Feb 5 at 10:05
    
@tylo Thanks for the catch, I've fixed the error. –  Seth Feb 5 at 19:59
    
You can assume that $\pmod q$ behave randomly. I saw this assumption in some papers. –  111 Feb 6 at 9:22
1  
"Randomly" is too unspecific without further specification. If you say $x \leftarrow \mathbb{Z}_p, y = x$ mod $q$, then $x$ is almost uniform distributed if $q$ is much smaller than $p$. And it is only (really) uniform distributed, if the cardinalities match (e.g. going from $\mathbb{Z}_6$ to $\mathbb{Z}_3$, where "mod 3" has two preimages each). –  tylo Feb 6 at 13:41
    
Thanks all for helping. –  5haffl Jul 13 at 19:44

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.