> 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.

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.

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.

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.

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 is not vulnerable to brute-force nor rainbow tables.

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 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.