Researchers Build True Random Number Generator From Carbon Nanotubes (ieee.org)

Wave723 writes: IEEE Spectrum reports on a true random number generator that was created with single-walled semiconducting carbon nanotubes. Researchers at Northwestern University printed a SRAM cell with special nanotube ink, and used it to generate random bits based on thermal noise. This method could be used to improve the security of flexible or printed electronics. From the report: "Once Mark Hersam, an expert in nanomaterials at Northwestern University, and his team had printed their SRAM cell, they needed to actually generate a string of random bits with it. To do this, they exploited a pair of inverters found in every SRAM cell. During normal functioning, the job of an inverter is to flip any input it is given to be the opposite, so from 0 to 1, or from 1 to 0. Typically, two inverters are lined up so the results of the first inverter are fed into the second. So, if the first inverter flips a 0 into a 1, the second inverter would take that result and flip it back into a 0. To manipulate this process, Hersam's group shut off power to the inverters and applied external voltages to force the inverters to both record 1s. Then, as soon as the SRAM cell was powered again and the external voltages were turned off, one inverter randomly switched its digit to be opposite its twin again. 'In other words, we put [the inverter] in a state where it's going to want to flip to either a 1 or 0,' Hersam says. Under these conditions, Hersam's group had no control over the actual nature of this switch, such as which inverter would flip, and whether that inverter would represent a 1 or a 0 when it did. Those factors hinged on a phenomenon thought to be truly random -- fluctuations in thermal noise, which is a type of atomic jitter intrinsic to circuits." Hersam and his team recently described their work in the journal Nano Letters.

Comments

Random Number

[rossdee]

42

Re:Random Number

[TeknoHog]

42

// chosen by fair dice roll. guaranteed to be random.

Re:Random Number

[Anonymous Coward]

http://dilbert.com/strip/2001-10-25

Re:Random Number

[Oswald McWeany]

42

// chosen by fair dice roll. guaranteed to be random.

Dice aren't perfectly random though.

Re:Random Number

[jellomizer]

I am not sure of the benefit purpose of a pure random generation. Or concept of data encryption relies on the fact that we can get the same random numbers, given the correct key. Now we can improve on the randomness of these numbers so the next value will be less predictable, but it will still need to be reproducible for so the system can decrypt the data.

Other uses of random data, for the most part seem random enough, and most of the problems seems to just be from poor implementation of existing random number generation.

Re:Random Number

[pem]

A random number is for generating the key, not using it.

Re:Random Number

[rgbatduke]

There are three meanings of the word "random" referring to a generator in this context:

a) Unpredictable.
b) Empirically satisfying all of the decorrelation properties of a random number sequence -- on average uniform in all bit patterns, on average lacking correlations at all lags (and hence non-periodic) and on all N-dimensional hyperplanes for all N, etc.
c) Both.

All that is asserted here is that they have a thermal noise generator that satisfies a). Big whoop -- thermal noise generators (and hardware generators in general) are commonplace: https://en.wikipedia.org/wiki/.... However, thermal noise and so on are often "colored" or "biased" -- they produce fluctuations that are unpredictable but it is almost impossible to get the noise to produce a string of e.g. 0's and 1's that satisfy b). One then is stuck using the unpredictable noise to randomize a pseudorandom number generator (for example, by xor'ing the two together) that produces a bit string that has the right uniformity and decorrelation properties but does so from an internal state that, if known, makes the string produced predictable.

AGAIN this sort of thing is pretty commonplace. Sources of "entropy" as in unpredictable activity are common enough and so are high quality pseudorandom number generators. The major problem then is rate. Few of the hardware generators can produce entropy FAST ENOUGH to keep up with a PRNG, so getting a source of "true random numbers" that is fast enough to use in e.g. Monte Carlo is not easy, and most people don't bother to try. Having a handful of unpredictable numbers suffices for e.g. encryption and that's really where this is headed.

I would wax poetic on the fact that EVEN thermal noise is probably not truly random; it is random the way a coin flip is random or, for that matter, the way a PRNG is random. The outcome of a coin flip is unpredictable only because we don't flip the coin with a precise knowledge of its state and the state of the flip environment and because we perhaps cannot integrate its equations of motion precisely enough from what knowledge we do have, but it is deterministic, hence not really unpredictable. Classical thermal noise is no different than a bunch of flipping coins bouncing around -- again deterministic but with lots of unknown state information. "True" random is a term that should probably be provisionally reserved to AT BEST quantum "coin flips", although in the master equation approach to resolving the state of a quantum "coin", the true origin of randomness is seen STILL to be the process of taking the trace of the surrounding environment, which is if you like the filter resolving the flip. That trace introduces "entropy" in the form of lost phase information and averaging over energy distributions that appears as unpredictability in the outcome, but if one views the "coin" AND the surroundings as a single quantum system its quantum trajectory is again deterministic. Randomness in quantum filtering experiments comes from the fact that the measuring apparatus that does the filtering must resolve it in a classical was with its quantum entangling and phases in general unknown and averaged over.

If one buys the holographic model in string theory (or plain old quantum theory as it is currently structured) the Universe is in a zero entropy state and there are no sources of "real" entropy. In this case there can BE no "true" random number generators. Whether or not nature is capable of generating true random numbers from some source other than our ignorance of state is an open empirical question.

Re:Random Number

[Myrdos]

In this case there can BE no "true" random number generators. Whether or not nature is capable of generating true random numbers from some source other than our ignorance of state is an open empirical question.

If we can prove there's no way to know the entire state, say via Heisenberg uncertainty principle, then there is no functional difference between 'true' randomness and randomness-through-ignorance. I'm not sure if the question has any meaning.

Re:Random Number

[cellocgw]

// chosen by fair dice roll. guaranteed to be random.

Dice aren't perfectly random though.

But fair dice are. Read, then post.

Re:Random Number

[sexconker]

Random has one true definition: Without cause.

As far as we know, it's impossible for true randomness to exist. Our Universe runs on causality. There are things we don't yet fully understand, and things that appear to operate in an unpredictable way, but there's no actual evidence that they do so in violation of causality, no evidence of the Universe being a simulation, no evidence of there being infinitely many Universes, etc.

If something has a cause, then it can be predicted and patterns can be identified. It is not random.

Re: Random Number

[jcfandino]

That's a big dice!

Re:Random Number

[TechyImmigrant]

There'a a difference, but you can't tell.

The difference becomes relevant in 'quantum secure entropy extractors' which are designed to be secure against 'maximally entangled adversaries'. I.E. Something that does know the state. With non determinism in the universe, quantum secure extractors can be built. In a deterministic universe, they cannot.

Re:Random Number

[rgbatduke]

If something has a cause, then it can be predicted and patterns can be identified. It is not random.

Except that there are phenomena that cannot be predicted. Even ones we know are not really random. Then there are quantum phenomena that MAY be really random. You are making a religious statement when you assert Universal causality as a definite truth instead of a conditional probability. And lack of evidence is not evidence of lack -- the best you can say is that it might make something less probable within certain bounds.

I agree that the Universe PROBABLY is causal and in a zero entropy state, because we have little definite evidence otherwise (time-irreversibility of things like Kaon and B decay aside, a few experiments that claim to demonstrate "true" quantum randomness aside). But according to science this is an empirical question, not a religious one. You might as well assert that as far as we know, it IS possible for true randomness to exist.

On the empirical note, if you are presented with a string of data, perform any and all tests on it that you like, and cannot prove that it is NOT random, what exactly is that evidence of? Please do not invoke religion in your answer such as a belief in causality, as that just begs the question. That's precisely what you are doing if you assert that quantum phenomena at a certain scale are not random. Maybe not, but we have no model that predicts them, we have theories that suggest that no model CAN predict them, when we examine them for randomness they appear random. The arguments (such as the arguments that lead to the Master Equation description of quantum phenomena) that allow for it to be otherwise are difficult and while they may be correct, it is far from certain (empirically) that they are.

Re:Random Number

[Quatermass]

Heck we used to use common Zenor Diodes to generate noise. Hardly new.

Re: Random Number

[KGIII]

You... I like you.

Throughout history, we have thought many things were random. In some cases, we decided that those acts had been done by gods. I am not sure random even exists. Traditionally, it has just meant poorly understood, even though we worded it differently. Bell's Theorum can get fucked.

Re: Random Number

[rgbatduke]

Well, not "get fucked", surely...

Ultimately it is an empirical question but it is an unusual one. The problem with looking only at locality in a single direction of time flow is that the underlying microdynamic propagators are (without exception as far as I know) reversible in time. My favorite example of this is in classical electrodynamics, where we CHOOSE to use retarded propagators, but where one can equally well formulate things in terms of advanced propagators and where Dirac did an amazing job of deriving radiation reaction theory using a mixture of advanced and retarded propagators (further supported by Wheeler and Feynman and the perfect absorber derivation which in turn is connected to Lindblad and master equation formulations of quantum theory).

This is where IMO it is very difficult to understand Bell's theorem. It seems to require forward (retarded) time only, but if one allows for advanced time as well as retarded time both operating simultaneously, the paradoxes disappear. It becomes literally impossible to hide the future state of the ultimate absorbers of any e.g. photons emitted from a quantum entangled system from the emitting system -- the entire path through all intermediate filters is NOT information that is unavailable to the emitting system. The real problem is that that the time evolution of a closed quantum system begun in a stationary state is stationary, period, from a very fundamental theoretical level. The "paradoxes" seem to arise when we try to create "observers" that are one part of the total system, "systems" that are another part of the total system, and a "bath" made up of everything else that is in an almost completely unknown state. EVERYTHING is fully quantum entangled, ALWAYS. But when you split things up, pseudoentropy appears as one is forced due to ignorance of boundary conditions and intermediate time evolution of the whole to use a statistical (and hence classical or at worst semiclassical) description of both bath and observer.

It's pretty easy for me to believe that the effective pseudoentropy of Universe-(sub)system is so absolutely enormous that the quantum description of any subsystem (averaged) is going to look "random" in accordance with Bell's inequality but not, in fact, be random. It isn't a matter of local hidden variables, it is a matter of unknown state variables in everything else coupled to the system by ordinary interactions.

"Using nanotubes" is the new black?

[TeknoHog]

Making a RNG from inverters is an old trick (shameless plug). So if there's any news here, it's making an inverter from nanotubes?

Re:"Using nanotubes" is the new black?

[NoNonAlphaCharsHere]

Yeah. Back in the old days (the 80's) we used an oscillator that had a REALLY cheap capacitor at its heart. It had a free running bitstream as input to a shift register.

Re:"Using nanotubes" is the new black?

[Anonymous Coward]

Netflix using nanotubes...

Texting using nanotubes...

Commuting to work using nanotubes...

Vaping using nanotubes...

A guitar amplifier using nanotubes...

Encryption using nanotubes...

Posting anonymously on Slashdot using nanotubes...

Re:"Using nanotubes" is the new black?

[Lisandro]

Intel CPUs all have RNG since the Pentium III days - and they all based on Johnson (thermal) noise IIRC.

Re:"Using nanotubes" is the new black?

[Applehu Akbar]

Nanotube condoms for ACs!

Re:"Using nanotubes" is the new black?

[ls671]

We have implemented a true random generator here on /. It is a bot posting as an undisclosed user.

You reply to it and its answers to your replies have proven to be always perfectly random.

Ok, here is what I am allowed to let you know; internally, it is code-named:
bqdhldq, think HAL.

Re:"Using nanotubes" is the new black?

[skids]

Well, they might exhibit less/different interaction with environmental factors so there's less opportunity for a side-channel attack to make them spit out predicatbly, or be able to generate more bits faster, or just be compatible with the rest of a chip made mostly out of nanotubes. But yeah, until I RTFA, I suspect it's just "BECAUSE... NANOTUBES!"

Re:"Using nanotubes" is the new black?

[rogoshen1]

that poor girl.

Re:"Using nanotubes" is the new black?

[JohnFen]

True, but there is vast room for improvement. Those RNGs, like other ones such as the inverter scheme mentioned above, aren't truly random -- they're just close enough to be practical.

The higher the quality of random numbers that we can economically produce, the higher the quality of crypto we can have.

Re:"Using nanotubes" is the new black?

[Lisandro]

Rambus analyzed Intel's in-CPU RNG implementation about 5 years ago and found it to be very robust, FWIW: http://www.rambus.com/wp-conte...

Re:"Using nanotubes" is the new black?

[NoNonAlphaCharsHere]

OK, you win the Internets for the day, even if nobody else noticed.

Re:"Using nanotubes" is the new black?

[TechyImmigrant]

Yes and no.

All generations since Ivy Bridge that have a CPU RNG are based on metastability, which treats all types of noise equally.

Before that there was an RNG based on using a thermal noise to drive a VCO which sampled a fast oscillator. This was used in the chipset, not the CPU. The Linux i810 driver is the driver for this older RNG. RdRand doesn't need a driver because it's just an instruction returning numbers from the RNG.

Re:"Using nanotubes" is the new black?

[TechyImmigrant]

At the time it was CRI. Rambus purchased CRI after that report was written.

Summary fail

[Wdi]

The random generator passed only 9 of 15 standard randomness tests of NIST. Not surprising - it is unlikely that the two inverter branches are identical to the atom level, and that is a prerequisite that the thermal noise has exactly equal chance of flipping either branch.

Re:Summary fail

[TeknoHog]

The random generator passed only 9 of 15 standard randomness tests of NIST. Not surprising - it is unlikely that the two inverter branches are identical to the atom level, and that is a prerequisite that the thermal noise has exactly equal chance of flipping either branch.

The NIST tests aren't necessarily that great for judging randomness. For example, too long streaks of ones or zeros will fail the test, even though they are possible in genuine random sources. I imagine one could devise an algorithmic, repeating stream of numbers that passes the NIST tests.

The issue of unequal chance for 0 and 1 is common in HWRNGs, and there are simple solutions for debiasing the output. https://en.wikipedia.org/wiki/...

Re:Summary fail

[Togden]

If it were truly random, surely it would pass the tests at random, and so really we should be checking that it passes different tests each time, except on occasion when it doesn't.

Re:Summary fail

[hord]

In a system where you have individual components that contribute to an overall distribution, the way you analyze it is through statistics. The reason why NIST rejects long strings of 0's and 1's is because in any system where these two values actually do flip on a regular basis, the statistics of getting long strands of a single digit rapidly drop to 0%. A "real" random number generator has to have cycles in it even if you can't predict them because the way in which we analyze and use them presume the cycles are there (Fourier analysis). Even if the cycle isn't there, we make on up and test against it.

Re:Summary fail

[Anonymous Coward]

There are several techniques for reducing bias and correlation, often called "whitening" algorithms

I feel offended but I'm not sure why. Hang on, let me go ask tumblr.

Re:Summary fail

[Lisandro]

Was the output processed for bias? That might explain it. Creating a true RNG is trivial; simply reverse-biasing a PN junction in a transistor will create a good source of avalanche noise which can be converted into a bitstream. It has to be processed to account for bias though, like with the Von Neumann algorithm: https://mathoverflow.net/quest...

Re:Summary fail

[religionofpeas]

You can fix this by generating enough random numbers, apply appropriate hash function, and use that as input on a good cryptographically secure pseudo random generator.

Re:Summary fail

[AmiMoJo]

The only thing interesting seems to be that they printed the circuit, thus making it suitable for use on flexible electronics. Hard to imagine an application where you would need a good RNG on a flexible circuit, but maybe one exists.

As it happens generating random numbers that pass the NIST tests isn't particularly difficult. Here's some code I wrote that passes all their tests, as well as Diehard and a few others I found: https://github.com/kuro68k/xrn...

Re:Summary fail

[Bob the Super Hamste]

Will that code pass the Dieharder tests? That was not meant to be snarky but was meant to be something for consideration.

Re:Summary fail

[AmiMoJo]

I'll give Dieharder a try when I get time. I added the results from the NIST tests to the repo in the mean time.

If it passes NIST and Diehard I'd expect it to pass Dieharder, but it's worth checking.

Re:Summary fail

[Anne Thwacks]

Unequal number of 0's and 1's is easily solved by dividing by 2.

I believe the use of thermal noise and dividing by 2 was well known during WW2. (Where "well known" means by people whose job required them to know, and who were unlikely to be killed for knowing too much).

I learned about it in the early 60's - it was claimed to be a good use for Zener diodes when they were invented - as the thermionic diodes previously used for this application made a lot of heat and kept dying. You still needed thermionic valves (ECC82's I think) for the divide by 2 as transistors were very slow in those days. They made a lot of heat and kept dying.

Re:Summary fail

[TechyImmigrant]

I'll give Dieharder a try when I get time. I added the results from the NIST tests to the repo in the mean time.

If it passes NIST and Diehard I'd expect it to pass Dieharder, but it's worth checking.

Try it sometime. It will fail Dieharder. Not because it's bad, but because perfect data will fail. The output from dieharder -l tells you that the OPSO, OQSO, DNA and SUMS tests are suspect or bad and indeed they fail often over good data. Also the default confidence limits mean you are likely to hit a suspect or fail regardless of the quality of the data.

The updated SP800-22rev1a tests are ok, but not if you use the NIST STS-2.1.2 software. The coefficients for the overlapping template matching test are simply wrong. You can buy my book to find the details when it's out next year, but for now, I've made a working implementation of the SP800-22 tests available at https://github.com/dj-on-githu... . This is the only implementation with the right coefficients.

There's also a tool to generate data of known quality to calibrate your tests. https://github.com/dj-on-githu...

There's also a re-implementation of ent for computing statistics over random data with better file handling than the original: https://github.com/dj-on-githu...

You're welcome.

Re:Summary fail

[TechyImmigrant]

Probably not. Dieharder implements distinguishability tests for PRNG algorithms. For an entropy source you want min-entropy estimation algorithms.

The primary source of these algorithms is the SP800-90B draft spec. Unfortunately they don't work well. I submitted public comment to NIST detailing the failures of the tests against simple cases of biased and correlated data. https://github.com/dj-on-githu....

Re:Summary fail

[TechyImmigrant]

Academics would tell you to use a MAC function instead of a hash, but you'll still get away with it.

Re:Summary fail

[sexconker]

7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7

For all you know, that's completely random.

Your comment violated the "postercomment" compression filter. Try less whitespace and/or less repetition.
Your comment violated the "postercomment" compression filter. Try less whitespace and/or less repetition.

Re:Summary fail

[AmiMoJo]

You were right: https://pastebin.com/PnzK3Pvx

Looks like I'm going to need to generate a lot more numbers to really get much out of that test. I'll grab the hardware and give it a try, as well as the other software tools you linked.

Re:Summary fail

[AmiMoJo]

Okay.

   Symbol Size(bits) = 1
   Shannon IID Entropy = 1.000000 bits per symbol
   Optimal compression would compress by 0.000000 percent
   Chi square: symbol count=1677721593, distribution=0.92, randomly exceeds 33.86 percent of the time
   Mean = 0.499988
   Monte Carlo value for Pi is 3.141438 (error 0.00 percent).
   Serial Correlation = 0.000056

Your python code allocated 6GB of RAM, ran for a bit and was killed. I tried it with a smaller file and got

TEST: frequency_within_block_test
Traceback (most recent call last):
  File "./sp800_22_tests.py", line 129, in <module>
    m = __import__ ("sp800_22_"+testname)
  File "/-------/sp800_22_frequency_within_block_test.py", line 25, in <module>
    from scipy.special import gamma, gammainc, gammaincc
ImportError: No module named scipy.special

The NIST code ran fine with both files.

Re:Summary fail

[Quatermass]

Sample the output for a hundred years, once a second for example. Then see if the mean is 0.5? HAHA.

Re:Summary fail

[TechyImmigrant]

User testing! Yay!

"ImportError: No module named scipy.special" is python's way of saying please install scipy. You can do that. I'll throw in my own implementation of the incomplete gamma function to break that library dependence when I work out the equation.

I can't help with your lack of RAM, but how large were the files? Some of the NIST tests increase their memory usage with data size, but NIST specify data sizes to be used with the tests in SP800-22Rev1a.

My problems with the NIST STS-2.1.2 code are:
A) On bad data (high bias) it will lock up (in the igammac function, hence using scipy's in my code, but it could benefit from using mpfr floats ).
B) On good data it finishes but doesn't return a result - no P values, no pass or fail.
C) The parameters in the overlapping template test are wrong.

Re:Summary fail

[EETech1]

If I recall correctly, weren't you involved with the Intel random number generator?

Re:Summary fail

[TechyImmigrant]

That isn't entirely untrue: https://www.youtube.com/watch?...

Re:Summary fail

[TechyImmigrant]

I've just push changes to remove the dependency on scipy. Feel free to pull them.

Implementing the gamma functions is how I prefer to spend my weekends.

Re:Summary fail

[AmiMoJo]

I'll give it a try, and post any issues on Github. Thanks.

Re:Summary fail

[TechyImmigrant]

Note that the NIST spec says to test with 1 Mibibit/128Kibytes of data. The tests run in reasonable time with data that size.

I'm working on some better tests that are more reliable and computationally more bounded. We shall see if I succeed.

Re:Summary fail

[AmiMoJo]

I need to port some code to libusb so I can pipe the data into Dieharder anyway. I tried creating a 2GB file and it still rewound it hundreds of times, and it actually failed tests that the smaller 100MB files passed. Something needs further investigation here.

The NIST code seems to cope with 100MB okay, takes several minutes to run. Ent seems to have some issues with files that size but ultimately does produce some useful output. I'm tempted to do some work on Ent to support larger files and some more tests.

I also want to put error detection on the device itself. At the moment the limitation is USB speed (it's only a full speed device, 12Mb/sec theoretical max but in practice maybe half that) and there is some free CPU time available to do some tests on the data. I'm also thinking of porting to ARM... There are some really cheap ARM dev boards, and it would be great if users could just buy one off-the-shelf and get a reliable TRNG with minimal effort and cost.

Re:Summary fail

[TechyImmigrant]

Dieharder needs on the order of a TB of data to avoid rewinding. BigCrunch is worse.

>it would be great if users could just buy one off-the-shelf and get a reliable TRNG with minimal effort and cost.
Someone should ask ARM why they don't provide on in their CPUs.

Re:Summary fail

[AmiMoJo]

Some ARM variants do have hardware RNG, although I think it's a manufacturer extension rather than a part of the ABI. I was actually thinking of going that route with an Atmel ARM that has USB 2.0 high speed and a hardware RNG, which they claim "passes" NIST tests and Diehard.

The built in RNG is a little slow though so I'd be using the same techniques I am on XMEGA to generate more entrophy, which is basically to use two ADCs to measure thermal noise in the on-board temperature sensor and discard all but the lowest order bit, and when I get 8 such bits I throw them into the hardware CRC32 generator and grab a single byte from its output.

I need to do more tests, such as using more than 8 bits of the CRC32 output. If I was building a custom USB dongle I'd include a reverse biased transistor source too. I want to investigate 5V options to avoid needing a 12V boost converter, or maybe I can use a simple voltage doubler to get 10V since that's only a diode and capacitor.

So it passes test one of a good RNG.

[Opportunist]

The first test of a good random number generator is obviously whether it can generate a true random number under normal operation conditions. This they claim to have accomplished.

The second test is just as critical and I'd be very interested in the result: Can any kind of manipulation be easily detected? Or is it possible to tamper with the device in such a way that it does generate a number predetermined by the manipulator without anyone else being able to determine that such manipulation took place?

Re:"True"? Not possible

[NoNonAlphaCharsHere]

Everything in the universe is predictable, including so called "chaos". There is no such thing as truly random.

Have you looked at what's coming out of the White House?

It may be random to us...

[little1973]

but it may not from the Universe' point of view.

According to Gerard 't Hooft, the superdeterminism loophole cannot be dismissed.

The Free-Will Postulate in Quantum Mechanics
https://arxiv.org/abs/quant-ph...

Entangled quantum states in a local deterministic theory
https://arxiv.org/abs/0908.340...

Is the randomness stochastic?

[PerlPunk]

OK, so, it's generating a series of truly random 0s and 1s. I don't have access to the article, but my question is if this truly random number generator has been identified as being a part of some stochastic process, like a binomial or poisson process? Would appreciate some more insight on this.

Re:Is the randomness stochastic?

[TechyImmigrant]

I expect (given my job makes me quite well prepared to answer) that the output would be statistically non stationary and so not fit nicely in a binomial or poisson distribution.

The question that needs answering is "What is the min-entropy of the data from this source".

Another question is "What is the distribution of quality of entropy across a large population of these devices". It seems likely that a large proportion would not work when built due to intrinsic device variation.

They answers might be in the paper, but I've failed to read it yet.

Re: "True"? Not possible

[Viol8]

You might want to read up on quantum theory sometime when you're done with Sesame Street.

Re: Uh Oh, be careful

[Jesus H Rolle]

Only if you say it three times while facing a mirror in the dark.

Horseshit

[Viol8]

"If we knew the state of every charged particle in the universe at a given time, we could compute the radiated fields from each and arrive at the actual value of RF noise detected some time later."

No, we couldn't, because ultimately a lot of the causes of EM emission are quantum and they are truly random.

"If we knew the state of every charged particle in the universe at a given time"

Read up on Heisenbergs Uncertainty Principle then get back to us. You're a moron.

Re:Horseshit

[Anonymous Coward]

Thank you for making my point for me. Heisenberg states that we cannot know the state of something without changing that state. The act of measuring something changes the something. But, this change is not random. It is determined by the stimuli, which we also can't know. We call it "random" because we can't know it, but just because we don't know it doesn't mean it is random.

Randomness is just a construct that we invented to fill the large, gaping holes in our understanding. It's not real. Early humans invented Gods to explain the things they didn't understand. Well. science pretty much obliterated the idea of Gods, but it still needed a way to explain the unknown, so it has invented bullshit theories like randomness, dark matter, quantum physics.

You're the moron, because you think you possess some level of knowledge about the universe.

I don't know shit, but at least I know I don't know shit. You don't know shit, but you think you do know shit. That's a far less tenable position to find ones self in.

Re:Horseshit

[Viol8]

"Randomness is just a construct that we invented to fill the large, gaping holes in our understanding"

For "our" , read "your".

"I don't know shit, "

Correct, go learn something.

Some quantum processes have no cause, there is simply an effect - eg spontanious generation of particles out of nowhere. This is true randomness and could not be predicted even if we could bypass the uncertainty principle and know the entire state of every particle and field in the universe.

Re:Horseshit

[david_thornley]

We can't know the results of experiments where we know the entire state. Take an electron. We make sure spin is up. We already know charge and mass, and are close enough on position. Run it through an apparatus to check left-right spin. The result is random, and various experiments have shown that there is no property of the electron that will determine the result.

Neat, but not particularly groundbreaking

[Lisandro]

Creating hardware RNGs is pretty trivial with off-the-shelf electronics; people have been using reverse-biased PN junctions on transistors for this application since forever.

Re:Neat, but not particularly groundbreaking

[religionofpeas]

You can also use a $10 webcam, cover the lens, and turn the gain up until it starts producing noise. Compensate for outside interference by calculating delta between two disjoint sets of random pixels.

Or you just use a reversed Base-Emitter junction

[gweihir]

At the voltage-level you get, very roughly half of the noise is quantum and "true" random (which is just Physic-speech for "we have no idea how it works"). Amplify, digitize, pipe into a randomness-pool and you are done. Can be accomplished for $20 or so in parts.

Or you can use a Zener Diode, and some RF amplifiers: https://www.maximintegrated.co...
Spectrum here goes well over 100MHz.

Nice save

[physicsphairy]

Researcher 1: "Our nanotube project is outputting completely garbage data. I guess this means we can't publish."
Researcher 2: "Or... can we?"

Re:Nice save

[SuiteSisterMary]

This is the history of science in a nutshell. The first example that springs immediately to mind is the Penzias-Wilson experiment.

Re:Nice save

[the_saint1138]

Nice! +1

Re:"True"? Not possible

[Anonymous Coward]

Everything in the universe is predictable, including so called "chaos". There is no such thing as truly random.

Wow! I knew there was a Flat Earth Society, I didn't know there was a Newton's Mechanical Universe Society. Old beliefs die hard.

nothing's really random

[v1]

although some things are sufficiently unpredictable as to be "close enough". Thermal noise, as this method is using, usually falls into this category.

I personally prefer algorithmic methods of generating random numbers. Sufficiently designed functions can perform well on random analysis while still offering you the option of fixed seeding for those cases where you need a consistent stream. (mainly used for testing and cryptography)

Re:nothing's really random

[JBMcB]

Are you talking about the difference between white noise (true randomness) and pink noise (evenly distributed randomness)?

Re:nothing's really random

[TechyImmigrant]

v1 is is talking about a preferring a deterministic RNG vs. a partially entropy entropy source.

A properly engineered RNG for crypto needs non determinism from an entropy source and needs uniform, full entropy data by running it through an entropy extractor. The 'algorithmic method' v1 mentions is a PRNG. It's optional and is used to increase performance by generating many outputs for each seed input.

Re:nothing's really random

[v1]

The only "perfect, unbreakable crypto" is the "one-time-pad", which requires both the sender and the receiver to have a truly (or sufficiently) random stream of numbers to use as a pad/xor. The limitations of this method are that (A) each pad can only be used once, (B) both parties need a sufficiently large amount of pad for their messages, (C) when they run out of pad, they have to get together somehow securely to exchange more large padding, and (D) pads are totally impractical to memorize.

Seedable random number generators get around those issues by (D) using a passphrase which is hashed to produce the seed, which (A) can incorporate a sequence number, date, etc so that the same passphrase can be reused several times without causing the pad to be reused, where (C) passphrases are much easier to exchange or send securely due to their much smaller size, and (B) they can produce arbitrarily large streams from a given seed.

A well-designed RNG will solve most of the problems of one-time-pad, in exchange for a possibly acceptable small increase in vulnerability to analysis.

Re: "True"? Not possible

[hord]

Which "quantum theory"? Quantum mechanics which uses statistical analysis? Quantum Field Theory which uses renormalization and statistical analysis? String theory which uses multi-dimensional tensor analysis? All of these are converging on higher dimensional linear algebra and are using techniques and strategies from computer science, complexity theory, information theory, and other deterministic disciplines.

What reading have you done?

Re:Alternative physics

[hord]

Physics claims that the laws of the universe are either fixed or can only change in a fixed way. That is determinism. It doesn't mean that the entire future is already completely predictable. It means that the phenomena that we observe can only be explained by principles which assume a very specific level of consistency. A mathematical type of consistency that implies a type of structure that you cannot escape. Things which look random to us are simply large-scale phenomena that are beyond our ability to completely systematically understand in a single unit of time or space. These are complex systems with dynamic outcomes. However, they are all driven by ruthless, deterministic, mathematical calculations.

Re: "True"? Not possible

[hord]

Since there isn't a mathematical definition of random generation, I would assume at this point it would be more reasonable to ask for proof that randomness is even a property of the universe at all. You can find mathematical theories that rely on randomness or random distributions. What you will never find is a real-world physical explanation for randomness because physics keeps saying it doesn't exist. What physics maintains is that there is a set of information in the universe, only part of which we understand. The rest is called entropy and when we bump into it, it looks random but it was really just stuff we didn't know that was already there doing deterministic stuff.

The air in the room you are breathing is a great example. It's "random" except that we can explain every molecule over air using the standard model of physics. So it's really not random. It's just very damned complicated.

Re:"True"? Not possible

[OneHundredAndTen]

Everything in the universe is predictable, including so called "chaos". There is no such thing as truly random.

Those who do not know quantum mechanics are condemned to carry on ignoring it.

Re:Alternative physics

[Ramze]

I'm not sure how to parse your statement. You seem to be using a very strange definition of determinism.

In physics, determinism would mean that if one could know the position, speed, charge, spin, and every other defining property of every particle in the universe, one could theoretically calculate the entire history and future of the universe. The universe isn't non-deterministic simply because that calculation would be too immense to process and the data impossible to collect, but because of the inherent uncertainty and superposition of many of those properties as well as the uncertainty in the outcome of particle interactions. If two particles interact, we can work out the probability of their interaction producing a wide range of particles, but we can't know which will come to pass.

Particle physics is based upon probabilities -- which is the exact opposite of determinism. Even though it's not random, it's not deterministic simply because there are rules to help determine probable outcomes. Einstein didn't like quantum mechanics because it wasn't deterministic -- thus his famous "God does not play dice with the universe." quote.

It's as if you're saying a dice roll isn't random simply because there are rules -- it must land on one of 6 sides. There are distributions other than random ones in particle physics -- normal distributions which aren't random, but instead show that some things are more likely to happen than others... but, that's again due to rules -- like mass/energy conservation rules & interference patterns. Particles often "break" rules -- like with quantum tunneling. So, even rules aren't so much rules as guidelines... as long as everything balances at the end. A particle can borrow energy to tunnel through a barrier so long as it gives the energy back when it's done.

It may be that you already understand this, but believe there is some deeper understanding in string theory (or the debunked pilot wave theory) or some other philosophy where you think we just don't understand and know enough to see the underpinnings of everything... but... physicists are pretty darned certain that random things happen all the time, the universe is inherently non-deterministic, and things happen based upon probabilities, not certainties... and there's really nothing deeper to explain the weirdness of it all.

Re: "True"? Not possible

[rgbatduke]

As I posted above, we do not know this. IF you accept e.g. the holographic MODEL of string theory, then there is no entropy even at the quantum level. On the other hand there are plenty of articles in QFT that discuss the possibility that QFT is truly irreversible at some level so the direction of time is not just a consequence of entropy.

It is perfectly fine to think that one or the other of these is "more likely" to be true on the basis of what one knows or guesses, but because physics is not religion it is not appropriate to state that there is not random as a proven fact, that the entropy of the Universe is zero and there are no true entropy sources. Ultimately this, like everything else, is an empirical question.

Personally I agree with you and think that whether or not the holographic model per se is correct, QFT is probably reversible and that the Universe is in a zero entropy (definite) state with no "outside" source of entropy to make it non-deterministic on the basis of internal dynamics alone. But in the end, experiments talk, bullshit walks and even the sexiest theoretical model is bullshit until it is confirmed by experiment.

rand()

[penandpaper]

int rand(){ // I rolled a 6 sided die to get a random number.
      return 3;
}

is there anything they can't do?

[Thud457]

BAH.

By definition carbon nanotubes are all inanimate carbon rods.

Re:The Nevada Gaming Commission

[Rockoon]

...and they along with most lottery commissions deferred to George Marsaglia while he was alive.

/. already has a true RNG

[fahrbot-bot]

Just post something snarky and wait for it to get modded a mix of: funny, troll and informative ...

Let's do things the hard way.

[TechyImmigrant]

When your full time job is designing RNGs, Reading articles on RNGs can be a little painful.

The term "TRNG" (True Random Number Generator) is a poorly defined thing. I think people think it means 'ideal non deterministic' but it's never used in that context and in this case we certainly don't have such a thing.

The thing they designed is a an "entropy source". It produces partially entropic nondeterministic data.

The chain of events in an RNG is..

Entropy source --> Online Test --> Entropy Extractor --> (If needed for performance) A CS-PRNG. (crypographically secure pseudo random number generator).

Entropy source : Makes partially entropic data. It doesn't matter what kind of source it is, whether quantum, lava lamp, circuit or whatever else, you never get perfect entropy from a physical process. The entropy extractor distills this kind of data into a smaller amount of data that is close to full entropy. 'Close' is mathematically described in terms that matter in cryptography.

Online Test: Continuously checks the ES is working while it's running. -- Top tip - This is the hard bit in RNG design.

So unless they can build and online test an entropy extractor in carbon nanotubes, they don't have a solution but they do have an entropy source. I don't know if they have done this or not, because the link in TFA doesn't work, despite my corporate IEEE account. If they have, then well done. If not, it's interesting anyway, but not ready for application.

Re:The Nevada Gaming Commission

[TechyImmigrant]

>and the Nevada Gaming Control Board are the arbiters on this matter.

The Nevada Gaming Control Board has an alarmingly weak set of rules for RNGs in gaming machines. It is trivial to make a non random RNG that meets the spec. It is as follows:

1.400 Random Selection Process and Random Number Generator
1. The random selection process must meet 95 percent confidence limits using a standard
chi-squared test for goodness of fit.
2. A gaming device using a software random number generator (RNG) shall:
(a) Not use static seed upon initialization;
(b) Cycle the RNG at a minimum average rate of 100Hz (100 times per second); and
(c) Not draw RNG values for future play.
3. A gaming device using a hardware random number generator shall:
(a) Continually monitor the RNG to ensure compliance with this standard. This shall be done
by performing a chi-squared goodness of fit evaluation over the most recent 10,000 random
outcomes selected for game play;
(b) Automatically maintain an event log displaying the results of the most recent 10 chisquared
tests to include the result of the test and the date and time the test was performed;
(c) Display a visual indicator of a failure; and
(d) Upon, two consecutive failures, enter into a tilt condition.
4. RNG’s used for purposes other than determining the game outcome must either:
(a) Be implemented as a separate instantiation of the RNG process; or
(b) Be based on an algorithm or method that can be demonstrated does not affect the game
outcome.
5. A game that draws a predetermined set of outcomes for a game, such as a shuffled deck
of cards, must prevent the information from being accessible.
6. Additionally, video poker games must not determine replacement cards prior to the player
selecting hold cards and initiating a draw.
7. The RNG and random selection process must be impervious to influences from outside the
device, including, but not limited to, electro-magnetic interference, electro-static interference, and
radio frequency interference.
8. A gaming device must use appropriate communication protocols to protect the random
number generator and random selection process from influence by associated equipment or other
devices which is conducting data communications with the gaming device.

There are many things wrong with this.
ChiSq GOF test for randomness is only a bias test. This 111111111111111110000000000000000000 would pass a Chi-sq test.

95% Confidence limits? You can be wrong 5% of the time?

Minimal conformance to this: "(b) Cycle the RNG at a minimum average rate of 100Hz (100 times per second); " Was used in an active timing attack against a slot machine.

This "(a) Continually monitor the RNG to ensure compliance with this standard. This shall be done
by performing a chi-squared goodness of fit evaluation over the most recent 10,000 random
outcomes selected for game play;" Is trivial to comply with in a completely non random system.

This is impossible: "7. The RNG and random selection process must be impervious to influences from outside the
device, including, but not limited to, electro-magnetic interference, electro-static interference, and
radio frequency interference."

Nice!

[JohnFen]

If this can be effectively commercialized, it would be a game-changer (no pun intended).

Re:Alternative physics

[TechyImmigrant]

Ohh. Let me try!

Current physical laws have non determinism built in, because this is what we observe in nature.
However the cause of that non determinism is not explained. It is an observation. It works very well in describing the world we see.

We could if we were speculating wildly, envisage every point in the universe at some sub plank scale containing a uniquely seeded deterministic RNG that is used to decide the outcome of interactions, and we wouldn't be able to tell the difference.

So it's reasonable to 'believe' we have a non deterministic universe, because it's what we see but we don't actually know, and you could equally reasonably choose to 'believe' we live in a deterministic universe because we don't know fundamental laws that would create non-determinism out of determinism, so the non determinism we see is more likely to be from a complex deterministic process underneath.

Since I've had about a decade where the answer to these questions mattered a lot to me (I work in crypto and mostly in RNGs for crypto) I've landed a lot more firmly in the "we don't know" camp and the "We can't tell the difference" camp.

     

Re: "True"? Not possible

[TechyImmigrant]

>Since there isn't a mathematical definition of random generation

Yes there is. There are several. Here are 4: HILL, Yao, Unpredicatibility and Information Theoretic entropy:

https://pdfs.semanticscholar.o...

this already exists

[slashmydots]

Over 10 years ago someone invented a PCI card that splits photons left or right over some kind of quantum thing and it's provably flawlessly random. Why is someone bothering to try and outdo that?

Re:this already exists

[SuiteSisterMary]

Well, for one thing, does your phone have a PCI slot? Is the technology you reference usable, in a practical way, in small technology; that is to say, small enough, inexpensive enough, easy enough to manufacture in bulk, no excessive power requirements, and so on?

Oxymoron of the day:

[jbengt]

. . . deterministic RNG . . .

Re:Oxymoron of the day:

[TechyImmigrant]

Nope. That's what a PRNG or DRBG algorithm is. The randomness defined in terms of computations bounds on prediction.

I don't get it.

[mark_reh]

Is a reverse biased pn junction a random noise source? Is this better? In what way?

Re:"True"? Not possible

[mark-t]

The universe's behavior is, for all intents and purposes, non-deterministic in the sense that any ability one may allegedly have to accurate predict the outcome of some state of the even a very tiny subset of the universe given all all available input cannot actually be observed.

Proof:

Assume that a black box could exist that can predict the outcome of a particular experiment wherein the output of black box is read as input. If this cannot be done, then any so-called deterministic nature to the universe is irrelevant, because you can't assume that any particular predicted outcome is necessarily what will actually happen.

The experiment is designed as follows: A mechanism has two levers, one on the right and one on the left, and is designed to read the output of the black box, and activate the lever that the black box indicates. The left lever of the mechanism outputs "right" while the right lever out outputs "left". The black box simply has to produce as output whatever the mechanism ultimately will. However, similar to the halting problem, this creates a paradox, as you can see that despite the entirely deterministic nature of the experiment, the black box cannot be used to predict its outcome.

Therefore, either the universe is non-deterministic, or else it is non-deterministic for all practical purposes, since any so-called prediction can only be as accurate insomuch as that information is never actually observed in the present. I personally subscribe to the former position because I believe it is the simpler situation, but even if the latter were true, it is entirely irrelevant to reality.

And if you can't predict the outcome of a random number generator, even if you know absolutely everything about it, what is the difference between that and truly random?

Re: "True"? Not possible

[david_thornley]

Quantum theory where there are no local hidden variables? Take an electron with spin straight up, and run it through an apparatus to check its spin horizontally? Last I looked (quite some time ago), quantum random values were generally from radioactive decay.