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.]
0. Proposal overview and motivation:
Currently, it is the case that, HSDirs can read the descriptors of the Hidden Services they host. Even if the descriptor was encrypted, HSDirs could still learn the address of the HSes by logging the client directory requests (which contain the hidden service address).
This proposal:
a) Defines cryptographic procedures to be followed by Tor clients and hidden services to allow HS address antienumeration.
b) Defines a new descriptor format which hides the descriptor content from entities who don't know the public key of the HS.
c) Changes the size (and semantics) of Hidden Service addresses.
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!
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).
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-term public key).
A client that knows the <z>.onion address and wants to acquire the HS descriptor, derives the <ephemeral public key> of the HS by using <z> and the same key derivation procedure that the HS uses. She also derives the symmetric key that decrypts the encrypted HS descriptor (#DESCFETCH).
The client then contacts the appropriate HSDir and inquires for the descriptor with index <ephemeral public key>. If the HSDir has such an index in its internal map, it passes the <metadescriptor> to the client (#DESCFETCH).
The client then verifies the signature of the metadescriptor, and if it's legit she decrypts the encrypted descriptor with the symmetric key. The client now has the Hidden Servide descriptor she was so looking for (#DESCDECRYPTION).
4. Security proof
XXX A security proof of the above scheme is under development. We are not going to implement or deploy anything before we have a solid proof of this.
5. Changes to the current HS protocol
5.0. Related proposals
This proposal is supposed to be applied on top of the "Migrate HS identity keys to Ed25519" proposal.
5.1. Ephemeral keypair derivation (#KEYPAIRDERIVATION)
XXX Leaving this unpsecified for now till the security proof comes along.
For now, let's assume that after this paragraph each HS has a per-TIME_PERIOD ephemeral keypair. It also has a symmetric key derived from the ephemeral public key (maybe even the hash of the ephemeral public key) to encrypt its descriptor.
Let's also assume that each client can generate the ephemeral public key of a HS given only its long-term public key (and knowledge of the current time-dependent nonce).
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.
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?
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.3. Metadescriptor fetching (#DESCFETCH)
A client that knows the long-term public key (onion address) of a hidden service can derive the ephemeral public key and the ephemeral symmetric key as specified in section 5.1.
A client that wants to fetch the metadescriptor of an HS, does an HTTP 'GET' request to the appropriate directory server asking for "/tor/rendezvous3/<z>" where <z> is the ephemeral public key of the HS.
# XXX should this get its own URI, even though we assume that these two proposals will be implemented and deployed simultaneously?
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.
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?
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 ?
Refs:
[0]: https://lists.torproject.org/pipermail/tor-dev/2012-September/004026.html . [1]: https://trac.torproject.org/projects/tor/ticket/8106
I'm posting the draft of a proposal that specifies how to hide HS descriptors and addresses from the hidden service directories. ... HSDirs could still learn the address of the HSes by logging the client directory requests (which contain the hidden service address). ... 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.
It is known there is a de-anon paper regarding HS, that is a separate weakness.
But the above words about HSDirs having plaintext access to any plaintext or decodeable '.onion' string (whether via the descriptor or request argument) is, as far as I know in current operation, being consistently and badly misdated, to the point of causing confusion, even in the above paper.
In current rend-spec.txt we have Sec 1.3, v2 descriptors are used post 0.2.2.1-alpha, specifically...
descriptor-id = H(permanent-id | H(time-period | descriptor-cookie | replica))
???
On Fri, Aug 16, 2013 at 5:10 PM, grarpamp grarpamp@gmail.com wrote:
In current rend-spec.txt we have Sec 1.3, v2 descriptors are used post 0.2.2.1-alpha, specifically...
descriptor-id = H(permanent-id | H(time-period | descriptor-cookie | replica))
Isn't the permanent-key field, described in that same section, the long term public key of the hidden service? I believe it is (unless stealth auth is used), and if it is, it's trivial to learn the .onion address given a hidden service descriptor.
(It can apparently be different when the "Stealth auth" feature from section 2.2 is in place, but I don't believe that's widely used, and it isn't an answer to the enumeration issue.)
cheers,
Isn't the permanent-key field, described in that same section, the long term public key of the hidden service? I believe it is (unless
Oops! Turns out I've glossed that as H(perm key) (which would be useless to a client) for well over a year. Makes some projects more interesting though. Anyway, will now read the rest of this proposal in shame. Thanks.
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.]
...
- 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!
- Parameters
TIME_PERIOD is XXX
- 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.
- 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?
On 17.08.2013 07:34, Matthew Finkel wrote:
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?
Y64?
"Y64 is a base64 variant used at Yahoo! when base64 information needs to be transmitted as part of a GET request. Regular base64 has three characters that aren’t URL-safe: plus (+), slash (/), and equals (=). Y64 encoding replaces these with dot (.), underscore (_), and dash (-), respectively."
Or would case sensitivity be too crazy?
On Sat, Aug 17, 2013 at 1:51 AM, Moritz Bartl moritz@torservers.net wrote:
mfrggzdfmztwq2lknnwg23tpobyxe43uov3ho6dzpjaueq2eivda.onion ?
characters that aren’t URL-safe: plus (+), slash (/), and equals (=). Y64 encoding replaces these with dot (.), underscore (_), and dash (-),
Or would case sensitivity be too crazy?
I think about DNS - Aka non-tor-internal implementations of it in onionland. Although dns has grown up nearer to a binary db, it was insensitive and with a narrow character range and length. Things from client app to local resolver to DNS server may be affected. / - %2F in URI, but it does cause problems when various software apps choose to write that filesystem reserved character to disk un-escaped, or send it to web that way. Functions - That they exist in Python, Perl, etc to convert this to/from hex/binary/etc. 16chars - Not 100% easy to memorize, so [even very] longer may not be a huge problem... see i2p, freenet, gnunet, etc. OnionCat/IPv6 - But extending beyond 80 bits facing will break this I think. I've seen some proposal on zzz.i2p for this re: their >80 bits.
On Fri, Aug 16, 2013 at 10:31 AM, George Kadianakis desnacked@riseup.net wrote:
As before: let me know when there's something you should I should give a number.
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.]
- Proposal overview and motivation:
Currently, it is the case that, HSDirs can read the descriptors of the Hidden Services they host. Even if the descriptor was encrypted, HSDirs could still learn the address of the HSes by logging the client directory requests (which contain the hidden service address).
This proposal:
a) Defines cryptographic procedures to be followed by Tor clients and hidden services to allow HS address antienumeration.
b) Defines a new descriptor format which hides the descriptor content from entities who don't know the public key of the HS.
c) Changes the size (and semantics) of Hidden Service addresses.
To be fair, the other proposal would need to do that too.
- 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!
One more: Christian Grothoff told me in Garching that GNUnet does something quite similar for its keys. So we should probably check out their approach too, and include them in the "related work" section of any hypothetical publication here. :)
- Parameters
TIME_PERIOD is XXX
- 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.
See also the not-entirely-baked "stealth authentication" approach in the current hidden service design.
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)
Derived from the _permanent_ public key, surely? The ephemeral one is the one attackers know.
and sign the ciphertext andthe 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).
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-term public key).
We should discuss the referer problem here, and make sure there's a good solution.
The design should allow an additional out-of-band key that doesn't appear in the URL.
A client that knows the <z>.onion address and wants to acquire the HS descriptor, derives the <ephemeral public key> of the HS by using <z> and the same key derivation procedure that the HS uses. She also derives the symmetric key that decrypts the encrypted HS descriptor (#DESCFETCH).
The client then contacts the appropriate HSDir and inquires for the descriptor with index <ephemeral public key>. If the HSDir has such an index in its internal map, it passes the <metadescriptor> to the client (#DESCFETCH).
The client then verifies the signature of the metadescriptor, and if it's legit she decrypts the encrypted descriptor with the symmetric key. The client now has the Hidden Servide descriptor she was so looking for (#DESCDECRYPTION).
- Security proof
XXX A security proof of the above scheme is under development. We are not going to implement or deploy anything before we have a solid proof of this.
- Changes to the current HS protocol
5.0. Related proposals
This proposal is supposed to be applied on top of the "Migrate HS identity keys to Ed25519" proposal.5.1. Ephemeral keypair derivation (#KEYPAIRDERIVATION)
XXX Leaving this unpsecified for now till the security proof comes along. For now, let's assume that after this paragraph each HS has a per-TIME_PERIOD ephemeral keypair. It also has a symmetric key derived from the ephemeral public key (maybe even the hash of the ephemeral public key) to encrypt its descriptor. Let's also assume that each client can generate the ephemeral public key of a HS given only its long-term public key (and knowledge of the current time-dependent nonce).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.
This also needs a publication date and/or expiry indicator, so that HSDirs know how long to hold them.
"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-----".
How is this symmetric key derived, exactly? What format does the encryption take? (Also, the encryption should probably have a MAC on it.)
"signature" NL signature [At end, exactly once] A signature of all fields above with the ephemeral private key of the hidden service.
As before, let me suggest that all of this take a format analogous to that used in proposal 220.
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? 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.3. Metadescriptor fetching (#DESCFETCH)
A client that knows the long-term public key (onion address) of a hidden service can derive the ephemeral public key and the ephemeral symmetric key as specified in section 5.1. A client that wants to fetch the metadescriptor of an HS, does an HTTP 'GET' request to the appropriate directory server asking for "/tor/rendezvous3/<z>" where <z> is the ephemeral public key of the HS. # XXX should this get its own URI, even though we assume that these two proposals will be implemented and deployed simultaneously?
I suggest that we deploy _only_ the format in this proposal. Is that what you meant?
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.
- 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?
Probably!
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 ?
That's okay with me.
(The migration proposal is sure going to be interesting, isn't it?)
One more thing to think about here: any design here should think about HSDir prediction resistance, as in https://trac.torproject.org/projects/tor/ticket/8244 )
yrs,
-
George Kadianakis -
grarpamp -
Matthew Finkel -
Moritz Bartl -
Nick Mathewson