3

https://facebookcorewwwi.onion/

The idea is that the Facebook onion address connects you to Facebook's Core WWW Infrastructure - check the URL again, you'll see what we did there - and it reflects one benefit of accessing Facebook this way: that it provides end-to-end communication, from your browser directly into a Facebook datacentre.

(emphasis mine)

It looks like facebook was able to generate exactly the url they wanted to generate.

Does this mean that, with massive resources comparable to those of facebook, it's possible to generate a collision with an existing hidden service?

3

No, and yes.

Facebook, hidden services, and https certs had talked on this. Facebook in fact brute forced only the first 40 bits and then made a backronym.

Their hidden service name is "facebookcorewwwi.onion". For a hash of a public key, that sure doesn't look random. Many people have been wondering how they brute forced the entire name.

The short answer is that for the first half of it ("facebook"), which is only 40 bits, they generated keys over and over until they got some keys whose first 40 bits of the hash matched the string they wanted.

Then they had some keys whose name started with "facebook", and they looked at the second half of each of them to pick out the ones with pronouncable and thus memorable syllables. The "corewwwi" 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 start with "facebook" and end with pronouncable syllables, but that's not brute forcing all of the hidden service name (all 80 bits).

However, when facing a really strong adversary, 80 bits is not enough. A high-end GPU (like a GTX 1080) can yield a hash rate at about 4 GHash/s, and specially designed ASICs go far beyond this. (See https://github.com/lachesis/scallion#speed--performance for more.) Although the public key generation would slow down the hash rate, an attacker with enough resource is able to achieve a few PHash/s, at which a full collision becomes feasible.

And there is another caveat. Partial collisions are also useful. Assuming you are not always memorizing the full address, an attacker could just mess up your memory and get you to visit their fake HS.

  • There's a slight problem with your math, you can't just hash any value and get a legitimate .onion. It needs to be the hash of a valid 1024bit RSA key. Generating large primes and doing bignum mathematics for every hash also limits the speed at which you can generate values to hash. While I agree that 80bits is low, and onion-ng should fix that, it's not quite as easy as just getting an 80bit pre-image collision (which is itself more difficult than just getting an 80bit collision of two arbitrary keys). – cacahuatl Aug 4 '17 at 18:52
  • I've used a similar method to generate keys like facebooks on a (not very powerful) laptop, e.g.: dearopqflamelord.onion and zymefamepearbere.onion and a whole host of others. – cacahuatl Aug 4 '17 at 18:53
  • @canonizingironize Yes, generating big prime numbers seems to be the bottleneck of brute forcing. But an attacker can go faster than shallot or something else by not checking for some algebraic properties of the generated keypair - who cares if a fake website is insecure? – nobody Aug 5 '17 at 2:35
  • I took a look at shallot and scallion. They use a fairly efficient way to generate keypairs (generating a lot of $e$ for one $n$) and the CPU part can be even faster. – nobody Aug 5 '17 at 14:57
  • Isn't that unbelievably lucky that they were able to find an onion url with all letters, including "www" and "core"? – pinhead Apr 26 '18 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.