[cabfpub] Ballot 144 -.onion domains

[Tom Ritter]

On 13 February 2015 at 11:18, Gervase Markham <gerv at mozilla.org> wrote:
> On 13/02/15 17:12, Tom Ritter wrote:
>> No, I think it is correct.  And yes, a well-resourced adversary.  I
>> think I've seen estimates that the bitcoin network as a whole turns
>> over 2^80 in some reasonable amount of time; government agencies; a
>> very large botnet; someone at Google gets bored ;)
>
> 2^80 CPU cycles, hashes, or keypair generations? I estimated keypair
> generation at 1000 cycles, but it could be more expensive than that.

Alright, let me do some handwaving and back-of-the-envelope
calculations.  Bitcoin network appears to be at about 300,000 Trillion
hashes/second, and a hash is ~64 cycles, we'll use a key gen as 1000
cycles so a keypair is 15 times as difficult.

(pow(2,80) * 15) / (300000 * pow(2,40)) / 3600 / 24 / 365.25 =
1.7412731006160165 years

In another expression, the bitcoin network is at 4048030.71 petaflops,
which was more than the top 500 public supercomputers in the world
combined. Except that's not accurate because it was in 2013 when
bitcoin was even smaller. [0]

So if you controlled the entire bitcoin network (HAH!), and my back of
the envelope handwaving is roughly correct, you could collide a .onion
address in about a year, year and a half.  If you were Google, and you
had the _best_ super computer in the world, it would take you
(4048030.71 * 1000) / 54902.4 = ~73,731 times longer[1].  So I came
out to be a little more than Gerv (1,000 years vs my 73,000) but
either way we're not talking something trivial.

Like I said - this is much weaker than we want for our cryptosystems.
But it's not so weak that it's practically exploitable today or in the
next couple years. If we're still using it in 2 years I'll be very
disappointed.  And unlike the internet, it is actually much easier to
upgrade the whole Tor network in a relative short timespan (6
months-year).

-tom

[0] http://www.forbes.com/sites/reuvencohen/2013/11/28/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined/
[1]http://www.top500.org/lists/2014/11/