[HN Gopher] How do computers generate random numbers?
___________________________________________________________________
How do computers generate random numbers?
Author : sunny--tech
Score : 47 points
Date : 2021-09-08 15:16 UTC (7 hours ago)
(HTM) web link (betterprogramming.pub)
(TXT) w3m dump (betterprogramming.pub)
| dekken_ wrote:
| some might say, it's impossible.
| rrauenza wrote:
| 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 wrote:
| That sounds a lot like what https://www.random.org/ does to
| create random numbers.
| rrauenza wrote:
| 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.
| SavantIdiot wrote:
| 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/Documen...
| panax wrote:
| 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 wrote:
| > 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.
| SavantIdiot wrote:
| > A perfectly random source could generate a string of 1M
| zeros,
|
| I you sample the thermal noise of the transistor used in
| your RNG too quickly you can get 1M zeroes. :)
| [deleted]
| xkeysc0re wrote:
| 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
|
| [1] https://gcpdot.com/
|
| [2] https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html
| Workaccount2 wrote:
| 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?
| pope_meat wrote:
| Hah, thanks for sharing this dot thing, what a bizarre little
| corner of the internet.
| xkeysc0re wrote:
| Kind of wild to think that it was a project funded by
| Princeton and personally supported by their Dean of
| Engineering for decades!
| atty wrote:
| 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.
| sunny--tech wrote:
| Link to bypass paywall: https://betterprogramming.pub/generating-
| random-numbers-is-a...
| unnouinceput wrote:
| It didn't
| dragontamer wrote:
| 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 wrote:
| PRNGs can actually be better than true RNGs, which is why RNGs
| generally provide a seed for a DRBG. RNG conditioning has to do
| things like remove extremely long series of 1's or 0's, and
| RNGs often cannot generate enough material fast enough for
| today's demands (e.g, <1Kbps).
| MauranKilom wrote:
| > Its a "reordering" of the sequence. That's it.
|
| Technically a PRNG state sequence could also have distinct
| loops, returning a reordering of only a subset of the sequence
| for any given seed. For example, `return state += 2;` would
| return two separate sequences for odd or even seeds. We know
| that a PRNG with N bits of state must necessarily repeat after
| 2^N invocations, but it requires further proof that a given
| PRNG will not repeat at smaller intervals.
|
| > 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.
|
| In light of the above, is it possible to prove this (through
| some property of AES)?
|
| (Also, we can't really prove that AES, or any other current
| algorithm, is cryptographically secure. Tomorrow, a new
| cryptanalysis technique could be revealed which breaks it.)
| dragontamer wrote:
| > (Also, we can't really prove that AES, or any other current
| algorithm, is cryptographically secure. Tomorrow, a new
| cryptanalysis technique could be revealed which breaks it.)
|
| Yeah, "Cryptographically secure" just means "according to
| currently published literature, no one has yet found a
| correlation between bits that leads to a faster than a 2^128
| attack on the key"
|
| Tomorrow, it might be broken. But AES has been around for a
| while, so its unlikely to break tomorrow. IIRC, the furthest
| anyone has gotten is like breaking 4-rounds of AES (out of
| 8).
| dragontamer wrote:
| > We know that a PRNG with N bits of state must necessarily
| repeat after 2^N invocations, but it requires further proof
| that a given PRNG will not repeat at smaller intervals.
|
| Yes, that's somewhat important for "smaller" 64-bit or
| 128-bit states.
|
| But at 512-bit states, the "average loop" is 2^256 (birthday
| paradox), so no one really cares at that point. We can see
| that Mersenne Twister is overprovisioned: 19937 bits of state
| and all 2^19937 visited in some order.
|
| But in practice, 64-bits worth of cycles (18-quintrillion) is
| sufficient for single-threaded simulations, and 128-bits is
| sufficient for multithreaded simulations.
|
| > In light of the above, is it possible to prove this
| (through some property of AES)?
|
| Yeah. AES is a block cipher that maps 128 bit blocks into
| "encrypted" 128-bit blocks. The reverse-AES (I'll call it
| unAES in this post) provides us the 1-to-1 unmapping as well.
|
| Meaning unAES(AES(0, key), key) == 0. unAES(AES(1, key), key)
| == 1. unAES(AES(2, key), key) == 2. (Etc. etc. for all
| possible 2^128 blocks)
|
| By the pidgeon-hole principle, we have 2^128 blocks
| associated with AES-encrypted blocks (named AES(0, key),
| AES(1, key)... AES(2^128-1, key)), and 2^128 blocks
| associated with our plaintexts (0, 1, 2, 3... 2^128-1). The
| only way all 2^128 map to each other is through a 1-to-1
| bijection.
|
| Or in another way: AES(X, key) == AES(Y, key) if-and-only-if
| X == Y. This is because deAES(AES(X, key), key) ==
| deAES(AES(Y, key), key) if-and-only if X == Y.
|
| Done. We know the AES-crypto method therefore only "loops"
| after 2^128, exploring the entire state-space. 2^128 possible
| inputs, 2^128 possible outputs, pigeonhole principle. QED,
| done.
| mjreacher wrote:
| "Anyone who attempts to generate random numbers by deterministic
| means is, of course, living in a state of sin."
|
| - John von Neumann
| qq4 wrote:
| I always wanted a Geiger counter for experiments like this.
| dragontamer wrote:
| 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-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 wrote:
| 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 wrote:
| 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.
| lkozma wrote:
| > 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%.
|
| To improve this situation you can use an additional
| trick: keep track of the sequence of thrown-away pairs,
| and look at them again in consecutive pairs, and generate
| some more random bits:
|
| * 00 00 -- throw away
|
| * 11 11 -- throw away
|
| * 00 11 -- output 1
|
| * 11 00 -- output 0
|
| and so on..
|
| see the paper "Iterating Von Neumann's Procedure for
| Extracting Random Bits" for details.
| comeonseriously wrote:
| 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.
| betwixthewires wrote:
| 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.
| dllthomas wrote:
| > 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.
| SilasX wrote:
| >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 wrote:
| 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.
| SilasX wrote:
| >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.
| Jerrrry wrote:
| 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 wrote:
| 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 wrote:
| In many cases the next problem would be what to use
| instead. The alternatives aren't too great either.
| IntrepidWorm wrote:
| Suggestion: Every device has a built in lava lamp that we
| process into visual noise... Bring the 70's back in a big
| way.
| hinkley wrote:
| 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.
| sunny--tech wrote:
| 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 wrote:
| 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 wrote:
| 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.
| postalrat wrote:
| > 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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.
| Borrible wrote:
| Use leftovers. They're all over the Universe.
|
| https://www.researchgate.net/publication/283762433_The_Cosmi...
| chipuni wrote:
| I just use the XKCD random number generator:
|
| https://xkcd.com/221/
| lscharen wrote:
| I'll take this opportunity to link to Luc Devroye's freely
| available book "Non-Uniform Random Variate Generation".
|
| 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.
| fnord77 wrote:
| I thought this was a solved problem for at least a decade with
| CPU instructions like `RDRAND`
| sodality2 wrote:
| 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-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 wrote:
| > 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 wrote:
| 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 wrote:
| PCIe and USB cards like this are available, generating TRNs using
| quantum optics:
|
| https://www.idquantique.com/random-number-generation/product...
| kerblang wrote:
| Did we ever resolve the flame war over /dev/random vs
| /dev/urandom? I recall puzzling over endless threads of no- _you
| 're_-wrong
| anotherevan wrote:
| "The generation of random numbers is too important to be left to
| chance." -- Robert R. Coveyou
| simonblack wrote:
| 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.
| abnry wrote:
| Obligatory XKCD: https://xkcd.com/221/
|
| And also Dilbert:
| https://dilbert.com/search_results?terms=Random+Number+Gener...
___________________________________________________________________
(page generated 2021-09-08 23:01 UTC)