[cabfpub] Ballot 144 -.onion domains

[kirk_hall at trendmicro.com]

Terrific calculations, Tom -- but I'm wondering how hard it was for Facebook to get their multiple .onion domains that included "facebook".

Yes, I'm concerned about the possibility of an exact clash, but I'm also concerned about the ability of a hacker to get a .onion domain that includes names commonly sought by hackers.  Perhaps Tor limit final .onion domains to random letters and numbers using the same pattern scanning methods that CAs use.

-----Original Message-----
From: Tom Ritter [mailto:tom at ritter.vg] 
Sent: Friday, February 13, 2015 9:40 AM
To: Gervase Markham
Cc: Kirk Hall (RD-US); Jeremy Rowley (jeremy.rowley at digicert.com); Ben Wilson (Ben.Wilson at digicert.com); CABFPub (public at cabforum.org)
Subject: Re: [cabfpub] Ballot 144 -.onion domains

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/
<table class="TM_EMAIL_NOTICE"><tr><td><pre>
TREND MICRO EMAIL NOTICE
The information contained in this email and any attachments is confidential 
and may be subject to copyright or other intellectual property protection. 
If you are not the intended recipient, you are not authorized to use or 
disclose this information, and we request that you notify us by reply mail or
telephone and delete the original message from your mail system.
</pre></td></tr></table>