[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:  normal           |      Milestone:     
Component:  Tor              |        Version:     
 Keywords:  SponsorZ tor-hs  |         Parent:     
   Points:                   |   Actualpoints:     
-----------------------------+----------------------------------------------

Comment(by rransom):

 Replying to [ticket:8106 asn]:

 > On actual solutions, Robert posted:
 > https://lists.torproject.org/pipermail/tor-
 dev/2012-September/004026.html
 > some months ago. I don't have the cryptographic skills to robustly
 analyze his idea, but if this is the only thing we have, we should point
 some cryptographers at it so that it gets some comments.

 For an Ed25519-based signature scheme with both the public-key group
 element and the base point blinded, the verification equation is
 equivalent to `S*B = (HB(nonce, B, A)^(-1))*R + H(R, HB(nonce, B, A)*B,
 HB(nonce, B, A)*A, M)*A`, where `R` is carefully chosen to be a uniform
 random group element and `HB(nonce, B, A)` is (computationally)
 independent of `R`.  This equation does not leak any more information
 about the log of `A` than the verification equation for unmodified Ed25519
 does, so this cryptosystem is obviously as safe as Ed25519.

 (My original proposal (only blind the public-key group element (`A` in
 Ed25519)) would have had a different, potentially leakier, verification
 equation.)


 > Are there any other proposed solutions out there? If not, this might be
 a fun research problem.

 Tor's hidden service protocol requires a cryptosystem with the following
 properties:
  * a keypair generation function keygen: RNG -> (PubKey, PrivKey);
  * a blinding function blindPub: (PubKey, BlindingNonce) -> BlindedPubKey;
  * a signing function sign: (RNG, PrivKey, PubKey, BlindingNonce, Message)
 -> Signature;
  * a signature-verification function verify: (RNG, BlindedPubKey, Message,
 Signature) -> Bool;
  * blindPub cannot be inverted, even by an attacker who knows the
 BlindingNonce value passed to it;
  * the output distributions of blindPub for different public keys are
 indistinguishable, even when BlindingNonce is known; and
  * signature forgery is infeasible (under the usual definition of security
 for a signature system, where (PubKey, BlindingNonce) is the type of
 public keys and (PrivKey, BlindingNonce) is the type of private keys (this
 implies security against forgery by someone who only knows
 BlindedPubKey)).

 (This is equivalent to a pair of signature schemes A and B, with a pair of
 blinding functions (A.PubKey, BlindingNonce) -> B.PubKey and (RNG,
 A.PrivKey, BlindingNonce) -> B.PrivKey, but specifying the properties that
 this pair of blinding functions needs would be more annoying.)


 The obvious ways to blind RSA-like and McEliece-like public keys allow an
 attacker to link different blinded versions of the same original public
 key.  It ''might'' be possible to blind public keys for multivariate-
 quadratic or Alekhnovich-type cryptosystems, but there's enough structure
 in MQ keys that I would expect to see linkability issues, and if there are
 suitable signature schemes based on the LPN-like problems, they won't be
 as well-understood as discrete-log-based signatures.  So, for now, any
 cryptosystem that solves this problem will look a lot like my (revised)
 proposal (unless someone comes up with a screwy pairing-based version that
 provides lower security and lower performance).

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