15 ms·

How do computers generate random numbers?

73 points by sunny--tech 5y ago

xkeysc0re 5y ago
Writing your own random number generator can be a lot of fun. Lots of sources of entropy out there. Inspired by lavarand[0], I wrote an RNG in Python based on the output of the Global Conscousness Dot[1] (which is a ridiculous project in its own right). There's a lot of ways to visualize and ascertain how "random" your numbers are as well, whether plotting Pearson's with matplotlib or using a command line tool like ent[2] to calculate the degree of entropy. [0] https://en.wikipedia.org/wiki/Lavarand https://en.wikipedia.org/wiki/Lavarand [1] https://gcpdot.com/ https://gcpdot.com/ [2] https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html
- pope_meat 5y ago
  Hah, thanks for sharing this dot thing, what a bizarre little corner of the internet.
  - xkeysc0re 5y ago
    Kind of wild to think that it was a project funded by Princeton and personally supported by their Dean of Engineering for decades!
- atty 5y ago
  From the GCP project: > The identification of events and the times at which they occur are specified case by case, as are the statistical recipes. The approach explicitly preserves some latitude of choice, as is appropriate for an experiment exploring new territory. Accepting loose criteria for event identification allows exploration of a variety of categories, while the specification of a rigorous, simple hypothesis test for each event in the formal series assures valid statistics. I’ve never seen someone so blatantly spell out that they are cherry picking, but also then argue that the cherry picking is good science ;) this is the sort of thing that gives real scientists a bad name.
- Workaccount2 5y ago
  I dug through the GCP dot page, and if I am understanding it correctly, their near-perfect RNGs have turned out to not be very random?
dragontamer 5y ago
A modern "pseudo random number" is simply a sequence of numbers that visits the state-space in an order that's difficult to detect with modern statistical tests. (Chi-squared, among others). See PractRand or TestU01 as two packages for testing these sequences. That is to say: instead of the sequence "0, 1, 2, 3, 4, 5... 4294967296... 0", your RNG will do some other sequence. Yes, "0, 3, 6, 9... 4294967295, 2, 5, 8... 4294967294, 1, 4, 7... 4294967293, 0, 3..." is a RNG of sorts, but an example of a really, really bad one that would instantly fail most statistical tests. :-) But conceptually, the Mersenne Twister, LCGRNG, and LSFR all accomplish this. Its a "reordering" of the sequence. That's it. A "cryptographic random number" just adds a few additional tests to the pool of statistical tests. In particular: differential cryptography gets into the nitty gritty about which bits can predict the results of other bits. You have to assume that the "opponent" is willing to use extraordinary amounts of computing power to detect patterns. If bit#25 has a 51% correlation with bit#30, you fail cryptographic random numbers. You need to be within 2^128 (at least) worth of security or more. That means a near 50% correlation (maybe 50.00000000001% is fine) between bits and future bits. For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. If the "opponent" doesn't know the key, the bitwise correlations are cryptographically sound (thanks to the hard work of the engineers behind AES). A true random number generator is just a cryptographic number generator applied to a truly random seed. White noise generators are a well known electronic-engineer trick: resistor noise is everywhere but is rather small (but you can build a white-noise generator from Johnson Nyquist noise if you really wanted). More likely, you use shot-noise from a transistor junction, at least at the hobbyist level. Intel / AMD have true random number generators from some kind of electrical noise generator on every CPU, which feeds into cryptographic random number generators. There are other sources of noise: radiation is a well known one but I'm not sure if they're practical. There's a "speed limit" to white noise generators. You only can extract so much entropy from them in a given time (ex: Remember: CPUs operate at 4GHz, or 0.25 nanoseconds per clock tick). Cryptographic random number generators "stretch" the true seed of randomness, while the white-noise generator continues to grab more entropy.
- SavantIdiot 5y ago
Borrible 5y ago
Use leftovers. They're all over the Universe. https://www.researchgate.net/publication/283762433_The_Cosmic_Microwave_Background_Radiation_Power_Spectrum_as_a_Random_Bit_Generator_for_Symmetric_and_Asymmetric-Key_Cryptography https://www.researchgate.net/publication/283762433_The_Cosmi...
fnord77 5y ago
I thought this was a solved problem for at least a decade with CPU instructions like `RDRAND`
- sodality2 5y ago
  It's preferred to use RDSEED and use that as a seed, instead of implicitly trusting the output of RDRAND. Mix it with user entropy (or system entropy). Some say RDRAND is a backdoor (and after Dual EC, it would not particularly surprise me). This is why RDRAND doesn't exist in Linux (or, maybe isn't the only source of entropy?): https://www.linux-magazine.com/Online/News/Linus-Says-No-Backdoor-in-Linux https://www.linux-magazine.com/Online/News/Linus-Says-No-Bac... Not sure the security implications of using poisoned seeds in addition to truly random seeds in an RNG. Some say that it's okay, because it cannot reduce security, only not increase it. But if the CPU RDRAND instruction is backdoored, couldn't the RNG instructions be intercepted and replaced so that RDRAND is the only seed? But, if your CPU is backdoored, why even bother with anything? etc, etc etc. This discussion could go on for a while.
  - foxfluff 5y ago
    > But if the CPU RDRAND instruction is backdoored, couldn't the RNG instructions be intercepted and replaced so that RDRAND is the only seed? If the CPU is going to detect and subvert your soft PRNG, it can do that whether you use RDRAND or not.
    - not2b 5y ago
      RDRAND is a microcoded instruction. The chipmaker does not publish that code, but they absolutely control what it does. If it has any flaws, whether deliberate or accidental, you can't fix them (the processor vendor might be able to fix it with a microcode update, but no one else can). That's why it isn't used. Your soft PRNG is an algorithm and a relatively simple one at that. You can test it, and verify that you get exactly the same sequence for a given seed whether you use a processor from Intel, AMD, ARM or someone else. Trying to detect and back door it would probably break a lot of other code. The bad guys would probably choose to attack you in a different way.
hdivider 5y ago
PCIe and USB cards like this are available, generating TRNs using quantum optics: https://www.idquantique.com/random-number-generation/products/quantis-random-number-generator/ https://www.idquantique.com/random-number-generation/product...
dekken_ 5y ago
some might say, it's impossible.
SavantIdiot 5y ago
I've been working with the NIST 800-22 evaluation suite [1] and yes, it is very hard. There are an infinite number of tests to determine if a number is random. Ultimately it comes down to probability that it is a good RNG/PRNG and the application. Ironically, if a PRNG is good enough, it can often be BETTER than a random source (which is why RNGs have a conditioning phase). [1] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documentation-and-Software/Guide-to-the-Statistical-Tests https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...
- panax 5y ago
  An infinite number of tests yes, it is like trying to find the best possible predictor of a source. No statistical test can prove that a source has full entropy and uniformly distributed, only disprove it. These tests are too often misused and are usually not very useful since they tell us nothing about how much entropy might be in the sample, and entropy sources are always biased anyway and fail the tests, and if you condition them then they will always pass the test even if not random at all. A better method is to develop a stochastic model of the entropy source and attempt to estimate bounds on the entropy, which is still generally not feasible. The statistical tests can then be used as a sanity check to verify your entropy estimates. The RNG needs a conditioning phase, or entropy extractor to transform the output into a distribution that is indistinguishable from uniform as is needed in cryptographic applications and you should always include this stage because virtually no physical entropy source has a uniform distribution. The best thing to do is to try to gather as much entropy as you can from sources and gather maybe 10x what you think you need and then put it through an entropy extractor like a cryptographic hash function to generate a PRNG seed then use the PRNG.
  - kevincox 5y ago
    > No statistical test can prove that a source has full entropy and uniformly distributed, only disprove it. It can't disprove it either. It can only say if it is "likely to be random" or "appears to be random". A perfectly random source could generate a string of 1M zeros, and most statistical tests would fail it. But that is not proof that it isn't random. A second test would likely not generate all zeros and would likely pass.
sunny--tech 5y ago
Link to bypass paywall: https://betterprogramming.pub/generating-random-numbers-is-a-lot-harder-than-you-think-b121c3e75d08?source=friends_link&sk=508f781bd2b7e0fc279950284c5a49ae https://betterprogramming.pub/generating-random-numbers-is-a...
- unnouinceput 5y ago
  It didn't
abnry 5y ago
Obligatory XKCD: https://xkcd.com/221/ https://xkcd.com/221/ And also Dilbert: https://dilbert.com/search_results?terms=Random+Number+Generator https://dilbert.com/search_results?terms=Random+Number+Gener...
betwixthewires 5y ago
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.
comeonseriously 5y ago
Back in the day, IIRC, you could set a sound blaster to generate white noise, then use that as either random number or input to your RNG algo.
rrauenza 5y ago
I'm trying to remember a technique based on listening to static or whitenoise and taking the least significant bit. You then take that stream of bits and postprocess it by looking for bit changes and don't use them directly. That's a vague and I'm sure inaccurate description, but it isn't enough for me to google it ... anyone know what I'm referring to?
- chipuni 5y ago
  That sounds a lot like what https://www.random.org/ https://www.random.org/ does to create random numbers.
  - rrauenza 5y ago
    Perhaps -- I can't find their description behind the process and I'm now curious about the math behind it. I think they would take a series of 0's and 1's.. 0010001110100100011 ...and map that into 0's and 1's based on the changes, not the numbers themselves. Maybe like 00 or 11 mapped to 0 and 10 or 01 mapped to 1? I can't recall.
    - denton-scratch 5y ago
      This sounds like the Von Neumann Extractor. https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor It's purpose is to remove bias: the propensity of physical random processes to produce more 1s than 0s (or v.v.). Unlike some whiteners (AES?) it can be implemented with a handful of gates.
      - rrauenza 5y ago
        Yes, that's it. And it's used to eliminate bias. I found a good explanation at https://www.youtube.com/watch?v=xquB4rDbsvc https://www.youtube.com/watch?v=xquB4rDbsvc at about 14min.
    - chipuni 5y ago
      random.org definitely uses that process. See: https://www.random.org/statistics/source-purity/ https://www.random.org/statistics/source-purity/
kerblang 5y ago
Did we ever resolve the flame war over /dev/random vs /dev/urandom? I recall puzzling over endless threads of no-you're-wrong
qq4 5y ago
I always wanted a Geiger counter for experiments like this.
- dragontamer 5y ago
  There's much cheaper, and easier, sources of white-noise. Anyone actually interested in the electronics of this should build a white-noise generator out of an Op-Amp + your favorite PN junction in reverse-bias mode (diode, BJT transistor, or whatever). Shot-noise from reverse-bias'd PN junctions is white noise at a quantum level. You're physically seeing the random electrons move across a junction that wasn't supposed to happen, and then amplifying those electrons up to levels we can detect (well... not our fingers to detect. But a fancy op-amp amplifier + arduino can detect). https://www.maximintegrated.com/en/design/technical-documents/app-notes/3/3469.html https://www.maximintegrated.com/en/design/technical-document... EDIT: This circuit from Maxim is reverse-breakdown noise from a Zener diode, which is more vigorous than shot-noise, and therefore easier to amplify. Its still white-noise and therefore "Truly random" up to the MHz. The circuit uses a Maxim voltage amplifier (I mean, the article is a big advertisement for how simple the MAX2650 is to use...)
  - jazzyjackson 5y ago
    Thank you, I was trying to find a guide to this that I lost long ago... but there is another step I remember to convert the analog noise into a digital signal, in order to replace /dev/random for instance. maybe you know the word I need to search for, it was something like using every two or three bits and anding or xoring them or whatever to magically erase any bias present in the shot noise, yielding a perfectly uniform distribution of 1s and 0s. I'd like to turn this into a circuit-building curriculum if I can find all the pieces again.
    - dragontamer 5y ago
      I don't know what your original tutorial said. There's many ways to do this problem. > maybe you know the word I need to search for, it was something like using every two or three bits and anding or xoring them or whatever to magically erase any bias present in the shot noise, yielding a perfectly uniform distribution of 1s and 0s. I forgot the name of this technique as well. Its rather simple: take the bitstream and look at it pairwise, you have 4 options: * 00 -- Throw away * 11 -- Throw away * 01 -- output 1 * 10 -- output 0 That's it. This always removes bias and returns a random 0 or 1 bit regardless of how biased the RNG is. 50% of outputs will be 0, and 50% of outputs will be 1. However, you're being "too smart for your own good" if you go down this route. A perfectly unbiased input would still have 50% of its inputs rejected, and already you've dropped the speed of the RNG by 50%. IMO: Signal processing is more obviously clean. Ultimately, you need to use analog techniques to finesse the white noise if you wanted to have assurances to the reliability of your RNG. You need to "clean up" the signal if you want the ADC / Input Pins to reliably read the data anyway, so making the analog circuitry a little bit more difficult (and maybe $1 more expensive) isn't a big deal. --------- I'd take the white-noise as a voltage-signal, and send it into a bandpass filter or a simple "notch" filter, lets say with 10MHz to 11MHz (named: filterA). filterA is then averaged across the last 100kHz (aka: 10 microseconds), which is just a simple low-pass filter (named: filterB). Finally: you compare filterA vs filterB (simple voltage comparator): filterA > filterB == 1, and filterA < filterB == 0. You'd safely be able to sample the data at 10MHz, or generate one bit every 100 nanoseconds. It'd be as simple as digitalRead(inPin) in Arduino (as long as the comparator outputs the voltage that's compatible with Arduino. You may need a level converter depending on how your comparator works). Bandpass filters are a complex subject of op-amps in of themselves, but are necessary parts of circuit design. The sooner you (and your students) are familiar with filter designs, the better. ------------ There might be some slight bias still (ex: if temperature is rising over time, or reducing over time), but I don't think there would be major amounts of bias. So bias-removal is still going to be useful. But don't use the technique described earlier: instead just AES-encrypt the input bits and then xor-it.
chipuni 5y ago
I just use the XKCD random number generator: https://xkcd.com/221/ https://xkcd.com/221/
mjreacher 5y ago
"Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin." - John von Neumann
anotherevan 5y ago
“The generation of random numbers is too important to be left to chance.” — Robert R. Coveyou
lscharen 5y ago
I'll take this opportunity to link to Luc Devroye's freely available book "Non-Uniform Random Variate Generation". http://www.nrbook.com/devroye/ http://www.nrbook.com/devroye/ An undergraduate algorithms + statistics class is sufficient to get a lot out of this book, even if it's just exposure to the wide variety of techniques for generating random numbers on a computer.
simonblack 5y ago
Two basic ways: Computed: NOT truly random. Way back in the late 70s, I had a BASIC program that used to output the very same set of 8-digit 'random' numbers every time the program was used. (Unless you did a special thing the first time, to obtain a random seed to generate a different sequence of pseudo-random numbers. IIRC, it was the number of machine cycles since the last time the floppy disk was accessed.) Hardware: Truly random: The machine counts machine cycles with a small maximum number before it overflows and restarts at zero. The machine looks at the time difference between things like key presses, or disk-spins, or something else that varies in time. No matter how good you are the variation in time between your key-presses is never the same at the very small time-flow level. That number is used as a seed to a pseudo-random generator.
Someone 5y ago
“The most common algorithms used for PRNGs are linear congruential generators” I doubt that is still true for ‘modern’ languages. Let’s google a few. https://docs.microsoft.com/en-us/dotnet/api/system.random?view=net-5.0 https://docs.microsoft.com/en-us/dotnet/api/system.random?vi... says “The current implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm”. So, that’s a no. https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html doesn’t appear to mention multiplicative algorithms, either. https://developer.apple.com/documentation/swift/systemrandomnumbergenerator https://developer.apple.com/documentation/swift/systemrandom... says “SystemRandomNumberGenerator is automatically seeded, is safe to use in multiple threads, and uses a cryptographically secure algorithm whenever possible.”
- sunny--tech 5y ago
  That's a good call out and I realize that was an error on my part. I meant to put in the Mersenne Twister but when I went back through my notes when I was writing, I misread that linear congruential generators were popular decades ago. I've edited that section.
dunefox 5y ago
I was asked to implement a random number generator in an interview not too long ago. This article should help...
- FabHK 5y ago
  Terrible interview question, imho.
  - dunefox 5y ago
    Not the only terrible one.
- actually_a_dog 5y ago
  I hope you were allowed to use some sort of reference material. Unless your previous work involved intimate familiarity with PRNGs, I would never expect anybody to be able to implement one on the spot, off the top of their heads. Even with reference material, I don't think I'd expect anything more involved than a linear congruential generator. Without reference material, probably the best I could do would be to read from one of the /dev/*random devices. I'm guessing that whatever the actual intention behind that question is that writing a function that essentially reads from a file doesn't match the expectation of the interviewer. :/ https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator
  - dunefox 5y ago
    No, no material, no background, just an interview with live coding for an entry level position because my minor was in computer science. "One out of a possible 1k algorithms" - half a dozen were asked.
jason_s 5y ago
I lost interest at "The most common algorithms used for PRNGs are linear congruential generators."

73 points by sunny--tech 5y ago

Writing your own random number generator can be a lot of fun. Lots of sources of entropy out there. Inspired by lavarand[0], I wrote an RNG in Python based on the output of the Global Conscousness Dot[1] (which is a ridiculous project in its own right). There's a lot of ways to visualize and ascertain how "random" your numbers are as well, whether plotting Pearson's with matplotlib or using a command line tool like ent[2] to calculate the degree of entropy. [0] https://en.wikipedia.org/wiki/Lavarand https://en.wikipedia.org/wiki/Lavarand [1] https://gcpdot.com/ https://gcpdot.com/ [2] https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html

pope_meat 5y ago
Hah, thanks for sharing this dot thing, what a bizarre little corner of the internet.
- xkeysc0re 5y ago
  Kind of wild to think that it was a project funded by Princeton and personally supported by their Dean of Engineering for decades!
atty 5y ago
From the GCP project: > The identification of events and the times at which they occur are specified case by case, as are the statistical recipes. The approach explicitly preserves some latitude of choice, as is appropriate for an experiment exploring new territory. Accepting loose criteria for event identification allows exploration of a variety of categories, while the specification of a rigorous, simple hypothesis test for each event in the formal series assures valid statistics. I’ve never seen someone so blatantly spell out that they are cherry picking, but also then argue that the cherry picking is good science ;) this is the sort of thing that gives real scientists a bad name.
Workaccount2 5y ago
I dug through the GCP dot page, and if I am understanding it correctly, their near-perfect RNGs have turned out to not be very random?

dragontamer 5y ago

A modern "pseudo random number" is simply a sequence of numbers that visits the state-space in an order that's difficult to detect with modern statistical tests. (Chi-squared, among others). See PractRand or TestU01 as two packages for testing these sequences. That is to say: instead of the sequence "0, 1, 2, 3, 4, 5... 4294967296... 0", your RNG will do some other sequence. Yes, "0, 3, 6, 9... 4294967295, 2, 5, 8... 4294967294, 1, 4, 7... 4294967293, 0, 3..." is a RNG of sorts, but an example of a really, really bad one that would instantly fail most statistical tests. :-) But conceptually, the Mersenne Twister, LCGRNG, and LSFR all accomplish this. Its a "reordering" of the sequence. That's it. A "cryptographic random number" just adds a few additional tests to the pool of statistical tests. In particular: differential cryptography gets into the nitty gritty about which bits can predict the results of other bits. You have to assume that the "opponent" is willing to use extraordinary amounts of computing power to detect patterns. If bit#25 has a 51% correlation with bit#30, you fail cryptographic random numbers. You need to be within 2^128 (at least) worth of security or more. That means a near 50% correlation (maybe 50.00000000001% is fine) between bits and future bits. For example: the sequence: {AES(0, key), AES(1, key), AES(2, key)... AES(2^128, key), AES(0, key)...} is a cryptographically secure random number generator. The sequence will loop after its 128 bits of state are exhausted. If the "opponent" doesn't know the key, the bitwise correlations are cryptographically sound (thanks to the hard work of the engineers behind AES). A true random number generator is just a cryptographic number generator applied to a truly random seed. White noise generators are a well known electronic-engineer trick: resistor noise is everywhere but is rather small (but you can build a white-noise generator from Johnson Nyquist noise if you really wanted). More likely, you use shot-noise from a transistor junction, at least at the hobbyist level. Intel / AMD have true random number generators from some kind of electrical noise generator on every CPU, which feeds into cryptographic random number generators. There are other sources of noise: radiation is a well known one but I'm not sure if they're practical. There's a "speed limit" to white noise generators. You only can extract so much entropy from them in a given time (ex: Remember: CPUs operate at 4GHz, or 0.25 nanoseconds per clock tick). Cryptographic random number generators "stretch" the true seed of randomness, while the white-noise generator continues to grab more entropy.

SavantIdiot 5y ago

Borrible 5y ago

Use leftovers. They're all over the Universe. https://www.researchgate.net/publication/283762433_The_Cosmic_Microwave_Background_Radiation_Power_Spectrum_as_a_Random_Bit_Generator_for_Symmetric_and_Asymmetric-Key_Cryptography https://www.researchgate.net/publication/283762433_The_Cosmi...

fnord77 5y ago

I thought this was a solved problem for at least a decade with CPU instructions like `RDRAND`

sodality2 5y ago
It's preferred to use RDSEED and use that as a seed, instead of implicitly trusting the output of RDRAND. Mix it with user entropy (or system entropy). Some say RDRAND is a backdoor (and after Dual EC, it would not particularly surprise me). This is why RDRAND doesn't exist in Linux (or, maybe isn't the only source of entropy?): https://www.linux-magazine.com/Online/News/Linus-Says-No-Backdoor-in-Linux https://www.linux-magazine.com/Online/News/Linus-Says-No-Bac... Not sure the security implications of using poisoned seeds in addition to truly random seeds in an RNG. Some say that it's okay, because it cannot reduce security, only not increase it. But if the CPU RDRAND instruction is backdoored, couldn't the RNG instructions be intercepted and replaced so that RDRAND is the only seed? But, if your CPU is backdoored, why even bother with anything? etc, etc etc. This discussion could go on for a while.
- foxfluff 5y ago
  > But if the CPU RDRAND instruction is backdoored, couldn't the RNG instructions be intercepted and replaced so that RDRAND is the only seed? If the CPU is going to detect and subvert your soft PRNG, it can do that whether you use RDRAND or not.
  - not2b 5y ago
    RDRAND is a microcoded instruction. The chipmaker does not publish that code, but they absolutely control what it does. If it has any flaws, whether deliberate or accidental, you can't fix them (the processor vendor might be able to fix it with a microcode update, but no one else can). That's why it isn't used. Your soft PRNG is an algorithm and a relatively simple one at that. You can test it, and verify that you get exactly the same sequence for a given seed whether you use a processor from Intel, AMD, ARM or someone else. Trying to detect and back door it would probably break a lot of other code. The bad guys would probably choose to attack you in a different way.

hdivider 5y ago

PCIe and USB cards like this are available, generating TRNs using quantum optics: https://www.idquantique.com/random-number-generation/products/quantis-random-number-generator/ https://www.idquantique.com/random-number-generation/product...

dekken_ 5y ago

some might say, it's impossible.

SavantIdiot 5y ago

I've been working with the NIST 800-22 evaluation suite [1] and yes, it is very hard. There are an infinite number of tests to determine if a number is random. Ultimately it comes down to probability that it is a good RNG/PRNG and the application. Ironically, if a PRNG is good enough, it can often be BETTER than a random source (which is why RNGs have a conditioning phase). [1] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documentation-and-Software/Guide-to-the-Statistical-Tests https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...

panax 5y ago
An infinite number of tests yes, it is like trying to find the best possible predictor of a source. No statistical test can prove that a source has full entropy and uniformly distributed, only disprove it. These tests are too often misused and are usually not very useful since they tell us nothing about how much entropy might be in the sample, and entropy sources are always biased anyway and fail the tests, and if you condition them then they will always pass the test even if not random at all. A better method is to develop a stochastic model of the entropy source and attempt to estimate bounds on the entropy, which is still generally not feasible. The statistical tests can then be used as a sanity check to verify your entropy estimates. The RNG needs a conditioning phase, or entropy extractor to transform the output into a distribution that is indistinguishable from uniform as is needed in cryptographic applications and you should always include this stage because virtually no physical entropy source has a uniform distribution. The best thing to do is to try to gather as much entropy as you can from sources and gather maybe 10x what you think you need and then put it through an entropy extractor like a cryptographic hash function to generate a PRNG seed then use the PRNG.
- kevincox 5y ago
  > No statistical test can prove that a source has full entropy and uniformly distributed, only disprove it. It can't disprove it either. It can only say if it is "likely to be random" or "appears to be random". A perfectly random source could generate a string of 1M zeros, and most statistical tests would fail it. But that is not proof that it isn't random. A second test would likely not generate all zeros and would likely pass.

sunny--tech 5y ago

Link to bypass paywall: https://betterprogramming.pub/generating-random-numbers-is-a-lot-harder-than-you-think-b121c3e75d08?source=friends_link&sk=508f781bd2b7e0fc279950284c5a49ae https://betterprogramming.pub/generating-random-numbers-is-a...

unnouinceput 5y ago
It didn't

abnry 5y ago

Obligatory XKCD: https://xkcd.com/221/ https://xkcd.com/221/ And also Dilbert: https://dilbert.com/search_results?terms=Random+Number+Generator https://dilbert.com/search_results?terms=Random+Number+Gener...

betwixthewires 5y ago

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.

comeonseriously 5y ago

Back in the day, IIRC, you could set a sound blaster to generate white noise, then use that as either random number or input to your RNG algo.

rrauenza 5y ago

I'm trying to remember a technique based on listening to static or whitenoise and taking the least significant bit. You then take that stream of bits and postprocess it by looking for bit changes and don't use them directly. That's a vague and I'm sure inaccurate description, but it isn't enough for me to google it ... anyone know what I'm referring to?

chipuni 5y ago
That sounds a lot like what https://www.random.org/ https://www.random.org/ does to create random numbers.
- rrauenza 5y ago
  Perhaps -- I can't find their description behind the process and I'm now curious about the math behind it. I think they would take a series of 0's and 1's.. 0010001110100100011 ...and map that into 0's and 1's based on the changes, not the numbers themselves. Maybe like 00 or 11 mapped to 0 and 10 or 01 mapped to 1? I can't recall.
  - denton-scratch 5y ago
    This sounds like the Von Neumann Extractor. https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor It's purpose is to remove bias: the propensity of physical random processes to produce more 1s than 0s (or v.v.). Unlike some whiteners (AES?) it can be implemented with a handful of gates.
    - rrauenza 5y ago
      Yes, that's it. And it's used to eliminate bias. I found a good explanation at https://www.youtube.com/watch?v=xquB4rDbsvc https://www.youtube.com/watch?v=xquB4rDbsvc at about 14min.
  - chipuni 5y ago
    random.org definitely uses that process. See: https://www.random.org/statistics/source-purity/ https://www.random.org/statistics/source-purity/

kerblang 5y ago

Did we ever resolve the flame war over /dev/random vs /dev/urandom? I recall puzzling over endless threads of no-you're-wrong

qq4 5y ago

I always wanted a Geiger counter for experiments like this.

dragontamer 5y ago
There's much cheaper, and easier, sources of white-noise. Anyone actually interested in the electronics of this should build a white-noise generator out of an Op-Amp + your favorite PN junction in reverse-bias mode (diode, BJT transistor, or whatever). Shot-noise from reverse-bias'd PN junctions is white noise at a quantum level. You're physically seeing the random electrons move across a junction that wasn't supposed to happen, and then amplifying those electrons up to levels we can detect (well... not our fingers to detect. But a fancy op-amp amplifier + arduino can detect). https://www.maximintegrated.com/en/design/technical-documents/app-notes/3/3469.html https://www.maximintegrated.com/en/design/technical-document... EDIT: This circuit from Maxim is reverse-breakdown noise from a Zener diode, which is more vigorous than shot-noise, and therefore easier to amplify. Its still white-noise and therefore "Truly random" up to the MHz. The circuit uses a Maxim voltage amplifier (I mean, the article is a big advertisement for how simple the MAX2650 is to use...)
- jazzyjackson 5y ago
  Thank you, I was trying to find a guide to this that I lost long ago... but there is another step I remember to convert the analog noise into a digital signal, in order to replace /dev/random for instance. maybe you know the word I need to search for, it was something like using every two or three bits and anding or xoring them or whatever to magically erase any bias present in the shot noise, yielding a perfectly uniform distribution of 1s and 0s. I'd like to turn this into a circuit-building curriculum if I can find all the pieces again.
  - dragontamer 5y ago
    I don't know what your original tutorial said. There's many ways to do this problem. > maybe you know the word I need to search for, it was something like using every two or three bits and anding or xoring them or whatever to magically erase any bias present in the shot noise, yielding a perfectly uniform distribution of 1s and 0s. I forgot the name of this technique as well. Its rather simple: take the bitstream and look at it pairwise, you have 4 options: * 00 -- Throw away * 11 -- Throw away * 01 -- output 1 * 10 -- output 0 That's it. This always removes bias and returns a random 0 or 1 bit regardless of how biased the RNG is. 50% of outputs will be 0, and 50% of outputs will be 1. However, you're being "too smart for your own good" if you go down this route. A perfectly unbiased input would still have 50% of its inputs rejected, and already you've dropped the speed of the RNG by 50%. IMO: Signal processing is more obviously clean. Ultimately, you need to use analog techniques to finesse the white noise if you wanted to have assurances to the reliability of your RNG. You need to "clean up" the signal if you want the ADC / Input Pins to reliably read the data anyway, so making the analog circuitry a little bit more difficult (and maybe $1 more expensive) isn't a big deal. --------- I'd take the white-noise as a voltage-signal, and send it into a bandpass filter or a simple "notch" filter, lets say with 10MHz to 11MHz (named: filterA). filterA is then averaged across the last 100kHz (aka: 10 microseconds), which is just a simple low-pass filter (named: filterB). Finally: you compare filterA vs filterB (simple voltage comparator): filterA > filterB == 1, and filterA < filterB == 0. You'd safely be able to sample the data at 10MHz, or generate one bit every 100 nanoseconds. It'd be as simple as digitalRead(inPin) in Arduino (as long as the comparator outputs the voltage that's compatible with Arduino. You may need a level converter depending on how your comparator works). Bandpass filters are a complex subject of op-amps in of themselves, but are necessary parts of circuit design. The sooner you (and your students) are familiar with filter designs, the better. ------------ There might be some slight bias still (ex: if temperature is rising over time, or reducing over time), but I don't think there would be major amounts of bias. So bias-removal is still going to be useful. But don't use the technique described earlier: instead just AES-encrypt the input bits and then xor-it.

chipuni 5y ago

I just use the XKCD random number generator: https://xkcd.com/221/ https://xkcd.com/221/

mjreacher 5y ago

"Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin." - John von Neumann

anotherevan 5y ago

“The generation of random numbers is too important to be left to chance.” — Robert R. Coveyou

lscharen 5y ago

I'll take this opportunity to link to Luc Devroye's freely available book "Non-Uniform Random Variate Generation". http://www.nrbook.com/devroye/ http://www.nrbook.com/devroye/ An undergraduate algorithms + statistics class is sufficient to get a lot out of this book, even if it's just exposure to the wide variety of techniques for generating random numbers on a computer.

simonblack 5y ago

Two basic ways: Computed: NOT truly random. Way back in the late 70s, I had a BASIC program that used to output the very same set of 8-digit 'random' numbers every time the program was used. (Unless you did a special thing the first time, to obtain a random seed to generate a different sequence of pseudo-random numbers. IIRC, it was the number of machine cycles since the last time the floppy disk was accessed.) Hardware: Truly random: The machine counts machine cycles with a small maximum number before it overflows and restarts at zero. The machine looks at the time difference between things like key presses, or disk-spins, or something else that varies in time. No matter how good you are the variation in time between your key-presses is never the same at the very small time-flow level. That number is used as a seed to a pseudo-random generator.

Someone 5y ago

“The most common algorithms used for PRNGs are linear congruential generators” I doubt that is still true for ‘modern’ languages. Let’s google a few. https://docs.microsoft.com/en-us/dotnet/api/system.random?view=net-5.0 https://docs.microsoft.com/en-us/dotnet/api/system.random?vi... says “The current implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm”. So, that’s a no. https://rust-random.github.io/book/guide-rngs.html https://rust-random.github.io/book/guide-rngs.html doesn’t appear to mention multiplicative algorithms, either. https://developer.apple.com/documentation/swift/systemrandomnumbergenerator https://developer.apple.com/documentation/swift/systemrandom... says “SystemRandomNumberGenerator is automatically seeded, is safe to use in multiple threads, and uses a cryptographically secure algorithm whenever possible.”

sunny--tech 5y ago
That's a good call out and I realize that was an error on my part. I meant to put in the Mersenne Twister but when I went back through my notes when I was writing, I misread that linear congruential generators were popular decades ago. I've edited that section.

dunefox 5y ago

I was asked to implement a random number generator in an interview not too long ago. This article should help...

FabHK 5y ago
Terrible interview question, imho.
- dunefox 5y ago
  Not the only terrible one.
actually_a_dog 5y ago
I hope you were allowed to use some sort of reference material. Unless your previous work involved intimate familiarity with PRNGs, I would never expect anybody to be able to implement one on the spot, off the top of their heads. Even with reference material, I don't think I'd expect anything more involved than a linear congruential generator. Without reference material, probably the best I could do would be to read from one of the /dev/*random devices. I'm guessing that whatever the actual intention behind that question is that writing a function that essentially reads from a file doesn't match the expectation of the interviewer. :/ https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator
- dunefox 5y ago
  No, no material, no background, just an interview with live coding for an entry level position because my minor was in computer science. "One out of a possible 1k algorithms" - half a dozen were asked.

jason_s 5y ago

I lost interest at "The most common algorithms used for PRNGs are linear congruential generators."