Slashdot Mirror
New Method for Random Number Generation Developed
Science Daily is reporting that a German team has developed a new method of random number generation that they hope will improve security. "The German team has now developed a true random number generator that uses an extra layer of randomness by making a computer memory element, a flip-flop, twitch randomly between its two states 1 or 0. Immediately prior to the switch, the flip-flop is in a 'metastable state' where its behavior cannot be predicted. At the end of the metastable state, the contents of the memory are purely random. The researchers' experiments with an array of flip-flop units show that for small arrays the extra layer makes the random number almost twenty times more 'random' than conventional methods."
uixon8wg2gvw
I have to wonder about this approach, if it falls into the category of seemingly random today, because we simply don't yet know how to predict the outcome, but maybe someone in a few years' time figures out the necessary principles to predict what the outcome will be?
Still, I suppose until such a time (if it ever arrives), this is probably a lot better than currently existing approaches.
I'd say based on the fact that all your characters were lower case, and the overwhelming proportion of characters to digits, there are significantly fewer bits of entropy in your so-called random comment than you would have us believe.
Ze Atomic Device! It iz Ztolen!
this one too.
The largest prime factor of my UID is 263267.
the generation of random number is too important to be left to chance.
Just pull random slashdot threads at -1 and hash that. Can't get more random than that.
Lets play a game, what XKCD am I thinking of?
always been one of my favorites... http://xkcd.org/221/
So your suggestion is to generate a random with a random? How do you get the random slashdot thread?
TFA fails to state whether they used existing memory types or if they intend to use a custom piece of hardware on board.
From TFA:
The team adds that the efforts of a cracker attempting to influence the array will be wholly obvious to a simple statistical analysis as -- depending on the type of attack -- either the whole array or single elements will be disturbed, whereas these are again selected randomly. So this true random number generator can protect systems against third-party snooping, potentially making private and sensitive transactions on the Internet more secure.
Now I'm really skeptical. A cracker who is able to "influence" the array might be able to influence it with a pseudorandom number generator that he/she can predict.
I think that hardware based RNGs, such as those detecting radioactive isotope decay, have been around for a while. I'm not sure how this one can provide more security, especially if the attacker has access to the hardware. I think that most gate transition thresholds can be influence by simple things like temperature anyway.
What exactly does "more random" mean in the summary? I think something is either random or it isn't. Perhaps this claim should just make us "more skeptical".
20 times more random?
umm.. errr... wha?
"His name was James Damore."
And one of my favorites: http://web.archive.org/web/20011027002011/http://dilbert.com/comics/dilbert/archive/images/dilbert2001182781025.gif
John
Would this beat methods such as leaky diodes or radio noise which some systems use to get random data?
--- Users are like bacteria -> Each one causing a thousand tiny crises until the host finally gives up and dies.
I always thought the WiFi radio in laptops would be a good thing for generating random numbers.
One person's random is another's expectation value
While this new technique may improve security, it seems to lack one important property of pseudo-random numbers that is required by many applications: reproducibility.
Good luck finding the bug in your program with a stream of randoms you'll never be able to reconstruct again.
A comment containing absolutely nothing but handwaving conjecture is moderated "Interesting". Thousands of dilletantes stroke their neckbeards in contemplation. Hmmmmm, yes, what if that thing you said?
9...9...9...9...9...9
No, it's based on thermal noise. It truly is random, but bear in mind that there's a bias to each bit that has to be compensated out.
Lacking <sarcasm> tags,
There is no way they can prove that these flip flops don't have bias one way or the other. Even if you could design a perfect circuit it would be subject to the imbalances between p-type and n-type transistors and process variations. This makes it impossible to create a perfect Gaussian metastability function or to place a device at the apex of that function such that the probability is 50/50 of switching to 1 or 0. Hence, you will not achieve truly random results. Metastability is also affected by the power supply voltage and current. A cryptographic device employing this technique could be subject to attack by lowering or modulating the power supply in such a way as to create predictable "random" numbers. i.e. make sure all the flip-flops transition to 1 or 0.
I am becoming gerund, destroyer of verbs.
No kidding - life was simpler back then.
Stupid P.E.T.A.
Sweet informative mod.
So your suggestion is to generate a random with a random? How do you get the random slashdot thread?
From the previous random, duh!
Track your TV Shows with your iPhone - FREE
Here is a slightly-absurd-but-awesomme dice rolling machine.
That's one problem it won't have, since the initial condition is at the balance point of P vs. N. The bias would show up in the curvature of the gain function around the bias point. It's not a large bias, and it's likely to vary from one device to the next -- so the prudent designer would have to correct for each bit's history. Still, thermal noise is easier to work with than radioactive decay.
Lacking <sarcasm> tags,
http://en.wikipedia.org/wiki/Entropy_(information_theory)
"Prefiero morir de pie que vivir siempre arrodillado!"
The only problem with the cat was they have 9 lives. No wonder we always kept getting live cats when we opened the box.
Seven puppies were harmed during the making of this post.
Every x years, someone will find and publish a way to cure cancer... in mice.
Every y years, someone will invent and publish a way to treat phase velocity as if it were group velocity.
Every z years, someone will discover and publish a way to use metastable flip-flops to produce random numbers.
http://pv.fernuni-hagen.de/docs/fechnerb_attack.pdf
Wer mit Ungeheuern kämpft, mag zusehn, dass er nicht dabei zum Ungeheuer wird. --Nietzsche
Obilgatory TheDailyWTF
Weather forecasters [...] also use random numbers
Here in New England, it sure seems like they already pick the next forecast out of a hat.. I think more randomness may actually make the forecasts more accurate
Actually, I've heard on the radio that some researchers (didn't catch their names) have recently demonstrated that the probability of the coin landing with in the same orientation it started with is slightly higher than the probability of landing the other way. And you can train yourself to influence the probability. So 50/50 ... probably close, but not necessarily, and definitely not for every coin and every person.
Please correct me if I got my facts wrong.
I think we finally have the answer to Friday's Ask Slashdot.
....wired to a serial port. Worked fine.
Regards;
Randomness, put simply, is the degrees of separation from which a given stream resembles Shakespeare. Or, if you prefer the top-down approach, the degrees it is separated from the plaintext output of a million monkeys at a million typewriters.
Logic elements being in non-deterministic states is not new. In fact, often enough considerable effort must be spent to make sure they _don't_ go into nondeterministic states. And some troll Phillips has actually already patented this, in 2003 (6631390).
A caveat is that such non-deterministic states are often not completely random; they're influenced by such things as the previous value of the flip-flop, variations in the power supply, the state of nearby circuits, etc.
I detect BS.
1 flip flop in a metastable state can produce at most 1 bit of entropy.
1 flip flip in a metastable state tends to produce in excess of 0.5 bits of entropy. It depends on many things, but done properly a normal circuit of this type wouldn't be producing anything nearly as small one 20th of a bit of entropy per flip flop.
The gains from combining an array of 20 flip flops to produce one really good entropic bit will only asymptotically take the randomness towards 1 bit per bit.
TFA doesn't cite references, so it's hard to go and check.
Evil people are out to get you.
Exact, random don't exist.
When you throw the dice we can guess the number that will appear with : their original position, the movement of the hand, how fast they throw, the speed of wind [...] but true random is a lie !
Assuming this is true, unless you actually know if you are a "head flipper" or a "tail flipper" (assuming of course you allways start with the same orientation) as long as the distribution of "head and tail flippers" is the same, the randomness of a random person flipping a coin stays intact.
This is where all those scratch monkeys went.
Who would win this election: Andrew Weiner vs Andrew Weiner's weiner.
TFA gives an example "Such simulations can test theories of hurricane formation, climate change, and the spread of disease epidemics, for instance." Which required repeatable random numbers.
For cryptography its fine though.
[Intentionally left blank]
Personally I like what I call "dice random" where there IS the possibility that you can roll the same number an infinite amount of times in a row.
Okay, I want all 1's, an infinite number of times in a row.
Probability of one 1: 1/6. Okay
Probability of n 1's: (1/6)^n. Okay
lim((1/6)^n) as n->infinity: 0. Wait, I thought you said there was a chance this could work!
Well, it isn't zero, it just approaches zero. Never actually gets there...
Probability of rolling a 1 on a single roll: 1/6
Probability of (n+1) 1's in a row: (probability of (n) 1's) * 1/6
No matter how many times you apply the inductive step, the result is greater than zero...
P.S. Who supplies your dice that can survive an infinite number of rolls? You could make a killing selling those to casinos. Once, anyhow.
Surviving an infinite number of rolls is not the problem... The real problem is that if you've got, say, a D20, and you get it to roll a 1 a large number of times, the ones will have all been rolled out. After that it'll have a hard time producing more 1's.
Bow-ties are cool.
Humor. It's a concept.
FYI, 52 year old male. Software developer. Intermittently Incompetent. Or is that Mittently competent? Dammit, now I'm confused again.
Please do not read this sig. Thank you.
They've developed 30-sided die?
This 7 ft tall automatic dice roller reads the rolls with a camera and laptop and serves them for game play. http://gizmodo.com/5270195/automatic-dice-machine-records-13-million-rolls-a-day
When the degree of accuracy needed to determine position, motion, etc. go below the Planck length, it is no longer possible to make such predictions. In other words, for a sufficiently chaotic system true randomness does exist.
'The tyrant will always find pretext for his tyranny.' - Aesop's Fables
There is an attempt on /. to make a meme out of complaints in the form of "As a $X year old lesbian/feminist grandmother and $Y programmer of $Z years, I find this offensive".
Grandparent post is just trolling.
Do what thou wilt shall be the whole of the Law
I would like to see a quantum physics approach to this. You know, acknowledging probabilities in measurements, quantization of state, etc.
Any sufficiently advanced intelligence is indistinguishable from stupidity.
As I understand it, the only truly random things in our universe involve some kind of quantum interaction--everything else is a reaction to something else.
But on the bright side, if they supplied a large number of quantum elements, they could always keep the other half "in-house" so they'd know when you'd used them all and needed more bits...
This whole quantum thing confuses me.
It isn't infinite, it just approaches infinite. The changes that you roll 1 an infinite number of times (as great-grandparent stated) is effectively zero. You'll never throw the dice that often, and even if you do, it will never, ever be all 1's.
Free beer is never free as in speech. Free speech is always free as in beer.
Every y years, someone will invent and publish a way to treat phase velocity as if it were group velocity.
Isn't this what a time-domain equalizer does? (if imperfectly due to finite delay in any useful implementation)
Mostly it pops up when someone is convinced they've found a way to transmit information faster than c.
The real problem is that if you've got, say, a D20, and you get it to roll a 1 a large number of times, the ones will have all been rolled out. After that it'll have a hard time producing more 1's.
Fact!
Their may be a grammatical error, misspeling, or evn a typo in this post.
Why is it always the grandmother and not the grandfather that is considered the most incompetent?
It's payback for all the TV commercials with people from later generations, where the incompetent guy always has to get schooled by his more intelligent wife. In reality all the smart wives are feminist C programmers but the commercials don't get into that.
And why older people?
As someone who is aging himself, I find this rather obvious.
Slashdot is home to some of the most racist techies.
You just shot yourself in the foot there, Mrs. C. Sexist and ageist I can believe, but not racist, unless people are keeping it to themselves. (Except for a couple null-pointer morons who paste racist, "N-word" laced shit as a FP and get modded down to hell.)
sample the last n number of twits on Twitter at any given second. That is true randomness for sure.
Did you ever wake up in the morning, with a Zombie Woof behind your eyes? -- FZ
return 4
We have perfectly good physical random-number generators -- your basic Boltzmann (Johnson) thermal noise is just the ticket. Hook any resistor above absolute zero to a A/D converter and you have a few microvlots of random noise-- after an A/D converter, a nice stream of random numbers. Well, not quite, A/D converters are less than perfect, so you'll just get semi-random numbers with a slight bias towards the A/D converter's nonlinearities. But pretty darn good.
If that's too weal a signal, you can avalanche a diode and get VOLTS of noise. ... or you could metastable some flip/flops.... but if you do you'll get HORRIBLE random numbers, as the metastable state amplifies and unbalances in the flip/flops. i.e. if one flip flop has one microvolt of unbalance towards the "1" state, the unbalance increases exponentially in just a few nanoseconds, making it most likely it will go into the "1" state solidly a very high percent of the time..
Stick to Johnson (resistor) noise, avalanche diodes, or even beta emitters. Forgit the metastable flippers.
for a sufficiently chaotic system true randomness does exist.
Chaos is based on this theory : Small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes for chaotic systems, rendering long-term prediction impossible in general.
This theory is really interesting but, in this case, you believe in "impossible" ? Near-to-infinite number of conditions mean they are predictable, they just immeasurably hard to predict.
I'm not a specialized in this kind of brain's food, maybe you got some reading for me to show me where I'm wrong.
A very simple circuit of properly biased IF-MAYBE gates in a feedback loop with OCCASIONALLY-PERHAPS registers will produce an infinite string of perfectly random bits which can then be sampled to give perfect random numbers. I would swear that every computer I have worked on (going back to a PDP-8i) has had one or more of these somewhere -- undocumented of course...
RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs. People use RANDOM.ORG for holding drawings, lotteries and sweepstakes, to drive games and gambling sites, for scientific applications and for art and music. The service has existed since 1998 and was built and is being operated by Mads Haahr of the School of Computer Science and Statistics at Trinity College, Dublin in Ireland.
http://www.random.org/
Near-to-infinite number of conditions mean they are predictable, they just immeasurably hard to predict.
Just a little fix : I mean small differences cause yield widely diverging outcomes, but "yield widely diverging outcomes" is predictable !
Planck length : Because of the tininess of the Planck length (about 1020 times smaller than the diameter of a proton) there is no hope of directly probing this length scale in the foreseeable future.
If something goes below Planck length, it's not predictable because it disapear (simplfication) ?
Things are (probably) predictable. I talk about an hypothetical situation, nothing provable as is, but it's not impossible.
How many times have you ever heard of a cracker breaking a system nowadays because the RNG was not sufficiently random???
Yes i know there have been instances where a crack was due to TOTAL LACK of an RNG (as in, the RNG was not implemented properly), but due to a properly implemented RNG with just a lack of entropy? Not that I recall.
I guess I don't get why there is a market large enough for this to warrant the research. There are several hardware-based RNGs that guarantee as close to "true randomness" as is possible by modern physics, and if you wanted true randomness, you would use one of those, not this half measure.
For me, my /dev/random based off my network traffic and mouse and keyboard and HD is good enough, thanks. Color me unconcerned.
From the era when Dilbert was funny.
There are already plenty of entropy sources on a typical PC, and the need for cryptographic strength randomness is rare enough that we can accumulate entropy without adding more hardware. We've already got timer chips, real time clocks, CPU cycle and instruction counters, mouse positions, graphics memory, audio inputs, accelerometers, rotation rate sensors on fans, temperature sensors on CPUs, motherboards, and disk drives, all the SMART data on the drives, packet checksums, and we currently aren't even using most of those. If you want to add entropy accumulators, use the ones we already have first. If they're not enough, it's fairly easy to add a white noise generator to your audio input. Plug in a radio tuned to static. Or even tuned to a station. It doesn't matter. Either has plenty of entropy. The sensors chip on my motherboard generates about 31 bits of entropy per read (probably due to spikes and sags on the power supply voltages) when read at 1 Hz. A drive's SMART data is probably good for a couple bits per second.
And how exactly is a metastable multivibrator a new thing anyway?
Support SETI@home
Mostly it pops up when someone is convinced they've found a way to transmit information faster than c.
C is fast but go to assembly for real speed !
PS: I know c stands for celerity in your post.
I made a pretty darn good rng a while ago. Simply have three independent white noise generators made with two transistors and an op-amp each. The noise is generated by a transistor going into avalanche mode, and that's basically influenced by quantum states. The problem with using just one is that its output isn't 50/50. So you XOR two. You can stop there but if you're really paranoid, use a third to clock a latch so you can't event predict when the random bit changes. All in all the whole circuit fit in a box smaller about 2" x 3" x 1".
http://en.wikipedia.org/wiki/Diehard_tests were quite happy with the output.
With /dev/random & urandom, I don't care about it anymore.
Can you really measure randomness?
Have you fscked your local propeller head today?
You'll never throw the dice that often, and even if you do, it will never, ever be all 1's.
Hey, every time I throw an infinite number of consecutive dice rolls, it has just as much a chance of rolling all ones as it does of rolling any other sequence...
Bow-ties are cool.
> Surviving an infinite number of rolls is not the problem... The real problem is that if you've got, say, a D20, and you get it to roll a 1 a large number of times, the ones will have all been rolled out. After that it'll have a hard time producing more 1's.
You havn't met my dice then have you. I swear the thinkgeek t-shirt spies have been watching my Tuesday night games.
It was Persi Diaconis, Professor of Statistics at Stanford University.
Read the report here: http://news.stanford.edu/news/2004/june9/diaconis-69.html
Uh, chill out and get out of your basement.
"They were pure niggers." – Noam Chomsky