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.
> 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.
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.
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).
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.)
> 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.
> (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).
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).
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.
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.
The issue isn't whether RDRAND is backdoored; it's that the output from the RDRAND circuitry is fed directly to an AES whitener, and the only thing you can test about the RDRAND output is the whitened output from AES.
Well, the output from AES is by definition indistinguishable from randomness, unless you have the key. So to test a TRNG, you need access to the input to the whitener. Intel doeesn't provide that access. So the hardware might be producing a continuous stream of zeroes, and you'd never know from examining the output of the whitener.
I believe Intel chips with RDRAND have been inspected using electron microscopes, and no flaw has been found in the hardware (I think it's two free-running oscillators whose outputs are sampled and XORed).
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).
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.
> 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.
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.
> No, you didn't. That number is most certainly not random, there are biases in it, you just don't know there are. Your mind is not random. This is why we use dice and not people to generate random bits.
Can't you say that any single (shortish) number is random? How you can demonstrate 99999999999999999999 isn't random?
Just looking at it with your eyes you can't. But there are statistical analysis techniques used to find bias in random numbers, patterns in random numbers generated using the same RNG and this is often used to demonstrate that some technique or generator is broken and cryptographically insecure. If a 128 bit number doesn't provide 128 bits of security then something in the generation of that number is broken.
There are other comments in this thread that get into some nitty gritty details of this that I don't pretend to be an expert on.
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.
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.
Many devices already have hardware sources of randomness built in. The problem is just that they are unverifiable and built by companies that have shown themselves to be untrustworthy.
No, the problem is that the built in sources aren’t funky enough ;)
In all seriousness, though, yes and guaranteeing that the manufacturing process itself can “bake” in the randomness is a super interesting area of research. It’s like 99% of the manufacturing process is an exercise in reducing variability, and then there’s PUFs, where you’re basically trying to maximize variability, but in such a way that you maintain computational precision.
There are great alternatives in principle. The problem is incentives to sabotage alternatives by governments and manufacturers. There are chips that produce real entropy, and processors come with integrated hardware for this purpose. The problem is that you don't know if the hardware is deliberately flawed in some way.
Specifically, PRNGs based on cryptographic algorithms (CSPRNGs) resist loss of existing entropy from having new, low entropy sources appended to the stream.
To my thinking, what is more important is that you don’t fool yourself about the amount of entropy from one source, or among sources. Two entropy sources that are dependent variables may be good separately but not together. Like the timings of keystrokes and network packets may be affected by the scheduler, or the fact that you are typing into a remote editor session which is bouncing ACKs back, or auto saving every time you hit enter or change focus.
Yes I'm aware that there's an ongoing debate about whether a human, or anything for that matter, can truly be random. But I wasn't going to bring this up in this article, or add caveats to every single point, or else this would've been unbearable to read.
I used artistic license in certain instances. But I agree some things could've been worded better and I'll edit those.
Oh no man, I'm not picking on you. This is an excellent article to explain the basics of random number generation. If you'd gotten into the weeds on it it wouldn't be as accessible.
There is important terminology in the world of all this stuff though, particularly "not all random numbers are the same" can confuse someone who then begins learning more about it.
>No, you didn't. That number is most certainly not random, there are biases in it, you just don't know there are.
Isn't that true of CSPRNGs as well, though? One of them may have some huge flaw that allows it to be predicted, we just don't know what it is yet.
(I think you basically agree with this in your last paragraph?)
More generally, when we ask for a random number, what we're usually looking for is a number uncorrelated with some other number. For example, when you're doing an experiment, the purpose of the randomization is to ensure that you're not really capturing some other effect that was setting which parameters were placed together.
That is, if you're deciding to run the control vs test case because of subtle fluctuations in the room's lighting (that you're unaware are influencing you), then you may have no effect at all, but you accidentally pick up an effect which was really due to the lighting, not to the thing you're trying to test. Using a dice roll prevents this, not because of randomization per se, but because it reliably breaks other correlations that might seep into the experiment.
To the extent that a human randomizer meets that in one particular domain, it may be good enough (not that you were saying otherwise). It's just ... you'd rather not bet on that being true in any given case.
Well, I'm referencing a "random" number generated in someone's head, not one generated by a CSPRNG. But with regard to CSPRNGs, an implementation can have a flaw, and we have seen these sorts of things happen, a well known example is MD5, a hash function, which are similar in principle to PRNGs, was broken.
My last paragraph basically amounts to if any of the axioms used for constructing any crypto are false then all cryptography based on them is breakable and this is not specific to any implementation. If they're not false, proper implementation works, and implementation details are more important. In principle, just using a provably random TRNG to generate a seed and then using a properly implemented CSPRNG to generate numbers from the seed, as long as the seed is provably destroyed the numbers are indistinguishable from random numbers. This is not true of "randomness" generated by the human brain. "You'd rather not bet on that being true" is exactly right, theoretically a human could produce a truly random number, but the likelihood is very low that no predictable external influence went into that process compared to using noise generated by the chaotic universe.
>Well, I'm referencing a "random" number generated in someone's head, not one generated by a CSPRNG.
What is that responding to? I thought I made the distinction between which one I was addressing pretty clear.
>But with regard to CSPRNGs, an implementation can have a flaw, and we have seen these sorts of things happen, a well known example is MD5, a hash function, which are similar in principle to PRNGs, was broken.
True, but my point was that the algorithm can itself be flawed, even if implemented correctly.
The point being, yes, you have Knightian uncertainty about the real factors that cause human-generated random numbers ... but you also have Knightian uncertainty about the existence of undiscovered flaws in your algorithm.
Yes, you're much less likely to run into the flaw if you're using a CSPRNG based on a high-entropy source, but in both cases it's true, or at least, impossible to rule out, that "there are biases in it, you just don't know there are."
Edit: And, FWIW, there aren't usable cryptosystems based on P=NP, which would actually be an improvement! Most are based on the far stronger assumption that certain "NP-intermediate" problems aren't feasibly solveable.
> 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.
> 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.
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.
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?
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.
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.
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).
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...)
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.
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.
> 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.
It gives you a continuously-varying output voltage. To get random numbers, you have to sample the output (presumably using a clock of some kind), and compare the sample with some reference (e.g. using a comparator).
How often you can sample depends on the bandwidth of the analogue noise-source. You still need to debias, and probably whiten as well. That's digital circuitry, and it's hard to make analogue and digital circuitry play nicely together on the same circuit board; the digital part tends to influence the analogue part through the power lines.
> That's digital circuitry, and it's hard to make analogue and digital circuitry play nicely together on the same circuit board; the digital part tends to influence the analogue part through the power lines.
Yeah. We can fortunately handwave a lot of those issues away by:
1. Working with an Arduino, which only has a 20MHz clock (best case), maybe 4MHz typical scenario.
2. Filtering down the white-noise to the Arduino-level speeds. (Note: Arduino / ATMega328pb ADC clock is only a fraction of its primary clock).
After all: sampling at 100MHz (generating a bit every 10 nanoseconds) would be very difficult! But sampling this at 1MHz is really easy, and probably could be done on a breadboard and hobby equipment.
It'd still be noisy as all heck, but running things slowly and at 5V will solve a lot of issues that faster clocks make difficult. You don't care about 100MHz noise when your circuits are only 1MHz!!
--------
Now if someone actually wanted that 100MHz (10 nanosecond) random bit generator... okay. That's tough. Now we gotta talk about ADC / High Speed Comparators, high-frequency / more expensive buffers / filters / opamps, miniscule errors, well done PCB-circuits, maybe even transmission line theory, large planes of copper to stabilize circuits... power-network filtering... etc. etc.
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.
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.
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 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. :/
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.
80 comments
[ 8.1 ms ] story [ 133 ms ] thread[0] https://en.wikipedia.org/wiki/Lavarand
[1] https://gcpdot.com/
[2] https://manpages.ubuntu.com/manpages/bionic/man1/ent.1.html
> 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.
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.
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.)
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.
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).
https://www.researchgate.net/publication/283762433_The_Cosmi...
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.
If the CPU is going to detect and subvert your soft PRNG, it can do that whether you use RDRAND or not.
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.
Well, the output from AES is by definition indistinguishable from randomness, unless you have the key. So to test a TRNG, you need access to the input to the whitener. Intel doeesn't provide that access. So the hardware might be producing a continuous stream of zeroes, and you'd never know from examining the output of the whitener.
I believe Intel chips with RDRAND have been inspected using electron microscopes, and no flaw has been found in the hardware (I think it's two free-running oscillators whose outputs are sampled and XORed).
How about always returning 0xffffffff? https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...
How about a bunch of collisions? https://github.com/systemd/systemd/issues/18184
Thanks, AMD...
https://www.idquantique.com/random-number-generation/product...
[1] https://csrc.nist.gov/Projects/Random-Bit-Generation/Documen...
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.
I you sample the thermal noise of the transistor used in your RNG too quickly you can get 1M zeroes. :)
And also Dilbert: https://dilbert.com/search_results?terms=Random+Number+Gener...
> "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.
Can't you say that any single (shortish) number is random? How you can demonstrate 99999999999999999999 isn't random?
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.
You can not. Randomness is a property of the procedure used to generate it, not the number.
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.
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.
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.
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.
I used artistic license in certain instances. But I agree some things could've been worded better and I'll edit those.
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.
"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.
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.
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.
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.
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.
Indeed. In that specific example, the author generated 24 binary digits, but only on 7 occasions was the digit the same as the previous digit. There were 23 opportunities to do so, and in a truly random sequence of digits the chance of any digit being the same as the previous one is 50%.
Applying the binomial distribution, the probability of observing 7 or fewer repeats with 23 trials and a 50% chance on each trial is only 4%. So with p = 0.04, we can reject the null hypothesis that the author's generated sequence is random, and conclude that it is biased.
There are online demos where you can try this yourself: https://people.ischool.berkeley.edu/~nick/aaronson-oracle/in...
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?
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.
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.
I found a good explanation at https://www.youtube.com/watch?v=xquB4rDbsvc at about 14min.
See: https://www.random.org/statistics/source-purity/
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...)
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.
> 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.
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.
It gives you a continuously-varying output voltage. To get random numbers, you have to sample the output (presumably using a clock of some kind), and compare the sample with some reference (e.g. using a comparator).
How often you can sample depends on the bandwidth of the analogue noise-source. You still need to debias, and probably whiten as well. That's digital circuitry, and it's hard to make analogue and digital circuitry play nicely together on the same circuit board; the digital part tends to influence the analogue part through the power lines.
Yeah. We can fortunately handwave a lot of those issues away by:
1. Working with an Arduino, which only has a 20MHz clock (best case), maybe 4MHz typical scenario.
2. Filtering down the white-noise to the Arduino-level speeds. (Note: Arduino / ATMega328pb ADC clock is only a fraction of its primary clock).
After all: sampling at 100MHz (generating a bit every 10 nanoseconds) would be very difficult! But sampling this at 1MHz is really easy, and probably could be done on a breadboard and hobby equipment.
It'd still be noisy as all heck, but running things slowly and at 5V will solve a lot of issues that faster clocks make difficult. You don't care about 100MHz noise when your circuits are only 1MHz!!
--------
Now if someone actually wanted that 100MHz (10 nanosecond) random bit generator... okay. That's tough. Now we gotta talk about ADC / High Speed Comparators, high-frequency / more expensive buffers / filters / opamps, miniscule errors, well done PCB-circuits, maybe even transmission line theory, large planes of copper to stabilize circuits... power-network filtering... etc. etc.
https://xkcd.com/221/
- John von Neumann
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.
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.
I doubt that is still true for ‘modern’ languages. Let’s google a few.
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 doesn’t appear to mention multiplicative algorithms, either.
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.”
I've edited that section.
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