News for hackers. Stuff that matters.
Re:Academics Make Theoretical Breakthrough in Random Number ... by electrograv on Wednesday May 18, 2016 @12:37AM (#11719765)
> 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

"Independent and no correlations" sounds like a crippling assumption if you want to use any two deterministic PSRNGs. How can you possibly guarantee they're completely un-correlated and independent without seeding them with collectively more bits of entropy than you can get out of the combined system?

I'm not sure what "independent" is even supposed to mean for a deterministic sequence, which by definition is recursively dependent.

Re:Academics Make Theoretical Breakthrough in Random Number ... by njohnson41 on Wednesday May 18, 2016 @12:42AM (#11719799)
That's because this result is not about combining weak deterministic PRNGs, it's about combining entropy sources (like two hardware random number generators).

This has always been possible, but it sounds like they've lowered the minimum entropy needed in the source streams to produce a high-quality output.

Re:Academics Make Theoretical Breakthrough in Random Number ... by electrograv on Wednesday May 18, 2016 @12:57AM (#11719853)
Thanks for the explanation, that makes sense. I think this quote threw me off:

> The academics’ latest work hurdles those restrictions allowing the use of sequences that are only weakly random

What does "weakly random" mean, if not a PRNG? Just low pure entropy per bit of sequence data? What's the threshold then between strong random and weak random -- wouldn't it be a continuum of entropy?

Minor nitpick: Also, how can a deterministic PRNG have less entropy (0) than that of its seed?

Re:Academics Make Theoretical Breakthrough in Random Number ... by njohnson41 on Wednesday May 18, 2016 @01:16AM (#11719922)
Right, the amount of entropy per bit of sequence is always between 0 (deterministic) and 1 (every bit is independent and 50/50) (... or between 0 and log2(k) in general if the element varies over a set of k things). These "weak" sources just have low entropy per bit. They could be biased (more 0s than 1s) or correlated (long runs of 0s/1s or periodicity), or just have some other pattern that sometimes holds.

A deterministic PRNG's sequence has exactly the entropy of it's seed, actually, but it has 0 bits of entropy per symbol, because its sequence is infinite.

The thing most people get confused about with entropy is in thinking that entropy is a property of some single object, like a bit string. Really, entropy is always a measurement about a probability distribution, just like mean or variance is. In the usual case with random streams, the distribution is P(x_i | x_i-1 ... x_0) for bits x_i in the stream, i.e. the distribution remaining for the current bit even if we know all previous bits. For a deterministic PRNG, once we can extract the key from the history (given unlimited compute power) that distribution becomes deterministic, so the entropy is 0.

Re:Academics Make Theoretical Breakthrough in Random Number ... by dietrichepp on Wednesday May 18, 2016 @01:32AM (#11719978)
The entropy of a single object is a meaningful concept. It is usually called Kolmogorov complexity.
Re:Academics Make Theoretical Breakthrough in Random Number ... by njohnson41 on Wednesday May 18, 2016 @01:47AM (#11720022)
Kolmogorov complexity is definitely meaningful, but it's not (Shannon) entropy, just conceptually similar. Many people think of something like Kolmogorov-complex sequences when they think of "random" sequences, which is (IMO) why they have trouble thinking of entropy as being about a probability distribution.

The one case where they coincide (sort of) is if you believe your random sequence is generated by a randomly chosen Turing machine, which I've only really seen in philosophical settings.

A uniformly chosen 64-bit integer still has exactly 64 bits of entropy, regardless of how much Kolmogorov complexity the actual bits you generate have.

Re:Academics Make Theoretical Breakthrough in Random Number ... by x0x0 on Wednesday May 18, 2016 @01:45AM (#11720015)
I'm not sure if I know the precise definition, but I think I remember how it's used.

weakly random:

let X a random variable over {0,1}^n. That is, X is a distribution over bit sequences of length n. Distribution means I assign each of the 2^n bit sequences a nonnegative probability that sums to 1.

If X were uniform (true random), then each sequence in the 2^n such possible sequences would have probability 2^-n. Unfortunately, we have no such sequence generators, or life would be easy.

Let the min entropy of X be the largest natural k such that P[X=x] <= 2^-k for every x. ie roughly how likely are such sequences to take their most likely value. Or how biased is our RV.

eg: uniform random over sequences of length n would have min-entropy n.

Again, the problem is we have no uniform random sequences available to us. Instead, we have biased sequences. So there is a long history of asking how can we take a biased random sequence and turn it into a random sequence. You do this with an extractor.

For example, suppose we had a sequence which produced independent bits 1 with probability p and 0 with probability q=1-p. However, we don't know p. What we could do (an extractor!) is use two sequence bits to produce one output bit, as so: sequence 0,1 has probability p x q, and sequence 1,0 has probability q x p. Map 0,1 to 0 and 1,0 to 1, and ignore 0,0 and 1,1. Now we can produce 0 with probability 1/2 and 1 with probability 1/2, ie we have uniform random from an input sequence of unknown bias (but perfectly uncorrelated, which also doesn't exist in nature. Life is hard.)

We measure the quality of extractors by calculating how bad (lower entropy) a sequence they can take and how close (statistical distance, which has a technical definition) they can output a distribution close to uniform.

Anyway, I got distracted, but in general weakly random means distributions or sequences which are biased. The less biased they are the more they're called "almost random." In general, you want to build extractors that run on sequences with unknown bias.

hth

Re:Academics Make Theoretical Breakthrough in Random Number ... by Sophistifunk on Wednesday May 18, 2016 @01:22AM (#11719948)
> how can a deterministic PRNG have less entropy (0) than that of its seed

If there's any way two seeds can eventually lead to identical internal states would be one example.

Re:Academics Make Theoretical Breakthrough in Random Number ... by hinkley on Wednesday May 18, 2016 @12:46PM (#11723272)
Let's say I have a machine that runs one cron job. It looks for work, writes a few files if it finds some. Over a three day holiday weekend, no work is queued so the machine hardly does anything. And it's on a vlan so there's little to no broadcast traffic hitting it.

Tuesday morning I ssh into the box. How much high quality entropy do you think I got from the nearly deterministic network and disc traffic on this machine? Maybe a few bits.

What I'm hoping comes of this is that we can find a better set of inputs for several/random, and that we can use more conservative estimates of entropy from the sources that are already used. Also I hope we find a way to treat intel's hardware RNG as a low quality input (currently it's a no quality input.)

Re:Academics Make Theoretical Breakthrough in Random Number ... by gizmo686 on Wednesday May 18, 2016 @12:47AM (#11719813)
A deterministic PSRNG has (by definition) 0 entropy, making them unfit for use as a source.

The point of an extractor (such as the one being presented here) is to take two (or more) sources of low quality true randomness, and produce a high quality random output.

Re:Academics Make Theoretical Breakthrough in Random Number ... by garrettgrimsley on Wednesday May 18, 2016 @01:59AM (#11720060)
Isn't it the security of the seed that determines whether a CSPRNG is an appropriate source of entropy? I was under the impression that if your seed is secure and you're using a CSPRNG then there isn't a problem with using that generator as an entropy source.
Re:Academics Make Theoretical Breakthrough in Random Number ... by dgacmu on Wednesday May 18, 2016 @02:58AM (#11720263)
No - you're mixing the terms "entropy" and "(pseudo)random bits". A CSPRNG can't be a source of entropy, period -- as noted above, it's always a deterministic function of its inputs. Entropy comes from truly unpredictable events, such as thermal noise, radioactive decay or cosmic radiation, etc.

One uses a CSPRNG to generate a sequence of pseudorandom bits, wherein the sequence can only be predicted if the initial input to the CSPRNG is known (the "seed"). If you want a really "random" key, the usual trick is to "harvest" some entropy from the system (e.g., from hardware sources, such as mouse timings, or dedicated hardware random generators based upon things believed to be physically random), condition it (make it uniformly distributed, unbiased, etc.), and then use those harvested "truly random" bits to seed your CSPRNG.

Re:Academics Make Theoretical Breakthrough in Random Number ... by tptacek on Wednesday May 18, 2016 @11:28AM (#11722619)
Real, sound cryptosystems routinely --- in fact, almost invariably --- source their keys from CSPRNGs. CSPRNGs can't source entropy, as you say, but in cryptography we're not looking for entropy. We're looking for unpredictability.

What confuses people is that cryptography usually jumpstarts itself with a small amount of entropy (or something close enough to entropy to count). That small seed of entropy gives us unpredictability for the life of the system, even though the bits we actually use will come from deterministic processes.

Re:Academics Make Theoretical Breakthrough in Random Number ... by garrettgrimsley on Wednesday May 18, 2016 @11:22AM (#11722578)
Got it, thanks!
Re:Academics Make Theoretical Breakthrough in Random Number ... by redcalx on Wednesday May 18, 2016 @10:05AM (#11722002)
Shannon entropy is a measure of how much new information each symbol in a communication channel gives us. In the case of a PRNG, if we know the seed then each symbol tells us nothing because we can generate the exact sequence from the seed, hence the Shannon entropy of each symbol is zero (provided you know the PRNG and the seed! - if you don't then you can determine them from a sequence, but that's another topic!).
Re:Academics Make Theoretical Breakthrough in Random Number ... by Aelinsaar on Wednesday May 18, 2016 @12:40AM (#11719792)
So... this is a bit like the XKCD comic, killing cancer cells in a petri dish, with a handgun? That is to say, what a nice theory, but in practice you'll rarely if ever find the conditions are met for it to work?
Re:Academics Make Theoretical Breakthrough in Random Number ... by coldtea on Wednesday May 18, 2016 @04:47AM (#11720583)
No, it's just a misunderstanding of the paper.
Re:Academics Make Theoretical Breakthrough in Random Number ... by Aelinsaar on Wednesday May 18, 2016 @09:28AM (#11721734)
Fair enough.