[tor-dev] Discussion on the crypto migration plan of the identity keys of Hidden Services

[George Kadianakis]

> George Kadianakis:
>> Thoughts?
>
> Can you make .onion domains really long and therefor really safe against
> brute force?
>

Oh. That reminded me of a topic I forgot to insert in my original post.

An onion address is the truncated (80 bits) hash of the public identity
key of a Hidden Service. This means that onion addresses currently provide
80-bits of self-authentication security.

An attacker who wants to impersonate a Hidden Service can start generating
RSA-1024 keypairs till she finds a public key that when hashed has the
same 80-bits prefix as the hash of the public key of the Hidden Service
she wants to impersonate. If she finds such a colliding public key, and
manages to give her own descriptor to the client instead of the descriptor
of the original hidden service, she can effectively impersonate that
hidden service.

While this is not an apparent threat at the moment, it would be a good
idea to make onions more resistant to impersonation attacks in the future.
The hash is currently truncated to 80-bits (16 characters of base32)
because that's arguably a convenient sized string to pass around verbally
or to write to a piece of paper or to graffiti on a wall.

If we move to the higher security of (e.g.) 128-bits, the base32 string
suddenly becomes 26 characters. Is that still conveniently sized to pass
around, or should we admit that we failed this goal and we are free to
crank up the security to 256-bits (output size of sha-256) which is a 52
character string?

I'm not sure myself. I guess it depends on the security properties of the
other primitives we select.

> Or have an option for maximum key length and a weaker default if common
> CPU's are still too slow? I mean, if you want to make 2048 bit keys the
> default because you feel most hidden services have CPU's which are too
> slow for 4096 bit keys, then use 2048 bit as default with an option to
> use the max. of 4096 bit.
>
> Bonus point: Can you make the new implementation support less painful
> updates (anyone or everyone) when the next update will be required?
> (forward compatibility)
>

I was also trying to think of a solution to this problem, but I failed.
You need some kind of scheme that allows Hidden Services to eventually
migrate to other identity keypairs without changing their onion -- and the
onion should still be able to act as an identifier for all those
as-yet-unknown identity keypairs. I would be surprised if there is an
elegant solution to this problem, but cryptography tends to surprise me.

A non-elegant solution might involve the Hidden Service having a long-term
signing keypair that is stored offline, and with that keypair it signs its
future identity keypairs (similarly to how PGP subkeys and master keys
work). The onion in this case would be the hash of the long-term public
key, and in the HS descriptors we would include the long-term public key,
the current public identity key and a signature of the public identity key
using the long-term key. This might work, but it's stupid, tiring (both
for the implementors and the hidden service operators) and doesn't go well
with schemes like https://trac.torproject.org/projects/tor/ticket/8106 .