Tor To Use Distributed RNG To Generate Truly Random Numbers (softpedia.com)

An anonymous reader quotes a report from Softpedia: Tor developers have been working on the next iteration of the Tor network and its underbelly, the Onion routing protocol, in order to create a stronger, harder-to-crack anonymous communications system. To advance the project, the developer team schedules brainstorming and planning meetings at regular intervals. The most recent of these meetings took place last week, in Montreal, Canada. In this session, the team tested the next generation of the Tor network working on top of a revamped Onion protocol that uses a new algorithm for generating random numbers, never before seen on the Internet. The Tor Project says it created something it calls "a distributed RNG" (random number generator) that uses two or more computers to create random numbers and then blends their outputs together into a new random number. The end result is something that's almost impossible to crack without knowing which computers from a network contributed to the final random number, and which entropy each one used. Last week, two University of Texas academics have made a breakthrough in random number generation. The work is theoretical, but could lead to a number of advances in cryptography, scientific polling, and the study of various complex environments such as the climate.

Comments

why is this needed?

[slashmydots]

Why are people still complaining about random numbers? Over 10 years ago I saw a documentary that showed off a quantum photon splitter PCI card that could go in any computer. The API let you generate random numbers based on splitting photons left or right and it was deemed closer to 50% each side than any other randomizing system ever invented. So...what happened to that? Doing quantum tasks with photons is actually relatively easy so the story was believable. I can't think of a better way in the physical universe to generate random numbers. So besides the problem of requiring volunteers running relays to have one of these custom piece of hardware, why don't they attempt to use this solution?

Re: why is this needed?

[slazzy]

They won't fit in a laptop.

Re:why is this needed?

[ledow]

Because paying for cards for every machine in the word, and mandating their use for every transaction from any machine, plus avoiding that device being compromised by a government entity, or turned into a TPM module is difficult enough.

Seriously, imagine if your bank's said, to comply with PCI DSS standards, you had to install this special card in your server.

1) That's enforced server downtime.
2) Most servers are virtual nowadays and not actually physical (and thus you can't guarantee that that "PCI card" your computer sees is even a real PCI card)
3) Are you going to trust a random piece of government- or even bank-mandated hardware in your machine reading the entire memory bus?

Nobody would touch it, even in the server-arena, let alone "every client in the world".

There are already lots of "random number generator" hardwares, everything from white-noise microphones to random instructions inside chips based on quantum noise (now obsolete and nobody really used them, except VIA chips). Nobody touched them. Where it matters, hardware exists to make it happen. Few use it.

Mandating it to every client or even every SSL-using server? Good luck. It just doesn't provide an advantage. Even those places with SSL accelerators (that just offload SSL transactions kind of like a reverse proxy) don't use them.

And the fact is that almost every weakness so far is not in the choice of random numbers but in the way those random numbers are handled later on. Except for embedded boards and no-permanent-state devices (which you should realise shouldn't be used for this kind of thing), filling up the entropy pool on any modern, network connected machine is pretty trivial.

Re: why is this needed?

[Dr_Barnowl]

You don't need special magic entropy cards, there's entropy all around most computers in the form of white noise - just use randomsound. Solves the problem on most laptops because they have a built in mic.

Re:why is this needed?

[fendragon]

For some purposes (and I don't know if this applies to Tor's intended use) I've heard that real physical sources of entropy simply don't generate it fast enough, especially after their output bit rate has been reduced by whitening to remove bias and correlation.

Re: why is this needed?

[zAPPzAPP]

A keyboard is typically on a serial connection (like USB) nowadays which does not produce real hardware interrupts on a key stroke.
Timestamps may be created when the OS detects a keystroke, but that is based on how time is scheduled to the serial connection, the timekeeping process and so on.
It seems likely that there is a certain pattern involved here caused by the OS scheduler that will become visible in time.

Re: why is this needed?

[wbr1]

Not in a laptop. They are still a matrix direct to the mobo.

Re: why is this needed?

[grub]

I'm sure they will have a new USB-C dongle for that.

Re: why is this needed?

[geek]

Entropy is a problem in VM's, especially when they don't have actual devices attached.

Current Opportunity

[andrewbaldwin]

Just use the daily finance / economic forecasts and predictions of the impacts on personal budgets, jobs, immigration.... that are being spouted by both sides of the current BREXIT** debate.

This can be generalised to any politician's promises but the current round are particularly egregious.

** Referendum for UK to leave/remain in the EU

White Noise

[Dr_Barnowl]

I ran into entropy problems when signing a lot of JAR files in a build process - turns out modern computers with their large RAM that caches disk etc don't generate as much entropy as they used to.

The solution I used was the randomsound daemon, which samples white noise from your mic to inject into your entropy pool.

Why not just use that? There's a crapload of white noise in most server rooms, even near most consumer PCs (just tape a mic next to one of the cooling vents). Actual genuine entropy rather than this card-shuffled pseudo entropy - making things complex just obscures things further, it doesn't really create randomness.

Re:pseudo+pseudo=true?

[campuscodi]

What if you do pseudo+pseudo+pseudo+pseudo+pseudo+pseudo+pseudo+pseudo+pseudo+pseudo? The specification doesn't say they must be two sources. They said multiple sources.

Re:pseudo+pseudo=true?

[Anonymous Coward]

That's essentially what they are doing.

By mixing deterministic pseudo-random streams you are never going to get a truly random result. What you will get though is much better quality fake random numbers that are harder to predict and the hope is that this will in turn help the whole system be more resilient to attack.

Re:Time Sync

[Anonymous Coward]

To avoid fingerprinting TOR users. A flurry of NTP sync packets from a single IP address every couple days could light someone up a TOR user.

What TAILS does on boot is request a page from one of many popular websites (facebook, google, etc) then use the HTTP response to get the time. Much more discrete.

They say "never done before" like that's good...

[Anonymous Coward]

In the world of crypto, I'd much rather be using something that's been around long enough to be thoroughly analysed. Every so often someone pops up with something new and exciting and different, then six months later gets shot down by the experts who describe exactly how to break it.

Telling us "even the authors can't predict what will come out of it" doesn't raise my confidence, either. I'd be a lot happier with a statement like "rigorous analysis shows that the random numbers generated will be uniformly distributed", or something like that.

Real crypto work is hard, and random number generation is part of the hard.

Re:pseudo+pseudo=true?

[gweihir]

No. The title is bullshit. This is about generating very hard to predict pseudo-random numbers, because you have to guess a large, distributed state and distributed seeding values.

As there is zero need for "true random" numbers in crypto (you only need "not guessable fro an attacker"), this is still a significant improvement.

Side note: Whenever something "mainstream" reports about random number generation, they get it wrong. It seems that non-experts routinely have no clue what is important here and what not. As for crypto, the philosophical question what "random" means is completely immaterial. Crypto just cares whether an attacker can somehow find out the "random" number or not and how difficult it is if it is possible. There is no need for "true" random numbers anywhere in crypto.

I prefer accelerometer based RNG

[rebelwarlock]

"Shake laptop to generate private key."

The generation of random numbers...

[ameline]

The generation of random numbers is too important to be left to chance.

Re:pseudo+pseudo=true?

[Anonymous Coward]

No, he's right about how RNG mathematics works. A collection of pseudo-randomly generated numbers if merged with the exclusive or operation (XOR) will be no weaker than the strongest single source of pseudo-randomness. On the other hand, it will not be stronger than the strongest single source of pseudo-randomness. The XOR merging is primarily done to make sure that the final number (the one actually used for the later cryptography) is as unpredictable as the least predictable source even when you have no idea which sources are predictable.

What you're thinking of is in the actual encryption stage, where every additional intentional key significantly decreases the security of the encryption, possibly with the creation of accidentally valid decryption keys as well.

Re:pseudo+pseudo=true?

[gweihir]

That is the idea. Although entropy-pools are much more sophisticated than using simple xor for this.

Re:pseudo+pseudo=true?

[gweihir]

An entropy-source is not a point of attack, as long as it is not relied on exclusively. This is a threshold-thing. Get enough good entropy and you are good, no matter how much "bad" entropy you add as well. Fundamental entropy-pool design principle. You really are clueless as to how this works.

Re:pseudo+pseudo=true?

[gweihir]

Indeed. You go from one point of attack to a group, and _all_ have to be attacked successfully for the scheme to be compromised. As long as even one source delivers good entropy, you are secure with a distributed mechanism.

Re:pseudo+pseudo=true?

[gweihir]

Exactly. You add points of attack, but _all_ have to be compromised for the attack to succeed. If, for example, you have one of the compromised Intel CPUs with a bad RDRAND generator (not detectable except with in-dept analysis of the physical chip), then even one other system feeding you good entropy makes you secure again.

Re:pseudo+pseudo=true?

[davidwr]

Whenever something "mainstream" reports about random number generation, they get it wrong.

Not always. Okay, technically, yes, but practically, no:

When I see TV shows that explain the "ping-pong-ball"-type lotteries, where a fan blows a bunch of numbered ping-pong balls around until one "pops out," they do a decent job of stating the obvious: This is about as random as you can get, assuming the ping-pong balls are all equal enough and the air is moving around enough to make any initial conditions (which balls were where before the air started moving) that could be controlled by a human being trying to cheat the system irrelevant.

Of course, we all know that there are minuscule differences in each ping-pong ball and we all know that, except where quantum effects become noticeable, initial conditions DO matter. But the point is that, like the "butterfly effect," a change in initial conditions that is too small for a human cheater to control can radically alter the outcome.

The same goes for TV-explanations of "it's obviously random in every practical sense of the word" things like a fair coin flip, a fair draw of a card from a deck of cards that has been shuffled in a good-but-uncontrolled way many times (i.e. not a "pharaoh shuffle" or other "controlled" shuffle), and the like.