Hacker News Reader

Comment by nocarrier | Hacker News Reader

Alec Muffet has done a lot of work to get Facebook running on TOR and he's a true believer. I really enjoyed working with him when I was at Facebook. He also did a lot of work to get .onion domains to be recognized by registrars as a special purpose domain name. This let us issue certificates on .onion.

I don't know if the story behind the facebookcorewwwi.onion domain name itself has been talked about much, but we wanted a memorable name for the domain so we took a new cluster that hadn't been put in production yet and threw something like 500k cores at brute forcing onion names till we had a memorable domain name. Alec had a script that looked for hashes that started with facebook and then he picked the one that seemed to fit the most. And that's how we have facebookcorewwwi.onion now.

View on HN

It took me only 24 hours and about $200-300 in compute to hit Blockchains hidden server key which is:

blockchainbdgpzk.onion

I'm pretty sure it's the second most trafficked site after FB

If anyone is looking at setting up a hidden service and wants a memorable name I still have the cluster setup.

Matching 10 characters isn't much of a challenge - it's why hidden service addressed on their own don't provide identity authentication and why we both went with SSL cents for Tor hidden services (provided by Digicert - who have been great advocates for the cause)

if you don't mind me asking, how many cores / what cloud service did you use to compute that?

Sorry I missed your reply - I was using AWS G1 insances (on the spot market) plus my own password cracking cluster (the old one had 6 ATi cards, building a new one now)

That's really interesting. Are you able to tell us how long those 500k cores were running for before the facebookcorewwwi.onion name was found?

We generated many candidates beginning with facebook, so I don't recall when that one was found--it just happened to be the one that looked the best. There's a number of backup memorable domains that we kept the keypairs for just in case facebookcorewwwi gets compromised somehow.

I don't remember how long we ran it for, but IIRC we had enough candidates to stop after a week or two. I'm guessing something like 100-200M cpu hours?

Thanks for sharing! I'm now curious to know what the energy bill came to and whether it would make it to the list of most expensive domain names[1].

[1] https://en.wikipedia.org/wiki/List_of_most_expensive_domain_...

100M...200M core h, 10 W/core, 50 $/MWh and we get 50k...100k $.

It's awesome we live in a world where we can throw 100-200 million cpu hours at something of a whim.

That each of those cores are billions of times faster than my first PC just puts the icing on the cake.

FWIW, we ran it on and off for about a month IIRC, as the cluster was put through its paces prior to going live. I also seem to remember Matt Jones doing a minor tweak to the scallion code to speed things up as well...

I don't understand quite, why so much brute force?

The onion-name is a hash of the public key the service uses, so you can't just pick a name and use it. They had to try many keypairs to find some that hashed to "facebook...." (Normally you generate your key and just use whatever name that hashes to, but it's cool to have one that's easy to remember)

The name of .onion address is the hash of a public key, so you can't choose it, or rather the only way is to generate random public and private key pairs and to keep the one that interest you.

Facebook must have generated an awful lot of key pairs to get "facebookcorewwwi". By the way, I hope they deleted the other generated pairs…

I have good faith that they didn't, or certainly not all of them. When Alex described the entire process they went through, he also smirked that should that primary key ever get compromised they have several others, almost as good, ready as drop-in replacements.

I do think he also mentioned that they only cared about keys that had their required prefix; all others were destroyed without anyone ever having access to them.

> I do think he also mentioned that they only cared about keys that had their required prefix; all others were destroyed without anyone ever having access to them.

Okay, that is what I was implying would be terrible otherwise. But actually it is quite obvious that they would not spend the disk space necessary the keep every single generated key pairs now that I think about it.

How would that be terrible?

The number of generated key pair to find "facebook" + keywords must have been gigantic, maybe even so much that it could be used as a kind of rainbow table which would allow people (or three letters agencies) who can access it to attack hidden services that use one of the .onion for which a corresponding private key is known.

This is not vulnerable to brute-force nor rainbow tables.

Relative to the 2^80 (1,208,925,819,614,629,174,706,176) possible onion addresses, whatever they generated would be miniscule.

Indeed. I was being stupid and didn't take the time to really think it through. Thanks to you and all the others who pointed that out :).

Presumably those 3 letter agencies also have the technology to generate RSA keys.

That shouldn't matter. If the scheme is vulnerable when some company generates a bunch of keys, it is vulnerable whether those keys are deleted or not.

If that is indeed tractable for a side project at Facebook over a few weeks, it's definitely tractable for someone who actually cares to attack Tor.

If I understand correctly finding an "equally good" domain name starting with facebook<something> should be equally possible yes.

Finding that same one again? Not likely.

This was a huge discussion on the Tor blog or subreddit. It was concluded that it is unlikely that they even found one existing key.

Nope. They ran a cluster to generate billions of addresses, and used some logic to find a nice one. But that won't help them a bit to find a specific address, since all the addresses they generated are only a vanishingly small fraction of the possible addresses.

If the key hash did not have facebook as the first eight characters it did not even get passed up to the aggregator and was instantly discarded.

Onion names are sort of public keys. You generate a secret key, then that's transformed/hashed into the public key that is your onion address.

Since onion addresses are essentially random strings of a certain length, the only way to get a "vanity" onion address is to brute force it.

Also, if I'm not mistaken, this means that if YOU can brute force a vanity domain, anyone else willing to throw down the same amount of computing power can perform the same brute force and discover your private key, taking over your onion site?

Edit: probably wrong, see below

Normally you brute force vanity addresses by having a range of acceptable outcomes, whereas to brute force a specific vanity address* you are only targetting a single outcome.

So they might have just set it to filter for facebook[dictionaryword]+ and this was the best match.

* Actually any address, it's not limited to brute forcing vanity addresses.

I guess I incorrectly assumed the process would be repeatable, but now I see that getting a specific duplicate equals bruteforcing the entire key space - even if the prefix is a chosen vanity name. I confused it with the effort of getting a similar address where just the vanity prefix needs to match.

It requires substantially more compute power to match "facebookcorewwwi" vs just finding a hash with a prefix of "facebook" that looks readable. Good luck hashing the remaining eight characters!

Well, it would just take twice as long as hashing the first 8... /s

I realize that was sarcasm.

But for the non-hash-aware among us, it would take on average 2,147,483,647 as long to brute force the last 8 with the same computing power and 4,294,967,295 as long to hash every combination of the last 8. This all assumes no vulnerabilities in the algorithm, of course.

It's base32, not base16, so you're off by several orders of magnitude - numbers should be 549,755,813,888 and 1,099,511,627,776.

I believe you are correct. I appreciate the correction.

Sure. The same is true for anything that uses public key encryption (Bitcoin for one). But the amount of computing power needed doesn't exist.

According to this person's math [1]: "It would take ~6.7e40 times longer than the age of the universe to exhaust half of the keyspace of a AES-256 key"

I don't know if Tor uses AES-256, but I'm sure any reasonable encryption algorithm would be similar.

[1] https://www.reddit.com/r/theydidthemath/comments/1x50xl/time...

The energy calculation assumes the computation is irreversible. If you use reversible computing, there is no lower bound: you can compute as much as you want for as little energy as you want.

The time calculation assumes our current computers and disregards Moore's law.

You have to create the algorithm to reverse an arbitrary AES-256 key, which is considered to be impossible, so that doesn't really make a difference. Your comment about current computers fails to grasp the scale that we are talking about here:

> It would take 10^38 Tianhe-2 Supercomputers running for the entirety of the existence of everything to exhaust half of the keyspace of a AES-256 key.

Let's assume that Moore's law is true for forever. In 300 years we will have a super computer capable of cracking a single AES-256 key in 37 millennium. However claiming that Moore's law will stay the same for 300 years when many think it won't last 30 is foolhardy.

>You have to create the algorithm to reverse an arbitrary AES-256 key, which is considered to be impossible, so that doesn't really make a difference.

What? Why is brute force impossible to code? I don't understand what you're claiming.

I agree that adding in Moore's law doesn't change the numbers by much. Moore's law plus weakening of cryptographic assumptions might do it, though. Plenty of previously-believed-to-be-strong crypto algorithms have been cracked, it's reasonable to think that we just don't have the tools to create unbreakable codes yet. (E.g. RSA is known to be breakable with quantum computers with Shor's algorithm.)

Shores algorithm doesn't break anything. It just reduces the key space. Considering the major increase in energy costs and major lag in computational power of quantum computing, shores algorithm won't be a threat to today's crypto for hundreds of years to come.

It reduces key space for most symmetric algorithms, but completely breaks RSA and ECC making them run in polynomial time.

> What? Why is brute force impossible to code? I don't understand what you're claiming.

You claim that a reversible algorithm takes zero time. I said that requires a reversible algorithm that applies to an arbitrary AES-256 key which is currently thought to be impossible.

Brute forcing is not breaking but instead simply enumerating the key space and is subject to the slow downs we are talking about here.

> I agree that adding in Moore's law doesn't change the numbers by much. Moore's law plus weakening of cryptographic assumptions might do it, though. Plenty of previously-believed-to-be-strong crypto algorithms have been cracked, it's reasonable to think that we just don't have the tools to create unbreakable codes yet. (E.g. RSA is known to be breakable with quantum computers with Shor's algorithm.)

But you are missing the point of cryptographic systems, the goal typically isn't to be forever uncrackable, it is to be effectively forever uncrackable which includes upgrading the strength of your cryptography over time.

If we were talking about cracking crypto within 100 years then maybe we could talk about reasonable fear, but all of these things involve timelines that are longer than that (including quantum computer work).

>You claim that a reversible algorithm takes zero time.

No, you misread my comment. Reversible computing can take almost no energy.

.onion addresses are just 80 bits, not 256. Someone estimated[1] that the amount of work to brute force one address is approximately the same as the amount of hashing that has been computed by the bitcoin network up to now, so it's clearly not physically impossible. This weakness is apparently a practical problem, because it made people unwilling to automatically issue SSL certificates for .onion addresses [2].

[1] https://news.ycombinator.com/item?id=11388997 [2] https://blog.cloudflare.com/the-trouble-with-tor/

The third part on the Tor project's blog at https://blog.torproject.org/blog/facebook-hidden-services-an... describes this well.

Check out mapgrep's comment on another thread below for a more in depth answer, too.

Onion domains are just an encoding of a hash of a public key. To get a memorable name, you have to find a keypair that hashes to some letters you want. There is no correlation between any of the characters, so you have to do an exhaustive search to find nice strings.

Because it happened in the past with a hashing algorithm that isn't resistant to getting faster as time progresses.

I remember this was talked about by a group at Ohio Linuxfest a couple years ago and also went into IP load balancing at scale. Really neat work being done there.

> This let us issue certificates on .onion.

Isn't TOR encrypted up to a hidden service anyway? Why would you HTTPS over TOR? Honest Question.

Probably authentication of server, but client still remains anonymous.

That's true. Exit nodes do not play a role in hidden services. But, Rendezvous point does. So, If your node somehow selected as rendezvous point for meeting, then you could possibly sniff the traffic.

This is incorrect, exit nodes are not involved with hidden services.

Edit: the original comment I replied to stated that exit nodes could sniff traffic.

Reply to new comment:

The connection is encrypted to the service's public key, what are you talking about? Stop spreading nonsense and go read documentation.

They cant. That is the whole concept behind the word "onion" that they cant.

It is encrypted, but when you're going to facebookcorewwwi.onion you only know that you're connecting to server that knows the corresponding private key, of which "facebookcorewwwi" is a hash. Which is already good. However, seeing EV certificate on this domain also shows you that the corresponding private key for HTTPS connection is signed by a certificate authority: that is, if you trust this CA, you can pretty much trust that you're connecting to Facebook, Inc.

To add on that explenation, EV is about identity. Its what should differential someone pretending to be facebook using facebookcorewwwl.com and the real entity. Its less about encryption and keys, and more about a CA claiming to have looked at the companies registration papers and other government official documents and thus confirmed their identity.

Reply on news.ycombinator.com