[tor-bugs] #8106 [Tor]: Make .onion addresses harder to harvest by directory servers

[Tor Bug Tracker & Wiki]

#8106: Make .onion addresses harder to harvest by directory servers
-----------------------------+----------------------------------------------
 Reporter:  asn              |          Owner:                    
     Type:  defect           |         Status:  new               
 Priority:  major            |      Milestone:  Tor: 0.2.5.x-final
Component:  Tor              |        Version:                    
 Keywords:  SponsorZ tor-hs  |         Parent:                    
   Points:                   |   Actualpoints:                    
-----------------------------+----------------------------------------------

Comment(by rransom):

 Replying to [comment:7 asn]:
 > Robert, in the scheme of comment:1, where you use Ed25519 for the
 > discrete-log-based long-term keypair, the HS address (".onion") is
 > supposed to be the Ed25519 public key base32'ed, right?

 I would use the Montgomery-form x coordinate of the public-key group
 element, not the Ed25519 public key format (which consists of the Edwards-
 form y coordinate plus an additional bit specifying the other Edwards
 coordinate's LSB).  (Point-reduced Montgomery form is more convenient for
 single-scalar variable-base multiplication, which is what a client would
 need to do with that group element in order to blind the public key.)

 For an elliptic curve without a secure ‘twist’, the Edwards-form y
 coordinate is probably better.  (The extra bit identifying the other
 coordinate is still unnecessary.)

 > If yes, Ed25519 public keys are 256-bits long, whereas old HS
 > addresses were only 80 base32'ed bits. This means that new HS
 > addresses will be much longer than the old ones, right?

 HS addresses for my protocol over the Curve25519/Ed25519 elliptic curve
 would be 255 bits long (so 51 base32 characters, not 52).  They would be
 longer than the current protocol's addresses, but 80-bit addresses are too
 vulnerable to brute-force attacks to be used in any new protocol (about
 2^80-n^ ‘operations’ to break the first of 2^n^ targets).

 Note that if you want to continue to sacrifice security for usability with
 the new HS protocol, you can use an elliptic curve over a smaller
 coordinate field.  For example, page 16 of
 [http://cr.yp.to/newelliptic/twisted-20080313.pdf] specifies a suitable
 curve over 2^160^ - 47 (32 base32 characters); impersonating any HS over
 that curve would require a discrete-logarithm computation (around 2^80^
 ‘operations’ to impersonate the first HS of any number of targets;
 significantly harder than brute-forcing an 80-bit space).  (There should
 be a good elliptic curve over a convenient 200-bit coordinate field too,
 if you want something in between that and Curve25519.)

 > If the difference is so big, why not just append a symmetric key to
 > the end of the 80-bits that currently get base32'ed?
 >
 > What am I missing here?

 80-bit addresses are no longer long enough to prevent impersonation by
 brute force.

 My protocol is the only one that can be used to prevent HSDir servers from
 linking an HS's descriptors across days (or whatever time periods you
 choose for the new protocol).  (If you want this feature, you'll also have
 to either encrypt HS descriptors or abandon introduction points at ‘day’
 boundaries.  Encrypting the bodies of HS descriptors (everything but the
 expiration time, day number, and serial number) is a good idea anyway.)

 Apart from those reasons, I see several possible protocols that fit your
 description (or are plausible extensions of it) except for the length of
 the public-key hash.  All of them are trickier to implement securely than
 my protocol, and require similar HS address lengths to my protocol for
 similar security levels.

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/8106#comment:8>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online