New Method for Random Number Generation Developed 395
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."
Judging by your comment... (Score:3, Insightful)
Re: (Score:2)
Here's a question about bits of entropy:
If they can mathematically calculate how random something is, can't they just mathematically determine what would be the most random series of numbers, and just use that?
Re: (Score:2)
No. Neither a number nor a sequence of numbers has, by itself, any entropy.
Re: (Score:3, Insightful)
Re: (Score:2)
No, that's really a measure of complexity. It can be used as *a* measure of "randomness", but it is not the same as entropy.
Re: (Score:2)
If they can mathematically calculate how random something is, can't they just mathematically determine what would be the most random series of numbers, and just use that?
Then all that's needed is legislation that requires everyone desiring a random series of numbers to use the one that was pre-calculated for them. Problem solved!
Re: (Score:2)
He never said what the encoding was
Re: (Score:2)
That however doesn't mean that it is any less random. I can make a random sequence using nothing more than 1's and 0's. Including the digit 2 would not make it any more random, it would just increase the randomness per character.
generation of random numbers (Score:5, Funny)
the generation of random number is too important to be left to chance.
Re: (Score:2)
Re: (Score:3, Informative)
Re:generation of random numbers (Score:5, Informative)
XKCD Bait (Score:5, Funny)
Lets play a game, what XKCD am I thinking of?
Re: (Score:2)
Re: (Score:3, Insightful)
Is this your card? [virtualp.us]
obligatory xkcd (Score:4, Funny)
Obligatory Dilbert (Score:2)
And one of my favorites: http://web.archive.org/web/20011027002011/http://dilbert.com/comics/dilbert/archive/images/dilbert2001182781025.gif [archive.org]
Re: (Score:3, Funny)
For those of us whose systems block the Wayback machine as an anonymizer, you might try http://dilbert.com/2001-10-25/ [dilbert.com] instead. (They started putting pretty much all of the old Dilberts online a few months ago.)
Re:Obligatory TheDailyWTF (Score:4, Funny)
Obilgatory TheDailyWTF [thedailywtf.com]
Taken to the next level: (Score:5, Interesting)
Hardware? (Score:4, Insightful)
TFA fails to state whether they used existing memory types or if they intend to use a custom piece of hardware on board.
Re:Hardware? (Score:4, Interesting)
TFA fails to state whether they used existing memory types or if they intend to use a custom piece of hardware on board.
My guess would be custom though not completely different from everyday stuff. I was familiar with "metastability" from my college courses where it was mentioned as a classic problem in electronics [wikipedia.org]. I suppose there could be a way to harvest this data from hardware before it gets corrected. I never thought of this before but if you had a long length of optical fiber cable (longer than what it's rated for use) then you could send messages through that and collect them on the other end. I mean, we implement parity to remove these random flips of bits through transmission, couldn't we also use this to increase randomness of random numbers? I think I've read of the network guys fighting metastability [acm.org] so their incorrectly implemented hardware could probably be exploited as sources of random bits.
What is "more random"? (Score:5, Insightful)
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".
Re: (Score:2)
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".
True random means that each item in your possibility list has equal chances of occurring.
If your possibility list is the numbers 1-10, then each number would have exactly a 10% chance of occurring, in order to be truly random.
If instead some numbers have a 10.001% chance of being chosen, and some others have a 0.999% chance of being chosen, then while the result might appear to be just as random, it is less random than the first case.
Of course anything else that adjusts the outcome and enables further predi
Re: (Score:3, Informative)
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".
True random means that each item in your possibility list has equal chances of occurring.
No, true random means the outcome cannot be predicted with certainty. What you're describing is one particular type of randomness known as the "uniform distribution". Gaussian or binomial random variables, for example, don't have equal likelihood for the outcomes but are still truly random.
Re: (Score:2)
Perfectly random?
Re: (Score:3, Interesting)
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".
Nothing can be ever be considered random. If it is, it's just in a state of "we just don't have a means of measuring it's next value."
You can call me guessing a "number between 1 and 10" random, but that's just because you don't know my method of choosing. If you did, it wouldn't be random at all. If you knew the order of the deck of cards, and precisely each transition of the shuffle, then the next card could easily be predicted. Since you don't have that power, it's considered "random".
Same thing with
Re: (Score:2)
Quantum mechanics would like to have a word with you.
Re: (Score:3, Informative)
Re: (Score:3, Informative)
Bell disagrees, and is backed up by empirical measurement.
Re:What is "more random"? (Score:5, Informative)
In Numerical Recipes for C they list several benchmarks for determining how good one random number generator is compared to another (based on various statistics measures) so it certainly is possible for one method to be more random than another. Read chapter 7 of that book for all the details you could possibly want on this subject (with references to even more information).
One way of generating a good random number in Linux is using /dev/random (which uses a hardware-based random signal as its source, I don't recall the details). However, it isn't fast enough for most applications, outputting only a few bytes per second of random information, although it can serve as a useful seed for other random number generators. Just run 'cat /dev/random > random_bytes.bin' to see its output.
I'm curious what rate random information can be generated using the method in the article. I'm presuming it's fast enough that an application could rely solely on this data without having to use it as a seed for a pseudo-random number generator. The question is how long does it take for the hardware to get to the state where its next value is unpredictable--in the case of /dev/random it's relatively long.
Re: (Score:3, Informative)
/dev/random is slow because it maintains an entropy pool filled by sources of randomness in the hardware -- things like mouse movements, keystroke timings, disk timings, etc. If reading from /dev/random drains the pool faster than it's filled, then /dev/random blocks until there is enough entropy. /dev/urandom uses the same techniques (same pool, even), but it doesn't block when the pool is drained of entropy. Theoretically this means that there could be enough information in the output of /dev/urandom to
Re: (Score:2)
Dedicated hardware random number generators are expensive and therefore aren't found in regular run of the mill consumer electronics. This is a simple, easy to manufacture, solid state device that improves randomness considerably. It's almost impossible to have a true random number generator, so we generally use pseudo-random number generators instead, generally software based ones. The problem is that given a certain seed value, a random number generator will always produce the same outputs. You might
Re: (Score:2)
Re: (Score:2)
There is no such thing as a random number generator, only a psuedo-random number generator.
If you allow special hardware this is almost too easy, listen to a geiger counter click using a microphone, etc.
If you insist on off the shelf PC hardware, simply record the sound input (better with a microphone attached, but just the hisssssssssss is OK too) then hash it or otherwise stir well.
the LSB of the timer for each keyboard interrupt works OK too.
There is probably a theoretical proof, that over a long enough congested enough internet path, you can get bits of randomness out of the least sig bits of
20 times more random? (Score:2)
umm.. errr... wha?
Re: (Score:2)
20 times more random?
I don't get it either. First they claim it's a true random generator that generates "purely random" numbers.
Then they proceed to explain that
... The degree of randomness possible depends on the size of the array ...
Can anybody tell me how this works?
Re: (Score:2)
I'm just going to assume they meant "can generate 20 times more entropy per second per cost-of-hardware than existing methods".
Re:20 times more random? (Score:5, Funny)
Actually Bruce only has a 50% chance of getting the answer in 0.019 seconds. Chuck Norris however just hits the researcher with a round house so hard that his grandmother spits out the answer, 100% of the time.
HM (Score:2)
Would this beat methods such as leaky diodes or radio noise which some systems use to get random data?
WiFi (Score:3, Interesting)
I always thought the WiFi radio in laptops would be a good thing for generating random numbers.
Re:WiFi (Score:5, Funny)
Brilliant! Just assign a bit based on whether or not it works in a given Ubuntu release!
Re:WiFi (Score:5, Funny)
Re: (Score:2)
So when you're generating your keys, all I have to do is blast your wifi and I can pick your keys for you? Cool!
reproducibility (Score:3, Insightful)
Good luck finding the bug in your program with a stream of randoms you'll never be able to reconstruct again.
Re:reproducibility (Score:4, Insightful)
Re: (Score:2)
Well...if you need a predictable stream, then maybe you should capture a single stream, and keep feeding that into the program? Then you can feed the same sequence every time.
Certainly you are right but... with a very small amount of work (a facility for switching out the randomness source), you can work around it easily.
There are plenty of applications where, a strong source of randomness is needed, and reproducibility is not needed at all.
-Steve
Re:reproducibility (Score:4, Insightful)
Horses for courses. If you want reproducible, you don't want true random. If you want security, you do.
Random numbers (Score:2)
9...9...9...9...9...9
Metastable Flip flops still have bias (Score:4, Interesting)
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.
Ratio sensitivity (Score:4, Interesting)
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.
Re:Metastable Flip flops still have bias (Score:5, Informative)
You're confusing Shannon entropy and true randomness. If you have a string of bits that are created by a process that is truly random but has a bias, it's easy to transform it into an unbiased (but shorter) string.
The problem with pseudo-random generators is that they're really not random at all: They're determinstic functions that map a seed onto a sequence of random bits. If you know the function and the seed, you can predict all of it, which leads to potential vulnerabilityies. The point of truly random numbers is that there's no possible information you could have that would enable you to predict it.
Re: (Score:3, Informative)
Somebody should name a law after this phenomenon (Score:2)
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.
Link to actual paper (Score:3, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Informative)
Question: why not simply use the random crap we all have on our PCs to generate random numbers? Say...choose 5 folders at random on a PC. You could use size limits to narrow the search..say between 500Mb and 2Gb. Then make a hash based on those five folders, something like file sizes or time stamps or a combination of the two, wouldn't that be pretty damned random?
Now maybe I'm understanding it wrong, certainly not a crypto expert by any stretch, but surely nobody has the exact combination of downloads+pictures+music+temp+docs that I do, and that data should be able to be mixed in plenty of ways to generate random numbers, yes? And by choosing random folders based on size instead of just choosing defaults you shouldn't run into the "everyone has the same" problem like the default contents of my music or my pictures, so am I missing something?
What you're describing sounds more like something that could be the "seed" for the random number generator - which would then still use an algorithm to generate the "random" numbers (since they're using an algorithm, they'd still just be pseudo-random).
Re: (Score:2)
Re: (Score:2, Insightful)
Re:Random today, but still random tomorrow? (Score:4, Insightful)
It's random folders all the way down.
Re:Random today, but still random tomorrow? (Score:5, Funny)
Question: why not simply use the random crap we all have on our PCs to generate random numbers? Say...choose 5 folders at random on a PC.
To understand recursion one must first understand recursion.
Re: (Score:2)
Determinism, we don't need no stinkin' determinism.
Re: (Score:2)
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?
A secure implementation of this would use some deterministic post-processing element (these days based on the AES-128 or SHA-256 primitives), so that even when the source of non-determinacy fails, you still get unpredictable output, as long as the cryptographic primitive has not been breached.
On the other hand, we still haven't got a good random number generator in our libc, and we can't just use RAND_bytes everywhere for licensing reasons. So our problems are far more mundane.
Re: (Score:2)
For licensing reasons = because of soft patent madness?
Re: (Score:2)
For licensing reasons = because of soft patent madness?
No, the OpenSSL license is incompatible with the GPL, so you have to think twice before using code from libcrypto, however convenient it might be.
This Is What's Wrong With Slashdot (Score:2)
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?
Re: (Score:2)
A comment containing absolutely nothing but handwaving conjecture is moderated "Interesting".
I often find conjecture to be more interesting than dull facts. GP was a good example, I personally find the mechanics of the random number generator to be boring. "It might be non-random but beyond our current prediction methods" is more interesting.
Also... hi, you're on the internet. What the hell did you expect?
Re: (Score:2)
Re: (Score:3, Funny)
Would you prefer tits or GTFO?
I'd prefer tits.
And random the day after that. (Score:2)
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.
Re: (Score:2)
I really don't think we need any dangerous new entropy source, we have collect plenty of entropy already, and when dealing with something as important as getting random numbers from an RNG if it ain't broke don't fix it
Re: (Score:2)
Part of the source for this randomness is the propagation of electricity in the circuit which can be different due to manufacturing impurities. You could potentially predict it, if you had the individual chip. That's better than what we have now, by a mile.
Re: (Score:2)
More importantly, the process variation of the transistors for each bit could lead each flip-flop to have its own, non-equal probability distribution. Thus, as certain bits would be more likely to be a 1 or 0, it's not truly random either. It would be like a 'fingerprint' for a specific piece of hardware. Run a few million random number requests and look at the distribution of the bits. Match them up, and the machines are likely to be the same (within the confidence interval after you run your statistic
Re: (Score:3, Informative)
If it's "purely" random (as they put it), then how can you measure the difference between it and a "conventional" method? Wouldn't comparing a pseudo random source to "true" randomness be like comparing a finit
Re: (Score:3)
Randomness is all about perception, i think.
The roll of a die is random (enough) for gaming because most people can't control their hand and the environment with enough precision to control/predict the outcome. In reality, the outcome is completely causal. The starting orientation of the die, the bounciness of the die, the sharpness of the edges, the velocity imparted by the hand, the hardness and friction of the rolling surface determine what the roll will be. With enough control over those inputs the r
Re: (Score:2)
Re: (Score:2)
And the half that is random is not very random, given that it's relatively short, all lower-case letters and digits, and emphasizes keys that can be found towards the middle of a QWERTY keyboard.
Re:This is a random comment. (Score:4, Insightful)
Re:This is a random comment. (Score:5, Insightful)
You bring this up as a humor point, but it can be a small problem, I think, when "non-random" sequences are removed from possible random number generations. For example, if a 4-digit pre-generated PIN is not allowed to use certain sequence types such as sequential, all the same, paired pairs, etc., it may take a fair slice out of the available keyspace (not sure that's the right word, but it's close enough), at least enough to narrow down the ambiguity in case some hints about the PIN are known by an attacker.
It's less of a problem with longer passwords, as the maximum entropy for a given entry expands while patterns take smaller bites out the available space, but it does reduce the possible entropy slightly.
It also reminds me of a Dilbert strip where he visits the accounting trolls, and they take him to their random number generator, which is another troll saying, "9... 9... 9... 9..." Dilbert asks if it's really random, and the first troll says, "That's the problem with randomness: you never really know."
Re:This is a random comment. (Score:5, Interesting)
Indeed. I listened to a podcast a while back in which Robert Krulwich (RadioLab?) discussed randomness with a researcher and how we think about randomness.
A scientist he interviewed stated that she assigned tasks to several different teams. For one team, she instructed them to flip a coin some fixed number of times (perhaps 100) and to then report the sequence of heads and tails (H H T H T T H T T T etc). For the second team, she instructed them to NOT flip a coin, but to simply write down a sequence that they think might be produced by the flipping of the coin. The teams each present their report, and she is not told which list was generated by which means.
However, she said it was easy to spot the "human" generated list, because it rarely contained a sequence of more than a few sequential entries of H H H H, for example. Whereas the truly random list might have even up to NINE sequential heads or tails. The average human just couldn't fathom such a "random" sequence [mathematicians excluded, naturally].
Re: (Score:3, Informative)
Radiolab, yes. Episode called Stochasticity [wnyc.org].
Re: (Score:3)
I do this as a teaching exercise in my intro stats class: give the instructions; split into two teams; leave; and come back in when a student knocks on the door. You can spot the difference almost immediately, with a sequence of about 50 "tosses".
It also shows them that absence of evidence is not evidence of absence. Usually, both of the teams gets approximately 50/50 distribution of H/T (within the margin of statistical significance), so this test is shown inadequate. However, once you write down the run-l
Re:This is a random comment. (Score:5, Funny)
2 to the 9'th is 256, so most random sequences would not have had 9 sequential results in a row.
In a world where 2^9 = 256, absolutely anything can happen.
Re: (Score:3, Interesting)
Re: (Score:2)
How can you tell?
Re: (Score:2)
Re:This is a random comment. (Score:4, Funny)
Man, no wonder you're here.
Re: (Score:3, Funny)
He's here because his grandmother can generate babies.
Re:This is a random comment. (Score:5, Funny)
Still? Damn, my mother can't even do that anymore. I don't even want to think about my 87 year old grandmother giving it a try.
Re: (Score:3, Interesting)
Keep in mind that it's possible for a 15-year-old to be a mother, 30-year-old to be a grandmother and a great grandmother at 45.
And since there are women who have given birth at 60 [wikipedia.org], you could technically be a great great grandmother at 60 AND have a kid who is younger.
Tacky, perhaps, but from a biological perspective you've certainly been successful.
Re: (Score:2)
If you want a random binary sequence, the ASCII result would less likely be readable.
If you want a random number, chances are you'll get only digits.
Re: (Score:2)
It could be a random number base64 encoded.
Re: (Score:2, Insightful)
Re: (Score:3, Funny)
So your suggestion is to generate a random with a random? How do you get the random slashdot thread?
From the previous random, duh!
Re: (Score:2)
No kidding - life was simpler back then.
Stupid P.E.T.A.
Re: (Score:3, Funny)
The only problem with the cat was they have 9 lives. No wonder we always kept getting live cats when we opened the box.
Re:Uhm (Score:4, Informative)
http://en.wikipedia.org/wiki/Entropy_(information_theory) [wikipedia.org]
Ask Slashdot (Score:2)
I think we finally have the answer to Friday's Ask Slashdot [slashdot.org].
Re:Or just flip a coin (Score:5, Interesting)
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.