[tor-dev] Draft of proposal "Stop HS address enumeration by HSDirs"

[Matthew Finkel]

Greetings Sir,

On Fri, Aug 16, 2013 at 05:31:33PM +0300, George Kadianakis wrote:
> Greetz,
> 
> I'm posting the draft of a proposal that specifies how to hide HS
> descriptors and addresses from the hidden service directories.
> 
> This proposal is supposed to go along with the proposal that specifies
> how to upgrade HS identity keys to use Ed25519. I posted that proposal
> some seconds ago.
> 
> This proposal (like the other one) is incredibly drafty in the sense
> that I might have forgotten to specify things that need to be
> specified. On the other hand, "release early; release often" they say,
> so here it goes.
> 
> Inlining:
> 

> Filename: xxx-onion-antienumeration-hsdirs.txt
> Title: Stop HS address enumeration by HSDirs
> Author: George Kadianakis
> Created: 16 August 2013
> Target: 0.2.5.x
> Status: Draft
> 
>                                          [More draft than Guiness.]
... 
> 1. Acknowledgments
> 
>   The cryptography behind this proposal was originally proposed by
>   Robert Ransom in a private email threadi and subsequently posted in
>   tor-dev [0]. Discussion was continued in trac ticket #8106 [1].
> 
>   During the past 6 months many bright people have looked at the
>   cryptography behind this scheme. The list of people includes Nadia
>   Heninger, Leonid Reyzin, Nick Hopper, Aggelos Kiayias, Tanja Lange,
>   Dan J. Bernstein and probably others that I can't recall at this
>   point. Thanks!
> 

Diito!

> 2. Parameters
> 
>   TIME_PERIOD is XXX
> 
> 3. Scheme overview
> 
>   Currently, Hidden Services upload their unencrypted descriptor to
>   hidden service directories (HSDirs). HSDirs store the unencrypted
>   descriptor in an internal map of: <hs address> -> <hs descriptor>
>   When a client wants the descriptor of an HS, it asks an HSDir for
>   the descriptor that corresponds to <hs address>. If the HSDir has
>   such an index in its map, it returns the <hs descriptor> to the
>   client.
> 
>   This proposal asks Hidden Services, to periodically derive a new
>   ephemeral keypair from its long-term identity key; the new keypair
>   is a function of the identity key and a time-dependent nonce. The
>   derivation should be one-way; if you know the identity key you
>   should be able to derive the ephemeral key, but not the other way
>   around. Finally, a client should be able to derive the ephemeral HS
>   public key from the long-term HS public key without knowing the
>   long-term HS private key (#KEYPAIRDERIVATION)
> 
>   Hidden Services then encrypt their descriptor with a symmetric key
>   (derived from the ephemeral public key) and sign the ciphertext and
>   the ephemeral public key with their ephemeral private key. Then they
>   place the ephemeral public key, the encrypted descriptor and the
>   signature in a "metadescriptor" document (#METADESC) and send it to
>   the HSDir (#DESCPUBLISH).
> 

Just for clarification, this will not be optional, correct? This is not
the a one-to-one placement for "stealth" auth-type?

>   The HSDir validates the signature of the "metadescriptor", and if
>   it's legit it stores the metadescriptor in an internal map of:
>   <ephemeral public key> -> <metadescriptor> .
>   (#DESCPUBLISH)
> 
>   Now, out of band, the HS gives to its clients a <z>.onion
>   address. <z> in this case is the long-term public key of the HS
>   (this is different from the current situation where <z> is the hash
>   of the long-tptycherm public key).

(tptycherm? Is this another Greek word that is not in my vocabulary? :)

 
> 5.2. HS descriptor publishing
> 
> 5.2.1. Metadescriptor format (#METADESC)
> 
>     The format of the metadescriptor that is uploaded to the HSDir is:
> 
>       "ephemeral-public-key" NL public-key
> 
>         [At start, exactly once]
> 
>         The ephemeral public key for this time period in base64 encoding.
> 
>       "encrypted-descriptor" NL encrypted-descriptor
> 
>         [Exactly once]
> 
>         An encrypted v3 hidden service descriptor (as specified in
>         xxx-hs-ecc-id-keys.txt). It's encrypted using the ephemeral
>         symmetric key of the HS, encoded in base64 and surrounded with
>         "-----BEGIN MESSAGE-----" and "-----END MESSAGE-----".
> 
>       "signature" NL signature
> 
>        [At end, exactly once]
> 
>        A signature of all fields above with the ephemeral private key
>        of the hidden service.

When you say "with the ephemeral private key", do you mean that this is
signed by that key?

> 
> 5.2.2. Metadescriptor publishing (#DESCPUBLISH)
> 
>     The metadescriptor specified above is published to the appropriate
>     HSDir by sending an HTTP 'POST' request to
>     "/tor/rendezvous3/publish" as specified in the "Migrate HS
>     identity keys to Ed25519" proposal.
> 
>     # XXX should this get its own URI, even though we assume that these
>     two proposals will be implemented and deployed simultaneously?
> 

I think because the two proposals will be combined when they're accepted
and implemented this should be fine. Perhaps this may confuse someone in
10 or 20 years when they read this prop, but maye a simple comment
stating that this section overrides section 3.2.1 in
xxx-hs-ecc-id-keys.txt might work.

>     Upon receiving a descriptor, the directory server checks the
>     signature, and discards the descriptor if the signature does not
>     match the enclosed public key. If the signature matches, the
>     directory server saves the descriptor in a map of:
>     <ephemeral-public-key> -> <metadescriptor>.
> 
... 
> 5.4. Metadescriptor decryption (#DESCDECRYPTION)
> 
>     The client then verifies the signature of the metadescriptor, and
>     discards it if it doesn't match the ephemeral public key that was
>     previously derived.
> 
>     If the signature matches, the client uses the derived ephemeral
>     symmetric key to decrypt the 'encrypted-descriptor' part of the
>     metadescriptor.
> 

Presently, HSDirs check the timestamp in the descriptor. Should this be
something clients do now? The only reason I think this may be
useful is to prevent replays, but it really depends on the validity
time period for a descriptor and the value of TIME_PERIOD. 

> 6. Discussion
> 
>   [Points here might deserve their own sections]
> 
>   Do we need the HSDir hash ring, even though the HS address and the
>   descriptor are now hidden from HSDirs?
> 

Do we have a better alternative? Should we also consider a different
architecture than two-sets-of-three-servers? Also, if we discuss this
then we'll need to revisit how a client determines which HSDir to ask.

>   An ed25519 public key is 32 bytes. 32 bytes in base32 encoding is 56
>   characters (or 52 with the '=' padding removed). Do we want a
>   different URL encoding or are we happy with addresses like:
>   mfrggzdfmztwq2lknnwg23tpobyxe43uov3ho6dzpjaueq2eivda.onion ?

What was the other encoding that Dan tested? Was that one shorter but
with crazier characters, maybe?