123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963 |
- Filename: 114-distributed-storage.txt
- Title: Distributed Storage for Tor Hidden Service Descriptors
- Version: $Revision$
- Last-Modified: $Date$
- Author: Karsten Loesing
- Created: 13-May-2007
- Status: Open
- Change history:
- 13-May-2007 Initial proposal
- 14-May-2007 Added changes suggested by Lasse Øverlier
- 30-May-2007 Changed descriptor format, key length discussion, typos
- 09-Jul-2007 Incorporated suggestions by Roger, added status of specification
- and implementation for upcoming GSoC mid-term evaluation
- 11-Aug-2007 Updated implementation statuses, included non-consecutive
- replication to descriptor format
- Overview:
- The basic idea of this proposal is to distribute the tasks of storing and
- serving hidden service descriptors from currently three authoritative
- directory nodes among a large subset of all onion routers. The three
- reasons to do this are better robustness (availability), better
- scalability, and improved security properties. Further,
- this proposal suggests changes to the hidden service descriptor format to
- prevent new security threats coming from decentralization and to gain even
- better security properties.
-
- Motivation:
- The current design of hidden services exhibits the following performance and
- security problems:
- First, the three hidden service authoritative directories constitute a
- performance bottleneck in the system. The directory nodes are responsible for
- storing and serving all hidden service descriptors. At the moment there are
- about 1000 descriptors at a time, but this number is assumed to increase in
- the future. Further, there is no replication protocol for descriptors between
- the three directory nodes, so that hidden services must ensure the
- availability of their descriptors by manually publishing them on all
- directory nodes. Whenever a fourth or fifth hidden service authoritative
- directory is added, hidden services will need to maintain an equally
- increasing number of replicas. These scalability issues have an impact on the
- current usage of hidden services and put an even higher burden on the
- development of new kinds of applications for hidden services that might
- require storing even more descriptors.
- Second, besides posing a limitation to scalability, storing all hidden
- service descriptors on three directory nodes also constitutes a security
- risk. The directory node operators could easily analyze the publish and fetch
- requests to derive information on service activity and usage and read the
- descriptor contents to determine which onion routers work as introduction
- points for a given hidden service and need to be attacked or threatened to
- shut it down. Furthermore, the contents of a hidden service descriptor offer
- only minimal security properties to the hidden service. Whoever gets aware of
- the service ID can easily find out whether the service is active at the
- moment and which introduction points it has. This applies to (former)
- clients, (former) introduction points, and of course to the directory nodes.
- It requires only to request the descriptor for the given service ID, which
- can be performed by anyone anonymously.
- This proposal suggests two major changes to approach the described
- performance and security problems:
- The first change affects the storage location for hidden service descriptors.
- Descriptors are distributed among a large subset of all onion routers instead
- of three fixed directory nodes. Each storing node is responsible for a subset
- of descriptors for a limited time only. It is not able to choose which
- descriptors it stores at a certain time, because this is determined by its
- onion ID which is hard to change frequently and in time (only routers which
- are stable for a given time are accepted as storing nodes). In order to
- resist single node failures and untrustworthy nodes, descriptors are
- replicated among a certain number of storing nodes. A first replication
- protocol makes sure that descriptors don't get lost when the node population
- changes; therefore, a storing node periodically requests the descriptors from
- its siblings. A second replication protocol distributes descriptors among
- non-consecutive nodes of the ID ring to prevent a group of adversaries from
- generating new onion keys until they have consecutive IDs to create a 'black
- hole' in the ring and make random services unavailable. Connections to
- storing nodes are established by extending existing circuits by one hop to
- the storing node. This also ensures that contents are encrypted. The effect
- of this first change is that the probability that a single node operator
- learns about a certain hidden service is very small and that it is very hard
- to track a service over time, even when it collaborates with other node
- operators.
-
- The second change concerns the content of hidden service descriptors.
- Obviously, security problems cannot be solved only by decentralizing storage;
- in fact, they could also get worse if done without caution. At first, a
- descriptor ID needs to change periodically in order to be stored on changing
- nodes over time. Next, the descriptor ID needs to be computable only for the
- service's clients, but should be unpredictable for all other nodes. Further,
- the storing node needs to be able to verify that the hidden service is the
- true originator of the descriptor with the given ID even though it is not a
- client. Finally, a storing node should learn as little information as
- necessary by storing a descriptor, because it might not be as trustworthy as
- a directory node; for example it does not need to know the list of
- introduction points. Therefore, a second key is applied that is only known to
- the hidden service provider and its clients and that is not included in the
- descriptor. It is used to calculate descriptor IDs and to encrypt the
- introduction points. This second key can either be given to all clients
- together with the hidden service ID, or to a group or a single client as
- an authentication token. In the future this second key could be the result of
- some key agreement protocol between the hidden service and one or more
- clients. A new text-based format is proposed for descriptors instead of an
- extension of the existing binary format for reasons of future extensibility.
- Design:
- The proposed design is described by the required changes to the current
- design. These requirements are grouped by content, rather than by affected
- specification documents or code files, and numbered for reference below.
- Hidden service clients, servers, and directories:
- /1/ Create routing list
- All participants can filter the consensus status document received from the
- directory authorities to one routing list containing only those servers
- that store and serve hidden service descriptors and which are running for
- at least 24 hours. A participant only trusts its own routing list and never
- learns about routing information from other parties.
- - rend-spec.txt, section 1.4: Added description of how to obtain a routing
- list of hidden service directories.
- - routerparse.c: Changed routerstatus_parse_entry_from_string to parse the
- "HSDir" flag in vote and consensus status documents.
- - routerlist.c: Changed router_get_routerlist() to initialize routing list.
- - or.h: Added hs_dirs member to routerlist_t.
- - Changed routerlist_free() to free storage held by routing list.
- - Added UPDATE_HS_DIRS_INTERVAL.
- - Added update_hs_dir_routing_table().
- - Changed run_scheduled_events().
- - Added is_hs_dir member to routerstatus_t.
-
- [Aug 11: Specified and running.]
- /2/ Determine responsible hidden service directory
- All participants can determine the hidden service directory that is
- responsible for storing and serving a given ID, as well as the hidden
- service directories that replicate its content. Every hidden service
- directory is responsible for the descriptor IDs in the interval from
- its predecessor, exclusive, to its own ID, inclusive. Further, a hidden
- service directory holds replicas for its n predecessors, where n denotes
- the number of consecutive replicas. (requires /1/)
-
- - rend-spec.txt, section 1.4: Added description of how to determine the
- responsible node(s) for a given descriptor ID.
- - routerlist.c: Added get_responsible_hs_dirs() to determine the routers
- that are responsible for a given descriptor ID.
-
- - Added is_hs_dir member to routerstatus_t.
- - Added have_enough_hs_dirs().
- - Added next_hs_dir().
-
- [July 9: Specified and running.]
-
- Hidden service clients and providers:
- /3/ Send tunneled HTTP request to hidden service directory in BEGIN_DIR cell
- - rend-spec.txt, section 1.4: Added the requirement that requests need to
- be sent via Tor.
- - rend-spec.txt, section 1.6: Added the requirement that requests need to
- be sent via Tor.
- [July 9: Pending]
- Hidden service directory nodes:
- /4/ Process tunneled HTTP request in BEGIN_DIR cell
- - rend-spec.txt, section 3.2: Added the requirement that requests need to
- be contained within BEGIN_DIR cells.
- - rend-spec.txt, section 3.3: Added the requirement that requests need to
- be contained within BEGIN_DIR cells.
-
- [July 9: Pending]
-
- /5/ Advertise hidden service directory functionality
- Every onion router that has its directory port open can decide whether it
- wants to store and serve hidden service descriptors by setting a new config
- option "HSDir" 0|1 to 1. An onion router with this config option being set
- includes the flag "hidden-service-dir" in its router descriptors that it
- sends to directory authorities.
- - tor.1.in: Added the config option HSDir.
- - dir-spec.txt, section 2.1: Added the flag hidden-service-dir to the
- router descriptor format.
- - rend-spec.txt, section 3.1: Added process of configuring a hidden service
- directory.
- - router.c: Changed router_dump_router_to_string() to include the
- hidden-service-dir flag in a router descriptor if configured.
- - or.h: Added HSDir to or_options_t.
- - config.c: Added config option HSDir.
- [July 9: Specified and running.]
-
- /6/ Accept v2 publish requests, parse and store v2 descriptors
- Hidden service directory nodes accept publish requests for hidden service
- descriptors and store them to their local memory. (It is not necessary to
- make descriptors persistent, because after disconnecting, the onion router
- would not be accepted as storing node anyway, because it has not been
- running for at least 24 hours.) All requests and replies are formatted as
- HTTP messages. Requests are directed to the router's directory port and are
- contained within BEGIN_DIR cells. A hidden service directory node stores a
- descriptor only when it thinks that it is responsible for storing that
- descriptor based on its own routing table. Every hidden service directory
- node is responsible for the descriptor IDs in the interval of its n-th
- predecessor in the ID circle up to its own ID (n denotes the number of
- consecutive replicas). (requires /1/ and /4/)
- - rend-spec.txt, section 1.2: Added the new v2 hidden service descriptor
- format.
- - rend-spec.txt, section 3.2: Added the acceptance of v2 publish requests.
- - routerparse.c: Added rend_parse_v2_service_descriptor() to parse a v2
- hidden service descriptor.
- - routerparse.c: Added desc_token_table[] to parse v2 hidden service
- descriptors.
- - routerparse.c: Added 8 keywords to directory_keyword to parse v2 hidden
- service descriptors.
- - rendcommon.c: Added rend_cache_store_v2_dir() to allow a hidden service
- directory to parse a v2 descriptor and store it in the local cache under
- its descriptor ID instead of its service ID.
- - or.h: Added constant REND_DESC_ID_V2_LEN to reflect that v2 descriptor
- IDs are longer than v0/1 onion addresses.
- - Changed directory_handle_command_post().
-
- [Aug 11: Specified and running.]
- /7/ Accept v2 fetch requests
- Same as /6/, but with fetch requests for hidden service descriptors.
- (requires /2/ and /4/)
- - rend-spec.txt, section 3.3: Added the processing of v2 fetch requests.
- - rendcommon.c: Added rend_cache_lookup_v2_dir() to allow a hidden service
- directory to look up a v2 descriptor in the local cache under its
- descriptor ID instead of its service ID.
- - or.h: Added constant REND_DESC_ID_V2_LEN to reflect that v2 descriptor
- IDs are longer than v0/1 onion addresses.
- - Changed directory_handle_command_get().
-
- [Aug 11: Specified and running.]
- /8/ Replicate descriptors with neighbors
- A hidden service directory node replicates descriptors from its two
- predecessors by downloading them once an hour. Further, it checks its
- routing table periodically for changes. Whenever it realizes that a
- predecessor has left the network, it establishes a connection to the new
- n-th predecessor and requests its stored descriptors in the interval of its
- (n+1)-th predecessor and the requested n-th predecessor. Whenever it
- realizes that a new onion router has joined with an ID higher than its
- former n-th predecessor, it adds it to its predecessors and discards all
- descriptors in the interval of its (n+1)-th and its n-th predecessor.
- (requires /1/)
- - rend-spec.txt, section 3.3: Added the replication of v2 descriptors.
- - Added HS_DIR_REPLICATION_INTERVAL.
- - Added next_hs_dir and previous_hs_dir.
- - Changed directory_handle_command_get().
- - Changed run_scheduled_events.
- - Added hs_dir_perform_replication().
- - Added rend_cache_lookup_v2_replicas.
- - Added DIR_PURPOSE_REPLICATE_RENDDESC_V2.
- - Changed directory_initiate_command.
- - directory_send_command.
- - Changed connection_dir_client_reached_eof.
- [Aug 11: To some extend specified, running.]
- Authoritative directory nodes:
- /9/ Confirm a router's hidden service directory functionality
- Directory nodes include a new flag "HSDir" for routers that decided to
- provide storage for hidden service descriptors and that are running for at
- least 24 hours. The last requirement prevents a node from frequently
- changing its onion key to become responsible for an identifier it wants to
- target.
- - dir-spec.txt, section 3.2: Added the status flag "HSDir" to the vote and
- consensus status document format.
- - dir-spec.txt, section 3.3: Added a rule for how an authority decides
- whether a router is assigned the flag "HSDir".
- - rend-spec.txt, section 3.1: Added the decision on whether an onion router
- is confirmed to act as hidden service directory or not.
- - routerparse.c: Changed router_parse_entry_from_string() to parse the
- "hidden-service-dir" flag in router descriptors.
- - routerparse.c: Added an entry to routerdesc_token_table[] to parse the
- "hidden-service-directory" flag in router descriptors.
- - routerparse.c: Added 1 keyword to directory_keyword to parse the
- "hidden-service-dir" flag in router descriptors.
- - or.h: Added is_hs_dir and wants_to_be_hs_dir members to routerinfo_t.
- - dirserv.c: Changed routerstatus_format_entry() to include the "HSDir"
- flag in vote and consensus status documents.
- - dirserv.c: Changed set_routerstatus_from_routerinfo() to set the "HSDir"
- flag.
- - Added dirserv_thinks_router_is_hs_dir().
- - Added MIN_UPTIME_HS_DIR and HS_DIR_REACHABLE_TIMEOUT.
- [Aug 11: Specified and running.]
- Hidden service provider:
- /10/ Configure v2 hidden service
- Each hidden service provider that has set the config option
- "PublishV2HidServDescriptors" 0|1 to 1 is configured to publish v2
- descriptors and conform to the v2 connection establishment protocol. When
- configuring a hidden service, a hidden service provider checks if it has
- already created a random secret_cookie and a hostname2 file; if not, it
- creates both of them. (requires /2/)
- - tor.1.in: Added the config option PublishV2HidServDescriptors.
- - tor.1.in: Added the files hostname2 and secret_cookie.
- - rend-spec.txt, section 1.1: Added requirement to create secret_cookie and
- hostname2 file.
- - rendservice.c: Added rend_get_hostname2() to assemble a v2 onion address.
- - rendservice.c: Changed rend_service_load_keys() to write a secret_cookie
- and a hostname2 file.
- - rendservice.c: Extended rend_service_t by a member secret_cookie.
- - or.h: Added PublishV2HidServDescriptors to or_options_t.
- - config.c: Added config option PublishV2HidServDescriptors.
- [July 9: Specified and running.]
- /11/ Establish introduction points with fresh key
- If configured to publish only v2 descriptors and no v0/v1 descriptors any
- more, a hidden service provider that is setting up the hidden service at
- introduction points does not pass its own public key, but the public key
- of a freshly generated key pair. It also includes these fresh public keys
- in the hidden service descriptor together with the other introduction point
- information. The reason is that the introduction point does not need to and
- therefore should not know for which hidden service it works, so as to
- prevent it from tracking the hidden service's activity. (If a hidden
- service provider supports both, v0/v1 and v2 descriptors, v0/v1 clients
- rely on the fact that all introduction points accept the same public key,
- so that this new feature cannot be used.)
- - rend-spec.txt, section 1.3: Instead of Bob's public key, the hidden
- service provider uses a freshly generated public key for every
- introduction point.
- - TODO: Change in rend_encode_v2_descriptors.
- [July 9: Specified, but not yet implemented.]
- /12/ Encode v2 descriptors and send v2 publish requests
- If configured to publish v2 descriptors, a hidden service provider
- publishes a new descriptor whenever its content changes or a new
- publication period starts for this descriptor. If the current publication
- period would only last for less than 60 minutes (= 2 x 30 minutes to allow
- the server to be 30 minutes behind and the client 30 minutes ahead), the
- hidden service provider publishes both a current descriptor and one for
- the next period. Publication is performed by sending the descriptor to all
- hidden service directories that are responsible for keeping replicas for
- the descriptor ID. This includes two non-consecutive replicas that are
- stored at 3 consecutive nodes each. (requires /1/, /2/, and /3/)
- - rend-spec.txt, section 1.2: Added the new v2 hidden service descriptor
- format.
- - rend-spec.txt, section 1.4: Bob's OP does not only upload v0/v1 service
- descriptors to the authoritative directories, but also v2 service
- descriptors to the hidden service directories.
- - rendservice.c: Changed upload_service_descriptor() to upload v2 hidden
- service descriptors, if configured.
- - rendservice.c: Changed rend_consider_services_upload() to also initiate
- the upload of v2 descriptors, if configured.
- - rendservice.c: Extended rend_service_t by a member secret_cookie.
- - rendcommon.c: Added rend_encode_v2_descriptor() to encode a v2
- descriptor.
- - or.h: Added constant DIR_PURPOSE_UPLOAD_RENDDESC_V2.
- - directory.c: Added directory_post_to_hs_dir().
- - directory.c: Changed directory_initiate_command() to also recognize v2
- publish requests.
- - directory.c: Changed directory_send_command() to also prepare v2 publish
- requests.
- - crypto.c: Added implementation for crypto_cipher_encrypt_cbc().
- - Changed connection_dir_client_reached_eof().
- [Aug 11: Specified and running.]
- Hidden service client:
- /13/ Send v2 fetch requests
- A hidden service client that has set the config option
- "FetchV2HidServDescriptors" 0|1 to 1 handles SOCKS requests for v2 onion
- addresses by requesting a v2 descriptor from a randomly chosen hidden
- service directory that is responsible for keeping replica for the
- descriptor ID. In total there are six replicas of which the first and the
- last three are stored on consecutive nodes. The probability of picking one
- of the three consecutive replicas is 1/6, 2/6, and 3/6 to incorporate the
- fact that the availability will be the highest on the node with next higher
- ID. A hidden service client relies on the hidden service provider to store
- two sets of descriptors to compensate clock skew between service and
- client. (requires /1/, /2/, and /3/)
- - tor.1.in: Added the config option FetchV2HidServDescriptors.
- - rend-spec.txt, section 1.5: Added the new v2 onion address format.
- - rend-spec.txt, section 1.6: Alice's OP downloads the service descriptors
- similarly as Bob's OP uploaded them in 1.4.
- - rendcommon.c: Changed rend_cache_lookup_entry to enable it to also lookup
- v2 descriptors.
- - rendcommon.c: Added rend_compute_v2_desc_id() to generate v2 descriptor IDs
- from v2 onion addresses.
- - rendcommon.c: Changed rend_valid_service_id() to also consider v2 onion
- addresses as valid and return the version number of the request (0 or 2).
- - rendclient.c: Added rend_client_refetch_v2_renddesc() to fetch v2 service
- descriptors using the secret cookie.
- - rendclient.c: Changed rend_client_remove_intro_point() to copy the secret
- cookie if the local descriptor has expired or there are no introduction
- points left.
- - or.h: Added FetchV2HidServDescriptors to or_options_t.
- - or.h: Added constant REND_DESC_ID_V2_LEN to reflect that v2 descriptor
- IDs are longer than v0/1 onion addresses.
- - or.h: Added constant DIR_PURPOSE_FETCH_RENDDESC_V2.
- - directory.c: Added directory_get_from_hs_dir().
- - directory.c: Changed directory_initiate_command() to also recognize v2
- fetch requests.
- - directory.c: Changed directory_send_command() to also prepare v2 fetch
- requests.
- - connection_edge.c: Changed connection_ap_handshake_rewrite_and_attach()
- to fetch v2 service descriptors.
- - connection_edge.c: Changed parse_extended_hostname() to accept both,
- current and v2 onion addresses.
- - config.c: Added config options FetchV2HidServDescriptors.
- [Aug 11: Base version specified and running, but no memory of failed
- hidden service directories, yet.]
- /14/ Process v2 fetch reply and parse v2 descriptors
- A hidden service client that has sent a request for a v2 descriptor can
- parse it and store it to the local cache of rendezvous service descriptors.
- - rend-spec.txt, section 1.2: Added the new v2 hidden service descriptor
- format.
- - rend-spec.txt, section 1.6: Alice's OP parses the reply received from the
- hidden service directory.
- - routerparse.c: Added rend_parse_v2_service_descriptor() to parse a v2
- hidden service descriptor.
- - routerparse.c: Added rend_decrypt_introduction_points() to decrypt and
- parse the list of introduction points.
- - routerparse.c: Added ipo_token_table[] to parse the decrypted
- introduction points of v2 hidden service descriptors.
- - routerparse.c: Added desc_token_table[] to parse v2 hidden service
- descriptors.
- - routerparse.c: Added 8 keywords to directory_keyword to parse v2 hidden
- service descriptors, and 5 to parse the decrypted list of introduction
- points.
- - rendcommon.c: Added rend_cache_store_v2_client() to parse a v2 descriptor
- and parse the encrypted list of introduction points.
- - or.h: Added rend_version and secret_cookie to edge_connection_t, to
- dir_connection_t, and to origin_circuit_t to be able to decrypt
- introduction points when receiving a v2 descriptor.
- - directory.c: Changed connection_dir_client_reached_eof() to also parse v2
- fetch replies.
- - crypto.c: Added implementation for crypto_cipher_decrypt_cbc().
- [July 9: Specified and running.]
- /15/ Establish connection to v2 hidden service
- A hidden service client can establish a connection to a hidden service
- using a v2 descriptor. This includes using the secret cookie for decrypting
- the introduction points contained in the descriptor. When contacting an
- introduction point, the client does not use the public key of the hidden
- service provider, but the freshly-generated public key that is included in
- the hidden service descriptor. Whether or not a fresh key is used instead
- of the key of the hidden service depends on the available protocol versions
- that are included in the descriptor; by this, connection establishment is
- to a certain extend decoupled from fetching the descriptor.
- - rend-spec.txt, section 1.8: Alice uses the public key that is included in
- the descriptor instead of Bob's permanent service key.
- - rendclient.c: Changed rend_client_introduction_acked() to copy the secret
- cookie in case the introduction point denied the request.
- - rendclient.c: Changed rend_client_remove_intro_point() to copy the secret
- cookie if the local descriptor has expired or there are no introduction
- points left.
- - or.h: Added secret_cookie to edge_connection_t, to dir_connection_t, and
- to origin_circuit_t to be able to decrypt introduction points when
- receiving a v2 descriptor.
- - circuitlist.c: Changed _circuit_mark_for_close() to pass the secret
- cookie to rend_client_remove_intro_point() when an intro circ has failed.
- - circuituse.c: Changed circuit_get_open_circ_or_launch() to fetch a v2
- descriptor with the secret cookie, if no descriptor is available, or copy
- the secret cookie to the circuit, in case it dies later, so that it can
- be used to fetch a new descriptor.
- [July 9: Base version specified and running, but without fresh key.]
-
- Hidden service descriptor:
- (Requirements concerning the descriptor format are contained in /6/ and /7/.)
-
- The new v2 hidden service descriptor format looks like this:
- onion-address = h(public-key) + cookie
- descriptor-id = h(h(public-key) + h(time-period + cookie + relica))
- descriptor-content = {
- descriptor-id,
- version,
- public-key,
- h(time-period + cookie + replica),
- timestamp,
- protocol-versions,
- { introduction-points } encrypted with cookie
- } signed with private-key
- The "descriptor-id" needs to change periodically in order for the
- descriptor to be stored on changing nodes over time. It may only be
- computable by a hidden service provider and all of his clients to prevent
- unauthorized nodes from tracking the service activity by periodically
- checking whether there is a descriptor for this service. Finally, the
- hidden service directory needs to be able to verify that the hidden service
- provider is the true originator of the descriptor with the given ID.
-
- Therefore, "descriptor-id" is derived from the "public-key" of the hidden
- service provider, the current "time-period" which changes every 24 hours,
- a secret "cookie" shared between hidden service provider and clients, and
- a "replica" denoting the number of this non-consecutive replica. (The
- "time-period" is constructed in a way that time periods do not change at
- the same moment for all descriptors by deriving a value between 0:00 and
- 23:59 hours from h(public-key) and making the descriptors of this hidden
- service provider expire at that time of the day.) The "descriptor-id" is
- defined to be 160 bits long. [extending the "descriptor-id" length
- suggested by LØ]
-
- Only the hidden service provider and the clients are able to generate
- future "descriptor-ID"s. Hence, the "onion-address" is extended from now
- the hash value of "public-key" by the secret "cookie". The "public-key" is
- determined to be 80 bits long, whereas the "cookie" is dimensioned to be
- 120 bits long. This makes a total of 200 bits or 40 base32 chars, which is
- quite a lot to handle for a human, but necessary to provide sufficient
- protection against an adversary from generating a key pair with same
- "public-key" hash or guessing the "cookie".
-
- A hidden service directory can verify that a descriptor was created by the
- hidden service provider by checking if the "descriptor-id" corresponds to
- the "public-key" and if the signature can be verified with the
- "public-key".
- The "introduction-points" that are included in the descriptor are encrypted
- using the same "cookie" that is shared between hidden service provider and
- clients. [correction to use another key than h(time-period + cookie) as
- encryption key for introduction points made by LØ]
- A new text-based format is proposed for descriptors instead of an extension
- of the existing binary format for reasons of future extensibility.
- Security implications:
- The security implications of the proposed changes are grouped by the roles of
- nodes that could perform attacks or on which attacks could be performed.
- Attacks by authoritative directory nodes
- Authoritative directory nodes are no longer the single places in the
- network that know about a hidden service's activity and introduction
- points. Thus, they cannot perform attacks using this information, e.g.
- track a hidden service's activity or usage pattern or attack its
- introduction points. Formerly, it would only require a single corrupted
- authoritative directory operator to perform such an attack.
- Attacks by hidden service directory nodes
- A hidden service directory node could misuse a stored descriptor to track a
- hidden service's activity and usage pattern by clients. Though there is no
- countermeasure against this kind of attack, it is very expensive to track a
- certain hidden service over time. An attacker would need to run a large
- number of stable onion routers that work as hidden service directory nodes
- to have a good probability to become responsible for its changing
- descriptor IDs. For each period, the probability is:
- 1-(N-c choose r)/(N choose r) for N-c>=r and 1 otherwise, with N
- as total
- number of hidden service directories, c as compromised nodes, and r as
- number of replicas
- The hidden service directory nodes could try to make a certain hidden
- service unavailable to its clients. Therefore, they could discard all
- stored descriptors for that hidden service and reply to clients that there
- is no descriptor for the given ID or return an old or false descriptor
- content. The client would detect a false descriptor, because it could not
- contain a correct signature. But an old content or an empty reply could
- confuse the client. Therefore, the countermeasure is to replicate
- descriptors among a small number of hidden service directories, e.g. 5.
- The probability of a group of collaborating nodes to make a hidden service
- completely unavailable is in each period:
- (c choose r)/(N choose r) for c>=r and N>=r, and 0 otherwise,
- with N as total
- number of hidden service directories, c as compromised nodes, and r as
- number of replicas
- A hidden service directory could try to find out which introduction points
- are working on behalf of a hidden service. In contrast to the previous
- design, this is not possible anymore, because this information is encrypted
- to the clients of a hidden service.
- Attacks on hidden service directory nodes
- An anonymous attacker could try to swamp a hidden service directory with
- false descriptors for a given descriptor ID. This is prevented by requiring
- that descriptors are signed.
- Anonymous attackers could swamp a hidden service directory with correct
- descriptors for non-existing hidden services. There is no countermeasure
- against this attack. However, the creation of valid descriptors is more
- expensive than verification and storage in local memory. This should make
- this kind of attack unattractive.
- Attacks by introduction points
- Current or former introduction points could try to gain information on the
- hidden service they serve. But due to the fresh key pair that is used by
- the hidden service, this attack is not possible anymore.
- Attacks by clients
- Current or former clients could track a hidden service's activity, attack
- its introduction points, or determine the responsible hidden service
- directory nodes and attack them. There is nothing that could prevent them
- from doing so, because honest clients need the full descriptor content to
- establish a connection to the hidden service. At the moment, the only
- countermeasure against dishonest clients is to change the secret cookie and
- pass it only to the honest clients.
- Compatibility:
- The proposed design is meant to replace the current design for hidden service
- descriptors and their storage in the long run.
- There should be a first transition phase in which both, the current design
- and the proposed design are served in parallel. Onion routers should start
- serving as hidden service directories, and hidden service providers and
- clients should make use of the new design if both sides support it. Hidden
- service providers should be allowed to publish descriptors of the current
- format in parallel, and authoritative directories should continue storing and
- serving these descriptors.
- After the first transition phase, hidden service providers should stop
- publishing descriptors on authoritative directories, and hidden service
- clients should not try to fetch descriptors from the authoritative
- directories. However, the authoritative directories should continue serving
- hidden service descriptors for a second transition phase. As of this point,
- all v2 config options should be set to a default value of 1.
- After the second transition phase, the authoritative directories should stop
- serving hidden service descriptors.
- Specification:
- The proposed changes affect multiple sections in several specification
- documents that are only mentioned in the following. (As for now, all changes
- to specification documents are limited to the SVN branch 114-dist-storage.)
- tor.1.in
- Added the config options HSDir (/5/), PublishV2HidServDescriptors (/10/),
- and FetchV2HidServDescriptors (/13/).
- Added the files hostname2 and secret_cookie (/10/).
- dir-spec.txt
- 2.1 Added the flag hidden-service-dir to the router descriptor format
- (/5/).
- 3.2 Added the status flag HSDir to the vote and consensus status
- document format (/9/).
- 3.3 Added a rule for how an authority decides whether a router is assigned
- the flag HSDir (/9/).
- rend-spec.txt
- 0.4 Added history
- 1.1 Added requirement to create secret_cookie and hostname2 file (/10/).
- 1.2 Added the new v2 hidden service descriptor format (/6/, /12/ and
- /14/).
- 1.3 Instead of Bob's public key, the hidden service provider uses a
- freshly generated public key for every introduction point (/11/).
- 1.4 Added description of how to obtain a routing list of hidden service
- directories (/1/).
- 1.4 Added description of how to determine the responsible node(s) for a
- given descriptor ID (/2/).
- 1.4 Bob's OP does not only upload v0/v1 service descriptors to the
- authoritative directories, but also v2 service descriptors to the hidden
- service directories (/12/).
- 1.4 Added the requirement that requests need to be sent via Tor (/3/).
- 1.5 Added the new v2 onion address format (/13/).
- 1.6 Added the requirement that requests need to be sent via Tor (/3/).
- 1.6 Alice's OP downloads the service descriptors similarly as Bob's OP
- uploaded them in 1.4 (/13/).
-
- 1.6 Alice's OP parses the reply received from the hidden service directory
- (/14/).
- 1.8 Alice uses the public key that is included in the descriptor instead
- of Bob's permanent service key (/15/).
- 3.1: Added process of configuring a hidden service directory (/5/).
- 3.1: Added the decision on whether an onion router is confirmed to act as
- hidden service directory or not (/9/).
- 3.2: Added the requirement that requests need to be contained within
- BEGIN_DIR cells (/4/).
- 3.2: Added the acceptance of v2 publish requests (/6/).
- 3.3: Added the requirement that requests need to be contained within
- BEGIN_DIR cells (/4/).
-
- 3.3: Added the processing of v2 fetch requests (/7/).
- 3.3: Added the replication of v2 descriptors (/8/).
- Implementation:
- The proposed changes affect the following changes in the source code. (As for
- now, all changes to code are limited to the SVN branch 114-dist-storage.)
- container.h
- Added prototype for smartlist_digest_next_circular() (/2/).
- container.c
- Added implementation for smartlist_digest_next_circular() (/2/).
- crypto.h
- Added 3 prototypes according to the changes in crypto.c (various
- requirements).
- crypto.c
- Added implementation for crypto_cipher_encrypt_cbc() (/12/).
- Added implementation for crypto_cipher_decrypt_cbc() (/14/).
- Added implementation for base32_decode() (various requirements).
- circuitlist.c
- Changed _circuit_mark_for_close() to pass the secret cookie to
- rend_client_remove_intro_point() when an intro circ has failed (/15/).
- circuituse.c
- Changed circuit_get_open_circ_or_launch() to fetch a v2 descriptor with the
- secret cookie, if no descriptor is available, or copy the secret cookie to
- the circuit, in case it dies later, so that it can be used to fetch a new
- descriptor (/15/).
- config.c
- Added config options FetchV2HidServDescriptors (/13/), HSDir (/5/), and
- PublishV2HidServDescriptors (/10/).
- connection_edge.c
- Changed connection_ap_handshake_rewrite_and_attach() to fetch v2 service
- descriptors (/13/).
- Changed parse_extended_hostname() to accept both, current and v2 onion
- addresses (/13/).
- directory.c
- Added directory_post_to_hs_dir() (/12/).
- Added directory_get_from_hs_dir() (/13/).
- Changed directory_initiate_command() to also recognize v2 publish (/12/)
- and fetch (/13/) requests.
- Changed directory_send_command() to also prepare v2 publish (/12/) and
- fetch (/13/) requests.
- Changed connection_dir_client_reached_eof() to also parse v2 fetch replies
- (/14/).
- Changed directory_handle_command_get() to handle v2 fetch requests (/13/).
- Changed directory_handle_command_post() to handle v2 publish requests
- (/12/).
- dirserv.c
- Changed routerstatus_format_entry() to include the "HSDir" flag in vote and
- consensus status documents (/9/).
- Changed set_routerstatus_from_routerinfo() to set the "HSDir" flag (/9/).
- or.h
- Added constants DIR_PURPOSE_UPLOAD_RENDDESC_V2 (/12/) and
- DIR_PURPOSE_FETCH_RENDDESC_V2 (/13/).
- Added constant REND_DESC_ID_V2_LEN to reflect that v2 descriptor IDs are
- longer than v0/1 onion addresses (/6/, /7/, and /13/).
- Added rend_version and secret_cookie to edge_connection_t, to
- dir_connection_t, and to origin_circuit_t to be able to decrypt
- introduction points when receiving a v2 descriptor (/14/ and /15/).
- Added is_hs_dir member to routerinfo_t and to routerstatus_t (/9/).
- Added hs_dirs member to routerlist_t (/1/).
- Added FetchV2HidServDescriptors (/13/), HSDir (/5/), and
- PublishV2HidServDescriptors (/10/) to or_options_t.
- Added 7 new members to rend_service_descriptor_t to store v2-specific
- information (/12/, /14/, and /15/).
- Added 11 prototypes and changed the signature of 1 according to the
- changes in .c files (various requirements).
- rendclient.c
- Changed rend_client_introduction_acked() to copy the secret cookie in case
- the introduction point denied the request (/15/).
- Added rend_client_refetch_v2_renddesc() to fetch v2 service descriptors
- using the secret cookie (/13/).
- Changed rend_client_remove_intro_point() to copy the secret cookie if the
- local descriptor has expired or there are no introduction points left (/13/
- and /15/).
- rendcommon.c
- Added rend_compute_v2_descriptor_fields() to prepare the encoding of a v2
- descriptor (/12/).
- Added rend_compute_desc_id() to generate v2 descriptor IDs from v2 onion
- addresses (/13/).
- Added rend_encode_v2_descriptor() to encode a v2 descriptor (/12/).
- Changed rend_valid_service_id() to also consider v2 onion addresses as
- valid and return the version number of the request (1 or 2) (/13/).
- Changed rend_cache_lookup_entry to enable it to also lookup v2 descriptors
- (/13/).
- Added rend_cache_lookup_v2_dir() to allow a hidden service directory to
- look up a v2 descriptor in the local cache under its descriptor ID instead
- of its service ID (/7/).
- Moved the parsing part from rend_cache_store() to the new function
- rend_cache_store_parse() to reuse it for v2 descriptors (/6/).
- Added rend_cache_store_v2_client() to parse a v2 descriptor and parse the
- encrypted list of introduction points (/14/).
- Added rend_cache_store_v2_dir() to allow a hidden service directory to
- store a v2 descriptor in the local cache under its descriptor ID instead of
- its service ID (/6/).
- rendservice.c
- Extended rend_service_t by a member secret_cookie (/10/ and /12/).
- Added rend_get_hostname2() to assemble a v2 onion address (/10/).
- Changed rend_service_load_keys() to write a secret_cookie and a hostname2
- file (/10/).
- Changed upload_service_descriptor() to upload v2 hidden service
- descriptors, if configured (/12/).
- Changed rend_consider_services_upload() to also initiate the upload of v2
- descriptors, if configured (/12/).
- router.c
- Changed router_dump_router_to_string() to include the "hidden-service-dir"
- flag in a router descriptor if configured (/5/).
- routerlist.c
- Changed router_get_routerlist() to initialize routing list (/1/).
- Added get_responsible_hs_dir() to determine the router that is responsible
- for a given descriptor ID (/2/).
- routerparse.c
- Added 14 keywords to directory_keyword; 1 to parse the "hidden-service-dir"
- flag in router descriptors (/9/), 8 to parse v2 hidden service descriptors
- (/6/ and /14/), and 5 to parse the decrypted list of introduction points
- (/14/).
- Added an entry to routerdesc_token_table[] to parse the
- "hidden-service-directory" flag in router descriptors (/9/).
- Added desc_token_table[] to parse v2 hidden service descriptors (/6/ and
- /14/).
- Added ipo_token_table[] to parse the decrypted introduction points of v2
- hidden service descriptors (/14/).
- Changed router_parse_entry_from_string() to parse the "hidden-service-dir"
- flag in router descriptors (/9/).
- Changed routerstatus_parse_entry_from_string to parse the "HSDir" flag in
- vote and consensus status documents (/1/).
- Added rend_parse_v2_service_descriptor() to parse a v2 hidden service
- descriptor (/6/ and /14/).
- Added rend_decrypt_introduction_points() to decrypt and parse the list of
- introduction points (/14/).
- Test:
- The changes were tested via test functions in test.c for separate,
- short-running functionality and using an automatic validation based on
- PuppeTor.
-
|