Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Since the attacker has control over when the weighted die is added in this case (an on/off switch that includes it once in every 6 rolls, but we don't know how many rolls it takes to "use" it), yes, you can.

Roll the die with it "off" a few billion times. You now have a very-consistent prediction about the range and probability of each value. Throw the switch to "on", roll a few times until you're sure it has been used up, then turn it off. Repeat a few billion times. Since the computation finishes at some point, the weighted die's influence will exist most-strongly at the beginning.

You're left with a crap-ton of random-ish fluctuations that over time shows a slight bias to being larger at the start (compared to "off"), after you turned it on. Since you know it's included once every 6 times (I'm assuming random here, to make it harder), it will be the distribution for 1/6th the size of the weighted value (or something similar, I forget exactly). If it wasn't randomly included, then you should see spikes every 6th round.

--

Note that this does not require knowing that you had dice at all, nor knowing how many, nor knowing that there is always a 6, 12, and 24 sided die in the mix and 2 dozen others. If you knew that, you could be more confident about what a normal distribution looked like, so you could finish earlier.



No. The attacker has control over what time period, not how many rolls.

You don't have the level of control you think. You are assuming that you will know exactly. When in truth you will only know approximately.

The human analogy falls down because we are slow. But with computers you would be controlling it from a distance, and latency would mean you wouldn't know exactly when.


Latency is just another bit of randomness. There have already been examples of using latency across the internet to extract encryption keys because e.g. someone didn't compare the checksum to the entire string and simply stopped once it was clear it wasn't valid. That's detecting nanosecond differences across a hundred-millisecond extremely noisy channel.

Besides, if you can get the output, you can tell how many rolls occurred, so it doesn't really matter. And this is a "chosen cyphertext" example, so the attacker has some idea of how long the computation will take under certain circumstances.




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

Search: