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
Why not just use analog hardware to do it; i.e. sampling of white noise?
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.
The longer people look without finding increases confidence...
This is a failure to make a good a random FullNameGenerator from two less good generators (FirstNameGenerator, SurnameGenerator). David is a common name. Zuckerman is a common name. David Zuckerman is not uncommon enough.
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)
to be sure: http://dilbert.com/strip/2001-10-25
Does that count as a reference to Trump? Does this post? Does a response to any of these questions count as such?
File under 'M' for 'Manic ranting'
Neither of these has a uniform distribution. In the former example, lower numbers are more likely. In the latter example, higher numbers are more likely.
Or this one
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.
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.
Or in the style of von Neumann, use transitions between 0 and 1 as they will come equally often. Map 01 to 0 and 10 to 1, for example.
Escher was the first MC and Giger invented the HR department.
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!
Not necessarily.
Low quality random means the distribution has biases or predictable patterns over long sequences.
Take eg, noise from a microphone. I has a distribution bias, and a few other problems that make it bad as a random source.
It is however, completely independent from data taken from a camera, which will have its own biases.
The idea here is pretty good- two biased sources that have uncorrelated biases can get you a less biased, more uniform distribution of values, and better entropy per sample.
Another source might be magnetometer data, or accellerometer data. There will be ramdom "jitter" around the data read. The data figure averages out to the reading you use normally. In this case, we dont care what direction you are moving or pointing. We are interested in the jitter, which concentrates around the bias of your heading. Naturally, it clusters around the bias, and is not uniform, making it a low quality source.
The more of these uncorrelated but low quality sources you can leverage, the more uniform and less predictable the sample distribution will be.
That is literally how security on the PS3 worked.
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...
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.
Good summary. This really is _theoretical_ work.
In practice, you just put enough "dirty"/"weak" random bits into a good CPRNG, and that is it. As long as your estimate of the entropy contained is not too high, this works and is secure. The problem people having with random-number generation is that they either select a bad (C)PRNG or they mess up the entropy estimation in seeding, e.g. due to overlooking negative effects from virtualization. Some also re-use initial, stored seeds (e.g. by cloning a VM and not redoing the seeds), and that is really a beginner's mistake. These are all engineering errors because the people doing it do not understand what they are doing.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
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.
"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.