[tor-dev] prop224: zero bits in addresses

[teor]

Hi all,

At the Montreal hidden service hackfest, we discussed another scheme shortening prop224 .onion addresses.
The only drawback is that it's exponentially difficult, so it can only chop off a few characters.

I'm describing it here because it has other useful properties, and can be used as:
1) an address versioning scheme, and/or
2) a configurable proof-of-work threshold for generating valid addresses.

The basic scheme works like this: (those of you familiar with bitcoin might recognise it)
A) Valid .onion address hashes must start with a certain, hard-coded number of 0 bits, followed by a 1 bit.
(We include the 1 bit, so that addresses with additional 0 bits can be used by a later version of the protocol.)
B) When generating a private key, the hidden service must discard any keys that yield .onion addresses that don't fit this bit pattern.
C) When creating a textual .onion address, Tor removes the hard-coded bits from the address.
D) When parsing a textual .onion address, Tor adds the hard-coded bits from the address.

Otherwise, the protocol proceeds as it would in prop224.

This kind of scheme is mentioned as a TODO in the existing proposal:
   [TODO: Alternatively, we could require that the first bit of the
   master key always be zero, and use a 51-byte encoding. Or we could
   require that the first two bits be zero, and use a 51-byte encoding
   and reserve the first bit. Or we could require that the first nine
   bits, or ten bits be zero, etc.]

In my very basic tests using Yawning's horse25519 on a laptop, it seems that 15 bits takes less than a second, but 20 bits can take from a few seconds to around a minute. Prop 224 .onion addresses already have 4 unused bits, so we could easily chop off 3-4 characters using this scheme, with only a small amount of computation the first time the hidden service runs.

Without a scheme like this, it's possible to generate hundreds of thousands of valid .onion addresses per minute on most recent processors. I'm not sure if this is a problem or not.

So we have to decide whether the added complexity is worth having addresses that are 3-4 characters shorter.
I'm not sure that it is, unless we like the idea of making it harder to generate valid .onion addresses, or unless we want to allow for extensible future versioning of .onion addresses, beyond the existing 4 unused bits.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B
ricochet:ekmygaiu4rzgsk6n
xmmp: teor at torproject dot org





-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160802/6e6d2fb4/attachment.sig>