Hacker News Reader

User inputs are not random but they certainly can be entropic.

It is crucial to inform the user of this, as software has.

"Generating random numbers, please move your mouse around randomly" is suitable for literally all use cases.

Yeah, you're right, I guess I should've been more clear, using user inputs naively as an RNG is a bad idea, using it as a source of entropy can be useful. I would never entirely rely on it though, noise is a must, all it can really do is speed up true random number generation, and then only if the implementation is right, combining the sources of entropy naively can lead to reduction in security also, to me the risk of that added complexity is not worth the speed up in anything critical, I'd rather not use user inputs at all.

In many cases the next problem would be what to use instead. The alternatives aren’t too great either.

Suggestion: Every device has a built in lava lamp that we process into visual noise... Bring the 70's back in a big way.

Many devices already have hardware sources of randomness built in. The problem is just that they are unverifiable and built by companies that have shown themselves to be untrustworthy.

No, the problem is that the built in sources aren’t funky enough ;)

In all seriousness, though, yes and guaranteeing that the manufacturing process itself can “bake” in the randomness is a super interesting area of research. It’s like 99% of the manufacturing process is an exercise in reducing variability, and then there’s PUFs, where you’re basically trying to maximize variability, but in such a way that you maintain computational precision.

There are great alternatives in principle. The problem is incentives to sabotage alternatives by governments and manufacturers. There are chips that produce real entropy, and processors come with integrated hardware for this purpose. The problem is that you don't know if the hardware is deliberately flawed in some way.

Specifically, PRNGs based on cryptographic algorithms (CSPRNGs) resist loss of existing entropy from having new, low entropy sources appended to the stream.

To my thinking, what is more important is that you don’t fool yourself about the amount of entropy from one source, or among sources. Two entropy sources that are dependent variables may be good separately but not together. Like the timings of keystrokes and network packets may be affected by the scheduler, or the fact that you are typing into a remote editor session which is bouncing ACKs back, or auto saving every time you hit enter or change focus.

> That number is most certainly not random, there are biases in it, you just don't know there are.

Indeed. In that specific example, the author generated 24 binary digits, but only on 7 occasions was the digit the same as the previous digit. There were 23 opportunities to do so, and in a truly random sequence of digits the chance of any digit being the same as the previous one is 50%.

Applying the binomial distribution, the probability of observing 7 or fewer repeats with 23 trials and a 50% chance on each trial is only 4%. So with p = 0.04, we can reject the null hypothesis that the author's generated sequence is random, and conclude that it is biased.

There are online demos where you can try this yourself: https://people.ischool.berkeley.edu/~nick/aaronson-oracle/in...

Yes I'm aware that there's an ongoing debate about whether a human, or anything for that matter, can truly be random. But I wasn't going to bring this up in this article, or add caveats to every single point, or else this would've been unbearable to read.

I used artistic license in certain instances. But I agree some things could've been worded better and I'll edit those.

Oh no man, I'm not picking on you. This is an excellent article to explain the basics of random number generation. If you'd gotten into the weeds on it it wouldn't be as accessible.

There is important terminology in the world of all this stuff though, particularly "not all random numbers are the same" can confuse someone who then begins learning more about it.

Artistic license is good.

Yeah I did edit that section:

"And that source will vary depending on what kind of random number generator you want to use.

I’m sure that last sentence caused some confused looks. What do you mean by “kind of random number generator”? Aren’t they all the same?"

Sorry if I came off snippy. I definitely appreciate the feedback.

> it could be that P=NP, it could be that an algorithm exists to factor numbers to primes

Nits but 1) even if P=NP, it is possible that the problems we've chosen have a lower bound on their polynomial-time algorithms that still leaves them secure for the indefinite future (O(n^Graham's Number) is polynomial). Of course, we also don't have any proof of that so your general point stands. Related, 2) an algorithm certainly exists to find prime factors - quite a few actually! - but none that we know of in polynomial time without quantum computing.

>No, you didn't. That number is most certainly not random, there are biases in it, you just don't know there are.

Isn't that true of CSPRNGs as well, though? One of them may have some huge flaw that allows it to be predicted, we just don't know what it is yet.

(I think you basically agree with this in your last paragraph?)

More generally, when we ask for a random number, what we're usually looking for is a number uncorrelated with some other number. For example, when you're doing an experiment, the purpose of the randomization is to ensure that you're not really capturing some other effect that was setting which parameters were placed together.

That is, if you're deciding to run the control vs test case because of subtle fluctuations in the room's lighting (that you're unaware are influencing you), then you may have no effect at all, but you accidentally pick up an effect which was really due to the lighting, not to the thing you're trying to test. Using a dice roll prevents this, not because of randomization per se, but because it reliably breaks other correlations that might seep into the experiment.

To the extent that a human randomizer meets that in one particular domain, it may be good enough (not that you were saying otherwise). It's just ... you'd rather not bet on that being true in any given case.

Well, I'm referencing a "random" number generated in someone's head, not one generated by a CSPRNG. But with regard to CSPRNGs, an implementation can have a flaw, and we have seen these sorts of things happen, a well known example is MD5, a hash function, which are similar in principle to PRNGs, was broken.

My last paragraph basically amounts to if any of the axioms used for constructing any crypto are false then all cryptography based on them is breakable and this is not specific to any implementation. If they're not false, proper implementation works, and implementation details are more important. In principle, just using a provably random TRNG to generate a seed and then using a properly implemented CSPRNG to generate numbers from the seed, as long as the seed is provably destroyed the numbers are indistinguishable from random numbers. This is not true of "randomness" generated by the human brain. "You'd rather not bet on that being true" is exactly right, theoretically a human could produce a truly random number, but the likelihood is very low that no predictable external influence went into that process compared to using noise generated by the chaotic universe.

>Well, I'm referencing a "random" number generated in someone's head, not one generated by a CSPRNG.

What is that responding to? I thought I made the distinction between which one I was addressing pretty clear.

>But with regard to CSPRNGs, an implementation can have a flaw, and we have seen these sorts of things happen, a well known example is MD5, a hash function, which are similar in principle to PRNGs, was broken.

True, but my point was that the algorithm can itself be flawed, even if implemented correctly.

The point being, yes, you have Knightian uncertainty about the real factors that cause human-generated random numbers ... but you also have Knightian uncertainty about the existence of undiscovered flaws in your algorithm.

Yes, you're much less likely to run into the flaw if you're using a CSPRNG based on a high-entropy source, but in both cases it's true, or at least, impossible to rule out, that "there are biases in it, you just don't know there are."

Edit: And, FWIW, there aren't usable cryptosystems based on P=NP, which would actually be an improvement! Most are based on the far stronger assumption that certain "NP-intermediate" problems aren't feasibly solveable.

I don't know what is actually done, but I would think you can do things like milliseconds between keystrokes, or distance mouse moved modulo 2 to generate randomness. That said I agree with your point humans are not random.

Are you using “random” to mean “uniformly random” and not (e.g) “beta-distributed random”?

Yes. Sorry, I overlook being explicit sometimes accidentally.

> No, you didn't. That number is most certainly not random, there are biases in it, you just don't know there are. Your mind is not random. This is why we use dice and not people to generate random bits.

Can't you say that any single (shortish) number is random? How you can demonstrate 99999999999999999999 isn't random?

Just looking at it with your eyes you can't. But there are statistical analysis techniques used to find bias in random numbers, patterns in random numbers generated using the same RNG and this is often used to demonstrate that some technique or generator is broken and cryptographically insecure. If a 128 bit number doesn't provide 128 bits of security then something in the generation of that number is broken.

There are other comments in this thread that get into some nitty gritty details of this that I don't pretend to be an expert on.

> Can't you say that any single (shortish) number is random? How you can demonstrate 99999999999999999999 isn't random?

You can not. Randomness is a property of the procedure used to generate it, not the number.

You're basically applying the Sorites paradox to random numbers.

Sure, asking whether or not any single number is random does not really make sense (although I suppose if we have enough digits to look at then something similar to Benford's law might apply to their distribution). But the point being made was about humans as random number generators and the distribution of numbers they produce. It's like comparing individual molecules to statistical physics.