[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):

 Here is ‘pseudocode’ (actually, ready-to-compile code written in a not-
 yet-implemented programming language) specifying exactly how to implement
 my signature scheme.

 {{{
 PrivKey = struct {
   a: Exponent;
   messageKeySecret: byte[32];
 };
 PubKey = struct {
   A: GroupElement;
 };
 BlindingNonce = byte[32];
 BlindedPubKey = struct {
   Bprime: GroupElement;
   Aprime: GroupElement;
 };
 Message = byte[];
 Signature = struct {
   R: GroupElement;
   s: Exponent;
 };

 B: GroupElement;

 keygen = procedure(): (PubKey, PrivKey) {
   priv := PrivKey{
     a = hashToExponent(generateRandomBytes(64)),
     messageKeySecret = generateRandomBytes(32)
   };
   pub := PubKey{
     A = scalarmult(priv.a, B)
   };
   return (pub, priv);
 };

 blindPub = procedure(pub: PubKey; nonce: BlindingNonce): BlindedPubKey {
   blindingExponent := HB(nonce, B, pub.A);
   return BlindedPubKey{
     Bprime = scalarmult(blindingExponent,     B),
     Aprime = scalarmult(blindingExponent, pub.A)
   };
 };

 sign = procedure(priv: PrivKey; pub: PubKey; nonce: BlindingNonce;
                  msg: Message): Signature {

   blindedPub := blindPub(pub, nonce);

   r := hashToExponent(H(priv.messageKeySecret, nonce, msg));
   R := scalarmult(r, blindedPub.Bprime);

   messageHash := H(groupElementToBytes(R),
                    groupElementToBytes(blindedPub.Bprime),
                    groupElementToBytes(blindedPub.Aprime),
                    msg);

   s := r + (hashToExponent(messageHash) * priv.a);

   return Signature{R = R, s = s};
 };

 verify = procedure(blindedPub: BlindedPubKey,
                    msg: Message, sig: Signature): Bool {

   messageHash := H(groupElementToBytes(sig.R),
                    groupElementToBytes(blindedPub.Bprime),
                    groupElementToBytes(blindedPub.Aprime),
                    msg);

   verificationEqLHS := scalarmult(sig.s, blindedPub.Bprime);
   verificationEqRHS := sig.R + scalarmult(hashToExponent(messageHash),
                                           blindedPub.Aprime);

   return (verificationEqLHS == verificationEqRHS);
 };
 }}}

 `sig.s` is computed in almost exactly the same way as Ed25519's `S`; the
 only change is in what is hashed along with the message.  (I've used a
 lowercase `s` here instead of Ed25519's uppercase `S` so that it won't be
 mistaken for a group element.)

 There is no need to skip Ed25519's multiplication of both sides of the
 verification equation by 8; I omitted it here (and in my post above) for
 the sake of clarity.

 To prove that the verification equation for this signature scheme leaks no
 more information about the secret key than Ed25519's verification
 equation, divide both sides of it by `blindingExponent` and divide the
 definition of `sig.R` by `blindingExponent`.  (The verification equation
 is '''equivalent to''' the equation I posted above.)

 Also note that the blinded public key contains the blinded base point; the
 attacker does not get to choose the base point separately from the blinded
 public-key group element.

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