1
$\begingroup$

This question is inspired by a RNG question and some of the comments in the one of the answers. I have been designing random number generators in hardware recently and my results are significantly better than what I get from /dev/random and /dev/urandom. I took a sample of 10000 results from /dev/random and /dev/urandom and the results are as follows: enter image description here enter image description here

I ran this a few dozen times and the results are about the same with /dev/random being better than /dev/urandom, but that's not the crux of my curiosity.

Mathematically, of course, we want a completely decorrelated sequence of numbers for a random set. My question is if there is a maximum value for correlation in a set of random numbers that is acceptable? From the hardware standpoint, I can save a lot of power if I have slightly less random numbers and this is a very appealing idea for me. I don't know if it matters, but I use my random number generator for a ECC engine.

Update It seems that my /dev/random and /dev/urandom differences were outputs from the same device, but just with less entropy. My working theory is that the second read from the device has less entropy, but more than the OS minimum requirement. However, my question on the maximum correlation is still how much is the maximum acceptable correlation in a series of "random" numbers.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ You might want to check NIST's toolkit for some thoughts on how 'good' an RNG/PRNG should be for cryptographic purposes. Also since you are looking at correlation, the serial-correlation test from these slides should give you a more concrete measure. $\endgroup$
    – SleuthEye
    Aug 7, 2016 at 2:31
  • 1
    $\begingroup$ If you can find a test that distinguishes (from data in samples of equal size) the output from /dev/random from the output of /dev/urandom, then at least one of the two generators is awfully broken (which is improbable for at least /dev/urandom in a modern OS). If your RNG can be reliably distinguished from a good /dev/urandom, then it is unsuitable for direct use in a cryptographic usage. That's the case of most hardware RNGs without post-conditioning, and is NOT a defect; only a reason to use post-conditioning. $\endgroup$
    – fgrieu ♦
    Aug 7, 2016 at 10:29
  • $\begingroup$ @fgrieu I wrote up my methods semi-formally: degnan68k.blogspot.com/2016/08/devrandom-vs-devurandom.html I have found that I get consistent results for /dev/urandom being "awfully broken". I also have similar behavior for a Linux machine (it's cloud machine, so I don't know the details of the hardware). Compared to hardware implementations, even /dev/random isn't as good, so I now have even more questions to answer. $\endgroup$
    – b degnan
    Aug 7, 2016 at 23:15
  • $\begingroup$ ...and I just learned that on MacOS /dev/random and /dev/urandom are the same, so this makes things more interesting. $\endgroup$
    – b degnan
    Aug 7, 2016 at 23:43
  • 1
    $\begingroup$ @b degnan: common wisdom is that a modern /dev/urandom has output indistinguishable from random. If it happens not to pass a randomness test, the first thing to put in doubt is the test. It is not entirely unseen to become convinced of finding bias when independent experiments show there is not. $\endgroup$
    – fgrieu ♦
    Aug 8, 2016 at 8:12

1 Answer 1

Reset to default
2
$\begingroup$

There is no limit as to the amount of correlation you can have from an entropy source for it to be useful, but correlation then places a restriction on how you extract the entropy.

The restriction is this: you have to individually process an entropy block of a size that exceeds the length of correlation. Thus no correlation between blocks. For a Geiger tube you might have a slight settlement time after each reading that might be of length (n + 10). That means you have to deal with blocks of readings greater than 10. I use a web cam that outputs 25KB images, so I have to treat that as a full 25KB block (n+25K) to extract the entropy. If I try to process the image on a byte by byte basis, I fall foul of the JPEG file format that envelops the true entropy within the image.

Correlation is impossible to remove programmatically as that requires a complete theoretic model of the underlying physics of the source. My suggestion is to side step it and consume entropy in blocks greater than any possible length of auto correlation. If you're reading noise it might only be at most (n+2) anyway.

From your blog post that initiated all this:-

/dev/urandom is a pseudo random number generator, a PRNG, while /dev/random is a “true” random number generator.

I would argue that both random and urandom are pseudo random number generators, and you are just comparing like with like and getting differing results! /dev/random breaks my no more entropy out than in rule from this post hence I think that it's not a TRNG at all.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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