7 ms·

It's a good introductory write up, but there are 3 things about it that frustrated me to no end. > "As a human, I can do this very easily. 10010101101001011000

It's a good introductory write up, but there are 3 things about it that frustrated me to no end. > "As a human, I can do this very easily. 100101011010010110001101 There, I just did it. 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. > What do you mean by “kind of random number”? Aren’t all random numbers the same. Not really. There are two primary types of random number generators. I growled audibly at this one. Random numbers should all be the same. In quality, not quantity, of course. There should be no discernible difference. There is one kind of random number, only different types of generators, with a PRNG if the seed is provably destroyed there should be absolutely no way to distinguish between a number generated by a PRNG and a TRNG. > The computer hardware isn’t the only source of entropy. The user’s own mouse and keyboard movements can be used as well. No. These movements are not random. Similar to my first gripe, your brain is not random. We used to use this approach to generate entropy and now we don't because this is understood, "random" user inputs should absolutely never be used to generate randomness in anything security related. > Despite the benefits of CSPRNGs, as with everything else in the tech industry, security can never be guaranteed. I'm glad you pointed this out. Everything in cryptography is based on unproven axioms, this is an important point that people should understand, it could be that P=NP, it could be that an algorithm exists to factor numbers to primes, we think not but really we don't know.

postalrat 5y ago
> 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?
- betwixthewires 5y ago
  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.
- Filligree 5y ago
  > 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.
- vanderZwan 5y ago
  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.
Jerrrry 5y ago
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.
- betwixthewires 5y ago
  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.
  - tinus_hn 5y ago
    In many cases the next problem would be what to use instead. The alternatives aren’t too great either.
    - IntrepidWorm 5y ago
      Suggestion: Every device has a built in lava lamp that we process into visual noise... Bring the 70's back in a big way.
      - tinus_hn 5y ago
        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.
        catlifeonmars 5y ago
        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.
sunny--tech 5y ago
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.
- betwixthewires 5y ago
  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.
  - sunny--tech 5y ago
    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.
SilasX 5y ago
>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.
- betwixthewires 5y ago
  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.
dllthomas 5y ago
> 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.
caylus 5y ago
> 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/index.html https://people.ischool.berkeley.edu/~nick/aaronson-oracle/in...
mindvirus 5y ago
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.
catlifeonmars 5y ago
Are you using “random” to mean “uniformly random” and not (e.g) “beta-distributed random”?
- betwixthewires 5y ago
  Yes. Sorry, I overlook being explicit sometimes accidentally.

postalrat 5y ago

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

betwixthewires 5y ago
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.
Filligree 5y ago
> 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.
vanderZwan 5y ago
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.

Jerrrry 5y ago

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.

betwixthewires 5y ago
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.
- tinus_hn 5y ago
  In many cases the next problem would be what to use instead. The alternatives aren’t too great either.
  - IntrepidWorm 5y ago
    Suggestion: Every device has a built in lava lamp that we process into visual noise... Bring the 70's back in a big way.
    - tinus_hn 5y ago
      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.
      - catlifeonmars 5y ago
        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.

sunny--tech 5y ago

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.

betwixthewires 5y ago
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.
- sunny--tech 5y ago
  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.

SilasX 5y ago

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

betwixthewires 5y ago
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.

dllthomas 5y ago

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

caylus 5y ago

> 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/index.html https://people.ischool.berkeley.edu/~nick/aaronson-oracle/in...

mindvirus 5y ago

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.

catlifeonmars 5y ago

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

betwixthewires 5y ago
Yes. Sorry, I overlook being explicit sometimes accidentally.