Academics Make Theoretical Breakthrough in Random Number Generation
threatpost.com
threatpost.com
Our problem with cryptography is not the quality of random numbers. We are fine at generating unpredictable, decorrelated bits for keys, nonces, and IVs. Soundly designed systems aren't attacked through the quality of their entropy inputs†.
The problem we have with randomness and entropy is logistical. So long as our CSPRNGs need initial, secret entropy sources of any kind, there will be a distinction between the insecure state of the system before it is initialized and the (permanent) secure state of the system after it's been initialized. And so long as we continue building software on general purpose operating systems, there will be events (forking, unsuspending, unpickling, resuming VMs, cloning VMs) that violate our assumptions about which state we're in.
Secure randomness isn't a computational or cryptographic problem (or at least, the cryptographic part of the problem has long been thoroughly solved). It's a systems programming problem. It's back in the un-fun realm of "all software has bugs and all bugs are potential security problems".
It's for that reason that the big problem in cryptography right now isn't "generate better random", but instead "factor out as much as possible our dependence on randomness". Deterministic DSA and EdDSA are examples of this trend, as are SIV and Nonce-Misuse Resistant AEADs.
† (unsound systems frequently are, but that just makes my point for me)
We already know how to build secure random number generators. Pretty much every real world problem with random numbers can be traced back to people not using secure random numbers (or not using random numbers at all due to bugs) or using random number generators before they were properly initialized (early boot time entropy problems).
This random number thing is so clouded in mystery and a lot of stuff gets proposed that solves nothing (like quantum RNGs) and stuff that's more folklore than anything else (depleting entropy and the whole /dev/random story). In the end it's quite simple: You can build a secure RNG out of any secure hash or symmetric cipher. Once you seeded it with a couple of random bytes it's secure forever.
"it's quite simple" - Are we talking security here? Then that phrase can't apply.
"You can build a secure <something> out of any <something else>." - Is that how security works?
"it's secure forever." - Gung'f jung Pnrfne fnvq. (This sentence is "encrypted" in case that's not clear)
"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.
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.
> 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?
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.
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.
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
If there's any way two seeds can eventually lead to identical internal states would be one example.
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.)
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.
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.
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.
(Edit: not the algo itself, just the notion of combining randomness.)
Interestingly the prof emailed me the next semester because that had caught his attention and he had worked out that the two processes are ultimately identical, just using very different notations.
For those of us who don't know systems theory, is there a simpler explanation of this? It sounds interesting
However, their Laplace transforms are much easier: X(s) and R(s), and because of how Laplace transforms work, F(s)X(s) (convolution becomes multiplication after a Laplace transform). So if F(s) is 1 / R(s), F(s)X(s) = X(s) / R(s), which means all of the correlation in X(s) is divided out, and you're left with an uncorrelated function, or fair coin in this case.
Basically, it proves that creating a biased coin really is impossible.
TL;DR: if you want unbiased coin IRL, make sure you catch it before it hits the ground.
one cannot, for example, weight a coin so that it is substantially more likely to land “heads” than “tails” when flipped and caught in the hand in the usual manner. Coin tosses can be biased only if the coin is allowed to bounce or be spun rather than simply flipped in the air.
Say you took a small disk shaped object like a hockey puck with a window on it and you filled it with sand. 50% white sand and 50% black sand. Inside the puck would be blades that are attached to a motor and rotated slowly to constantly change the pattern. The pattern formed in the window would be truly random wouldn't it? You could mount this to a PCIE card with a camera...
And they are less cool than avalanche noise, when you're asking nerds like us.
IMHO, one of the best devices to get low amounts of randomness is still the dice (cube). Casino-grade, if you're anal about it. I use that to throw Diceware passphrases.
I'd certainly dispute the "memorable" part for most people on Earth.
You could use this on $LANGUAGE of your choice, or $CORPUS of your choice.
(Also, it seems much more memorable to me than an equivalent random stream of bits are.)
Still, neither "wrowd", nor "aut", nor "settea" looks or sounds English-like to me. I wouldn't even begin to know how to pronounce it.
It's nice in a sense, sure, but I suppose I could even remember (real) French words better, despite all those accents and me not speaking French.
"aut": a logarithmic unit of measurement indicating the level of automation of a process. "I think we can get another couple of auts out of the sentiment-analysis pipeline."
"settea": a genus of shrubs in the family Settaceae.
I frown on casually lying to people over the internet. The term 'OK' originally stood for 'all correct'.
http://www.etymonline.com/index.php?term=OK
http://www.straightdope.com/columns/read/503/what-does-ok-st...
You're trying to allude to NOKD, which is (1) completely unrelated, and (2) not lost.
This is one interpretation of QM. There are many theories explaining eigenbasis collapse (the "random-looking" phenomenon), and some of them are deterministic.
The important thing here is that the data stream is hard or impossible to predict. It doesn't have to be truly random, because we don't even know if "truly random" is a sensible thing to ask for. What we're actually hoping is that you can't predict the result of a measurement, whether or not it's because of randomness or something else.
Most RNGs also don't rely on the uncertainty principle (or, more generally, non-commutative measurements), but instead on e.g. radioactive decay. This is an eigenbasis collapse mechanism (with the two eigenstates being "this thing hasn't decayed" or "this thing has decayed"), but it's not based on uncertainty. This is easier to build physically.
The uncertainty principle isn't the aspect of quantum mechanics that is used in these RNGs. They only need the fact that they can perform an action (measurement of some observable) whose outcome is not predictable. They do not attempt to measure different observables, since this would not help produce randomness. It is in essence just a (theoretically ideal) dice roll.
Basically, it removes the possible attack vector of replacing any command-and-control circuitry with your own, suborned, components.
[0] - https://www.llnl.gov/news/lawrence-livermore-scientist-devel...
Also, it integrates very well. The smaller the diode, the better randomness you'll get.
But, yes, with enough precision a resistor would do.
For example, perhaps the black grains have a slightly different density, so they might tend to congregate more on the upper or lower side of the window, ever so slightly.
In general, natural processes seldom produce perfectly unbiased streams of independent coin flips. There's usually some post processing.
If two such devices were identical in every way and started from the same conditions (i.e: the sands were placed in the devices the exact same way) then over a sufficient amount of time the sand mixture in the two devices would reach an identical equilibrium state of mixing. At least that's how two gases would act. No idea about sand.
Your argument basically boils down to "chaos theory is wrong, because I /can/ know everything".
Over time the sand could (perhaps) grind itself into flour and not exude the same mechanical properties anymore.
Finally, even if that worked, it might be good for what, 2,3, maybe 5 samples per second. If you take too many pictures before the sand moves, it's no longer random. What if I need millions of random numbers ?
> We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least logCn for a large enough constant~C. Our extractor outputs one bit and has error n−(1). The best previous extractor, by Bourgain, required each source to have min-entropy 499n.
> A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n1−, for any 0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n−q bits are chosen almost \polylog(n)-wise independently, and the remaining q=n1− bits are chosen by an adversary as an arbitrary function of the n−q bits. The best previous construction, by Viola, achieved q=n12− .
> Our explicit two-source extractor directly implies an explicit construction of a 2(loglogN)O(1)-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.
Also, this paper was peer-reviewed and published at one of the top theory conferences in the field. This doesn't guarantee the proof is correct, but it means it received a certain level of scrutiny during the review process.
Also also, this paper being public (and high-profile) means that the probability of some mythical 'bug' in the proof remaining undiscovered for long enough for the technique to be applied to real systems is exactly zero.
I don't understand. Isn't this like the family of someone accused of spying saying "he's not a spy, he's a teacher"?
It would be much easier to just code a flaw into the actual implementations of RNGs based on this.
It doesn't matter if a few turn out unreliable, predictable or if they malfunction, you just need those first few hundred bits to seed your system CSPRNG with.
1. They can give userland programs direct access to a permanently "seeded" source of entropy, so that you don't have to route requests through the kernel.
2. They solve the cold-start entropy problem for embedded systems that can't easily generate sufficient entropy within milliseconds of initialization.
The former problem is only solved if the HWRNG is part of the ISA for the platform. If you have to pull it from a device, you might as well just pull it from urandom or getrandom().
Other than that, we're not really dealing with problems real security software has. People don't break cryptosystems by attacking the quality of entropy extraction from interrupts and whatnot. I have the same reaction to proposals on LKML about improving the entropy inputs to the LRNG. I mean, great, knock yourself out. But that's not solving a problem systems programmers actually have.
Frankly, it seems to me that if you're worrying about the intentions of your CPU manufacturer, you're screwed anyway. I guess that I also haven't put that much thought into it though.
This paper explains how to weaken the intel RNG by modifying only one logic gate and still make it passes the integrity tests.
I think not trusting a hardware RNG is a valid concern. As a consumer, it might not be a big deal, but what if you're buying CPUs for use in top-secret government machines? Given Intel's interests, it may likely comply with a backdoor request depending on the target.
One of the areas I'd like to look into is hardware integrity checking. It's most likely impossible, but it's worth a shot.
Ideally it should be private and contain some amount of entropy.
I've had the exact same idea, derived from a machine to roll dice.
I was going to use a simple motor rotating with a cam, beneath a die in a small enclosed box. Stops after N cam rolls, snaps a picture of the die face, bit of OCR and continues. You could generate quite a few random numbers using say two 32 side dies. A simpler method with less moving parts would be what you've described. I remember playing this game with a dice enclosed with a spring. Press it down and the spring bent, popped back and the dice rolled.
Practically: lots of cryptographic protocols just ask for a source of randomness, but don't care where it's from.
Also quantum 'randomness': https://qrng.anu.edu.au
PS: Thanks for clarifying @gizmo686. The arch linux wiki suggests that urandom re-uses the entropy pool that dev/random accumulates, so this is indeed a BAD idea.
I found this helpful as well:
https://en.wikipedia.org/wiki/Randomness_extractor
1) /dev/urandom and /dev/random are not independent
2) This paper describes an algorithm for combining random streams. That algorithm is not xor (which has been known for a long time).
But definitely don't XOR the two.
Also, do you mean that/dev/urandom should be used even for cryptographic applications?
Here's a nice article about it: http://www.2uo.de/myths-about-urandom/
The recent discussion about Ruby SecureRandom has some references about the subject: https://news.ycombinator.com/item?id=11624890
I mean it sounds trivial. Why not take the hash of the first random number, and xor it with the first random number. Then optionally hash the output and use that as a seed for a RNG. If any part of the process isn't very random, that's fine, it's still nearly impossible to reverse and doesn't hurt the other parts.
I tried to skim the paper, but it's really dense. Can someone who understands it explain how what they did is different than the obvious approach of running inputs from the two sources through a cryptographically strong hash function?
Also, note that you need at least two independent sources. This is because with a single source you just can't have a good extractor for any imperfect source. For example, imagine you are using a hash function to extract one uniform bit from an n-bit input. If the input source is the set of all n-bit strings such that H(x) = 0, which has pretty high min-entropy, you end up with a 'randomness extractor' that is just a constant function. This is highly contrived, but that is what you have to work with when you say "any" in theorem statements.
To fix this, you need at least two sources, where one source 'keys' the other, and therefore as long as the sources aren't working together (i.e., they are independent), there is nothing they can do to sabotage our randomness extraction. The inner product is a simple example of an extractor that works as long as each source has at least n/2 min-entropy. I have no idea what the construction of this new paper looks like, but it's an improvement on this min-entropy required. However, since this improvement is asymptotic, it's unclear whether it is any useful at all for realistic ranges of length and min-entropy.
In reality, this is entirely irrelevant for practical purposes. The work-horse tools of randomness extraction in practice are hash functions, block ciphers, and universal hashes, so this new paper is interesting from a theoretical point of view only. Yet another example of university PR departments being insultingly misleading in their press releases.
Example of independent but correlated variables: http://www.tylervigen.com/spurious-correlations
Let X be a normally distributed random variable with zero mean, and say Y = X^2. Clearly they are not independent. Covariance, which is needed for (pearson) correlation coefficient, can be calculated to be 0:
Cov(X, Y) = E(XY) - E(X)E(Y)
= E(X^3) - 0 (Since E(X) = mean(X) = 0)
= 0 (Since X is centered at 0)
:)
Can a rigorous definition of "source" be found somewhere?
- i.e. if X(w) > 0, then w has length n.
So Math.random() * Math.random() ? :)
Because Math.random returns a real number between 0 and 1, with finite bits, a<1 and b<1
ab < b and ab < a
2ab < a + b
2 < (a+b)/ab
0 < (a+b)/ab - 2
This equation has roots. Given that there is a finite bitspace, IEEE float/double -- if ab is .9 for example, then the possible (a,b) pairs for the result are 2^(number of bits) * (1-.9) = one tenth of the bitspace
You planned to have 2X where X was the entropy of Math.random alone. Instead you got 1/10 of 2X, 1/5 of the entropy of just using Math.random. A total failure. Hows that for shits and giggles. This is why crypto should be left to mathematicians. Dont invent your own hashes, don't invent your own crypto. And don't try to combine two entropy sources with novel approaches, you'll most likely fail.
I'm not very versed on mathematics yet, just getting into it. But you can already see multiplication is a terrible terrible choice versus an actual hash. But even a hash will leave us vulnerable considering our random source is the same.
It is imperative to use a binary hash that leaves all possible input pairs equally probable for the output. That is what this paper is about.
As I write that I get a funny "no way" feeling. This is so unnatural feeling, if Its true it is indeed a breakthrough. I have to read the paper again.
When people complained about Linux mixing in the Intel hardware rng Linus replied that mixing low quality sources have good entropy - and he got a lot of stick for that.
That they are on different computers is immaterial.
The problem with Linux was people complaining that mixing the Intel RNG into the existing entropy pool would lower the entropy of the entire pool, effectively letting a backdoored Intel RNG render the random system untrustworthy. Linus' response was the fairly simple/logical observation that "that's not how entropy works".
Suppose we have a random bit string with entropy X and we xor the bit string with a completely deterministic bitstring, what's the result? Clearly you have a bitstring that STILL has entropy X, because the result is completely dependent on our initial bitstring. Mixing with a deterministic bitstring doesn't make the output of our XOR any more predictable then the original bitstring, it's equally random.
So Linus' argument was that "IF the Intel RNG is completely backdoored and deterministic mixing it with the entropy pool will have no effect on the entropy in the pool. HOWEVER, if the Intel RNG is anything but completely deterministic, i.e. there is even a tiny bit of randomness in it, this will actually INCREASE the pool's entropy.
So mixing a completely backdoored RNG will have no negative impact, but mixing anything that's not 100% predictable will have a positive impact, so there's no reason to not always mix the hardware RNG with the pool.
1 - The entropy mixing is more complex than simply XOR, making such a thing considerably harder
2 - If you expect this level of backdooring from your CPU, you have bigger problems :)
Hopefully this research yields a wonderful new algorithm for combining the sources and makes it a simple kernel patch away.