Pseudo-Random vs. True Random (2012) | Hacker News Reader

Pseudo-Random vs. True Random (2012)

boallen.com

37 pointscrmrc11421 comments

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.

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.

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.

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.

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.

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

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_mec...

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.

If interested, see this past HN discussion from time of publication:

https://news.ycombinator.com/item?id=5850067

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!)

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)

They already do. 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...

Fun times

So Linus is fine with it, and FreeBSD fed it into yarrow/fortuna which is the kernel boot time initialized entropy pool.

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.

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.

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.

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.

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

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

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....

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

I'd expect it's fixed since PHP 7.1.0:

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?

Reply on news.ycombinator.com