Slashdot Mirror
Theoretical Breakthrough Made In Random Number Generation (threatpost.com)
msm1267 quotes a report from Threatpost: Two University of Texas academics have made what some experts believe is a breakthrough in random number generation that could have longstanding implications for cryptography and computer security. David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, published a paper in March that will be presented in June at the Symposium on Theory of Computing. The paper describes how the academics devised a method for the generation of high quality random numbers. The work is theoretical, but Zuckerman said down the road it could lead to a number of practical advances in cryptography, scientific polling, and the study of other complex environments such as the climate. "We show that if you have two low-quality random sources -- lower quality sources are much easier to come by -- two sources that are independent and have no correlations between them, you can combine them in a way to produce a high-quality random number," Zuckerman said. "People have been trying to do this for quite some time. Previous methods required the low-quality sources to be not that low, but more moderately high quality. We improved it dramatically." The technical details are described in the academics' paper "Explicit Two-Source Extractors and Resilient Functions."
And the secret algorithm is... multiplication!
Note: IANAM
FP Also I tried to read the brief and as a CS major it was above my head. Must be a math thing.
Hold up, wait a minute, let me put some pimpin in it
Now all you astronomers have to worry about is small numbers statistics.
My understanding is that, while a nice development, this is FAR from a breakthrough, theoretical or otherwise - the core ideas have been widely known in the cryptography community for a long time.
Wow! David Zuckerman, the writer/producer of Family Guy is also a noted Computer Science professor...Man, a lot of the jokes make more sense now!
Why not just use analog hardware to do it; i.e. sampling of white noise?
- amount of time (in milliseconds) it takes, after a /. article appears, for the first "First Post!" or "Cows say MOO" post.
- Number of references to Trump on /. over a period of three consecutive days.
Worst of all it's random number generator... exactly how hard would it be to test it?
Random number generators are notoriously hard to test. You can run as many tests as you like, and find no pattern. But that doesn't mean no pattern is there.
I'm theoretically amazed that this theoretical breakthrough was ever theorized! Theoretically speaking, if the theory espoused in this theoretical breakthrough could theoretically be accomplished in actuality (or it laypersons' terms, "fo realz") ...the theoretical applications of this un-accomplishment could theoretically change the world of theoretical cryptography in ways which at this point could ONLY BE THEORIZED.
The longer people look without finding increases confidence...
http://dilbert.com/strip/2001-...
A few days ago I had dinner with a friend of mine who worked on this project. Curiosity got the best of me and I said: "Level with me man, did you really create a random number generator?" And he said: "More or less."
"I like to lick butts!" by MobileTatsu-NJG (#32700246) (Score:5, Informative)
Yep, but you've always got to check the n+1 case for trivial repetition...
to be sure: http://dilbert.com/strip/2001-10-25
The problem is that one can never be sure that an attacker hasn't found a pattern, but is holding it to themselves.
I also don't see the breakthrough. We can do the same thing by simply concatenating the previous output and the new input to the generator and hashing it.
I see this very salient question raised earlier-- why not use a dedicated white noise generator for random picks?
Most places you are going to need a good random integer are going to be in places where a dedicated diode based noise source is going to add cost to the system, and thus not be ideal. Things like an ATM machine, a cellphone, a laptop, whatever.
The cost is not in the actual component cost (a diode costs what, a few cents?) but in a standardized interface to that noise source.
Conversely, there are several very low quality sample sources that have no physical correlation with each other on such systems that can be leveraged, which have well defined methods of access, which add zero additional cost to the system.
Say for instance, microphone input + radio noise floor on a cellphone. Perhaps even data from the front and rear cameras as well. (EG, take Foo miliseconds of audio from the microphone, get an snr statistic from the radio, and have a pseudorandom shuffle done on data from the front and rear cameras. These sources are, independently, horrible sources of random. They are however, independent of each other. If this guy has found a really good way of getting good random from bad sources, then a quality random sequence can be generated quickly and cheaply this way. This would allow the device to rapidly produce quality encrypted connections without a heavy computational load, vastly improving the security of the communication, and do so without any additional OS level support, or extra hardware.)
When deriving a key pair for the likes of GPG, it can take several minutes of "random" activity on the computer to generate a sufficiently high quality entropy pool for key generation. That is far too slow to have really good, rapidly changing encryption on a high security connection. Something like this could let you generate demonstrably random AES 256 keys rapidly on the fly, and have a communication channel not even the NSA can crack.
The trick here is for them to reliably demonstrate that the rapidly produced sequences are indeed quality random sequences with no decernable pattern.
"two sources that are independent and have no correlations between them"
I TOLD you mot to look. Now thanks to the observer effect,.there IS something they both have in common! Co-relationships are now inevitable unless we can find a recipient that has nothing in common with you - anyone got a spare alien around to read the message?
"Transparent" is a shit show that trades on every stereotype going. A man in drag is NOT a transsexual.
Some genius.
two sources that are independent and have no correlations between them
This requirement seems already a bit far from "low-quality".
The importance of random numbers in Crypto is that encryption keys must be prime for most if not all of the encryption algorithms to work. It is very hard to generate large prime numbers (e.g. 4000 bits) using an exact methods but it is somewhat easy to calculate the probability that a large number is prime. So what we can do is generate a highly probable prime number by simply generating random numbers and checking to see if they are probably prime. If the random numbers you use to generate keys in this way are predictable then your keys are predictable. Thus the quality of randomness is very important to the quality of the encryption key.
Reminds me of the joke, "I'm not going to drink anymore.....(whisper.)...or any less."
As long as Apple gets it and shuffle stops jumping back to the same area many, many times a day then I'll be happy. That shit gets on my nerves, yo!
Is it really possible to define the unpredictable?
See the blog post by a graduate student at MIT:
https://mittheory.wordpress.com/2015/08/15/purifying-spoiled-randomness-with-spoiled-randomness/
They do outline a construction. It's not just an existence proof.
Any guest worker system is indistinguishable from indentured servitude.
I think their idea is to skip the bits in 1st source based on the bits in the 2nd source. So, on average, 2n bits from the 1st source and 2n bits from the 2nd source would produce n random bits.
Any guest worker system is indistinguishable from indentured servitude.
heck with that. I use brown noise in my SJW random number generator. I tried using black noise, but the numbers kept moving to and 'fro. I used to use pink noise, but it was in an elevator with some XY chromosomes, and next thing I knew, the sequencer was stuck in a loop.
The importance of random numbers in Crypto is that many symmetric encryption protocols rely on efficiently generating random numbers (e.g., nonces, symmetric keys).
The quality of the random numbers you use to generate prime keys for RSA are of course important too, but generally generating primes isn't done as frequently (because testing them is relatively slow) so efficiently combining two low-entropy sources isn't as critical because you can combine sources of low-entropy and achieve high quality random number using currently known methods.
One way to think about this is to understand how to get a unbiased number out of a biased coin? A simplistic Von-Neumann extractor.
Basically, flip the coin twice, discard HH/TT and assign HT and TH to 0 and one. This throws away alot of flips (depending on how biased the coin is) but gets you what you want if the flips are independent.
Now imagine instead of a 2x2 matrix, a really large matrix that takes in a sequence of flips that depends on the minimum entropy of the source so that you avoid throwing away flips. How do you fill the elements of this matrix?
You can watch here and learn something...
Let's test it with a string of zeros and a string of ones. Both are some low quality random.
I.e. in situations where you are entropy-starved (so not on regular computers) and getting the, say, 256 bits of entropy to seed a CPRNG is hard to come by. This only applies to really small embedded systems that have no A/D converters or the like. (With an AD converter, just sample some noisy source or even an open input and you get something like > 0.1 bit entropy per sample. Needs careful design though.) Whether such a very small embedded system can the use the math needed here is a different question. In most cases, the right solution is to just sample more noise-source input.
So maybe a "theoretical breakthrough", but likely not very relevant in practice.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Which is why, contrary to what the GP says, theoretical results are of such high importance. It's easy to miss patterns in apparently random numbers, so such tests are always open to question, but if you can prove certain properties about said stream theoretically then, so long as the implementation is good, that stream is 100% guaranteed to have those properties.
But when is random not random enough? Aren't random number generators sufficiently random for all intents and purposes?
Finally, slashdot, some honest to goodness computer science. Bravo.
So basically, the theory is that two bad batches of numbers can generate a good batch of numbers. I call bull.
Note how they don't show any kind of proof ... but claim that it is going to save the world.
Setec Astronomy
Which hinges on the quality of the hash function. None of these cryptographic hash functions can be fully proven to work. Their applications seem to be leaps and bounds beyond the best theoretical work, but only by stretching their own weak theoretical guarantees very thin.
So this work is somewhat low-level on what it says it can do, but has much firmer foundations.
Random number generators are notoriously pointless to test.
You know they're not actually random (I'm with Einstein on this one).
"7,7,7,7,7,7,7,7,7,7,7,7,..." is just as "random" as any other sequence.
People need to shut the fuck up about random numbers because they don't want random numbers.
They want uniformly distributed numbers that don't fit any easily-identifiable pattern.
The problem is that it outputs its internal state. Masking the output whilst maintaining its random characteristics is a difficult problem to solve ,not dissimilar to what this paper would need to solve.
Finally a good explanation from a person who seems to understand the topic. Thank you.
Let me know when you can prove that, Nobel have a prize for you ;)
That being the problem with randomness, it is borderline impossible to prove (and if you are unlucky, easier to disprove).
The associated problem in cryptography is trustable randomness ;)
The classic case of that is the RNG embedded in most Intel chips, where Intel refuse to give
specific details, and no one would trust them anyway, so it is not used for anything really secure.
That is not a problem with Intel specifically of course, it is a problem with trusting any 3rd party.
The main issue with a quantum noise based RNG is how do you verify it - just trust the vendor? ;)
We used to use Yarrow for this purpose, but it suffered from the problem that you needed to estimate the entropy of your sources. Fortuna was introduced to address this, and allows you to combine entropy sources without estimating the amount of entropy that they contain. What does this add beyond that?
I am TheRaven on Soylent News
"7,7,7,7,7,7,7,7,7,7,7,7,..." is just as "random" as any other sequence.
But you can calculate the exact probability with which this sequence will be produced by a real random number generator, and if this probability is extremely low and nevertheless the sequence occurs, then that's reason enough to reject your pseudo-random number generator.
They do outline a construction. It's not just an existence proof.
They do? It didn't seem very explicit at all.
Lots of mathematics though.
I should use this sig to advertise my book ISBN-13 : 978-1501515132.
function getLowQualityRandomSource1() { /// determined by fair random die roll /// determined by fair random die roll /// uber-random!!!
return 4;
};
function getLowQualityRandomSource2() {
return 6;
};
function getHighQualityRandomSource() {
return getLowQualityRandomSource1() + getLowQualityRandomSouce2();
};
"More" was one of his inputs and "Less" was the other.
There is a probability of anything happening, the question is if the probability actually matches what's predicted. For any infinitely large set of random numbers is an infinitely large set of the same number being repeated. sexconker is 100% correct once you understand they used an extremely example to prove a point.
So if you combine a Trump speech with a Palin speech, you get random Shakespeare?
Table-ized A.I.
The probability of "7,7,7,7,7,7,7,7,7,7,7,7" is the same as 1,2,3,4,5,6,7,8,9,0,1,2 or any other 13-int sequence.
You are thinking of placing sequences in categories (k consecutive numbers), for which the probability indeed decreases rapidly with k.
But that requires you to define similar sequences, which is a form of finding patterns.
NB: The message above might reflect my opinion right now, but not necessarily tomorrow or next year.