Linux RNG May Be Insecure After All

Okian Warrior writes "As a followup to Linus's opinion about people skeptical of the Linux random number generator, a new paper analyzes the robustness of /dev/urandom and /dev/random . From the paper: 'From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the "robustness" notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice.'" Of course, you might not even be able to trust hardware RNGs. Rather than simply proving that the Linux PRNGs are not robust thanks to their run-time entropy estimator, the authors provide a new property for proving the robustness of the entropy accumulation stage of a PRNG, and offer an alternative PRNG model and proof that is both robust and more efficient than the current Linux PRNGs.

Comments

Random number generators are hard

[moonwatcher2001]

Linus always says Linux is perfect. Linus can be wrong.

Re:Random number generators are hard

[TheloniousToady]

Linus always says Linux is perfect. Linus can be wrong.

Clearly, Nomad should sterilize him. (And BTW, Nomad prefers that you call it the "GNU/Linux System".)

Re:Random number generators are hard

[WaywardGeek]

No, RNGs are easy. Super easy. Just take a trustworthy source of noise, such as zener diode noise, and accumulate it with XOR operations. I built a 1/2 megabyte/second RNG that exposed a flaw in the Diehard RNG test suite. All it took was a 40 MHz 8-bit A/D conversion of amplified zener noise XORed into an 8-bit circular shift register . The Diehard tests took 10 megabytes and said if it found a problem. My data passed several times, so I ran it thousands of times, and found one test sometimes failed on my RNG data. Turns out the Diehard tests had a bug in that code. Sometimes the problem turns out to be in the test, not the hardware.

Re: Random number generators are hard

[Anonymous Coward]

Not all Linux systems use the GNU userspace.

Re: Random number generators are hard

[Anonymous Coward]

No, RNGs are easy. Super easy. Just take a trustworthy source of noise

Therein lies the tricky part. Getting a trustworthy source of noise is harder than you may think. Especially when you're writing software with no control over the hardware it runs on.

Re:Random number generators are hard

[Anonymous Coward]

Good for you. That is still not a viable solution for generating cryptographic keys, IVs, salts, and so on. Two drawbacks with your idea:

1. Too slow. You need far more random data than a zener diode can generate. You could combine many of them, but then you need to combine them in the right way.

2. Unreliable. Zener diodes are easy to affect with temperature, and you need to make sure that hardware flaws don't make them produce 1 more often than 0 (or the other way around).

This is why we need software RNGs. We take a good hardware-based seed from multiple sources (combined using SHA256 or something), and then use that to seed the CSPRNG (not just a PRNG). The CSPRNG then generates a very long stream of secure random data which can then be used.

I'm not too pleased about the design of Fortuna, but it seems like one of the better choices for how to combine HW input and generate an output stream.

Re: Random number generators are hard

[Vintermann]

The nice thing about randomness though, is that it adds up. If you xor one stream of hopefully random bits with another stream of hopefully random bits, you get a result that is at least as random as the best of the two streams, quite possibly better than either. It's a rare and precious thing in cryptography: something you can't make worse by messing up. At worst you make no difference.

So if you're paranoid, come up personally with a ridiculously long phrase (you don't need to remember it), feed it through a key derivation function, and use it in a stream cipher with proven security guarantees (in particular one that passes the next-bit test for polynomial time). Instead of using this directly, xor it together with a source of hopefully random stuff.

If you write to /dev/random this is more or less what happens. Write to it to your heart's content - it can only make it better, not worse. (This is as I recall, please check with an independent source before you try).

Voila, no matter what NSA has done to your HRNG chip, this door is secured. Your time is better spent focusing on the other doors, or the windows.

(But you should be very careful in using HRNG output directly. I am very surprised to read that some open source OSes disable the stream cipher if a HRNG is present - this is a very bad idea!)

Re: Random number generators are hard

[pspahn]

Pick two random dates between 1950 (or earlier... arbitrary cut-off) and today. Then go to that date and find all the sports scores from that day. Do some random math on those scores independently. Then take those two results and do some more random math between the two.

Add in more Nth days as you please.

That enough entropy for you? I guess it might not be. I suppose you could also factor in which days of the week the Cleveland Browns are likely to win on, since that is definitely random.

Re: Random number generators are hard

[behrooz0az]

And How do You suggust we come up with those random dates again?

Re: Random number generators are hard

[Anonymous Coward]

If you write to /dev/random this is more or less what happens. Write to it to your heart's content - it can only make it better, not worse. (This is as I recall, please check with an independent source before you try).

Depends. If the entropy pool is empty, the output will only be as good as what you put in. Might be better to wait a little longer and allow the pool to replenish from other, better entropy sources.

Re: Random number generators are hard

[Ventilator]

Sounds interesting. Can you name any Distros?

Re:Random number generators are hard

[AmiMoJo]

It seems unlikely that you would get good results from such a set up without whitening the data, but you don't mention doing that. Did you try it with anything other than the rather old Diehard tests? Do you know they are not an indication of cryptographicly secure randomness? Do you have a schematic that could be reviewed for errors?

Re: Random number generators are hard

[Anonymous Coward]

Android

Re: Random number generators are hard

[Anonymous Coward]

This is of course false. If the random streams are correlated, the output is decidedly non-random. For instance, if you take two copies of the same ("random") sequence, their xor will be a most emphatic 0.

Now, the point of this mental exercise is - proving that something is not correlated is usually very difficult; crypto is about provable bounds, and saying that something is uncorrelated because it has no reason to be correlated is not proof enough.

Re: Random number generators are hard

[Anonymous Coward]

Apart from many embedded systems..... Android seems like a big one

Re: Random number generators are hard

[magic maverick]

Android. Many embedded systems. Many micro systems, such as tomsrtbt or similar (now virtually unneeded, due to the lack of floppy discs on new computers, and the prevalence of booting of CDs or USB flash drives). Many lightweight systems, such as Damn Small Linux.
Etc.

See also: Toybox.

Re: Random number generators are hard

[Anonymous Coward]

Your suggestions can indeed be used to seed /dev/random, as long as you are aware that you still need plenty of other sources for the numbers to become unpredictable.

For example, the day of the week gives roughly log2(7) bit of entropy, assuming they play all days of the week and that the scheduling of games is random.

Re: Random number generators are hard

[Anonymous Coward]

There are roughly 23000 days since 1950. So your output space is roughly that squared, which is only about 500 million. A tiny space of randomness to work in - a computer could just check all of them.

And you just need a separate secure random generator to pick the dates!

It's RNGs all the way down...

Re: Random number generators are hard

[jalopezp]

I don't know of any distros that completely eschew GNU. The two are very tightly integrated, originally the kernel was written to run gnu, and even now, it cannot be built but with gcc. While I believe that they have done much to contribute to the free software we care about, loads of people here on /. have some disdain for gnu, and with that in mind might want to ban it from their systems. You can do this by replacing the individual components. BSD userland has been successfully ported to linux, and with Plan 9 from User Space you can take advantage of some great ideas that came with Plan 9 (though if you care enough for the benefits of Plan 9 plumbing, filesystem namespaces, and networking, I might recommend you go with the whole thing - Plan 9 is much, much better designed than unix, we just need to port our software).

The main GNU components in all distros are usually glibc, gcc, and coreutils. If you don't compile anything, you don't need gcc, and if you're really into compiling, you probably use the llvm. Soon, it is said, LLVM will be able to build the linux kernel. As for the others, there are several packages available in most distributions that will replace them. Most likely, you will replace glibc with uClib and coreutils with BusyBox. You will lose some functionality doing this, but it is definitely possible to run a free system without GNU. I might point out that I don't think this is a great idea, and should go for it only if for some inexplicable reason, you dislike GNU.

Check out this answer for more info.

Re:Random number generators are hard

[Rockoon]

2. Unreliable. Zener diodes are easy to affect with temperature, and you need to make sure that hardware flaws don't make them produce 1 more often than 0 (or the other way around).

A good implementation assumes that there is an unknown bias and produces an unbiased (to within 50% +/- whatever margin you want) output anyways.

Re:Random number generators are hard

[WaywardGeek]

I built this in the mid 90's, and at the time the old DOS-based Diehard tests were the best I could find. Certainly the stream should be whitened before used in cryptography, but the data directly from the board passed the Diehard tests without whitening. However, the board XORed 80 bits from the A/D to produce a single output bit (or more - this was software controllable). Since the 8-bit randomness accumulator was rotated 1 bit every sample, each bit was XORed 10 times with each of the A/D outputs. I did some simple correlation analysis on the raw A/D output, and found that the 4th lowest bit had significant, but small correlation - I forget now, but something like less than 1/128th bias to the previous bit. The lowest 3 bits were even more random, and I did not detect correlation other than what I could explain through non-linearity of the ADC. I also looked at the analog signal, and it was a best described as biased random walk, where the signal prefers to return to 0 more the further from 0 it got. It had strong random components at the limit of my scope's frequency: 100MHz.

While it was based on zener avalanche noise, real zeners are designed to minimize this noise. I used the reverse Vbe breakdown of a cheap NPN transistor instead, which was a far superior noise source. I had a couple clever tricks In my design, but frankly saving a transistor or two isn't going to make the world a better place. There's nothing wrong with the designs I find with Google, like this one.

Re:Random number generators are hard

[Anonymous Coward]

Easier just to stick a microphone out of my front window.

Re:Random number generators are hard

[Anonymous Coward]

Careful ! How do you know you don't extract too many bits from your randomness source ? I find it laudable you actually build a dedicated hardware device, but you should still do some REASONING about how much entropy you can get from your contraption per second.

For example, you could simply take too many samples per second and have lots of correlation in your "random" numbers.

Re: Random number generators are hard

[Anonymous Coward]

And that's exactly it. A computer is non-random. Given identical input conditions, it is supposed to behave in exactly the same way for each and every run. Even things like the movement of the mouse or the feedback from a microphone can be recorded and replayed and it would re-generate the exact same numbers. Short of hardware RNGs, it's not foolproof in software given hardware that is functioning as designed.

Re: Random number generators are hard

[Anonymous Coward]

llvm cannot compile the kernel until they add an option to not omit NULL checks after NULL dereference. This is known to generate incorrect code in kernel mode.

Re: Random number generators are hard

[Anonymous Coward]

I suppose you could also factor in which days of the week the Cleveland Browns are likely to win on, since that is definitely random.

The Browns (heck, even the Jaguars) are most likely to win on a Sunday. That's just about the least random thing you could come up with.

Re:Random number generators are hard

[postbigbang]

The TCO of a randomly measured Zener diode or other noise source is likely to be pretty darn close, cycle to cycle as it takes a bit of TCO delta to produce a lot of randomization change. Therefore NOT so easy to change unless you use a lot of temperature -- on the the same diode. Change the family, even the diode within a family (although less so in a batch) and you can get some delta.

I agree to all suggestions that multiple hashing techniques can be used to prevent filling the entropy pools, and multiple seed sources are better than one. It can be done without a lot of code and CPU cycles. It just takes tougher math and knowing how to use FPUs effectively-- test them for presence then make them do a little work.

Re:Random number generators are hard

[Anonymous Coward]

xxxx

MEEEEP. BAD IDEA AHEAD !

Your "great idea" comes up in variousxxx forms (other people use de-tuned radios or TVs) all the time. What do you xxxNOISExxxx think would happen if somebody wanted to attack your crypto by running a loudspeaker and a sine wave ? Then your nice xxxx "randomness" source would immediately be not so random any more.

Strong crypto random numbers must xxxx be immune against external input - electronic or otherwise.
xxxx

Re:Random number generators are hard

[Anonymous Coward]

Only whitened data can give good results? That's racist!

Re:Random number generators are hard

[WaywardGeek]

Here's the math I did to prove to myself that the non-randomness error is tolerable.

I saw 1% correlation between successive samples of the 4th lowest bit of the ADC (the upper bits, were worse, the lower are even more random). So, model the low 4 bits probability of being 1 as 0.5 + e, where e is an error of 0.01. XORing two together, the probability of being 1 is (.5 + e)(.5 - e) + (.5 - e)(.5 + e) = 0.5 - 2e^2, so the new error is 2e^2, or 0.0002. Merge again, and it's 80*10^-9. Once more and it's 12.8*10-18. Then 327*10-30, and finally 215*10-57. That's what I'd get merging 32 of the low 4 bits , but I actually merged 40, and while the high bits are highly correlated, they still do add randomness.

Re: Random number generators are hard

[Anonymous Coward]

the problem is in "pick two random dates" if your pick is not truly random then the attacker could possibly follow your system and arrive at your randomly generated numbers. As soon as a randomizing system is based on a random input, your system is broken (because your first random choice is not as random as it should be). Unless the input is truly random - in which case making the system more intricate may just be a waste of time.

Re: Random number generators are hard

[Anonymous Coward]

incoming patent for sports statistic based cryptography.

Also an NSA project to start rigging baseball games to weaken cryptographic strength.
Being a Booky is now a national security threat.

Re: Random number generators are hard

[Anonymous Coward]

Dice. Or do you believe the NSA has infiltrated your local comic book shop (or whatever your preferred location for purchasing dice is)?

Re: Random number generators are hard

[Anonymous Coward]

This information about "adding randomness" is false.

If you add two uniform distributions of random numbers, you will wind up with a new normal distribution.

Think about the game of craps. You have a pair of fair six-sided dice that more frequently result in a 7 than any other combination. Individually, each die has a uniform distribution from 1-6.

Re: Random number generators are hard

[mcgrew]

I suppose you could also factor in which days of the week the Cleveland Browns are likely to win on, since that is definitely random.

You think they're losers? let me introduce you to the Chicago Cubs, who haven't won the world series since 1908 (Go, Cardinals!)

Re: Random number generators are hard

[Anonymous Coward]

How is that random? That sounds pretty deterministic to me. ;)

Re: Random number generators are hard

[Anonymous Coward]

As the Toybox (Busybox replacement) controversy shows Youtube video
There are real benefits to being away from the GPL that cannot be done otherwise.

Also, other non-mobile libc replacements like musl exist.

Re: Random number generators are hard

[Anonymous Coward]

Without analysing the data, let me venture a guess: The Cleveland Browns are/were most likely to win on Sundays!

Right? Am I right?

Re: Random number generators are hard

[sFurbo]

Are you saying that the NSA have gotten to Games Workshop?.

The TL-DR on that link is that the dice normally seen (rounded corners, holes to mark the numbers) are horrendiously unfair, giving ones up to 30% of the time, in stead of the fair 16.7%.

Re: Random number generators are hard

[pspahn]

Do you think you're right? I'm not sure if you are, considering they have also played on Monday, Thursday, and Saturday (probably some Fridays and potentially other days as well if you go back earlier than 1950).

Since the number of times they've played on days other than Sunday are fewer, maybe they're like 5-0 on Saturday, which means Saturday would be their highest winning percentage day, especially considering there have been a lot of terrible Sundays.

Re: Random number generators are hard

[Anonymous Coward]

I suppose you could also factor in which days of the week the Cleveland Browns are likely to win on, since that is definitely random

And a Cleveland Brown jock looks up from his Slashdot: Dayum! Just when I thought it's ok to read Slashdot!

Re:Random number generators are hard

[Anonymous Coward]

Linux IS perfect. You dont understand shit.

Re:Random number generators are hard

[Agripa]

There are all kinds of ways to design the hardware to prevent problems besides the obvious of measuring various environmental variables like temperature.

Feedback from the output of each slicer can adjust the comparison threshold to produce an output with an equal number of high and low states over an arbitrary period of time. This technique is commonly used for closed loop control of duty cycle in applications requiring precision waveform generation. The slicer threshold can be monitored as another health indicator.

The diodes used as noise sources can be used in pairs and measured differentially to remove common mode influences. This can be extended to use multiple sets of diodes for both health monitoring and redundancy.

Re:Random number generators are hard

[Anonymous Coward]

1. Too slow. You need far more random data than a zener diode can generate.

Really? You did see where he stated 0.5 MB/s, right? I've never seen /dev/random give me more than a few bytes without me then having to move my mouse around.

2. Unreliable. Zener diodes are easy to affect with temperature, and you need to make sure that hardware flaws don't make them produce 1 more often than 0 (or the other way around).

It's trivial to filter for bias towards 1 or 0 bits. You have to throw away a lot of data to do it, but when you're done, you know your bias is eliminated.

Here's how it's done:

Count how many consecutive 1 bits you receive. Then ignore the intervening 0 bits. Then count how many consecutive 1 bits you receive. Then ignore the next batch of 0 bits. So you now have two counts, we'll call them A and B. Since they're both counts of 1 bits, their lengths are, on average, going to be identical, even if the random source is more biased to producing one type of bit than the other. So then you just do this:

If A < B, output a 0 to your random data stream.
If A > B, output a 1 to your random data stream.
if A = B, output no data.

To double the output of your data, you simultaneously do the same thing comparing the length of each pair of counts of consecutive 0 bits. (So you're not really ignoring them as stated above, you're just not comparing them to counts of 1 bits, because you're assuming there's a bias there.)

It's actually pretty easy to toss together a script to do this with data read from the "line in" on your sound card. You don't even have to attach it to anything as it's hardware likely isn't really accurate to 16 bits anyway and so even when presented with complete silence you're going to see a lot of noise in the least-significant bit of the samples you read. The results may not be as great as a custom-built RNG source, but just XOR your data with /dev/random and you'll end up with something that's more random than using just /dev/random alone.

Dilbert RNG

[johnsnails]

http://dilbert.com/dyn/str_strip/000000000/00000000/0000000/000000/00000/2000/300/2318/2318.strip.gif

Re:Dilbert RNG

[Anonymous Coward]

Came here for the "Nine Nine Nine Nine Nine Nine". Left happy.

Re:Dilbert RNG

[The MAZZTer]

http://xkcd.com/221/

Re:Dilbert RNG

[AlphaWoIf_HK]

I didn't even click on the link and knew it was some fag linking xkcd.

Well, it is a link that leads to xkcd.com, so it's not exactly difficult to figure out that that's where the link leads.

Re:Dilbert RNG

[Anonymous Coward]

another copy-paste response, lame.

Re:Dilbert RNG

[gandhi_2]

http://www.penny-arcade.com/comic/2004/03/19

Re:Dilbert RNG

[jmhobrien]

I think you need to re-assess your attitude. Perhaps some people have not seen those links? Did you consider the possibility that the comment was not for you? Like rhetorical questions?

Lighten up or Fuck off. You are taking this way too seriously.

Re:Dilbert RNG

[Anonymous Coward]

http://xkcd.com/1/

Re:Dilbert RNG

[Anonymous Coward]

I do what I can..

Re:Dilbert RNG

[jeremyp]

It's always worth posting links to XKCD in order to wind up Anonymous Cunts like your good self.

Re:Dilbert RNG

[fellip_nectar]

Aww, diddums! Did the nasty man post the link you were going to post before you?

Re:Dilbert RNG

[marcello_dl]

True slashdotters do not read the links either.

Re:Dilbert RNG

[somersault]

Keep up the good work

Re:Dilbert RNG

[CaptSlaq]

I didn't even click on the link and knew it was some fag linking xkcd. It's not clever. It's not funny. Just the subject containing something about RNG, with a link under it and not even a short, useless, one sentence post shows the kind of unoriginal, uninspired, idiot is making the post. It was funny to read when it came out. It's even funny when clicking on the Random button on the site and seeing it. It's NOT funny when someone links to it from a one-sentence post and thinks they're so fucking clever to have discovered xkcd. You probably still use lmgtfy and think you're so damn clever. It means in real life, you're an unoriginal hipster doofus. Got anything to do with sanitizing inputs to a SQL database, etc.? Link to Bobby Tables. Got a nerd-project slow-ass turing machine? Like a minecraft logic circuit from redstone? Link to the one where it's some guy alone in the world making a computer out of rocks. Got a story about password security or encryption? Link to the one where they beat the password out of the guy with a wrench. Fuck off. You're not clever.

http://xkcd.com/1053/

Guess you're not one of today's 10000. Thanks for playing.

Re:Dilbert RNG

[Anonymous Coward]

It's fucking amazing to find my own troll reused by someone else two years after I posted it!

http://thedailywtf.com/Comments/Random-Char-and-TriplyRandom-Double.aspx#368204

Re:Dilbert RNG

[Anonymous Coward]

Perhaps he was being sarcastic and you should take your own advice? ;-) (though i actually agree with you)

Re:Dilbert RNG

[omnichad]

So you're the one that's claiming that old xkcd comics are so passé, but you're calling them the hipster?

I was telling people things were no longer cool before it was cool.

Re:Dilbert RNG

[Anonymous Coward]

Thank you for illustrating the kind of attitude that gives xkcd its readers.

Re: Dilbert RNG

[foobar bazbot]

I didn't even click on the link and knew it was some fag linking xkcd.

Well, it is a link that leads to xkcd.com, so it's not exactly difficult to figure out that that's where the link leads.

Yeah, but unlike GP, you couldn't deduce that link was posted by a cigarette!

Re:Dilbert RNG

[Anonymous Coward]

I think the emphasis was on the word fag

Re:Dilbert RNG

[Anonymous Coward]

Still trying to work out how he knew he/she was a fag, maybe the OP used one of their 'safe words'

Re:Dilbert RNG

[readeracc]

What's the point of sarcasm if no-one can pick it out and it sounds more like a typical troll?

Re:Dilbert RNG

[Anonymous Coward]

You didn't Google hard enough...

Dupe!

[VanessaE]

.....wait! it's not what you think.

"a new paper analyzes the robustness of /dev/urandom and /dev/urandom."

So now we're putting the dupes together into the same summary? Jeez, can't we at least wait a few hours first?

Re:Dupe!

[Anonymous Coward]

Coincidence. They were chosen at random.

Re:Dupe!

[Anonymous Coward]

Slashdot's random summary-inconsistency generator is still pretty robust.

At what scope of time or size of output data?

[fishnuts]

At what scope/scale of time or range of values does it really matter if a PRNG is robust?
A PRNG seeded by a computer's interrupt count, process activity, and sampled I/O traffic (such as audio input, fan speed sensors, keyboard/mouse input, which I believe is a common seeding method) is determined to be sufficiently robust if only polled once a second, or for only 8 bits of resolution, exactly how much less robust does it get if you poll the PRNG say, 1 million times per second, or in a tight loop? Does it get more or less robust when the PRNG is asked for a larger or smaller bit field?

Unless I'm mistaken, the point is moot when the only cost of having a sufficiently robust PRNG is to wait for more entropy to be provided by its seeds or to use a larger modulus for its output, both rather trivial in the practical world of computing.

Re:At what scope of time or size of output data?

[jythie]

The headline is somewhat sensational. There is a pretty wide gulf between an abstract and rather arbitrary metric and a practical vulnerability. This is kinda the security equivalent of pixel peeping, a fun mathematical exercise at best and pissing contest at worst, but ultimately not all that important.

Re:At what scope of time or size of output data?

[Anonymous Coward]

Right up until someone figures out how to use those "ultimately not all that important" technical weaknesses to good use. And then suddenly every single last deployed system might turn out to be vulnerable. Which might already be the case, but has been kept carefully secret for a rainy day.

Of course, usually it's a lot of "theoretical" shadow dancing, and given the nature of the field some things will indubitably remain unclear forever (unless another Snowden stands up, who just happens to give us a clear-enough answer), but there are an awful lot of people working exactly on finding this sort of entirely theoretical stuff and turning it into practical usability, while keeping their findings secret.

So, unfortunately, this sort of mathematical tin foil hattery is necessary, because all we know is that we're behind the curve (we only know what's made public), not how much behind the curve, and we have the disadvantage of the cost of fixing a large installed base.

We more or less can't afford not to peep pixels, because we simply don't know how much is too much, and how much is too little. This despite a foul-mouthed "looking ahead is hard!" populist figure with a noted lack of technical innovation skill.

Re:At what scope of time or size of output data?

[fuzzyfuzzyfungus]

The headline is somewhat sensational. There is a pretty wide gulf between an abstract and rather arbitrary metric and a practical vulnerability. This is kinda the security equivalent of pixel peeping, a fun mathematical exercise at best and pissing contest at worst, but ultimately not all that important.

I am definitely not a statistician; but there may be applications other than crypto and security-related randomization that break (or, rather worse, provide beautifully plausible wrong results) in the presence of a flawed RNG.

Re:At what scope of time or size of output data?

[Anonymous Coward]

First of all, not all computers are PCs. A server running in a VM has no audio input, fan speed, keyboard, mouse, or other similar devices that are good sources of entropy. A household router appliance running Linux not only has no audio input, fan, keyboard, or mouse -- it doesn't even have a clock it can use as a last resort source of entropy.

Second, there are many services that require entropy during system startup. At that point, there are very few interrupts, no mouse or keyboard input yet, and some of the sources of entropy may even be initialized yet.

One problematic situation is a initializing a household router. On startup it needs to generate random keys for its encryption, TCP sequence numbers, and so on. Without a clock, a disk, a fan, or any peripherals, the only good source of entropy it has is network traffic, and there hasn't been any yet. A router with very little traffic on its network may take ages to get enough packets to make a decent amount of entropy.

dom

Re:At what scope of time or size of output data?

[Anonymous Coward]

it's means it is. What the fuck does that make you, apostrotard?

Re:At what scope of time or size of output data?

[steelfood]

Useless for you. But the NSA might disagree. The math is what keeps them at bay. If the math shows cracks, it'd be certain that the NSA has figured out some kind of exploit. Keep in mind that the NSA doesn't rely on just one technique, but can aggregate multiple data sources. So those interrupts that the RNG relies on can be tracked, and the number that results can be narrowed to a searchable space. Keep in mind that 2^32, which is big by any human standard, is minuscule for a GPU.

Re:At what scope of time or size of output data?

[Anonymous Coward]

"A household router appliance running Linux not only has no audio input, fan, keyboard, or mouse -- it doesn't even have a clock it can use as a last resort source of entropy."

It probably has a radio with signals of varying strengths and packet losses. It also probably has a multitude of routed, nonrouted, and broadcast packets on its various network interfaces. And on top of that, it's connected to a global network of nodes with varying packet delivery times, and where at any time it can ask for a multitude of continuously changing and a least partially stochastic metrics (e.g. exchange rates, 4th word of news headlines, youtube +1 counts, etc, etc).

Re:At what scope of time or size of output data?

[Anonymous Coward]

But it's made by dlink et all and thus unlikely to put any of that in the entropy pool.

They're the sort who would use a user agent string for a backdoor so that they can reuse their web app code to do stuff.

Re:At what scope of time or size of output data?

[jhol13]

Your attitude is exactly what is wrong with security. Quite a few still use MD5 because "it is not that broken". Linus really should take a look in this new provably better method and adapt it ASAP and not wait until it bites hard.

Re:At what scope of time or size of output data?

[kscguru]

VMs do have good sources of entropy ... while a server indeed has no audio / fan / keyboard / mouse inputs (whether physical or virtual), a server most certainly does have a clock (several clocks: on x86, TSC + APIC + HPET). You can't use skew (as low-res clocks are implemented in terms of high-res clocks), but you still can use the absolute value on interrupts (and servers have a lot of NIC interrupts) for a few bits of entropy. Time is a pretty good entropy source, even in VMs: non-jittery time is just too expensive to emulate, the only people who would try are the blue-pill hide-that-you-are-in-a-VM security researchers.

The real security concern with VMs is duplication ... if you clone a bunch of VMs but they start with the same entropy pool, then generate an SSL cert after clone, the other SSL certs will be easily predicted. (Feeling good about your EC2 instances, eh?) This isn't a new concern - cloning via Ghost has the same problem - but it's easier to get yourself into trouble with virtualization.

Re:At what scope of time or size of output data?

[Anonymous Coward]

Every scope, every range. It's supposed to be a CSPRNG. It isn't. So it needs replacing.

I'm not sure about their suggestion, offhand, but I'd suggest maybe talking to Schneier. Skein-based Fortuna, maybe?

Re:At what scope of time or size of output data?

[Anonymous Coward]

Great, concise analysis! AC said it's not CSPRNG, therefore it isn't. Doesn't matter that the paper didn't even get their assumptions about that PRNG straight, the verdict is in!

How's that you're not sure about their suggestion? You seemed to analyse, understand and verify all the other suggestions from the paper immediately.

Re:At what scope of time or size of output data?

[Anonymous Coward]

Yes, for example a random dithering method may introduce a high frequency component with an amplitude less than 1 lsb.
Or the raytracer slightly skews the refraction to a another pixel in you one-coloured texture.

In most applications you want a deterministic outcome, even in a game where you want a random signals for enemy movement you might want something deterministic like the ANSI-C random function that is guaranteed to generate the same sequence from the same seed every time.
Even when you are generating random identifiers you don't want a true random number. You want something that is guaranteed to not generate the same number twice in a row.

There may be other applications for a true RNG, but I think you will have a very hard time finding one.

Re:At what scope of time or size of output data?

[FireFury03]

It probably has a radio with signals of varying strengths and packet losses.

This is true. Although I suspect a lot of the time the CPU isn't going to get to see a lot of that stuff (although with most wireless chipsets being softmac devices, maybe it does?)

It also probably has a multitude of routed, nonrouted, and broadcast packets on its various network interfaces.

In a dark-start situation (coming up from a wide area power outage), possibly not. Imagine an ADSL router whereby all the clients are connected via wireless. The clients can't talk to the router until it has managed to initialise the wireless encryption subsystems, which requires entropy. Even on a wired network, you may well only see a few DHCP requests from workstations. Obviously rebooting a router onto a large active network is different to rebooting the entire network at the same time, as would happen in a power outage.

And on top of that, it's connected to a global network of nodes with varying packet delivery times, and where at any time it can ask for a multitude of continuously changing and a least partially stochastic metrics (e.g. exchange rates, 4th word of news headlines, youtube +1 counts, etc, etc).

A global network that it may well be unable to access until it has enough entropy to make a cryptographic handshake with the upstream peer.

Re:At what scope of time or size of output data?

[Xest]

Exactly. If the recent leaks have taught us anything it's that the NSA has managed to produce real working exploits where previously such issues have just been discarded as nothing to worry about because they were "only theory".

At this point it's stupid to assume that just because you can't come up with a working exploit that someone with the resources the NSA has hasn't already.

It's of course not even just the NSA people should worry about, it seems naive to think the Russians, Chinese et. al. haven't put similar resources into this sort of thing, the difference is they just haven't had their Snowden incidents yet. I'd imagine the Chinese and Russians have exploits for things the NSA hasn't managed to break as well as the NSA having exploits for things the Chinese and Russians haven't managed to break. Then there's the Israelis, the French, the British and many others.

It's meaningless to separate theory and practice at this point. If there's a theoretical exploit then it should be fixed, because whilst it may just be theoretical to one person, it may not to a group of others.

Re:At what scope of time or size of output data?

[Anonymous Coward]

Lots of people still use MD5, because it's widely available, fast, and good enough for what they need. Just like CRC32 is good enough for certain tasks. MD5 may be broken for cryptographic purposes, but it's still fine to use for things like key-value stores.

Re:At what scope of time or size of output data?

[Anonymous Coward]

MD5 is perfectly fine, if your goal is to check for transfer/storage/software errors. Attacks, not so much - but there are situations where that's not actually a worry.

Not that it has any benefits over SHA256 that matter to me...

Re:At what scope of time or size of output data?

[Rockoon]

Its trivial to show that typical PRNG's are frequently not good enough for the monte-carlo simulations and testing that they are thrown at. An N-bit PRNG can only produce at most half of all N+1 bit sequences, a quarter of all N+2 bit sequences, an eighth of all N+3 bit sequences, and so on....

Given this, obviously the larger N is, the better. Of course most standard libraries use a 32-bit (or less) generator and most programmers are lazy or uneducated in the matter... so only half of all 8-billion to one shots are even possible with that 32-bit generator and then each can only be sampled if the generator just happens to be in the perfect 4-billion to one shot state....

As the saying goes...Random numbers are too important to be left to chance.

Re:At what scope of time or size of output data?

[JasterBobaMereel]

A VM is by definition running on a host that can skew what the VM sees and so is intrinsicly insecure ...

Re:At what scope of time or size of output data?

[ctr2sprt]

The real security concern with VMs is duplication ... if you clone a bunch of VMs but they start with the same entropy pool, then generate an SSL cert after clone, the other SSL certs will be easily predicted.

Yeah, I encountered that the other day. Built a VM, took a snapshot, did some stuff, reverted, did the same stuff. I was testing a procedure doc I was writing. Part of the procedure was creating an SSL cert, and I got an identical one on both attempts. That seems a little fishy to me; I would expect the certs to be (by the standards of cryptography) very similar, not identical. With that said, I didn't actually generate the cert myself, I ran a script (which I didn't write) to do it. The script might be using the same random seed or something. Or it could be a characteristic of moznss.

Feeling good about your EC2 instances, eh?

No shit. It might be worthwhile to use your desktop or some other hardware you control to seed your VM's PRNG with higher-quality entropy. That way, you should at least be able to avoid collisions with other VMs on the same hardware.

Re:At what scope of time or size of output data?

[fatphil]

The abstract seems to be talking about recovery from state compromise.

If you've got state compromise, you've already run code that you didn't want to run, and therefore you are not in control of your machine any more.

Game over. They're logging your keystrokes too, probably.

Re:At what scope of time or size of output data?

[Anonymous Coward]

More realistically, they would subject the Linux Device Under Attack by a sequence of nicely timed network packets in an attempt to DEFINE the state of the Linux RNG entropy pool. So the idea "let's take the timestamp of IP packets as a great source of randomness" might be not so great after all.

We all should get off our asses and build a USB device with a physical randomness source and use that as the sole source of crypto RNG. It would probably cost about 50 cent if mass-produced. Essentially, it is a piece of analog noise source (a semiconductor PN junction for example) coupled to an A/D converter. Plus the USB connectivity of course.

Re:At what scope of time or size of output data?

[Anonymous Coward]

I half-way agree. But that does not mean I do not appreciate that some people are kneedeep in it and trying to improve it. some day this theoretical issue may be so well understood that its a real issue with exploitcode in the wild.

Id rather say that it is not so important now, but ultimately it will be.

Re:At what scope of time or size of output data?

[Anonymous Coward]

MD5 is not that broken - for plenty of uses, but not security uses. But certainly Linus should pay attention to improvements (not just security improvements) and ignoring them would be foolish. On the other hand, he should not jump on the first alternative presented as it may be much worse in the long run (or backdoored?) what we have now at least have worked rather well over a long time (perfect is the enemy of good enough), everything new that sounds better isnt necesarilly so.

And if you need real random numbers you should not rely on the stock software version in your OS anyways. That is like expecting the standard radio and stereo-speakers that came with your car to be the best available.

Re:At what scope of time or size of output data?

[Anonymous Coward]

Quite a few still use MD5 because "it is not that broken".

MD5 is intended to identify situations where data corruption has occurred, it is not and never was supposed to be used as a tamper-proof mechanism or other sort of security system. So if you've been using it for anything else then you're not doing things properly to start with.

Re:At what scope of time or size of output data?

[sylvandb]

If there's a theoretical exploit then it should be fixed, because whilst it may just be theoretical to one person, it may not to a group of others.

The problem with that logic is when the nature of the theoretical defect and the supposed fix are both so complex as to render uncertain whether the fix will introduce a flaw more exploitable than the original theoretical flaw.

Some flaws are very obvious and the fix equally so. This is not one.

urandom uber alles

[Anonymous Coward]

"....robustness of /dev/urandom and /dev/urandom"

i will fight to the death any one who says /dev/urandom is less/more robust than /dev/urandom

Re:urandom uber alles

[Aighearach]

Bad call, in a fight to the death a tie doesn't help you any...

Re:urandom uber alles

[I'm New Around Here]

How about cufflinks? I can get a pair with lasers in them. Do those help?

Re:urandom uber alles

[I'm New Around Here]

What? I got modded offtopic for mentioning cufflinks, but Aighearach gets +1 Funny for bringing in neckties?

Where's the justice, /.?

Re:urandom uber alles

[HybridST]

You didn't put the laser cufflinks on a cufflink-wearing shark for starters.

Re:urandom uber alles

[sylvandb]

Where's the justice, /.?

moderation = (moderation + rand() % 5 - rand() % 5) % 6;

It's confirmed!

[Anonymous Coward]

"As a followup to Linus's opinion people skeptical of the Linux random number generator, a new paper analyzes the robustness of /dev/urandom and /dev/urandom .

I just checked /dev/urandom and /dev/urandom. The bitstreams are identical! Damn you, NSA!

Yawn

[Anonymous Coward]

The output of a software RNG, aka PRNG (pseudo random number generator), is completely determined by a seed. In other words, to a computer (or an attacker), what looks like a random sequence of numbers is no more random than, let's say,

(2002, 2004, 2006, 2008, 2010, 2012...)

However, the PRNG sequence is often sufficiently hashed up for many applications such as Monte Carlo simulations.

When it comes to secure applications such as cryptography and Internet gambling, things are different. Now a single SRNG sequence is pathetically vulnerable and one needs to combine multiple SRNG sequences, using seeds that are somehow independently produced, to provide a combined stream that hopefully has acceptable security. But using COTS PC or phone doesn't allow developers to create an arbitary stream of independent RNG seeds, so various latency tricks are used. In general, these tricks can be defeated by sufficient research, so often a secure service relies partly on "security through obscurity", i.e. not revealing the precise techniques for generating the seeds.

This is hardly news. For real security you need specialized hardware devices.

Re:Yawn

[mrchaotica]

For real security you need specialized hardware devices.

Yep. I think it's about time to hook up the ol' lava lamp.

Re:Yawn

[AHuxley]

Somewhere deep in China there is an unexpected rush order for desktop lava lamps and well understood open CPU products.

Re:Yawn

[Anonymous Coward]

"For real security you need specialized hardware devices."

Indeed. And it's worth considering that the Raspberry Pi has a Hardware RNG built in. Also, the tools to make it functional are in the latest updates to Raspian...

Did I mention that an RPi B is actually cheaper than the least expensive HWRNG-device (the Simtec Entropy Key - which is waaaayyyy backordered at the moment) - and about three times faster?

Re:Yawn

[Anonymous Coward]

Frankie!!! I told you to stop posting my pin codes to the Internet!!!

Re:Yawn

[Anonymous Coward]

PRNG != CSPRNG

It is deterministic, but not predictable. Also, while I definitely agree you need good hardware devices, you definitely also need a CSPRNG (e.g. Fortuna) to make good use of the hardware, otherwise you are suceptible to hardware flaws that damage your security.

Re:Yawn

[Chatterton]

Or the dice-o-matic :-)

Re:Yawn

[buchner.johannes]

LavaRnd works based on a CCD in a dark can producing noise, not a lava lamp.

Re:Yawn

[Anonymous Coward]

So does Intel CPUs.

The previous discussion was about whether or not to remove the Intel hardware RNG from the equation, because Intel is an American company, and as such subject to NSA requirements. I.e, nobody knows if the Intel hardware RNG is a true random number generator, or a pseudo random number generator with a secret key that only the NSA knows.

(Some would claim that such a suggestion is tinfoil hat material, but lately, Edward Snowden has been making the tinfoil had crowd say "damn, it's worse that I feared" multiple times).

Re:Yawn

[gl4ss]

you can check how a sw random works.

you can not check, generally, check how a hw random built into a chip works.

and heck... if the one in the rasp is good enough for you then probably the intel equivalent should suffice. however what good are real random numbers when you want a repeatable string of random numbers for which the seed is hard to guess from the numbers...

Re:Yawn

[Anonymous Coward]

The thing is, even if the Intel RNG has a secret key only the NSA knows it's better for Linux to use it than ignore it; more sources pseudo-randomness can only add entropy to the pool, adding predictable bits can't subtract from it. If the worst case is true and the Intel RNG is 100% predictable to any attacker who knows a secret NSA key, using it as an entropy source will give that attacker the same problem to solve as not using it, and give everyone else a harder problem.

Re:Yawn

[Anonymous Coward]

Somewhere in China they are producing lots of identically behaving lava-lamps

Unpossible

[Anonymous Coward]

"a new paper analyzes the robustness of /dev/urandom and /dev/urandom"

cool, they really should make random numbers redundant

next, we should make Slashdot moderators redundant.

and then, Slashdot articles redundant.

yay!

But But But

[Anonymous Coward]

It'z teh Linux!!!!!1111oneoneoneeleventyone!!!!!

Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

So, with all the 'revelations' and discussion surrounding this and encryption over the past several weeks, I've been wondering if a local hardware based entropy solution could be developed. By 'solution', I mean an actual piece of hardware that takes various static noise from your immediate area, ranging from 0-40+kHz( or into MHz or greater?), both internal and external to case, and with that noise builds a pool for what we use as /dev/random and /dev/urandom. Perhaps each user would decide what frequencies to use, with varying degrees of percentage to the pool, etc.. etc...

It just seems that with so much 'noise' going on around us in our everyday environments, that we have an oppurtunity to use some of that as an entropy source. Is anyone doing this, cause it seems like a fairly obvious implementation.

Re:Hear me out: Locally Generated Entropy Pool

[mrchaotica]

I linked to LavaRnd in a reply to an earlier post, but at the risk of being redundant, I'll mention it again.

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

It's not a risk of being redundant. It's a certainty. Unless you are from England. Then what you have done is not redundant, it was useful though repeated.

Just sayin'

Re:Hear me out: Locally Generated Entropy Pool

[Aighearach]

Unless this abstract can be translated into an actual attack of some sort, the chances are mostly in the area of creating new holes, not really in improving security.

Re:Hear me out: Locally Generated Entropy Pool

[Demonantis]

Greatest implimentation of a RNG I have seen. Not really realistic to have in every server room. http://gamesbyemail.com/News/DiceOMatic

Re:Hear me out: Locally Generated Entropy Pool

[WaywardGeek]

Yes. Hardware high-speed super-random number generators are trivial. I did it with amplified zener noise through an 8-bit 40MHz A/D XORed onto an 8-bit ring-shift register, generating 0.5MB/second of random noise that the Diehard tests could not differentiate from truly random numbers. XOR that with an ARC4 stream, just in case there's some slight non-randomness, and you're good to go. This is not rocket science.

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

RC4 is cracked, and a 120MHz radio signal can bias your generator.

(That wiped the smile off your face, didn't it!)

Two unstable Os, at different frequencies, work well, with an appropriate whitener and shielding. You need to determine when measurable entropy falls below a certain level from raw and cease. Use that to seed a pure CSPRNG - the Intel generator uses this construct with the DRBG_AES_CTR (which seems to be OK, if you trust AES, unlike the hairbrained and obviously backdoored DRBG_Dual_EC). You also need a mechanism for software to read the pre-whitened seed so it can estimate, or replace your CSPRNG with another (like Fortuna).

Re:Hear me out: Locally Generated Entropy Pool

[AmiMoJo]

Dual_EC_DRBG did well against Diehard but is known to be backdoored by the NSA. The Linux PRNG does well against it too. In other words Diehard is known to be a poor test for a cryptographically secure PRNG.

Unfortunately there is no simple suite of tests you can perform to make this determination. Zener noise is a good source of entropy but the chances of your A/D being unbiased, or that XORing with an ARC4 stream is enough to remove the bias completely is slim. At best you created another useful source of entropy, but TFA points out that even with many excellent sources the way the Linux /dev/random system mixes them is potentially weak.

Apparently it is rocket science.

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

No. Diehard*er* is quite good at detecting issues on HRNGs. But you must use it on the real random stream, preferably using test points before debiasing, after debiasing, and after non-crypto-hash whitening. Dieharder (and any other randomness test) will be *useless* after any crypto-hash-based whitening, **obviously**.

Which is why nobody likes the Intel RDRAND RNG, we cannot trust it nor test it, because no matter how good or bad it is, it WILL look random.

This is actually the issue as well with such lovely hardware as the SimTec Entropy Key (http://www.entropykey.co.uk/): the safest against defects/eavesdropping and more ready-to-use the HRNG is, the more you need to trust the manufacturer.

What you need to help Linux and the *BSDs generate great random numbers is something like the VIA Padlock RNG, which doesn't destroy the confidence on the RNG by crypto-hashing it.

As for ARC4 being broken, and MD5 being broken, well, these hashes are perfectly good for whitening purposes of a good HRNG. Maybe less so for a PRNG.

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

Plug a microphone in it, use the lowest bits from the soundcard?

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

Hardware high-speed super-random number generators are trivial.

Sure, but you can only trust them if you build them yourself. You cannot even trust one that _looks_ trivially correct, because you cannot trust the parts it's made of.
A little example of why: http://hackaday.com/2013/10/09/troll-physics-3-leds-powered-by-hand/

Re:Hear me out: Locally Generated Entropy Pool

[WaywardGeek]

No, a 120MHz radio signal cannot bias my generator unless the signal is so strong that the noise signal goes outside the ADC input range. Simply adding non-random bias to a random signal does not reduce the randomness in the signal. Simply XORing all the ADC output bits together for 80 cycles, where the low 4 bits correlate sample-to-sample less than 1%, and you get an error of less than 1 part in 10^50 of non-randomness. Add any signal you like to the noise, and it wont make any difference, so long as you don't clip.

You're thinking of a primitive hardware RNG that amplifies the signal to a single bit. Such generators are far slower (1 bit per sample, rather than 8, and you have to wait for the entire signal to become uncorrelated) and susceptible as you suggest to bias. Why would anyone waste most of the randomness in a signal by amplifying it to the rails?

Re:Hear me out: Locally Generated Entropy Pool

[WaywardGeek]

There's a simple fact that makes hardware RNGs easy. It really isn't rocket science.

XORing bits that each contain a small amount of true randomness leads quickly to high quality true randomness. Model the output bit stream from the hardware RNG as v(i) for the i-th bit. Assume each v(i) is 1 with probability 0.5 + e(i), where e(i) is an error function of magnitude 0.5. e(i) can be a function of previous v(i), a periodic signal, or some clever signal injected directly from the NSA. However, with magnitude 0.5, all you have to do is XOR the v(i) values together until you achieve the desired level of true randomness.

For bits v(1) and v(2), v(1) XOR v(2) has probability of being 1 = (0.5 + e(1))(0.5-e(2)) + (0.5 - e(1))(0.5 + e(2)) = 0.5 -2*e(1)*e(2). If e is bounded in magnitude by some number, like 0.4, you can easily compute how many bits you must XOR together to get the desired randomness. For a very poor quality RNG output error of 0.4, I need to XOR the output stream 7 times, generating 1 output bit for each 128 from the hardware RNG. The resulting error in randomness would be less than 1 part in 10^12.

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

Simply adding non-random bias to a random signal does not reduce the randomness in the signal.

do you know how i know that you don't know what you're talking about?

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

Dual_EC_DRBG is not known to be backdoored. It is believed to be, but that isn't the same thing, I certainly haven't seen any evidence that proves anyone has a backdoor to it. Although, with the evidence available it is prudent to avoid using it anyway

Re:Hear me out: Locally Generated Entropy Pool

[Anonymous Coward]

Could you, say, put that zener noise generator and supporting harware on a tiny USB dongle?

You could probably get a cheap micro that has the A/D and the computational facilities to do the rest, along with a USB interface to boot. (I imagine you'd use some sort of serial-over-USB scheme to feed data back to the host system. That would be easy to deal with.)

I doubt it would be more than a micro and a few bits of supporting electronics, along with the zeener. Tiny, cheap, robust entropy generator you could trust. (And audit)

Re:Hear me out: Locally Generated Entropy Pool

[WaywardGeek]

Let me try again using software this time instead of hardware. If I let my PC count from 0 to 2^32 in a loop until I hit enter, then the lowest bits will be very random, while the highest aren't very random at all. If I do this over and over, and XOR all the bits of all the counter results together, I can easily create crypto-grade random bits. If a hacker manages to add a signal of his design to my counter values, it has no impact on the randomness of my generated bits. This is obvious once you know that XORing a non-random value on top of a random value in no way reduces its randomness. If a random value v has exactly 50% probability of being 1, then I can flip the value by XORing 1 onto it, and it still has exactly 50% chance of being 1. Now if the hacker could AND values onto the counter values, I'd lose randomness, but any operation that is mathematically a permutation, like addition or XOR, does not reduce randomness.

The system I built does the same thing, generating 40 million 8 bit values per second that are similar to the counter values described above. The low bits are highly random, and the high bits are not. If you simply add a signal to these values it has zero impact on the randomness of the result, just like with the counter values. Now if your signal overloads the amplifier, causing clipping, then the output might be 255 for many samples. That would brake the RNG, just like AND-ing 0's onto my counters would do.

Anyway, this is not rocket science. People seem to think you can't make good random data without a Ph.D. in cryptography, but in reality, all you need is a source of *some* randomness and the XOR operation. The math is pretty simple, too.

Re:Hear me out: Locally Generated Entropy Pool

[doti]

and mix it with the lowest bits from all sensors available, like various temperature sensors, fan speed, etc.

mobile devices usually have even more sensors to use.

So write a better one

[Gothmolly]

These guys had the time, brains and resources available to do a full breakdown of how /dev/random might not be so random.... why not go all the way, submit a patch and fix it?

Re:So write a better one

[Frosty Piss]

Hey, if *LINUS* say the RNG is fine and all you idiots know NOTHING, hey, that's good enough for me.

Re:So write a better one

[interval1066]

It might have been a scholarly F-U to Linus, if so, why would they fix it?

Re:So write a better one

[Anonymous Coward]

It might have been just business as usual with a click-bait title slapped on by editors.

A lot of research papers go like: "Here's a problem we've thought up, here's a formal definition, here's a method to identify it, here's application of this method to existing implementations showing how awful they are, (optionally) here's our take on the problem and benchmark on our arbitrary criterion against those implementations showing how everyone could fix it if they'd just listen to us. PS: We didn't research how practical are requirements on successful exploit and our proposed implementation, but dang are our formulas neat!" They need to prove they did a ground-breaking, novel and important research after all, don't they?

And then news sites go and write articles reading "Wereallgonnadie!!11 (If all the planets and stars align juuuust right)"

Re:So write a better one

[Z00L00K]

"Not so random" means that you can mathematically calculate how likely it is that you can predict the next number over a long time. If you can predict the next number with an accuracy of 1 in 250 while the random generator provides 1 in 1000 then the random generator isn't that random.

Many random generators picks the previous value as a seed for the next value, but that is definitely predictable. Introduce some additional factors into the equation and you lower the predictability. One real problem with random generators using previous value as a seed without adding a second factor is that they can't generate the same number twice or three times in a row (which actually is allowed under the randomness rules).

It's a completely different thing to create a true random number. For a 32 bit number you essentially should have one generator source for each bit that don't care about how the bit was set previously. It is a bit tricky to create that in a computer in a way that also allows for fast access to a large number of random numbers and prevent others from reading the same random number as you do.

For computers it's more a question of "good enough" to make prediction an unfeasible attack vector.

Re:So write a better one

[Xest]

Because whilst they may have had the time and resources to research it and come up with a solution, they don't necessarily have the time and resources to fight their patch past Commander Torvald's ego and army of protective zealots.

Many bright academics simply have better things to do than get involved in that sort of childishness. Research is what they enjoy and they have neither the time nor interest in political bickering to get involved, especially if it flies in the face of logic - i.e. someone refusing to let something be fixed simply because they have too big an ego to admit they were wrong, rather than because they have a valid counter argument.

Blame Linus for building a public image of himself as a hot-headed grand-dictator rather than a rational level-headed respectful leader for scaring smart people off. Note that I'm not saying he is the former, I don't know him personally well enough, maybe he is rational, level-headed and respectful in person, but that's not the public image he's built of himself and he's done neither himself nor his project any favours in building the image he has, as much fun as it seems at the time to bitchslap stupid people down in the most brutal way one can manage with words.

Sometimes it's just better to do what you're good at and leave the rest to everyone else. In this case the guys behind this study are probably good at the research but neither good nor interested in dealing with the politics of getting a patch accepted and would hence rather let others deal with that, or who knows, maybe even Torvalds himself will now accept that there's a theoretical problem that may be exploitable in practice and will change his mind and do it without any argument.

Re:So write a better one

[Ash Vince]

Because whilst they may have had the time and resources to research it and come up with a solution, they don't necessarily have the time and resources to fight their patch past Commander Torvald's ego and army of protective zealots.

Or maybe now they have actually created a paper that may or may not define a real issue (I'll wait and see how this is peer reviewed as I have no idea about theoretical weaknesses created by different ways of combining sources of entropy in order to create random data) with the kernel in depth (not just some moronic bullshit petition based on a completely incorrect assessment of how someone guessed something would work with no real investigation of the actual system involved) the kernel team will actually look at this and make an assessment of how they could fix this.

In short this is far more likely to be well received and result in changes being made to the the kernel as these guys did some investigation. The previous petition starting moron just demanded changes without understanding what he was asking for changes to at all and without being able to recommend a better way of doing it, instead he just said "Don't do this" even though the kernel did not actually do that anyway.

These guys are not saying "Do not trust RdRand as intel might have been paid off by the NSA to make it crap", instead they are picking apart the minutiae of how the kernel combines sources of entropy (something the guy who started the petition did not know it did at all) and suggesting subtle changes to make it better. The two things are so far apart that there is no reason to even dream that both would garner the same response.

Re:So write a better one

[Xest]

You're just focussing on one incident though, and there have been hundreds over the years. Often Linus is right and is just dealing with an idiot, but sometimes he's not.

But I'm simply reasoning a response to the GP's post as to why people may wish to steer clear of contributing a fix once they've written a paper. If a clique is unnecessarily cruel to anyone, no matter how stupid that person, then that's going to put people off interacting with it directly. As far back as the original Tanenbaum debate he's admitted himself that he could be a bit over the top, but rather than do something about it he's only gotten worse.

I hope you're right that they do evaluate this and do something if necessary, but fundamentally my point is that this may be for the best anyway. I suspect this will work far better than if they'd just published a fix themselves and had to potentially face Linus' defensiveness, particularly as Linus has had to publicly be defensive on this issue already (albeit for valid reasons in that case) such that it's probably not his favourite topic right now and not one he wants to revisit if he can help it.

Or to cut a long story short, the GP asked why they didn't just fix it themselves. I'm offering one possible reason why that may be- that it may just be best to write the paper, avoid the politics and let the kernel developers deal with it amongst themselves. They're understandably a tight knit group, but also one that's highly opinionated, so it probably is best to just hand them your research, walk away, and leave them to it, rather than try and fix it yourself and then argue with them about whether you're a talented enough developer to allow the fix through, whether it's necessary, whether there's a better way of implementing it and so forth - they'll probably be happier figuring all that out amongst themselves if they feel there's a valid concern anyway.

Re:So write a better one

[Anonymous Coward]

Research is what they enjoy and they have neither the time nor interest in political bickering to get involved, especially if it flies in the face of logic - i.e. someone refusing to let something be fixed simply because they have too big an ego to admit they were wrong, rather than because they have a valid counter argument.

Then they got into the wrong career. If you want to do research and not deal with political bickering, do it in your free time and just throw it up on your personal webpage. If you try to make a job of it, you will deal with that quite frequently (even if the sources are a small minority of colleagues). Trying to get something past Linus (whether the real one or an imagined image) wouldn't be exceptional, just par for the course.

A bigger problem might be that it can be easier to find bugs and security problems than finding fixes for the problems you've uncovered.

Re:So write a better one

[freeze128]

It still won't increase my chances of getting winning lottery numbers by 4 times, so it's "good enough".

I knew the day would come

[OhANameWhatName]

From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom

The internet must have finally run out of porn.

Re:I knew the day would come

[Anonymous Coward]

not possible... where's the rule 34 on random number generators?

Re:I knew the day would come

[king neckbeard]

chatroulette is the closest thing that comes to mind.

Re:I knew the day would come

[philip.paradis]

Penises are anything but random on chatroulette.

Re:I knew the day would come

[Anonymous Coward]

I haven't ventured on penis^Wchatroulette to verify, but I imagine the details (e.g. skin colour, size, erectness) of the penis to be random.

Incorrect and irresponsible headline

[Anonymous Coward]

I swear, if I worked for the NSA I'd be pushing out headlines like this to make people ignore real security issues...

The article is a highly academic piece that analyzes the security of the linux rng against a bizarre and probably pointless criteria: What is an attacker's ability to predict the future output of the RNG assuming he knows the entire state of your memory at arbitrary attacker selected points in time and can add inputs to the RNG. Their analysis that the linux rng is insecure under this (rather contrived) model rests on an _incorrect_ assumption that Linux stops adding to the entropy pool when the estimator concludes that the entropy pool is full. Instead they offer the laughable suggestion of using AES in counter mode as a "provably secure" alternative.

(presumably they couldn't get a paper published that said "don't stop adding entropy just because you think the pool is at maximum entropy", either because it was too obviously good a solution or because their reviewers might have noticed that Linux already did that)

Re:Incorrect and irresponsible headline

[TheRealMindChild]

Also, any measurement that they use to know the state will change the state

Re:Incorrect and irresponsible headline

[FrangoAssado]

Their analysis that the linux rng is insecure under this (rather contrived) model rests on an _incorrect_ assumption that Linux stops adding to the entropy pool when the estimator concludes that the entropy pool is full.

Exactly. The maintainer of the /dev/random driver explained this and a lot more about this paper here.

Re:Incorrect and irresponsible headline

[AHuxley]

The NSA and GCHQ did all they could to stay out of the press from the 1960-80's. In the 1990's they thought they had the best cover ever: the internet is just too "big" and crypto offered for export too complex and open.
Add in law reform, projected data storage costs and wise sock puppets - everything was looking great for ongoing domestic surveillance infrastructure.
The political leadership, color of law, telcos, software brands, press, academics, hardware brands, lawyers where all tamed as needed.
The problem with the headlines is the lack of fear by the public at this point in time.
People are LOL, interested, creative, getting involved, rethinking their education, thinking about code, looking back at their pasts for that moment of total crypto failure.
An East German view would be: coders are out front of a Church with source code lines, talking, compiling, sharing, fixing and educating in public.
They can see the cameras, know they will be in a domestic database.
They dont care about academic 'trouble', no flight lists, that anyone of them could be a corporate or gov "agent provocateur" - they are getting on with fixing code and examining hardware, line by line this time.
See the reaction of the AC sockpuppets vs years ago. The trance of citation needed no longer works.
The AC sockpuppets have to show their true traits, personal attacks, anger, the right to rule and the classic "I saw something" and now I want a police state.

Re:Incorrect and irresponsible headline

[Aighearach]

Yeah, because random number generators is like pr0n for the masses, and will distract them from boring stuff like the government monitoring and storing that really stupid thing they said about their boss, right next to their cybersex session with their mistress.

Re:Incorrect and irresponsible headline

[Anonymous Coward]

So can you put in a different estimation value, or make it run 10-100-1000x more entropy than it used to by "default"?

Re:Incorrect and irresponsible headline

[bytesex]

[wtfamireading.jpg]

Re:Incorrect and irresponsible headline

[BitZtream]

And that is irrelevant.

This is code, not quantum physics. The changes made by measurement are measurable and predictable themselves.

Whatever happened to

[mark_reh]

zener diodes biased into avalanche mode to generate random noise? I don't think even the NSA has figured out how to hack laws of thermodynamics.

Re:Whatever happened to

[sanitycrumbling]

So, as somebody who has no idea what that means (sorry) - how can that be truly random? Aren't there some laws of physics that would govern how it would work?

Re:Whatever happened to

[Nemyst]

Laws don't mean you will know for sure how a measurement will turn out. One of the fundamental tenets of quantum mechanics is that you cannot determine in advance in which state a particle will be. If it is in a superposition of 0 and 1, for instance, there will be a likelihood for it to, once measured, be 0 or 1, and that likelihood may be biased, but you cannot know any of this unless you created the bias in the first place. Even then, even if you know the exact likelihood, unless the particle is entirely, 100% in one state, you cannot predict which state it will be in when you measure it. Despite this randomness, quantum mechanics has many clear laws, and some of these define the randomness, like Heisenberg's uncertainty principle.

Now, of course, using quantum effects to produce random numbers is a bit impractical. The GP's suggestion might be more practical, I don't know that particular method, but the general point still stands.

Re:Whatever happened to

[eladts]

The laws of physics, namely quantum mechanics, do include randomness in them. Everything is probabilistic in principle. Usually, this randomness isn't manifested at large scales, but under certain circumstances it can be. That's how you build a hardware RNG. http://en.wikipedia.org/wiki/Hardware_random_number_generator

Re:Whatever happened to

[OneAhead]

There are quantum effects involved in this process. Quantum effects (more specifically wave function collapse) are thought to be a source of true, inherent and perfectly unpredictable randomness. Throw that into a massive (from an atomistic point of view) chaotic system and you get a gigantic mess that is impossible to simulate with sufficient precision to predict the noise that comes out (and far, far beyond our computational means even if you don't care about precision).

I would say "read more about it here, but a lot of what's written there is inaccurate. Both resistor noise and avalanche noise have important quantum nature and classifying them under "physical phenomena without quantum-random properties" is factually incorrect. The second comment by user "agr" in the discussion nails it. Pretty much anything involving electrons is quantum at the microscopic level.

Re:Whatever happened to

[mark_reh]

avalanche diodes conduct bursts of current at random times. A true random number generator simply measures time between those bursts of current then scales that value to whatever numerical range you need.

You can also time the clicks produced by a geiger-mueller tube detecting beta radiation from a radioactive source, but that requires a lot more difficult-to-integrate hardware.

Even if you base the final random number on a truly random source you have to ensure that the scaling routine doesn't introduce any sort of bias into the final value. THAT is the tricky part.

Re:Whatever happened to

[Anonymous Coward]

It doesn't have to be a Zener diode; any transistor will work

Re:Whatever happened to

[steelfood]

Somebody's gotta implement it in hardware. Do you trust Intel or AMD? I don't. If I can run an OSS analyzer on it and the results come out positive, I might be convinced. But I'm not sure this feature even exists for any consumer chips.

Re:Whatever happened to

[gman003]

Well, Intel and VIA have such things integrated into their processors now. Unfortunately, they (at least Intel - not sure how VIA's implementation worked) decided to whiten the data in firmware - you run a certain instruction that gives you a "random" number, instead of just polling the diode. With all the current furor over the NSA stuff, many people are claiming that it *is* hacked.

Re:Whatever happened to

[Z00L00K]

Use one GM tube for each bit, and let it toggle that bit on or off for each detected decay. To be really sure have different radioactive samples for each GM tube isolated from each other.

If you feel unsure - use two different isotopes, double the number of bits, then XOR them together and use the result as the random number.

Scale up to the number of bits you need.

If that's not random enough I don't know what will be constituted random enough.

Re:Whatever happened to

[profplump]

Without whitening you're likely to get biased output, which is undesirable in most of the contexts where you'd want a truly random number in the first place. You can do whitening in software, which is fine for things like seeding a PRNG where you've already got a lot of code related to managing incoming entropy, but it makes the instruction difficult to use in other contexts where you just want a random number for direct consumption. On the other hand, pre-whitened data is just as useful for PRNG seeds *and* can be consumed directly. Arguably they should *also* provide access to the raw stream so you can do your own whitening (or not, if your use doesn't require it) but if they're only going to add one instruction it's easy to see why they chose the whitened version.

Re:Whatever happened to

[AmiMoJo]

Even if they didn't whiten the data you could never trust that they didn't bias the measurement somehow. Besides which TFA isn't questioning the sources of entropy, of which there are many in a typical Linux system, it is the way that they are combined.

Re:Whatever happened to

[Anonymous Coward]

VIA gives you access to the stream before whitening, or at your choice, after a simple Von Neuman whitener, which does NOT destroy the observable weaknesses on the random data.

This IS GOOD. In fact, it is *perfect* for input you need to feed to your entropy pool (Linux, BSDs) or PRNG.

Re:Whatever happened to

[BitZtream]

If you feel unsure - use two different isotopes, double the number of bits, then XOR them together and use the result as the random number.

You just epic failed, the XOR did it for you. The XOR is going to actually result in reduced randomness.

Re:Whatever happened to

[Anonymous Coward]

Get NSA backdoored hardware but install a Chinese hardware RNG. Then you know you are safe ;-)

Re:Whatever happened to

[Anonymous Coward]

if they're only going to add one instruction it's easy to see why they chose the whitened version.

Because the instruction totally couldn't be coded to choose whether to whiten depending on a flag.

Re:Whatever happened to

[Z00L00K]

Not necessarily - 32 random bits xor 32 random bits will still be 32 random bits, the difference is that you will introduce two factors of uncertainty due to different decay rates. The XOR function is blind, you only get problems if you use it on a seed value or the result of a function.

Re:Whatever happened to

[Anonymous Coward]

So you're suggesting buying lots of smoke alarms and gutting them for their radioactives? That got people a bit worked up last time it was tried.

Re:It's Not That Hard, Folks

[queazocotal]

That's not quite the point.
The two random devices are there not to be alternate sources of randomness, but to be a good source of provably random numbers gained from hardware randomness mixed into the entropy pool, and another source of cryptographically random numbers seeded from the first - but with perhaps orders of magnitude less entropy per output bit compared to input bits.
The first source will stop outputting when it runs low on entropy.

The Article And Paper Titles Are Nonsense

[Anonymous Coward]

/dev/random and /dev/urandom are simply devices that are supposed to return a cryptographically secure continuously-reseeded pseudorandom number stream. /dev/random blocks when the entropy pool is depleted and /dev/urandom continues to produce a pseudorandom pad using the same underlying secure hash algorithm. There are, and have always been, "problems" with how the entropy remaining in /dev/random's pool is calculated insofar that it's the subjective call of whatever entropy provider is restocking the pool. Anyone who cares about that is using dedicated hardware random number generators. Everybody else uses /dev/urandom. The people who use /dev/random are usually those who don't realize that the only difference between it and /dev/urandom is that it blocks.

It's a waste of time to focus on quantifying the entropy metric that /dev/random uses to decide when it's time to block and wait for more entropy. The security of /dev/random and /dev/urandom come from the hash being used to munge the entropy. Various hashes have been and are being used, including SHA-1 and, god forbid, the NSA's favorite, Dual EC DBRG. That's where the weakness in /dev/random / /dev/urandom springs from, not any of that theoretical shit.

If you want to know whether or not your application is getting exploitable correlation-possible randomness from /dev/urandom, examine your kernel's drivers/char/random.c and see which hash it's using.

And what about other open source PRNGs?

[Anonymous Coward]

If the Linux one has questionable randomness then what does that say of the PRNGs in other operating systems, be they open or otherwise?

This is my contention: encryption on the Internet isn't necessarily weak because of the algorithms but because of key selection.

Thus even if we have AES256, maybe the real strength is AES100 or less.

Linus = on NSA payroll?

[Anonymous Coward]

He "confirmed" he'd been asked to backdoor linux, he never confirmed whether or not he agreed... :)

Re:Linus = on NSA payroll?

[Anonymous Coward]

Of course, and since it's free software we're talking about, we're all on NSA payroll. You included. QED

Re:Linus = on NSA payroll?

[Anonymous Coward]

His response could also be interpreted as a joke. All we know is that if he has been asked to do it, he isn't allowed to talk about it. Personally, I don't think the NSA would ask Linus to backdoor the kernel, I think they would go with a more subtle approach of having someone else introduce a backdoor, because if Linus and the other maintainers can spot the backdoor during the submission process then the NSA hasn't obfuscated the backdoor well enough and it is likely someone else who examines the code will be able to spot it.

Concerned and wondering!

[EzInKy]

Can anyone provide a link to a site that reviewed the source code and vetted the security of all RNGs?

So just build your own

[Anonymous Coward]

It isn't hard and works best when used to continuously reseed the kernel's entropy pool.

https://www.binarymagi.com/drupal/node/18

many times a day he says Linux needs changes

[raymorris]

Linus signs off on many changes everyday. He does expect you to read the code before trying to change it. That was the problem before - someone put up a change.org petition that made clear they had no idea how it worked.

Re:many times a day he says Linux needs changes

[WaywardGeek]

I just read TFA and associated paper, and the petition. Linus was right, the petition was pointless, and motivated by confusion on the petitioner's part. However, the paper points out some scary issues in the Linux PRNG. It's tin-foil hat stuff, but it shows how one user on a Linux system could write a malicious program that would drain the entropy pools, and then feed the entropy pool non-random data which Linux would estimate as very random. If this attack were done just before a user uses /dev/random to generate a cryptographic key, that key could be compromised, meaning the attacker may be able to guess it.

The paper echos a call for Linux to stop estimating entropy, meaning effectively we'd just have /dev/urandom only, and people who require cryptographically strong random bits would have to look elsewhere. As a practical matter, I disagree. /dev/random may not be 100% secure, but it's handy.

Re:Random Post Number

[Aighearach]

And if you'd have only guessed "first," like everybody else, you'd have a 5 instead of a 0.

Randomness is an illusion

[Anonymous Coward]

The sequence "1 2 3 4 5 6 7 8 ..." belongs to the set of randomly generated numbers. But there are so many fools out there who would exclude such a sequence from that set. Which would then make that resulting set of random numbers biased.

Haven't these people got anything better to do with their time?

Re:Randomness is an illusion

[Z00L00K]

And 6 6 6 is also in the set of random numbers.

Re:Randomness is an illusion

[wonkey_monkey]

But there are so many fools out there who would exclude such a sequence from that set. Which would then make that resulting set of random numbers biased.

Yes, but they're only playing the lottery, so what harm does that do?

This is only for recovery after state compromise

[gweihir]

If the CPRNG state is not compromised, the Linux random generators are secure. In fact the property required for robustness is quite strong: Recovery from compromise even if entropy is only added slowly. For example, the OpenSSL generator also does not fulfill the property. Fortuna does, as it is explicitly designed for this scenario.

I also have to say that the paper is not well-written as the authors seem to believe the more complicated formalism used the better. This may also explain why there is no analysis of the practical impact: The authors seem to not understand what "practical" means and why it is important.

Achtung morons !

[Anonymous Coward]

Only a fool believes in perfect security.

To know a god's mind: First become your own god...

[VortexCortex]

Yes, there are apparently laws that approximate how it would work, however to know the outputs one would need to have information about all the energy field states that make up the device's matter (and dark matter) at a given plank time.

In the past when I've needed a random number generator I've used a single infrared LED and IR Diode connected to a serial port. Poll the difference between the time it takes a photon to build up, be emitted, and detected multiple times and use the lowest bits as the random values. It's a lot slower, but it's basically the same principal -- Using the quantum uncertainty principal by observing quantum phenomena to generate randomness. In a real pinch, I just have the user move their mouse around like a loon...

Even if we had perfect equations to predict physical phenomena (we do not), we'd still need to know the initial state of the Universe and have 13.7 billion years of clock time (running as fast as absolutely possible) in a separate isolated universe to predict the random numbers with certainty... Any transfer of information between the isolated universe and our own would screw up the future calculations of randomness, due to the cascade of information entanglement.

Predicting the random numbers would be like trying to figure out what hash to include within this message right here [cf372106a91cd957d5a1046b57534485ddbdd4c0] so that when the message is hashed the the result would match that prior value. You could run the hash, insert it, but that would change the message's hash -- True, you could brute force the hash, but the message is entire Universe.

Let's see, we'll try everything before this paragraph using all zeros first, and see if that's the matching hash... nope. So, we'll insert the value we just got and hash it again: [211c7d73a0c66355921ef0dfb99019a2cce71754]? Nope... this could take a while, maybe we should start counting up from 0000000000000000000000000000000000000000 towards ffffffffffffffffffffffffffffffffffffffff to keep track. This is a SHA-1 hash, so it'll take 2^159 iterations on average, (or about 730,750,820,000,000,000,000,000,000,000,000,000,000,000,000,000 tries). You feeling lucky? Further, we could run through all the combinations and never get the message to be self hashing since the answer for above might not be in ASCII hex, or it might not exist in this message's problem space -- i.e., No solution may exist for the above universe. In other words: Our tool / assumption about the universe's laws / our representation of reality might not accurately reflect the true reality that the hash (or diodes) operate within, or our assumption that the problem is solvable may be wrong... So, you see, it's not perfectly random, but since we can't simulate the entire universe within itself, thermodynamics and quantum effects are random enough for our purposes -- Otherwise all lotteries could be considered rigged.

Insecure?

[Anonymous Coward]

Quick, someone validate RNG's usefulness before its feeling of self-worth is affected! I would, but I don't care.

Ted Ts'o on Schneier.com

[Mister Liberty]

has some thoughts on the study and the subject:
https://www.schneier.com/blog/archives/2013/10/insecurities_in.html

Re:Ted Ts'o on Schneier.com

[amaurea]

Here's direct link Ted's post. The most interesting points are (if I understand them correctly):

1. The insecurity discussed in the paper is about how quickly the Linux entropy pool recovers from a compromised state. I.e. imagine that somebody somehow gains full read access to your computer's memory, and reads your randomness pool (but kindly does not read all your private keys etc.), but then loses that access at some later pool. How long does it take until the entropy pool has recovered enough entropy to be usable again? I think in most cases one would already have lost at the time an attacker gained full read access to your system, and wouldn't worry much about what happens after that. So this is a pretty irrelevant issue.

2. The paper relies on the assumption that Linux stops collecting new entropy once it thinks the pool is sufficiently random. That hasn't been the case for quite some time - it now continues to mix in new entropy no matter how random it thinks the pool is.

I would not be very worried about this. And I think all the suggestions that people use hardware RNGs *instead* of /dev/random are misguided. While hardware RNGs are good in theory, and make a good input into /dev/random, they are, unlike the Linux source code, difficult to verify.

Random enough?

[duke_cheetah2003]

I think the only question on my mind is what exactly is deemed insecure for? Generating public/private key pairs? Doing encryption for SSL/TLS?

I've been around computers for a good number of years and I know no computer can be truly random, but isn't there a point where we say, "It's random enough."? Is this OP saying.. Linux's RNG isn't "Random Enough." and my question is.. what isn't it random enough for?

Re:Random enough?

[Anonymous Coward]

It is random enough. Really. As long as you're not in a broken platform which is extremely deterministic, has booted a few seconds ago, AND has no hardware source of real entropy, like routers, APs printers...

All Linux distros will save/restore at least 1KiB of random data to pre-seed (via mixing, so no previous randomness is lost) at boot (without entropy credit, so /dev/random might still block but both /dev/random and /dev/urandom WILL be random after that safety seeding).

Modern linux kernels *and* distros (yes, both are doing it) also dump into the entropy pool all variable data it can find from boot (distros will do the equivalent of "dmesg > /dev/random" on top of the pre-seed-over-shutdown-and-reboots we've done since 1997 or thereabouts), and that includes stuff like time, MAC addresses, PCI addresses, device detection order (which changes between boots depending on device/bus timings)...

And a modern Linux kernel will never stop feeding entropy to the RNG, even if it is full and nothing is touched it (which is pretty much impossible, since every process fork and TCP/IP packet uses some randomness...).

haveged?

[kangsterizer]

http://www.issihosts.com/haveged/

Easy, fast random numbers

[SpaceLifeForm]

wget http://www.slashdot.org/ | sha512sum

Re:Easy, fast random numbers

[Anonymous Coward]

Bad idea. Have you seen how many duplicated articles we get here?

Re:Huh

[Anonymous Coward]

It's good you posted this, because it just shows how desperate and ridiculous you are as a person that you'd rather cling on to this sensationalist news article rather then do any research into the topic.

Now everyone knows who to ignore in the future.

What's up with the anti-Linus trolling?

[Anonymous Coward]

Linus never said that the Linux RNG is perfect. He leashed out against a person who wanted to remove the rdrand instruction, without understanding that the rdrand instruction doesn't add to the entropy estimate. And he was completely right (even though mocking stupid people is not good style).

This paper is about "vulnerabilities of the entropy estimator" so it is no related to the rdrand thing, because the latter does not contribute to the entropy estimate.

So why did the poster and the editors have to make the connection? There is only two sad answers:
1) They are trolling - and if you read they are unfortunately successfully
2) They are idiots and do not know what they are talking about

Slashdot is becoming the Fox news of the tech-world. :(

Re:What's up with the anti-Linus trolling?

[Joining Yet Again]

If I were writing a malicious RDRAND instruction, it would correlate with the bits being XORed with, in order to reduce entropy.

The whole assumption that a new source of entropy can't reduce randomness is based on the idea that a new sequence is independent of other sequences. It doesn't need to be.

Degenerate case: old sequence = new sequence; output: stream of 0s.

Panic!

[Anonymous Coward]

I'm having a security panic over here!

as a quick fix I deleted /dev/random and did ln -s /dev/zero /dev/random

Re:Panic!

[Anonymous Coward]

Good idea. /dev/zero is a lot faster and according to the conspiracy theorists, it is as secure.

Very Informative.

[basecastula]

Half way down in the comments.

Re:Very Informative.

[Lennie]

If you are gonna do that, might as well link to the comment:

https://www.schneier.com/blog/archives/2013/10/insecurities_in.html#c1909001

And watch Linus rant

[Anonymous Coward]

about how they should just shut up because they're not programmers and just understand that they don't know how to write the Linux kernel as well as he does...

Re:And watch Linus rant

[Anonymous Coward]

Wow, you need to be a programmer to understand math now?

random source

[Anonymous Coward]

Just sample a few kb from the integrated microphone (given that there arent't too many zeros in sequence). It's enough for beating even the mighty NSA.

Can't we do this like with time

[Anonymous Coward]

And have some RNG servers on the internet. There is bound to be a few that are trustworthy.

So where is the pull request to fix the problem?

[Ice Station Zebra]

Linus is waiting.

Plan 9 is indeed much better designed, but ...

[Taco Cowboy]

Plan 9 is much, much better designed than unix, we just need to port our software

I do concur with you, PLAN 9 was indeed a much better designed OS, from the ground up, but, as all the techies who have been in the tech field already know ...
 
  better product does not always become the guaranteed winner in the marketplace

Re:Plan 9 is indeed much better designed, but ...

[LoRdTAW]

Plan 9 failed simply because it fell short of being a compelling enough improvement on Unix to displace its ancestor. Compared to Plan 9, Unix creaks and clanks and has obvious rust spots, but it gets the job done well enough to hold its position. There is a lesson here for ambitious system architects: the most dangerous enemy of a better solution is an existing codebase that is just good enough.
â"Eric S. Raymond[3]

Re:To know a god's mind: First become your own god

[Anonymous Coward]

Even if you had perfect measurements and knowledge of the configuration of a system, quantum mechanics has systems that will be probabilistic and random. QM is not about lack of details or making approximations, it posits that natural is inherently probabilistic and not deterministic in certain ways. More details would not help in a system properly setup to utilize those random processes, only QM being wrong. While that is always a possibility, it takes more than people saying they don't like its probabilistic nature to demonstrate that it is not an accurate description of reality.

Re:/dev/random is not random

[Anonymous Coward]

Huh? Why the hell is this not at -2 (troll, incorrect/FUD/st0n3d) ? /dev/random is defined to be at least as good (crypto/random-wise) as /dev/urandom in Linux, the BSDs, and all their derivates. It is also like that in AIX and Solaris, therefore in everything that matters. Heck, on FreeBSD, /dev/random and /dev/urandom are exactly the same...

Hardware RNG for servers and VMs

[steveha]

I think it is past time for CPUs to provide hardware random numbers. Via CPUs have done this for years, but Via CPUs are just too slow for most uses. (I used to run my mail server on a Via C3... I am a lot happier now that my server runs on an AMD low-power dual-core.)

Recent Intel chips do have some sort of random number generator (RdRand).

Hardware RNG accessories are available but expensive.

There is the LavaRnd project, which I think is really darn cool. However, I downloaded the source code, and it hasn't been updated since 2003... a decade later, GCC won't even compile the code. (GCC now issues warnings about some of the code and they set the "treat warnings as errors" flag. I didn't experiment with disabling that flag and trying the code out.) Also, the supported hardware list is a short list of decade-old webcams.

(Note: this would be a good project for a high school student or college student who knows C: update LavaRnd so it builds with GCC or Clang, get it working with at least one currently-available webcam, and write a report about it.)

The Raspberry Pi has a hardware RNG as part of the system-on-a-chip, and Linux on the Pi supports it. You could set one up as a randomness server to your VMs, and that would be quite inexpensive. At least the VMs could reseed their PRNGs with random values pulled from the Pi.

http://vk5tu.livejournal.com/43059.html

If you have a sound device, Audio Entropy Daemon may work.

http://www.vanheusden.com/aed/

P.S. Haveged looks interesting... I just discovered it and I don't know how well it actually works.

https://www.digitalocean.com/community/articles/how-to-setup-additional-entropy-for-cloud-servers-using-haveged

Re:Hardware RNG for servers and VMs

[steveha]

Entropy Broker: A project to allow one computer to act as a randomness server to others. Could use any actual hardware machine to seed any number of VMs.

See also the comments in the LWN article, where someone with the user name "starlight" simply sends random data over SSH and then the receiving computer uses rngd to mix that data into the entropy pool. Simple, and simple is good.

https://lwn.net/Articles/546428/

http://www.vanheusden.com/entropybroker/

Re:Hardware RNG for servers and VMs

[Anonymous Coward]

Building a HW RNG should be fairly easy if you don't need to worry about attackers with physical access. You don't need too many fancy parts, a noise source such as a grounded box with a spark-gap transmitter and receiver pair, a zener or a CCD, an ADC ($1 in bulk, $2 individually) and an I2C to USB bridge or microcontroller with USB capability. Total cost should be in the $10 range for a megabit/s capable generator. Reading your links this is basically the LavaRnd approach.

Re:Random Post Number

[NotQuiteReal]

To be fair, it is "Offtopic" [sic], however, it IS the 2nd post, and I knew it would be, so why would I have "guessed" first post?

I am also the same guy who won a bet that I could link to my own post in my sig... but I didn't collect because I wouldn't give my PayPal info to some random Slashdot user.

Re:Random Post Number

[Aighearach]

You don't have to give "paypal info" you only have to give an email address; you can just add a throw-away address to your paypal account, and then delete it right after the payment. If there is even something to worry about there. It doesn't have to be the primary address that can be used to gain access to the account.

But you can't trust them

[DrYak]

But you can't trust a single CPU hardware random number generator.

It could pretty well be a simple 128bit counter, encrypted using a good cypher and a password known to an attacker.
(If its a good cypher, the output *will* look like random noise and the cypher should be *next-bit-attack* resistant, so without the password, no way to know that each block is logically following the other).

That's the debate with Linus mentionned in the summary: You could be the guy who actually designs hardware random number generators, you know you design is a good one, you've checked the hardware implementation and you've controlled the mask that was sent to foundry.
Still, unless you own an electronic microscope, there's no way for you to know that a given CPU actually has your design in it, or if at the lest minute a part of the mask was swapped and replaced with the "counter-with-known-password" by the local NSA insider.

You can use the hardware generator as *A* random source, to be mixed with all other sources, in order to produce a finally random result which is a composite of all source (XOR the sources together, then run it through a secure hashfunction or cryptofunction to remove any bias).
But you can't relly on it as the *ONLY SOURCE* of randomness.

At least the VMs could reseed their PRNGs with random values pulled from the Pi.

Thus the VMs should not *RESEED* with value pulled from the Pi. The VMs should use the Pi as one of the several source of entropy mixed to produce random numbers.

DieHard vs. Crypto RNGs

[billstewart]

Yes, Diehard can't tell you if a random number stream is good enough for cryptographic use. But if it tells you that the stream is not good, then it's not good enough for crypto.

Also, while you should use cryptographic whitening techniques for actual crypto use, you shouldn't do that for your Diehard input, because that'll hide any flaws Diehard could have found. There are other kinds of whitening that can make sense (e.g. if you get long runs of the same bit because you're sampling the hardware faster than it changes, you'll want to compress those before doing Diehard.)

Entropy for VMs

[billstewart]

If you don't trust the server not to play with the clock on your VM, you can't trust the server not to steal your data wholesale.

But there really does need to be a mechanism for the server to feed high-quality randomness to the VM, whether it's through a device driver or a well-known address on the box or something, and it needs to be available at or just after boot time on the VM.

There is no "very similar" in crypto

[billstewart]

Yes, the entropy pools could be very similar. But if you're doing anything cryptographically strong, you're going to take the input and run it through a hash function, so on average a one-bit change in the input will change half the bits in the output. If you got the same SSL cert both times, none of the input bits were different.

If your attacker knows the state of your entropy pool when you start, and knows you're only changing a few bits of input, he can model the PRNG's behaviour to try all the different values of those input bits, and probably get lucky about guessing the output.

Mod Parent Up, Please!

[billstewart]

Absolutely correct - you can't trust the hardware if you can't see it. Via and Pi are probably ok; people are rather more paranoid about Intel. Audio hardware can be useful (but you have to be sure what it'll do if there's no microphone plugged in.)

And as far as your signature line goes, it's really annoying how hard it's been to tell headlines in the NYT or WSJ from headlines in The Onion lately, especially about politics.

Radio signals biasing your RNG

[billstewart]

Believe me, if the CIA is beaming high-powered radio signals at your RNG to bias the output, you've got more serious problems than just a good RNG can fix... (What's the frequency, Kenneth?)

OTOH, if a 60 Hz or 120 Hz signal can bias your generator, that's a much different problem.