5 ms·

Pseudo-Random vs. True Random (2012)

37 points by crmrc114 6y ago

tptacek 6y ago
For security, you don't care whether random numbers are "truly random" or not; you care whether they're cryptographically secure. Your mental model should be of a stream cipher, which is a tool that stretches a short secret into a very long secret. The question you should ask yourself is, "have I fed this generator 16-32 bytes of unguessable material, and does it use cryptographically sound tools to spool out random bytes from that seed?" Your kernel arranges to do this for you, and, for security-sensitive applications, is the RNG you should use to the exclusion of all others, "true" or not.
- tialaramex 6y ago
  I feel like the question you've suggested people ask themselves is a bit over-complicated. Maybe the right way to phrase the question is instead just: Can somebody else guess these numbers? It doesn't actually matter whether bad guys can guess your numbers because you use Python's non-cryptographic PRNG or because you mistakenly overwrote the genuinely random numbers you had with zeroes, or they've planted a physical device inside your computer stealing the random numbers used, it only matters that they can guess the numbers.
- ChrisSD 6y ago
  Put more simply: It's the unpredictability of the output that's important. It doesn't matter if it's "true" randomness or not. Unless of course you're looking to leverage the theoretical strengths of a one time pad.
- SAI_Peregrinus 6y ago
  It's also quite possible there is no such thing as "true" randomness. If one of the deterministic interpretations of quantum mechanics is correct and there's no other source of randomness in the laws of physics, then TRNGs are just looking at the output of chaotic systems, just like PRNGs are. Random.org's atmospheric noise source isn't even quantum-mechanical, it's classical deterministic chaos. It's a PRNG with an enormous state.
  - tialaramex 6y ago
    One of the unknown corner cases in this space is that it implies hidden state. We've ruled out Local Hidden State with physics experiments, but you can't rule out Global Hidden State that way. There could be in this sense say, a 1MB global "random seed" for our universe. In this model you can build Quantum Computers but when you build a really big one to, for example, attack traditional public key cryptography with Shor's algorithm it mysteriously doesn't work. This is because without you knowing it your Quantum Computer is using the global hidden state as scratch storage and it ran out. Almost everything about this scenario is terrible news, but on the bright side you can't attack modern cryptography with a Quantum Computer because it won't work.
  - irjustin 6y ago
    I'm not sure why you're being downvoted. It's not an unreasonable question/thought. The heisenberg uncertainty principle says we cannot know both position and momentum perfectly at the same time where I believe your comment is originating from? In theory, if we perfectly know the quantum information then a system's state is perfectly reproducible (probably not us... ultra aliens?) since no quantum information is ever lost (probably...). To my best understanding, this is the idea of the holographic principle[0]. [0] https://www.youtube.com/watch?v=klpDHn8viX8 https://www.youtube.com/watch?v=klpDHn8viX8
    - SAI_Peregrinus 6y ago
      No, just interpretations of QM, Heisenberg doesn't change anything here. Wikipedia has a nice table[0]. Any deterministic interpretation says that the results of experiment are all entirely predetermined by the entire past history of the universe. This includes Heisenberg's principle, since what you choose to measure is also deterministic, and thus the imprecision is predetermined. There's nothing in the laws of physics that rules out these interpretations. Thus, we can't definitively say that TRNGs exist in this universe. We also can't say that they don't, of course, since all the interpretations of QM make the same observable predictions and thus are equally likely to be correct. [0]https://en.wikipedia.org/wiki/Interpretations_of_quantum_mechanics#Comparison https://en.wikipedia.org/wiki/Interpretations_of_quantum_mec...
ggm 6y ago
How many gates would it cost, to include the various quantum like random sources as hardware on-die? Open gate transistors, thermal effects, radiative effects... (Not that there are not risks, and it is a mistake to assume on-die is not risky)
- jesboat 6y ago
  They already do. http://en.wikipedia.org/wiki/RdRand http://en.wikipedia.org/wiki/RdRand has been around on x86 for a while. Unfortunately, they're essentially unauditable and sometimes frightfully broken, eg https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/ https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd... Fun times
  - ggm 6y ago
    So Linus is fine with it, and FreeBSD fed it into yarrow/fortuna which is the kernel boot time initialized entropy pool.
    - ChrisSD 6y ago
      Putting it into a pool is fine. It can be XORed with other sources. And if at boot time there's no stored entropy and no other sources, then it's better than nothing until more sources become available.
082349872349872 6y ago
On the other hand, if one is chipping for spread spectrum, a PRNG is much more useful than a TRNG.
McGlockenshire 6y ago
FWIW, the information in this article is out of date. For example, as the article picks on PHP, PHP now uses the Mersenne Twister for regular rand(), and gives access to a CSPRNG through random_int() and random_bytes(). By "now" here I mean as of five years ago. It's still important for developers to understand the "P" in PRNG, but at least we have less possible foot-shooting by default in PHP now. (Evergreen statement!)
andyljones 6y ago
The link at the bottom of the post to the actual explanation is broken. Here's a web archive version: https://web.archive.org/web/20191106104440/http://cod.ifies.com/2008/05/php-rand01-on-windows-openssl-rand-on.html https://web.archive.org/web/20191106104440/http://cod.ifies.... TL;DR the default Windows random number generator is (was?) an LCG[1], and that's what PHP calls into by default. [1] https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator
- acqq 6y ago
  I'd expect it's fixed since PHP 7.1.0: https://www.php.net/manual/en/function.rand.php https://www.php.net/manual/en/function.rand.php "Note: As of PHP 7.1.0, rand() uses the same random number generator as mt_rand(). To preserve backwards compatibility rand() allows max to be smaller than min as opposed to returning FALSE as mt_rand()." Maybe somebody could run the code from the OP on Windows with a newer PHP and check?
hellofunk 6y ago
There are many applications for which you definitely do not want a true random number. Sometimes you want your random numbers to exist in a uniform distribution, for example.
- gopiandcode 6y ago
  This is incorrect. True random (vs pseudo-random) relates to whether the past outcomes of the generator provide any information about the future invocations. There is nothing stating that a true random generator can not conform to some distribution There are cases where you might not want a true random generator, although this relates more to the importance of unpredictability versus the performance requirements for your domain.
  - Spivak 6y ago
    Or maybe a more succinct way of putting it. You can sample random numbers from any distribution. There's nothing special about the uniform distribution except that it's one that people want most of the time.
greencar 6y ago
If you cross your eyes a little the second one shows a schooner
crmrc114 6y ago
I was wondering how I would quickly check the randomness of a RNG. When I noticed a couple websites had randomly generated bmps. I guess with the human brain being an awesome visual pattern detector this is a quick and easy test. Anyhow I stumbled on this page from 2012 and figured I would share.
deleted 6y ago
[deleted]
merricksb 6y ago
If interested, see this past HN discussion from time of publication: https://news.ycombinator.com/item?id=5850067 https://news.ycombinator.com/item?id=5850067

37 points by crmrc114 6y ago

For security, you don't care whether random numbers are "truly random" or not; you care whether they're cryptographically secure. Your mental model should be of a stream cipher, which is a tool that stretches a short secret into a very long secret. The question you should ask yourself is, "have I fed this generator 16-32 bytes of unguessable material, and does it use cryptographically sound tools to spool out random bytes from that seed?" Your kernel arranges to do this for you, and, for security-sensitive applications, is the RNG you should use to the exclusion of all others, "true" or not.

tialaramex 6y ago
I feel like the question you've suggested people ask themselves is a bit over-complicated. Maybe the right way to phrase the question is instead just: Can somebody else guess these numbers? It doesn't actually matter whether bad guys can guess your numbers because you use Python's non-cryptographic PRNG or because you mistakenly overwrote the genuinely random numbers you had with zeroes, or they've planted a physical device inside your computer stealing the random numbers used, it only matters that they can guess the numbers.
ChrisSD 6y ago
Put more simply: It's the unpredictability of the output that's important. It doesn't matter if it's "true" randomness or not. Unless of course you're looking to leverage the theoretical strengths of a one time pad.
SAI_Peregrinus 6y ago
It's also quite possible there is no such thing as "true" randomness. If one of the deterministic interpretations of quantum mechanics is correct and there's no other source of randomness in the laws of physics, then TRNGs are just looking at the output of chaotic systems, just like PRNGs are. Random.org's atmospheric noise source isn't even quantum-mechanical, it's classical deterministic chaos. It's a PRNG with an enormous state.
- tialaramex 6y ago
  One of the unknown corner cases in this space is that it implies hidden state. We've ruled out Local Hidden State with physics experiments, but you can't rule out Global Hidden State that way. There could be in this sense say, a 1MB global "random seed" for our universe. In this model you can build Quantum Computers but when you build a really big one to, for example, attack traditional public key cryptography with Shor's algorithm it mysteriously doesn't work. This is because without you knowing it your Quantum Computer is using the global hidden state as scratch storage and it ran out. Almost everything about this scenario is terrible news, but on the bright side you can't attack modern cryptography with a Quantum Computer because it won't work.
- irjustin 6y ago
  I'm not sure why you're being downvoted. It's not an unreasonable question/thought. The heisenberg uncertainty principle says we cannot know both position and momentum perfectly at the same time where I believe your comment is originating from? In theory, if we perfectly know the quantum information then a system's state is perfectly reproducible (probably not us... ultra aliens?) since no quantum information is ever lost (probably...). To my best understanding, this is the idea of the holographic principle[0]. [0] https://www.youtube.com/watch?v=klpDHn8viX8 https://www.youtube.com/watch?v=klpDHn8viX8
  - SAI_Peregrinus 6y ago
    No, just interpretations of QM, Heisenberg doesn't change anything here. Wikipedia has a nice table[0]. Any deterministic interpretation says that the results of experiment are all entirely predetermined by the entire past history of the universe. This includes Heisenberg's principle, since what you choose to measure is also deterministic, and thus the imprecision is predetermined. There's nothing in the laws of physics that rules out these interpretations. Thus, we can't definitively say that TRNGs exist in this universe. We also can't say that they don't, of course, since all the interpretations of QM make the same observable predictions and thus are equally likely to be correct. [0]https://en.wikipedia.org/wiki/Interpretations_of_quantum_mechanics#Comparison https://en.wikipedia.org/wiki/Interpretations_of_quantum_mec...

ggm 6y ago

How many gates would it cost, to include the various quantum like random sources as hardware on-die? Open gate transistors, thermal effects, radiative effects... (Not that there are not risks, and it is a mistake to assume on-die is not risky)

jesboat 6y ago
They already do. http://en.wikipedia.org/wiki/RdRand http://en.wikipedia.org/wiki/RdRand has been around on x86 for a while. Unfortunately, they're essentially unauditable and sometimes frightfully broken, eg https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/ https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd... Fun times
- ggm 6y ago
  So Linus is fine with it, and FreeBSD fed it into yarrow/fortuna which is the kernel boot time initialized entropy pool.
  - ChrisSD 6y ago
    Putting it into a pool is fine. It can be XORed with other sources. And if at boot time there's no stored entropy and no other sources, then it's better than nothing until more sources become available.

082349872349872 6y ago

On the other hand, if one is chipping for spread spectrum, a PRNG is much more useful than a TRNG.

McGlockenshire 6y ago

FWIW, the information in this article is out of date. For example, as the article picks on PHP, PHP now uses the Mersenne Twister for regular rand(), and gives access to a CSPRNG through random_int() and random_bytes(). By "now" here I mean as of five years ago. It's still important for developers to understand the "P" in PRNG, but at least we have less possible foot-shooting by default in PHP now. (Evergreen statement!)

andyljones 6y ago

The link at the bottom of the post to the actual explanation is broken. Here's a web archive version: https://web.archive.org/web/20191106104440/http://cod.ifies.com/2008/05/php-rand01-on-windows-openssl-rand-on.html https://web.archive.org/web/20191106104440/http://cod.ifies.... TL;DR the default Windows random number generator is (was?) an LCG[1], and that's what PHP calls into by default. [1] https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator

acqq 6y ago
I'd expect it's fixed since PHP 7.1.0: https://www.php.net/manual/en/function.rand.php https://www.php.net/manual/en/function.rand.php "Note: As of PHP 7.1.0, rand() uses the same random number generator as mt_rand(). To preserve backwards compatibility rand() allows max to be smaller than min as opposed to returning FALSE as mt_rand()." Maybe somebody could run the code from the OP on Windows with a newer PHP and check?

hellofunk 6y ago

There are many applications for which you definitely do not want a true random number. Sometimes you want your random numbers to exist in a uniform distribution, for example.

gopiandcode 6y ago
This is incorrect. True random (vs pseudo-random) relates to whether the past outcomes of the generator provide any information about the future invocations. There is nothing stating that a true random generator can not conform to some distribution There are cases where you might not want a true random generator, although this relates more to the importance of unpredictability versus the performance requirements for your domain.
- Spivak 6y ago
  Or maybe a more succinct way of putting it. You can sample random numbers from any distribution. There's nothing special about the uniform distribution except that it's one that people want most of the time.

greencar 6y ago

If you cross your eyes a little the second one shows a schooner

crmrc114 6y ago

I was wondering how I would quickly check the randomness of a RNG. When I noticed a couple websites had randomly generated bmps. I guess with the human brain being an awesome visual pattern detector this is a quick and easy test. Anyhow I stumbled on this page from 2012 and figured I would share.

deleted 6y ago

[deleted]

merricksb 6y ago

If interested, see this past HN discussion from time of publication: https://news.ycombinator.com/item?id=5850067 https://news.ycombinator.com/item?id=5850067