Tor To Use Distributed RNG To Generate Truly Random Numbers (softpedia.com) 130
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.
Re: (Score:1)
and how can you know that the one generated on a computer that is not your own is not malicious?
and, no - i have not rtfa yet. gotta go to work.
Re: (Score:1)
Get data from one or more sources + your own local data.. put then thru a sha.
Add to this that the sources you used may be one or more hops away from you, and all data has been encrypted each hop it made..
To figure out what random-number you used they would have to:
1. Figure out from what sources you got the data (or somehow be able to inject the data, how that now would be done since it's the client that decides where to fetch it from)
2. Figure out what order you merged the data received from multiple host
Re: (Score:3)
Re: (Score:2, Insightful)
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: (Score:2)
Re:pseudo+pseudo=true? (Score:5, Informative)
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.
Re: (Score:1)
Nailed it. If you are an expert on 3 topics, and note that the media seems curiously incompetent when reporting on those three topics, but then flip the page to topics you are not as expert about- why would you assume the quality of the reporting got better? I remember reading a bunch of stories about video games back in the day, that got details wrong like crazy. Why would they get international politics correct if they can't even report on a fucking video game properly?
Re: (Score:1)
It's kind of the opposite of an improvement. Now the localized task of generating a random number for crypto operations will be distributed to unknown peers, almost certain to be chosen by some kind of obscure network architecture that if documented at all outside of code will simply provide an avenue of attack (manipulating network load, other machines on the network, etc) outside of what was previously possible.
Actually as long as you also generate a random number yourself, and just xor everything together, it still can't be worse than what they're doing now.
Re: (Score:3)
That is the idea. Although entropy-pools are much more sophisticated than using simple xor for this.
Re: (Score:2, Insightful)
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 n
Re: (Score:2)
What you're thinking of is in the actual encryption stage
Possibly. Talk about incompetence coupled with arrogance. Dunning-Kruger at work.
Re: (Score:2)
> On the other hand, it will not be stronger than the strongest single source of pseudo-randomness.
This seems very unintuitive. If I have a stream where every 5th bit is predictably zero, and a stream where every 7th bit is predictably one, then the second stream is the more random of the two. If I xor them together, then every 35th bit is predictably zero, but my resultant stream seems much more random than either of the two originally, right? I could predict 1/7th of the data originally, and now I c
Re: (Score:3)
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: (Score:3)
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: (Score:3)
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: (Score:2)
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 t
Re: (Score:2)
Can two pseudo random numbers actually be combined to give a truly random number?
LOL, no.
I'm no mathematician, but I'm pretty sure there's no such thing as 'true random numbers'. I think the closest we can come is the Quantum Random Bit Generator [random.irb.hr] from some years ago.
Re: (Score:2, Interesting)
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.
Re: (Score:1)
The packets sent over TOR should be encrypted, such that they cannot be ascertained to be of a specific protocol to someone not using TOR. If you are referring within the TOR network, then using UNIX time or UTC (i.e. something without timezone information) should provide no identifying information in addition to TOR masking the external IP address of anyone more than 1 hop away from you.
It is my understanding that IP addresses within the TOR network are not necessarily chartable to physical location in th
why is this needed? (Score:5, Interesting)
Re: why is this needed? (Score:3)
Re: why is this needed? (Score:4)
You don't need special magic entropy cards, there's entropy all around most computers in the form of white noise - just use randomsound [ubuntu.com]. Solves the problem on most laptops because they have a built in mic.
Re: (Score:1)
Are you a Markov chain by any chance?
No, it's just a poor RNG.
Re: (Score:1)
Sure there's entropy in the natural environment. Problem is you have no idea how much. What looks random to you might have been carefully crafted by the enemy. Trusting the environment is a really, really bad idea in cryptography.
Re: why is this needed? (Score:5, Insightful)
Entropy is a problem in VM's, especially when they don't have actual devices attached.
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
Re: (Score:2)
What about people running TOR nodes on computers that cant use one of these cards for whatever reason?
Re: why is this needed? (Score:1)
People all learned to type on the same keyboard layouts, so have we have very predictable biases when it comes to hitting keys.
Even if that wasn't the case humans just can not generate true randomess to save their lives. You could randomly remap the layout every time you mash the keys and you'd still produce preditable output.
These "generate entropy by wiggling" exercises are weak and only used if a proper RNG is otherwise not available.
Re: (Score:2)
It's still MUCH slower than background noise from a microphone or thermal noise from a resistor, but at least it uses hardware that's al
Re: (Score:3)
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: (Score:3)
Re:why is this needed? (Score:4, Insightful)
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: (Score:2)
There's no reason to buy a separate card though, most modern cpus have builtin hardware rng [wikipedia.org].
Re: (Score:1)
That are black-boxes without any information given from the manufacturer of how it does it..
But sure, those are useful as *one* of the sources of data you feed to the PRNG you run.. The more sources the better... If one source is "corrupt" it does not make the whole PRNG to fail..
Re: (Score:2)
When your processor is compromised, everything is compromised. If you believe your cpu is malicious, the rng is the least of your worries. Guess what, your "secure" prng also runs on the cpu.
Re: (Score:1)
That's not even theoretically true.
It is additional hardware (Score:2)
Re: (Score:3)
Re: (Score:2)
These things are unworkable in practice. Too expensive, too unreliable and nobody wants to pay for them. OS support is typically lacking as well.
Re: (Score:2)
Note: I am not associated with the Tor project, just an interested observer. I happen to be implementing a similar protocol for something else.
Because it needs to be resistant to compromised nodes. The reason for this that hidden service connection details (though not the server IP obviously, since all of this happens through Tor channels) are stored in directory servers which are randomly assigned each day. The choices of directory server are derived from a pseudo-random string [1] [torproject.org]
Current Opportunity (Score:5, Funny)
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 (Score:4, Interesting)
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 [ubuntu.com] 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: (Score:2)
I suppose one argument against is that any white noise from a device not designed to generate pure white noise could be baised in some way and while this wouldn't make it predictable it could narrow its range of truly random values.
However I agree that its still better than the pseudo random stuff we use now. Its not like an analogue white noise generator would be hard to build and include in a CPU which could then be A->D'd by the chip and an instantanious value made available via a register.
Re: (Score:2)
I do not know why they would have to be precisely matched but semiconductor junctions have more excess noise and less stringent requirements for amplification and measuring the differential noise while rejecting external common mode influences applies just as well to them. With a resistance based noise source, you have to be careful that you are not actually measuring the voltage or current noise of the amplifier and if you are going to do that, then you do not need the resistance based source.
Re: (Score:2)
I would think that in a modern world, that sound is one of the most predictable sets one can choose from. Our world is filled with white noise that is actually cyclic in nature, which produces random noise, but with very little variation, which makes the sample set much smaller than you would think. This is why sound engineers can filter ambient sounds from audio to isolate the actual sounds they want to hear.
My guess, is that the best way to generate truly random numbers is to combine several sources toget
Re: (Score:2)
And then you have a machine with a digital input that is actually fed digital music. And, oops, you are screwed. The problem here is that for one user that knows what he is doing, this is fine. As a general solution, this falls flat on its face. The actual solution would be something like the Intel RDRAND instruction, but unfortunately that is a compromised design that you cannot trust. ("Compromised Design" means they can swap out the actual secure implementation for a compromised one and the design preven
Re: (Score:2)
Virtualized platforms also have a hard time with entropy, as their hardware is emulated.
There are several daemons you can use, eg. haveged or randomsound, or entropyd. You can also use network broadcast traffic to seed entropy (can't recall how at the moment), and various other sources. What's needed, I think, is a means to source all of these to generate entropy so this becomes less of a problem.
I can just see (Score:1)
Someone putting a number of RNG systems onto TOR so they control providing the "random" number.
They say "never done before" like that's good... (Score:2, Insightful)
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 di
Get off my Lawn (Score:1)
I prefer accelerometer based RNG (Score:4, Funny)
Distributed RNG? (Score:2)
What the hell is a distributed ranger?
Sent from FF XI.
Re: (Score:2)
A distributed ranger is one what was left sitting on a railroad crossing until a freight train arrived.
The generation of random numbers... (Score:3)
I sorta did this in the 1980s (Score:2)
Re: (Score:2)
... I had them roll a die and tell me the result. Then I flipped a coin. Heads, their die roll stood. Tails I used 7 minus their die roll (we were playing Traveller, which only used d6), which inverted the result of their roll. They got the satisfaction of controlling their own fate by rolling their own dice, and I was satisfied there was no cheating going on.
While this solved the immediate problem of being able to trust the players, it fails to provide any guarantee to the players that you aren't cheating when it comes to the coin-flip. You know their dice roll before you report the coin result, so you could easily manipulate the outcome (to an extent; you can only choose between N and 7-N).
I'm not quite sure how to reduce this to something you could easily do by hand, but there is a way around this issue when computers are involved. Instead of a dice roll, gen
Re: (Score:2)
GM = God. It doesn't matter if God cheats.
Re: (Score:2)
GM = God. It doesn't matter if God cheats.
Then why bother with the players' input at all? Just have the GM choose the result. While the GM may be the ultimate authority, the players clearly do care about the GM's ability to influence the result, or they would just let the GM roll the dice for them.
Anyway, the principle is applicable to situations other than role-playing games where it is important that neither side has the ability to cheat. For example, online blockchain-based lottery systems like SatoshiDice are based on a similar principle, with
Re: (Score:2)
Cryptography can be used to generate shared random numbers for multiple parties.
https://en.wikipedia.org/wiki/... [wikipedia.org]
THERE IS NO SUCH THING AS RANDOM (Score:1)
And you should care why
Yes, just like ALL philosophical questions, isn't that right?
We just need to get our job done and then EVERYTHING is just fine! We don't have to worry about anything else, ever. Curiosity killed the cat. Blinders on, job done, life good. This is how our ancestors went from common apes to homo sapiens. And anyway, what makes it doesn't keep it!
Or you could not be fucking retarded.
It may be tempting to go with the fl
Hardware RNG is like 50 bucks (Score:2)
Hardware RNGs are like 50 bucks. Wikipedia even has a compare page, and you can go higher if you need to. It is unusual to need a shockingly large amount of random bits to begin with, after all.
https://en.wikipedia.org/wiki/... [wikipedia.org]
So this TOR thing is nice, especially because computers baseline can generate psuedorandom numbers pretty darned quickly, and merging them is better than not merging them. But if you, personally, care, using a hardware RNG and having it seed and combine with your prng (such as Linu
From TFA (Score:2)
No shit Sherlock. No devs of any RNG should be able to predict the output when it's in the deployed. And Tor devs is not a team of Avengers.
seems unnecessary (Score:2)
People keep talking about getting the "perfect" random number. Since when is the random number the weakest link in security?
Just throw some mouse, keyboard, microphone input into your pseudorandom number generator, and it's impractical to break.
government assistance (Score:1)