Opened 2 years ago

Closed 21 months ago

#18191 closed defect (invalid)

.onion name collision

Reported by: cypherpunks Owned by:
Priority: Very High Milestone:
Component: Core Tor/Tor Version:
Severity: Critical Keywords:
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

The output of SHA1 has a length of 160 bit. To make handling the URLs more convenient we only use the first half of the hash, so 80 bit remain. Taking advantage of the ​Birthday Attack, entropy can be reduced to 40 bit. That's why collisions could be found with moderate means. This is not a problem for Tor since all an attacker might be able to do is create two different public keys that match the same .onion name. He would not be able to impersonate already existing hidden services.

Why he would not be able? As I know, there is no built-in way to authenticate a HS if there is a collision: the legit and fake HSes will be indistinguishable from each other.

Child Tickets

Change History (7)

comment:1 Changed 2 years ago by teor

Resolution: duplicate
Status: newclosed

This is addresses in proposal #224 by extending the length of hidden service addresses.
Until then, collisions are possible, but unlikely.

comment:2 Changed 2 years ago by cypherpunks

Priority: MediumImmediate
Severity: NormalBlocker

Until then, collisions are possible, but unlikely.

LOL. If anyone can generate human-readable .onion address with desired beginning/ending on an ordinary PC, then NSA can generate a key corresponding to any existing .onion address (which is 32*32 much effort). It is not unlikely, if the NSA wants to make MiTM on specific .onion sites (I'm sure they want), because they can afford ASICs for this and I'm sure they already have an FPGA-based bruteforcer (it can be no harder than a masterthesis).

comment:3 Changed 2 years ago by nickm

It would be helpful to understand the difference between a collision and a second preimage.

comment:4 Changed 23 months ago by cypherpunks

Priority: ImmediateVery High
Resolution: duplicate
Severity: BlockerCritical
Status: closedreopened

This is not a problem for Tor since all an attacker might be able to do is create two different public keys that match the same .onion name. He would not be able to impersonate already existing hidden services.

Why not, is the public key cached somewhere? Does there take some kind of decentralized registration of hidden services take place?

I find this highly unlikely because Hidden services can be created instantly and thousands are created each month (?)
In order to cache or register every public key you'd need quite some disk space.

Please don't just close this without proper explanation!

And simply use (way) more than 80 bits, and a different hash algorithm.

Last edited 23 months ago by cypherpunks (previous) (diff)

comment:5 in reply to:  4 Changed 23 months ago by teor

Replying to cypherpunks:

This is not a problem for Tor since all an attacker might be able to do is create two different public keys that match the same .onion name. He would not be able to impersonate already existing hidden services.

Why not, is the public key cached somewhere? Does there take some kind of decentralized registration of hidden services take place?

I think the quote is subtly wrong in at least two ways. And since you didn't source it, that makes it hard for me to work out if the context explains it better. But I'm not going to follow it up, as we're working on a replacement right now.

Here's the first mistake:
The address is a hash of the public key. The public key is included in the hidden service descriptor. The public key matches the private key for the hidden service. But the public key is looked up by address. So a limited form of impersonation is possible in clients without cached descriptors.

Here's the second mistake:
A birthday attack only gives you a collision (one match in the output) not a second preimage (the input that produces a specific output match).

I find this highly unlikely because Hidden services can be created instantly and thousands are created each month (?)
In order to cache or register every public key you'd need quite some disk space.

Indeed. You should read up on the distributed hidden service hash ring.
https://gitweb.torproject.org/torspec.git/tree/rend-spec.txt

Please don't just close this without proper explanation!

You may need to do some further reading to understand the explanations that we're giving you.

And simply use (way) more than 80 bits, and a different hash algorithm.

Yes, here is the proposal to do just that:
https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.txt
We're implementing it right now.

comment:6 Changed 22 months ago by cypherpunks

Thanks for your explanation, and great to see progress being made on Hidden services!

comment:7 Changed 21 months ago by cypherpunks

Resolution: invalid
Status: reopenedclosed

cypherpunks, you misunderstand the difference between a preimage and collision attack. A preimage attack involves creating input which hashes to the same output as a target, such as trying to generate your own HS key that is valid for facebookcorewwwi.onion. A collision attack involves starting from scratch and creating two inputs which hash to the same output, but an output you cannot control. You don't get to choose which two private keys will collide, so you can't "target" an existing address. Tor HSes provide 80 bits of preimage resistance and 40 bits of collision resistance. All proper n-sized cryptographic hash functions provide n bits of preimage resistance, and n/2 bits of collision resistance.

It's still a good idea to increase the size of HS addresses (as prop224 will do) because 80 bits of preimage resistance, while not bad, is not something that should be relied upon when faced with a billion dollar budget.

You shouldn't re-open a closed ticket just because you don't understand the reasons behind it closing. Explain why it should not be closed (in this case, it should be) before re-opening it right away.

Note: See TracTickets for help on using tickets.