Re: [tor-talk] Facebook brute forcing hidden services

[Roger Dingledine <arma@xxxxxxx>]

On Fri, Oct 31, 2014 at 12:23:02PM +0000, Mike Cardwell wrote:
> https://www.facebook.com/notes/protect-the-graph/making-connections-to-facebook-more-secure/1526085754298237
> 
> So Facebook have managed to brute force a hidden service key for:
> 
> http://facebookcorewwwi.onion/ 
> 
> If they have the resources to do that, what's to stop them brute
> forcing a key for any other existing hidden service?

I talked to them about this. The short answer is that they did the vanity
name thing for the first half of it ("facebook"), which is only 40 bits
so it's possible to generate keys over and over until you get some keys
whose first 40 bits of the hash match the string you want.

Then they had some keys whose name started with "facebook", and they
looked at the second half of each of them to decide which one they thought
would be most memorable for the second half of the name as well. This
one looked best to them -- meaning they could come up with a story about
why that's a reasonable name for Facebook to use -- so they went with it.

So to be clear, they would not be able to produce exactly this name
again if they wanted to. They could produce other hashes that started
with "facebook", but that's not brute forcing all of the hidden
service name (all 80 bits).

For those who want to explore the math more, read about the "birthday
attack":
https://en.wikipedia.org/wiki/Birthday_attack

And for those who want to learn more (please help!) about the improvements
we'd like to make for hidden services, including stronger keys and
stronger names see,
https://blog.torproject.org/blog/hidden-services-need-some-love

--Roger

-- 
tor-talk mailing list - tor-talk@xxxxxxxxxxxxxxxxxxxx
To unsubscribe or change other settings go to
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk