Hacker News new | comments | ask | show | jobs | submit login
Academics Make Theoretical Breakthrough in Random Number Generation (threatpost.com)
389 points by oolong_decaf on May 18, 2016 | hide | past | web | favorite | 157 comments



I'm sure this is as important to computer science as the article claims, but not having even read the paper I can say pretty confidently that it isn't going to have much of an impact on computer security. Even if it became far easier to generate true random numbers, it wouldn't change (a) how we generate randomness at a systems level or (b) what goes wrong with randomness.

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)


While this may be an interesting theoretical result it almost certainly has zero practical implications for cryptography.

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.


I'm far from being an expert, but I doubt that.

"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)


Hanno is in fact an expert, and the opinion he's relating (particularly, the frustration with breakable Rube Goldberg random number generators people build) is shared by most crypto engineers.


Prnfre pvcure vf nyfb xabja nf EBG13


Yeah, one of them. I think the number is flexible for good old Caesar.


A "couple" meaning literally two?


Here's a link to the actual paper: http://eccc.hpi-web.de/report/2015/119/


> 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.


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.


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?


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.


The entropy of a single object is a meaningful concept. It is usually called Kolmogorov complexity.


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.


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


> 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.


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.)


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.


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.


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.


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.


Got it, thanks!


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!).


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?


No, it's just a misunderstanding of the paper.


Fair enough.


Reminds me of the Von Neumann method of using a biased coin to generate unbiased random coin flips: http://web.eecs.umich.edu/~qstout/abs/AnnProb84.html

(Edit: not the algo itself, just the notion of combining randomness.)


That was on the final of my Stochastic Processes class back in the Pleistocene. I just took the easy way and used system theory: find a system with a transfer function that is the inverse of the power spectral density of the autocorrelation function for the biased coin (Mason's rule guarantees this is possible, if sometimes impractical even in theory), and run the output through that system.

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.


> find a system with a transfer function that is the inverse of the power spectral density of the autocorrelation function for the biased coin

For those of us who don't know systems theory, is there a simpler explanation of this? It sounds interesting


Sure. A "system" (which is an incredibly broad term; in practice a circuit composed of resistors, capacitors, and inductors can model any linear system so we stick with that) takes the signal x(t) and maps it to something else, f(x(t)). The autocorrelation function r(t) defines the bias of the coin (r(t) is generally given in the problem, or in real life found empirically). All of these functions are difficult to work with directly.

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.


Cool. But note that this is not a problem that you're likely to run into in practice. Nolan and Gelman claim that you can't actually bias a coin.

http://www.stat.berkeley.edu/~nolan/Papers/dice.pdf


How to create an unfair coin and prove it with math: https://izbicki.me/blog/how-to-create-an-unfair-coin-and-pro...


> Amazingly, it takes some pretty big bends to make a biased coin. It’s not until coin 3, which has an almost 90 degree bend that we can say with any confidence that the coin is biased at all.

Basically, it proves that creating a biased coin really is impossible.


It is impossible by bending. It's probably still possible (not to say practical) by crafting a coin with a hidden compartment of a heavier metal.


The paper states that this would only alter the center of mass. If you catch the coin or it lands on a soft surface, it has no effect, because the outcome is determined by the time when it stops. If you allow it to bounce, then yes.

TL;DR: if you want unbiased coin IRL, make sure you catch it before it hits the ground.


From the paper linked above:

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.


"Coin" is a metaphor in mathematics for any process with a binary outcome (a binary random variable, so to speak). These things exist in practice everywhere.


There's a nice way to extend von Neumann's basic idea naturally to the most efficient extractor: http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf


What makes randomness so hard? I had this crazy thought awhile back and wondering if it would work out:

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...


Mechanical devices utilizing some form of chaotic behavior are usually pretty good sources of randomness, but they have a really high probability of malfunctioning (when your motor stops, you get predictable outputs), the are subject to wear-and-tear, and their entropic properties can be hard to quantify.

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.


Shameless plug (of my FOSS): if you like Diceware, you might like Molis Hai even better. Maps the 56-bit sequence 0x556bfdce0148c9 to "wrowd aut settea". I betcha the corresponding diceware passphrase is way longer and less memorable. cf https://www.brinckerhoff.org/molis-hai/pwgen.html, or download FOSS repo from github.


I get "aaron nitty ms exxon inept" for the same value in Diceware (with a few bits spare, hence "aaron" from near the start of the alphabet). Subjective but I think that's more memorable.


quite a bit longer, though...


Sure, but how does the raw length matter? The computer is storing it hashed anyway; the human can probably type five actual words faster than 3 pseudo-words.


What's that? Gaelic? Old English?

I'd certainly dispute the "memorable" part for most people on Earth.


I haven't looked at the source, but the linked page claims to use a Markov model trained on an English corpus (in this case, A Tale of Two Cities), so it emits English-like sequences of letters and spacing, and uses that in conjunction with a Huffman tree setup to map random bitstrings to the pseudo-English phrases.

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.)


Ah, English-like. Not English. That eluded me.

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.


"wrowd": a portmanteau for "wrong crowd". "Take care, you don't want to hang out with the wrowd".

"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.


Re: wrowd. The term 'OK' originally meant 'Our Kind'. There was another term "NOK" meaning "Not Our Kind" which got lost. Now we have wrowd, maybe it will fare better.


> The term 'OK' originally meant 'Our Kind'. There was another term "NOK" meaning "Not Our Kind" which got lost.

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.


Nah. Alluding to the usage of the word in my youth. But go ahead, defer to authority and call names! This is the internet after all.


Are you claiming that a usage from your youth predates ("originally meant") the usage of 1838?


And for something as trivial as a two-letter acronym, does the first appearance in print cement it for all time? Does it constrain conventional usage forever? I'd check out some other acronyms to get an idea of their various usages and meanings over time. There's a site for that.


In the context of "originally meant" (your words), yes, the original meaning of a word is going to be its meaning when the word first came into usage. Sure, word meaning can change over time, but their original meaning shouldn't.


People that want seriously random numbers use radioactive decay because the underlying physical phenomena (described via quantum mechanics) is fundamentally random and cannot predict the time, energy, and direction of decay all at the same time (as far as my limited understanding is aware).


>underlying physical phenomena (described via quantum mechanics) is fundamentally random

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.


> cannot predict the time, energy, and direction of decay all at the same time

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.


Here's a great example of radioactive decay in use as a source of entropy[0]. Essentially, each component of a nuclear weapon derives its own private key at time of assembly from the radiation of the weapon itself, and saves the public keys of all the other components; thereafter, it'll only respond to signed communication from those other components.

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...


Diode avalanche current has the same fundamental randomness (predicted by QM), and does not require radioactive elements.

Also, it integrates very well. The smaller the diode, the better randomness you'll get.


I've heard you can just sample a noisy resistor, too.


Resistors do not have that nice property that a single particle can start a macroscopic cascade of events.

But, yes, with enough precision a resistor would do.


What you describe is essentially a hardware-based source of randomness. These devices sample various kinds of random physical processes to produce random streams of data. None of them are perfect but some are really good.

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.


Wouldn't that change the distribution but not the randomness?


Depends on what you mean by randomness.

In general, natural processes seldom produce perfectly unbiased streams of independent coin flips. There's usually some post processing.



You can try to extract the random noise of a webcam CCD sensor, no need to move mechanical parts that are prone to failure.

ObLink: http://www.lavarnd.org/what/process.html


I don't really know what I'm talking about here but...

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 "if" is pretty much untenable. Find me two identical sand particles.

Your argument basically boils down to "chaos theory is wrong, because I /can/ know everything".


It does not boil down to that I think. It was a good question which got enlightening answers.


It got one other answer, which was not terribly different.


Yes both good


Sure, eventually. At the same point in time that the monkeys produced "Hamlet" on a bunch of typewriters. The problem is the number of entry variables -- even if the starting position was X, the affects of gravity, friction, and general entropy would result in different states.


how do you know the two colors of sand will weigh the same amount ? if not, over time the heavy sand will sink and "sort" the color.

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 ?


You use a randomness extractor like http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf (or more sophisticated) to generate the actual unbiased random numbers from your source.



> Abstract:

> 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.

http://eccc.hpi-web.de/report/2015/119/


What is the possibility that this is an attack on cryptography; convince people that it's safe to produce random numbers this way using an inaccurate "proof" and then have an easy/easier time decrypting stuff produced by anyone who uses it?


Exactly zero. The authors are well-known theory researchers at a major university, not NSA double-agents.

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.


"The authors are well-known theory researchers at a major university, not NSA double-agents."

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"?


Dave Zuckerman has been doing theoretical CS research for about twenty-five years. Are you saying you think it's likely that either (a) he was an NSA double agent this whole time, or (b) he recently started doing clandestine work for the NSA inserting backdoors into abstract theoretical results about Ramsey graphs and two-source extractors?


I'm not saying anything about this particular person; just amused as to people's attitudes towards people who might be engaged in secret work on behalf of a government, as if detecting such a person is straightforward, or that people have "spy" on their passport, etc. If you look at the history of spying, leakers and double agents you can see people do it for all sorts of reasons; money, blackmail, belief that your country is doing something wrong or that you need to help your country defeat another country's ideology etc.


I think the general consensus is that it doesn't matter whether or not he is some clandestine NSA agent because his paper is just a theoretical proof that is almost entirely removed from any implementations based on his work. If there is some fundamental flaw in his work, then it's likely to be discovered before RNGs based on this work come into wide-spread use.

It would be much easier to just code a flaw into the actual implementations of RNGs based on this.


Wait for it to be confirmed by other cryptographers before implementing it.


Don't implement this at all. Even if it's better than the LRNG or FreeBSD kernel RNG, it's not worth pursuing. It's probably an interesting and important CS result. That doesn't mean it belongs in systems.


My first thought was to make a tiny cheap RNG chip using ~4 different really cheap TRNG sources (diodes, etc) with this as a mixer, for embedded systems (routers and similar).

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.


There are two real-world problems hardware RNGs can solve, as far as I can tell:

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.


Could someone explain why XORing the outputs of the two sources isn't optimal?


Suppose both sources are 90% zeros. Their XOR will be mostly (82%) zeros too.


And in terms of Shannon entropy, the original two bits have 0.469 bits of entropy each, and the resulting XORd bit has 0.68 bits of entropy. So this extractor is far from ideal.


(Actually for the "90% zero" sources, OR would be a slightly better extractor than XOR, yielding a resulting bit with 0.70 bits of entropy).


I guess what I'm wondering is, how could you possibly expect to do better? You told me why the result is bad, but gave no intuition on why I should expect better (I don't).


The simple trick is to take pairs of bits. If you get 01, output 0. If you get 10, output 1. Otherwise, output nothing. Even if the source is biased (as long as successive bits are uncorrelated), you get an unbiased 50:50 output. But obviously you get fewer bits out than you put in. The construction in the paper is basically a more efficient version of this.


I have always wondered why not introduce physical randomness into cryptography. Let's take scalability out of the question and look at the problem at the fundamental level. If we used a box of sand that shifted each time a random number was requested and a camera to scan and produce a number from this source would it not more random than any other method? I'm not a professional in this field I am just truly asking why not..


New Intel chips use a special bistable circuit to generate random bits in hardware, but many people don't seem to trust it (talk of back doors and such).

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.


Most kinds of CPU misbehavior are detectable: "-Did it add the two numbers correctly? -No it did not" Randomness is different: "-Did it generate a random number? -Well it generated some kind of number...."


> but many people don't seem to trust it

This paper explains how to weaken the intel RNG by modifying only one logic gate and still make it passes the integrity tests.

http://sharps.org/wp-content/uploads/BECKER-CHES.pdf


Yeah, Intel's new design blows everything else out of the water when it comes to throughput, but it consumes more power.

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.


Only truly truly dependable with 99.9^ % certainty is to build your own CPU and RNG.


I've often visualized a Trouble Pop-o-matic[0] hooked to a webcam and a solenoid. The solenoid would pop the die, and simple computer vision could count the pips or number on the die. I'm unsure how many would be needed to make SSL work.

[0] http://i.imgur.com/fL9Bg0M.jpg


Why not just put your cat in front of it and use sha3 on the image?


Just capture an image from any webcam. I seem to remember something like SSL cert creation using mouse movement for entropy seeding.


That would be PuTTYgen[1] actually.

[1]: http://www.chiark.greenend.org.uk/~sgtatham/putty/


Well if it's pure black or white or sth like that, it's within the reach of brute-forcing.

Ideally it should be private and contain some amount of entropy.


PGP/GPG traditionally did this too.


Ah, I think that's where I used it, when trying PGP for mail signing.


"I've often visualized a Trouble Pop-o-matic[0] hooked to a webcam and a solenoid."

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.


Check random.org - they go the easy route and use antennas to capture atmospheric noise as input.


Cynically: you can't write papers about this.

Practically: lots of cryptographic protocols just ask for a source of randomness, but don't care where it's from.


There was some service (maybe still around) that did this with cameras and lava lamps.

edit: https://en.wikipedia.org/wiki/Lavarand


Also random.org. I thought I remembered seeing one that used radioactive decay to generate random files for download but I can't find it now.


HotBits: https://www.fourmilab.ch/hotbits/

Also quantum 'randomness': https://qrng.anu.edu.au


Well CERN produce terabytes of data from experiments (when running!); particle collision images must be random with much more disorder than mere decay timings.


Awesome, at least I am not crazy. A lava lamp was not my first choice but somehow fitting :)


I can't remember their names off the top of my head (not near a PC) but there are packages available for some Linux distributions that use your audio (i.e. microphone) and video (i.e. webcam) input devices for generating entropy.


This is already the most common source, no? /dev/random uses environmental noise collected from device drivers.


Does this imply that XORing /dev/urandom with /dev/random is a good practice?

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
Overall, their construction quite reminds me of a double pendulum, which is one of the simplest examples of deterministic chaos.


No.

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).


/dev/urandom and /dev/random are identical in every way, except that /dev/random blocks when the "entropy estimator" decides there "isn't enough entropy". However, due to the properties of the CSPRNG they use, such estimates have dubious value. Overall, you should always use /dev/urandom.

But definitely don't XOR the two.


Why does /dev/urandom use up the nice entropy of /dev/random when it doesn't provide any guarantees anyway?

Also, do you mean that/dev/urandom should be used even for cryptographic applications?


What do you mean by "use up the nice entropy"? You can use /dev/urandom for cryptographic applications (in fact _you should_).

Here's a nice article about it: http://www.2uo.de/myths-about-urandom/


I shall ready your link in full at a later time. For now, is there any problem with using /dev/random other than that it is blocking?


Yes, /dev/urandom is backed by a CSPRNG, and thus should be used even for cryptographic applications

The recent discussion about Ruby SecureRandom has some references about the subject: https://news.ycombinator.com/item?id=11624890


How is this different than taking two independent bits with < 1 bit entropy and XORing them together to combine their entropy? (up to a max of 1 full bit)


For one, XOR doesn't remove bias. (If both sources are biased, so will be their XOR.)


I read the article and the comments and I'm still confused why this is important.

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.


Hashing low entropy random sources is not going to get you high quality random seeds...


Why not? Xor it with a random constant if it's sensitive to zeros. But you aren't going to get any more entropy out of it than any other method.


"...if you have two low-quality random sources...you can combine them in a way to produce a high-quality random number..."

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?


The most notable thing is the lack of assumptions. You don't have to assume anything other than the min-entropy of the sources. With a hash function, you generally need to assume that the hash function is a good extractor, instead of showing that it is one. Instead, what we have here is an extractor built up from first principles.

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.


How well does this handle a biased source of random numbers in one or more of the inputs? If someone has set up your random number source to be more easily exploitable (or just done a really bad job setting it up), does combining it with another poor source with this approach mean the results are still useful?


Isn't "Independent and no correlations" redundant? How can two random variables be independent but correlated?


Dependence is stricter than correlation: the population violates probabilistic independence. Correlation can help guide statisticians to finding a dependence between variables, because correlation measures how close or how far a sample is to independence. But this gives rise to the "Correlation does not imply causation" adage.

Example of independent but correlated variables: http://www.tylervigen.com/spurious-correlations


An easy example is two thermal sources in the same environment.


Not really. Zero correlation does not necessarily imply independence. From the example on this resource[1]:

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)

[1] http://mathforum.org/library/drmath/view/64808.html


The paper itself does not explicitly require there to be "no correlations". My guess is that that phrase was added by the journalist as emphasis.


But can anyone extract the algorithm from the paper?

:)


Can someone explain why it's considered so hard to get randomness? I mean you can take old radio and you hear random noise, is it hard to create tiny antenna in the computer?


another article via UT (Uni. Texas), "New Method of Producing Random Numbers Could Improve Cybersecurity" ~ http://news.utexas.edu/2016/05/16/computer-science-advance-c...


> A source X on n bits is said to have min-entropy at least k if

Can a rigorous definition of "source" be found somewhere?


I think it is a random variable X whose support is a subset of the set of n-length strings.

- i.e. if X(w) > 0, then w has length n.


But can anyone extract an algorithm from the paper? :)


“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,”

So Math.random() * Math.random() ? :)


F(a,b) = ab = ba leaves rather hideous properties of the input apparent. Because your operation is both associative and commutative, your operation is an abelian group. Any result ab says a lot about the probability of a certain input pair.

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.


The * signs botched your formatting


Thanks for letting me know -- that was a curious annoyance. I am not going to edit the post but I'll make sure I don't slaughter my future posts.


No, the article says "two sources that are independent and have no correlations between them".


Math.random() * hwclock ?


If your hwclock is a source of randomness, maybe you should be worried ;)


Perhaps Math.random()@computer1 and Math.random()@computer2


See my post about why multiplying two sources of random numbers will actually reduce the entropy to less than even a single one of the sources: https://news.ycombinator.com/reply?id=11719840&goto=item%3Fi...

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 long as you ensure they are different algos and have different seeds...?

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.


Linus actually argued something slightly different. That discussion was about whether a "bad" random source can weaken a "good" source. This paper is about constructing a "good" source from two independent "bad" sources.

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.


That's also assuming it isn't maliciously correlated to produce an output that after XOR leaks secret entropy.


Sure, if you're hardware RNG is inspecting your RAM and trying to compromise your entropy pool that could be done, but:

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 :)


> Linus replied that mixing low quality sources have good entropy

Hopefully this research yields a wonderful new algorithm for combining the sources and makes it a simple kernel patch away.


That sounds more like one source. :p


praise RNGesus!




Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: