Make rend-spec-ng.txt into a proper (pair of) proposals.

See rendspec-ng branch in my torspec repository for the revision history.

3 files changed, 1826 insertions, 0 deletions

diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 99845a4..0d79a82 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -144,6 +144,8 @@ Proposals by number:
 221  Stop using CREATE_FAST [CLOSED]
 222  Stop sending client timestamps [CLOSED]
 223  Ace: Improved circuit-creation key exchange [OPEN]
+224  Next-Generation Hidden Services in Tor [DRAFT]
+225  Strawman proposal: commit-and-reveal shared rng [DRAFT]
 
 
 Proposals by status:
@@ -160,6 +162,8 @@ Proposals by status:
    203  Avoiding censorship by impersonating an HTTPS server
    219  Support for full DNS and DNSSEC resolution in Tor [for 0.2.5.x]
    220  Migrate server identity keys to Ed25519 [for 0.2.5.x]
+   224  Next-Generation Hidden Services in Tor
+   225  Strawman proposal: commit-and-reveal shared rng
  NEEDS-REVISION:
    131  Help users to verify they are using Tor
    190  Bridge Client Authorization Based on a Shared Secret
diff --git a/proposals/224-rend-spec-ng.txt b/proposals/224-rend-spec-ng.txt
new file mode 100644
index 0000000..f88a287
--- /dev/null
+++ b/proposals/224-rend-spec-ng.txt
@@ -0,0 +1,1709 @@
+Filename: 224-rend-spec-ng.txt
+Title: Next-Generation Hidden Services in Tor
+Author: Nick Mathewson
+Created: 2013-11-29
+Status: Draft
+
+
+-1. Draft notes
+
+   This document describes a proposed design and specification for
+   hidden services in Tor version 0.2.5.x or later. It's a replacement
+   for the current rend-spec.txt, rewritten for clarity and for improved
+   design.
+
+   Look for the string "TODO" below: it describes gaps or uncertainties
+   in the design.
+
+   Change history:
+       2013-11-29: Proposal first numbered. Some TODO and XXX items remain.
+
+0. Hidden services: overview and preliminaries.
+
+   Hidden services aim to provide responder anonymity for bidirectional
+   stream-based communication on the Tor network. Unlike regular Tor
+   connections, where the connection initiator receives anonymity but
+   the responder does not, hidden services attempt to provide
+   bidirectional anonymity.
+
+   Other features include:
+
+     * [TODO: WRITE ME once there have been some more drafts and we know
+       what the summary should say.]
+
+   Participants:
+
+      Operator -- A person running a hidden service
+
+      Host, "Server" -- The Tor software run by the operator to provide
+         a hidden service.
+
+      User -- A person contacting a hidden service.
+
+      Client -- The Tor software running on the User's computer
+
+      Hidden Service Directory (HSDir) -- A Tor node that hosts signed
+        statements from hidden service hosts so that users can make
+        contact with them.
+
+      Introduction Point -- A Tor node that accepts connection requests
+        for hidden services and anonymously relays those requests to the
+        hidden service.
+
+      Rendezvous Point -- A Tor node to which clients and servers
+        connect and which relays traffic between them.
+
+
+
+0.1. Improvements over previous versions.
+
+   [TODO write me once there have been more drafts and we know what the
+   summary should say.]
+
+0.2. Notation and vocabulary
+
+   Unless specified otherwise, all multi-octet integers are big-endian.
+
+   We write sequences of bytes in two ways:
+
+     1. A sequence of two-digit hexadecimal values in square brackets,
+        as in [AB AD 1D EA].
+
+     2. A string of characters enclosed in quotes, as in "Hello". These
+        characters in these string are encoded in their ascii
+        representations; strings are NOT nul-terminated unless
+        explicitly described as NUL terminated.
+
+   We use the words "byte" and "octet" interchangeably.
+
+   We use the vertical bar | to denote concatenation.
+
+   We use INT_N(val) to denote the network (big-endian) encoding of the
+   unsigned integer "val" in N bytes. For example, INT_4(1337) is [00 00
+   05 39].
+
+0.3. Cryptographic building blocks
+
+   This specification uses the following cryptographic building blocks:
+
+      * A stream cipher STREAM(iv, k) where iv is a nonce of length
+        S_IV_LEN bytes and k is a key of length S_KEY_LEN bytes.
+
+      * A public key signature system SIGN_KEYGEN()->seckey, pubkey;
+        SIGN_SIGN(seckey,msg)->sig; and SIGN_CHECK(pubkey, sig, msg) ->
+        { "OK", "BAD" }; where secret keys are of length SIGN_SECKEY_LEN
+        bytes, public keys are of length SIGN_PUBKEY_LEN bytes, and
+        signatures are of length SIGN_SIG_LEN bytes.
+
+        This signature system must also support key blinding operations
+        as discussed in appendix [KEYBLIND] and in section [SUBCRED]:
+        SIGN_BLIND_SECKEY(seckey, blind)->seckey2 and
+        SIGN_BLIND_PUBKEY(pubkey, blind)->pubkey2 .
+
+      * A public key agreement system "PK", providing
+        PK_KEYGEN()->seckey, pubkey; PK_VALID(pubkey) -> {"OK", "BAD"};
+        and PK_HANDHAKE(seckey, pubkey)->output; where secret keys are
+        of length PK_SECKEY_LEN bytes, public keys are of length
+        PK_PUBKEY_LEN bytes, and the handshake produces outputs of
+        length PK_OUTPUT_LEN bytes.
+
+      * A cryptographic hash function H(d), which should be preimage and
+        collision resistant. It produces hashes of length HASH_LEN
+        bytes.
+
+      * A cryptographic message authentication code MAC(key,msg) that
+        produces outputs of length MAC_LEN bytes.
+
+      * A key derivation function KDF(key data, salt, personalization,
+        n) that outputs n bytes.
+
+   As a first pass, I suggest:
+
+      * Instantiate STREAM with AES128-CTR. [TODO: or ChaCha20?]
+
+      * Instantiate SIGN with Ed25519 and the blinding protocol in
+        [KEYBLIND].
+
+      * Instantiate PK with Curve25519.
+
+      * Instantiate H with SHA256. [TODO: really?]
+
+      * Instantiate MAC with HMAC using H.
+
+      * Instantiate KDF with HKDF using H.
+
+   For legacy purposes, we specify compatibility with older versions of
+   the Tor introduction point and rendezvous point protocols. These used
+   RSA1024, DH1024, AES128, and SHA1, as discussed in
+   rend-spec.txt. Except as noted, all RSA keys MUST have exponent
+   values of 65537.
+
+   As in [proposal 220], all signatures are generated not over strings
+   themselves, but over those strings prefixed with a distinguishing
+   value.
+
+
+0.4. Protocol building blocks [BUILDING-BLOCKS]
+
+   In sections below, we need to transmit the locations and identities
+   of Tor nodes. We do so in the link identification format used by
+   EXTEND2 cells in the Tor protocol.
+
+         NSPEC      (Number of link specifiers)   [1 byte]
+         NSPEC times:
+           LSTYPE (Link specifier type)           [1 byte]
+           LSLEN  (Link specifier length)         [1 byte]
+           LSPEC  (Link specifier)                [LSLEN bytes]
+
+   Link specifier types are as described in tor-spec.txt. Every set of
+   link specifiers MUST include at minimum specifiers of type [00]
+   (TLS-over-TCP, IPv4) and [02] (legacy node identity).
+
+   We also incorporate Tor's circuit extension handshakes, as used in
+   the CREATE2 and CREATED2 cells described in tor-spec.txt. In these
+   handshakes, a client who knows a public key for a server sends a
+   message and receives a message from that server. Once the exchange is
+   done, the two parties have a shared set of forward-secure key
+   material, and the client knows that nobody else shares that key
+   material unless they control the secret key corresponding to the
+   server's public key.
+
+0.5. Assigned relay cell types
+
+   These relay cell types are reserved for use in the hidden service
+   protocol.
+
+      32 -- RELAY_COMMAND_ESTABLISH_INTRO
+
+            Sent from hidden service host to introduction point;
+            establishes introduction point. Discussed in
+            [REG_INTRO_POINT].
+
+      33 -- RELAY_COMMAND_ESTABLISH_RENDEZVOUS
+
+            Sent from client to rendezvous point; creates rendezvous
+            point. Discussed in [EST_REND_POINT].
+
+      34 -- RELAY_COMMAND_INTRODUCE1
+
+            Sent from client to introduction point; requests
+            introduction. Discussed in [SEND_INTRO1]
+
+      35 -- RELAY_COMMAND_INTRODUCE2
+
+            Sent from client to introduction point; requests
+            introduction. Same format as INTRODUCE1. Discussed in
+            [FMT_INTRO1] and [PROCESS_INTRO2]
+
+      36 -- RELAY_COMMAND_RENDEZVOUS1
+
+            Sent from introduction point to rendezvous point;
+            attempts to join introduction point's circuit to
+            client's circuit. Discussed in [JOIN_REND]
+
+      37 -- RELAY_COMMAND_RENDEZVOUS2
+
+            Sent from introduction point to rendezvous point;
+            reports join of introduction point's circuit to
+            client's circuit. Discussed in [JOIN_REND]
+
+      38 -- RELAY_COMMAND_INTRO_ESTABLISHED
+
+            Sent from introduction point to hidden service host;
+            reports status of attempt to establish introduction
+            point. Discussed in [INTRO_ESTABLISHED]
+
+      39 -- RELAY_COMMAND_RENDEZVOUS_ESTABLISHED
+
+            Sent from rendezvous point to client; acknowledges
+            receipt of ESTABLISH_RENDEZVOUS cell. Discussed in
+            [EST_REND_POINT]
+
+      40 -- RELAY_COMMAND_INTRODUCE_ACK
+
+            Sent form introduction point to client; acknowledges
+            receipt of INTRODUCE1 cell and reports success/failure.
+            Discussed in [INTRO_ACK]
+
+0.5. Acknowledgments
+
+   [TODO reformat these once the lists are more complete.]
+
+   This design includes ideas from many people, including
+     Christopher Baines,
+     Daniel J. Bernstein,
+     Matthew Finkel,
+     Ian Goldberg,
+     George Kadianakis,
+     Aniket Kate,
+     Tanja Lange,
+     Robert Ransom,
+
+   It's based on Tor's original hidden service design by Roger
+   Dingledine, Nick Mathewson, and Paul Syverson, and on improvements to
+   that design over the years by people including
+     Tobias Kamm,
+     Thomas Lauterbach,
+     Karsten Loesing,
+     Alessandro Preite Martinez,
+     Robert Ransom,
+     Ferdinand Rieger,
+     Christoph Weingarten,
+     Christian Wilms,
+
+   We wouldn't be able to do any of this work without good attack
+   designs from researchers including
+     Alex Biryukov,
+     Lasse Øverlier,
+     Ivan Pustogarov,
+     Paul Syverson
+     Ralf-Philipp Weinmann,
+   See [ATTACK-REFS] for their papers.
+
+   Several of these ideas have come from conversations with
+      Christian Grothoff,
+      Brian Warner,
+      Zooko Wilcox-O'Hearn,
+
+   And if this document makes any sense at all, it's thanks to
+   editing help from
+      Matthew Finkel
+      George Kadianakis,
+      Peter Palfrader,
+
+
+   [XXX  Acknowledge the huge bunch of people working on 8106.]
+   [XXX  Acknowledge the huge bunch of people working on 8244.]
+
+
+   Please forgive me if I've missed you; please forgive me if I've
+   misunderstood your best ideas here too.
+
+
+1. Protocol overview
+
+   In this section, we outline the hidden service protocol. This section
+   omits some details in the name of simplicity; those are given more
+   fully below, when we specify the protocol in more detail.
+
+1.1. View from 10,000 feet
+
+   A hidden service host prepares to offer a hidden service by choosing
+   several Tor nodes to serve as its introduction points. It builds
+   circuits to those nodes, and tells them to forward introduction
+   requests to it using those circuits.
+
+   Once introduction points have been picked, the host builds a set of
+   documents called "hidden service descriptors" (or just "descriptors"
+   for short) and uploads them to a set of HSDir nodes. These documents
+   list the hidden service's current introduction points and describe
+   how to make contact with the hidden service.
+
+   When a client wants to connect to a hidden service, it first chooses
+   a Tor node at random to be its "rendezvous point" and builds a
+   circuit to that rendezvous point. If the client does not have an
+   up-to-date descriptor for the service, it contacts an appropriate
+   HSDir and requests such a descriptor.
+
+   The client then builds an anonymous circuit to one of the hidden
+   service's introduction points listed in its descriptor, and gives the
+   introduction point an introduction request to pass to the hidden
+   service. This introduction request includes the target rendezvous
+   point and the first part of a cryptographic handshake.
+
+   Upon receiving the introduction request, the hidden service host
+   makes an anonymous circuit to the rendezvous point and completes the
+   cryptographic handshake. The rendezvous point connects the two
+   circuits, and the cryptographic handshake gives the two parties a
+   shared key and proves to the client that it is indeed talking to the
+   hidden service.
+
+   Once the two circuits are joined, the client can send Tor RELAY cells
+   to the server. RELAY_BEGIN cells open streams to an external process
+   or processes configured by the server; RELAY_DATA cells are used to
+   communicate data on those streams, and so forth.
+
+1.2. In more detail: naming hidden services [NAMING]
+
+   A hidden service's name is its long term master identity key.  This
+   is encoded as a hostname by encoding the entire key in Base 32, and
+   adding the string ".onion" at the end.
+
+   (This is a change from older versions of the hidden service protocol,
+   where we used an 80-bit truncated SHA1 hash of a 1024 bit RSA key.)
+
+   The names in this format are distinct from earlier names because of
+   their length. An older name might look like:
+
+        unlikelynamefora.onion
+        yyhws9optuwiwsns.onion
+
+   And a new name following this specification might look like:
+
+        a1uik0w1gmfq3i5ievxdm9ceu27e88g6o7pe0rffdw9jmntwkdsd.onion
+
+   Note that since master keys are 32 bytes long, and 52 bytes of base
+   32 encoding can hold 260 bits of information, we have four unused
+   bits in each of these names.
+
+   [TODO: Alternatively, we could require that the first bit of the
+   master key always be zero, and use a 51-byte encoding. Or we could
+   require that the first two bits be zero, and use a 51-byte encoding
+   and reserve the first bit. Or we could require that the first nine
+   bits, or ten bits be zero, etc.]
+
+1.3. In more detail: Access control [IMD:AC]
+
+   Access control for a hidden service is imposed at multiple points
+   through the process above.
+
+   In order to download a descriptor, clients must know which blinded
+   signing key was used to sign it. (See the next section for more info
+   on key blinding.)  This blinded signing key is derived from the
+   service's public key and, optionally, an additional secret that is
+   not part of the hidden service's onion address. The public key and
+   this secret together constitute the service's "credential".
+
+   When the secret is in use, the hidden service gains protections
+   equivalent to the "stealth mode" in previous designs.
+
+   To learn the introduction points, the clients must decrypt the body
+   of the hidden service descriptor. The encryption key for these is
+   derived from the service's credential.
+
+   In order to make an introduction point send a request to the server,
+   the client must know the introduction point and know the service's
+   per-introduction-point authentication key from the hidden service
+   descriptor.
+
+   The final level of access control happens at the server itself, which
+   may decide to respond or not respond to the client's request
+   depending on the contents of the request. The protocol is extensible
+   at this point: at a minimum, the server requires that the client
+   demonstrate knowledge od the contents of the encrypted portion of the
+   hidden service descriptor. The service may additionally require a
+   user- or group-specific access token before it responds to requests.
+
+1.4. In more detail: Distributing hidden service descriptors. [IMD:DIST]
+
+   Periodically, hidden service descriptors become stored at different
+   locations to prevent a single directory or small set of directories
+   from becoming a good DoS target for removing a hidden service.
+
+   For each period, the Tor directory authorities agree upon a
+   collaboratively generated random value. (See section 2.3 for a
+   description of how to incorporate this value into the voting
+   practice; generating the value is described in other proposals,
+   including [TODO: add a reference])  That value, combined with hidden service
+   directories' public identity keys, determines each HSDirs' position
+   in the hash ring for descriptors made in that period.
+
+   Each hidden service's descriptors are placed into the ring in
+   positions based on the key that was used to sign them. Note that
+   hidden service descriptors are not signed with the services' public
+   keys directly. Instead, we use a key-blinding system [KEYBLIND] to
+   create a new key-of-the-day for each hidden service. Any client that
+   knows the hidden service's credential can derive these blinded
+   signing keys for a given period. It should be impossible to derive
+   the blinded signing key lacking that credential.
+
+   The body of each descriptor is also encrypted with a key derived from
+   the credential.
+
+   To avoid a "thundering herd" problem where every service generates
+   and uploads a new descriptor at the start of each period, each
+   descriptor comes online at a time during the period that depends on
+   its blinded signing key. The keys for the last period remain valid
+   until the new keys come online.
+
+1.5. In more detail: Scaling to multiple hosts
+
+   [THIS SECTION IS UNFINISHED]
+
+   In order to allow multiple hosts to provide a single hidden service,
+   I'm considering two options.
+
+      * We can have each server build an introduction circuit to each
+        introduction point, and have the introduction points responsible
+        for round-robining between these circuits. One service host is
+        responsible for picking the introduction points and publishing
+        the descriptors.
+
+      * We can have servers choose their introduction points
+        independently, and build circuits to them. One service host is
+        responsible for combining these introduction points into a
+        single descriptor.
+
+   If we want to avoid having a single "master" host without which the
+   whole service goes down (the "one service host" in the description
+   above), we need a way to fail over from one host to another. We also
+   need a way to coordinate between the hosts. This is as yet
+   undesigned. Maybe it should use a hidden service?
+
+   See [SCALING-REFS] for discussion on this topic.
+
+   [TODO: Finalize this design.]
+
+1.6. In more detail: Backward compatibility with older hidden service
+      protocols
+
+   This design is incompatible with the clients, server, and hsdir node
+   protocols from older versions of the hidden service protocol as
+   described in rend-spec.txt. On the other hand, it is designed to
+   enable the use of older Tor nodes as rendezvous points and
+   introduction points.
+
+1.7. In more detail: Offline operation
+
+   In this design, a hidden service's secret identity key may be stored
+   offline. It's used only to generate blinded identity keys, which are
+   used to sign descriptor signing keys. In order to operate a hidden
+   service, the operator can generate a number of descriptor signing
+   keys and their certifications (see [DESC-OUTER] and [ENCRYPTED-DATA]
+   below), and their corresponding descriptor encryption keys, and
+   export those to the hidden service hosts.
+
+1.8. In more detail: Encryption Keys And Replay Resistance
+
+   To avoid replays of an introduction request by an introduction point,
+   a hidden service host must never accept the same request
+   twice. Earlier versions of the hidden service design used a
+   authenticated timestamp here, but including a view of the current
+   time can create a problematic fingerprint. (See proposal 222 for more
+   discussion.)
+
+1.9. In more detail: A menagerie of keys
+
+   [In the text below, an "encryption keypair" is roughly "a keypair you
+   can do Diffie-Hellman with" and a "signing keypair" is roughly "a
+   keypair you can do ECDSA with."]
+
+   Public/private keypairs defined in this document:
+
+      Master (hidden service) identity key -- A master signing keypair
+        used as the identity for a hidden service. This key is not used
+        on its own to sign anything; it is only used to generate blinded
+        signing keys as described in [KEYBLIND] and [SUBCRED].
+
+      Blinded signing key -- A keypair derived from the identity key,
+        used to sign descriptor signing keys. Changes periodically for
+        each service. Clients who know a 'credential' consisting of the
+        service's public identity key and an optional secret can derive
+        the public blinded identity key for a service. This key is used
+        as an index in the DHT-like structure of the directory system.
+
+      Descriptor signing key -- A key used to sign hidden service
+        descriptors. This is signed by blinded signing keys. Unlike
+        blinded signing keys and master identity keys, the secret part
+        of this key must be stored online by hidden service hosts.
+
+      Introduction point authentication key -- A short-term signing
+        keypair used to identify a hidden service to a given
+        introduction point. A fresh keypair is made for each
+        introduction point; these are used to sign the request that a
+        hidden service host makes when establishing an introduction
+        point, so that clients who know the public component of this key
+        can get their introduction requests sent to the right
+        service. No keypair is ever used with more than one introduction
+        point. (previously called a "service key" in rend-spec.txt)
+
+      Introduction point encryption key -- A short-term encryption
+        keypair used when establishing connections via an introduction
+        point. Plays a role analogous to Tor nodes' onion keys. A fresh
+        keypair is made for each introduction point.
+
+   Symmetric keys defined in this document:
+
+      Descriptor encryption keys -- A symmetric encryption key used to
+        encrypt the body of hidden service descriptors. Derived from the
+        current period and the hidden service credential.
+
+   Public/private keypairs defined elsewhere:
+
+      Onion key -- Short-term encryption keypair
+
+      (Node) identity key
+
+   Symmetric key-like things defined elsewhere:
+
+      KH from circuit handshake -- An unpredictable value derived as
+      part of the Tor circuit extension handshake, used to tie a request
+      to a particular circuit.
+
+
+2. Generating and publishing hidden service descriptors [HSDIR]
+
+   Hidden service descriptors follow the same metaformat as other Tor
+   directory objects. They are published anonymously to Tor servers with
+   the HSDir3 flag.
+
+   (Authorities should assign this flag as they currently assign the
+   HSDir flag, except that they should restrict it to Tor versions
+   implementing the HSDir parts of this specification.)
+
+2.1. Deriving blinded keys and subcredentials [SUBCRED]
+
+   In each time period (see [TIME-PERIOD] for a definition of time
+   periods), a hidden service host uses a different blinded private key
+   to sign its directory information, and clients use a different
+   blinded public key as the index for fetching that information.
+
+   For a candidate for a key derivation method, see Appendix [KEYBLIND].
+
+   Additionally, clients and hosts derive a subcredential for each
+   period. Knowledge of the subcredential is needed to decrypt hidden
+   service descriptors for each period and to authenticate with the
+   hidden service host in the introduction process. Unlike the
+   credential, it changes each period. Knowing the subcredential, even
+   in combination with the blinded private key, does not enable the
+   hidden service host to derive the main credential--therefore, it is
+   safe to put the subcredential on the hidden service host while
+   leaving the hidden service's private key offline.
+
+   The subcredential for a period is derived as:
+       H("subcredential" |
+         credential |
+         blinded-public-key).
+
+2.2. Locating, uploading, and downloading hidden service descriptors
+       [HASHRING]
+
+   To avoid attacks where a hidden service's descriptor is easily
+   targeted for censorship, we store them at different directories over
+   time, and use shared random values to prevent those directories from
+   being predictable far in advance.
+
+   Which Tor servers hosts a hidden service depends on:
+
+         * the current time period,
+         * the daily subcredential,
+         * the hidden service directories' public keys,
+         * a shared random value that changes in each time period,
+         * a set of network-wide networkstatus consensus parameters.
+
+   Below we explain in more detail.
+
+2.2.1. Dividing time into periods [TIME-PERIODS]
+
+   To prevent a single set of hidden service directory from becoming a
+   target by adversaries looking to permanently censor a hidden service,
+   hidden service descriptors are uploaded to different locations that
+   change over time.
+
+   The length of a "time period" is controlled by the consensus
+   parameter 'hsdir-interval', and is a number of minutes between 30 and
+   14400 (10 days). The default time period length is 1500 (one day plus
+   one hour).
+
+   Time periods start with the Unix epoch (Jan 1, 1970), and are
+   computed by taking the number of whole minutes since the epoch and
+   dividing by the time period. So if the current time is 2013-11-12
+   13:44:32 UTC, making the seconds since the epoch 1384281872, the
+   number of minutes since the epoch is 23071364.  If the current time
+   period length is 1500 (the default), then the current time period
+   number is 15380. It began 15380*1500*60 seconds after the epoch at
+   2013-11-11 20:00:00 UTC, and will end at (15380+1)*1500*60 seconds
+   after the epoch at 2013-11-12 21:00:00 UTC.
+
+2.2.2. Overlapping time periods to avoid thundering herds [TIME-OVERLAP]
+
+   If every hidden service host were to generate a new set of keys and
+   upload a new descriptor at exactly the start of each time period, the
+   directories would be overwhelmed by every host uploading at the same
+   time. Instead, each public key becomes valid at its new location at a
+   deterministic time somewhat _before_ the period begins, depending on
+   the public key and the period.
+
+   The time at which a key might first become valid is determined by the
+   consensus parameter "hsdir-overlap-begins", which is an integer in
+   range [1,100] with default value 80. This parameter denotes a
+   percentage of the interval for which no overlap occurs.  So for the
+   default interval (1500 minutes) and default overlap-begins value
+   (80%), new keys do not become valid for the first 1200 minutes of the
+   interval.
+
+   The new shared random value must be published *before* the start of
+   the next overlap interval by at least enough time to ensure that
+   clients all get it. [TODO: how much earlier?]
+
+   The time at which a key from the next interval becomes valid is
+   determined by taking the first two bytes of
+
+     OFFSET = H(Key | INT_8(Next_Period_Num))
+
+   as a big-endian integer, dividing by 65536, and treating that as a
+   fraction of the overlap interval.
+
+   For example, if the period is 1500 minutes long, and overlap interval
+   is 300 minutes long, and OFFSET begins with [90 50], then the next
+   key becomes valid at 1200 + 300 * (0x9050 / 65536) minutes, or
+   approximately 22 hours and 49 minutes after the beginning of the
+   period.
+
+   Hidden service directories should accept descriptors at least [TODO:
+   how much?] minutes before they would become valid, and retain them
+   for at least [TODO: how much?] minutes after the end of the period.
+
+   When a client is looking for a service, it must calculate its key
+   both for the current and for the subsequent period, to decide whether
+   the next period's key is valid yet.
+
+2.2.3. Where to publish a service descriptor
+
+   The following consensus parameters control where a hidden service
+   descriptor is stored;
+
+        hsdir_n_replicas = an integer in range [1,16]
+                             with default value 2.
+
+        hsdir_spread_fetch = an integer in range [1,128]
+                             with default value 3.
+
+        hsdir_spread_store = an integer in range [1,128]
+                             with default value 3.
+
+        hsdir_spread_accept = an integer in range [1,128]
+                             with default value 8.
+
+   To determine where a given hidden service descriptor will be stored
+   in a given period, after the blinded public key for that period is
+   derived, the uploading or downloading party calculate
+
+        for replicanum in 1...hsdir_n_replicas:
+            hs_index(replicanum) = H("store-at-idx" |
+                                 blinded_public_key | replicanum |
+                                 periodnum)
+
+   where blinded_public_key is specified in section KEYBLIND, and
+   periodnum is defined in section TIME-PERIODS.
+
+   where n_replicas is determined by the consensus parameter
+   "hsdir_n_replicas".
+
+   Then, for each node listed in the current consensus with the HSDir3
+   flag, we compute a directory index for that node as:
+
+           hsdir_index(node) = H(node_identity_digest |
+                                 shared_random |
+                                 INT_8(period_num) )
+
+   where shared_random is the shared value generated by the authorities
+   in section PUB-SHAREDRANDOM.
+
+   Finally, for replicanum in 1...hsdir_n_replicas, the hidden service
+   host uploads descriptors to the first hsdir_spread_store nodes whose
+   indices immediately follow hs_index(replicanum).
+
+   When choosing an HSDir to download from, clients choose randomly from
+   among the first hsdir_spread_fetch nodes after the indices.  (Note
+   that, in order to make the system better tolerate disappearing
+   HSDirs, hsdir_spread_fetch may be less than hsdir_spread_store.)
+
+   An HSDir should rejects a descriptor if that HSDir is not one of the
+   first hsdir_spread_accept HSDirs for that node.
+
+   [TODO: Incorporate the findings from proposal 143 here. But watch
+   out: proposal 143 did not analyze how much the set of nodes changes
+   over time, or how much client and host knowledge might diverge.]
+
+2.2.4. URLs for anonymous uploading and downloading
+
+   Hidden service descriptors conforming to this specification are
+   uploaded with an HTTP POST request to the URL
+   /tor/rendezvous3/publish relative to the hidden service directory's
+   root, and downloaded with an HTTP GET request for the URL
+   /tor/rendezvous3/<z> where z is a base-64 encoding of the hidden
+   service's blinded public key.
+
+   [TODO: raw base64 is not super-nice for URLs, since it can have
+   slashes. We already use it for microdescriptor URLs, though. Do we
+   care here?]
+
+   These requests must be made anonymously, on circuits not used for
+   anything else.
+
+2.3. Publishing shared random values [PUB-SHAREDRANDOM]
+
+   Our design for limiting the predictability of HSDir upload locations
+   relies on a shared random value that isn't predictable in advance or
+   too influenceable by an attacker. The authorities must run a protocol
+   to generate such a value at least once per hsdir period. Here we
+   describe how they publish these values; the procedure they use to
+   generate them can change independently of the rest of this
+   specification. For one possible (somewhat broken) protocol, see
+   Appendix [SHAREDRANDOM].
+
+   We add a new line in votes and consensus documents:
+
+       "hsdir-shared-random" PERIOD-START VALUE
+       PERIOD-START = YYYY-MM-DD HH:MM:SS
+       VALUE = A base-64 encoded 256-bit value.
+
+   To decide which hsdir-shared-random line to include in a consensus
+   for a given PERIOD-START, we choose whichever line appears verbatim
+   in the most votes, so long as it is listed by at least three
+   authorities. Ties are broken in favor of the lower value. More than
+   one PERIOD-START is allowed per vote, and per consensus. The same
+   PERIOD-START must not appear twice in a vote or in a consensus.
+
+   [TODO: Need to define a more robust algorithm. Need to cover cases
+   where multiple cluster of authorities publish a different value,
+   etc.]
+
+   The hs-dir-shared-random lines appear, sorted by PERIOD-START, in the
+   consensus immediately after the "params" line.
+
+   The authorities should publish the shared random value for the
+   current period, and, at a time at least three voting periods before
+   the overlap interval begins, the shared random value for the next
+   period.
+
+[TODO: find out what weasel doesn't like here.]
+
+2.4. Hidden service descriptors: outer wrapper [DESC-OUTER]
+
+   The format for a hidden service descriptor is as follows, using the
+   meta-format from dir-spec.txt.
+
+     "hs-descriptor" SP "3" SP public-key SP certification NL
+
+       [At start, exactly once.]
+
+       public-key is the blinded public key for the service, encoded in
+       base 64. Certification is a certification of a short-term ed25519
+       descriptor signing key using the public key, in the format of
+       proposal 220.
+
+     "time-period" SP YYYY-MM-DD HH:MM:SS NUM NL
+
+       [Exactly once.]
+
+       The time period for which this descriptor is relevant, including
+       its starting time and its period number.
+
+     "revision-counter" SP Integer NL
+
+       [Exactly once.]
+
+       The revision number of the descriptor. If an HSDir receives a
+       second descriptor for a key that it already has a descriptor for,
+       it should retain and serve the descriptor with the higher
+       revision-counter.
+
+       (Checking for monotonically increasing revision-counter values
+       prevents an attacker from replacing a newer descriptor signed by
+       a given key with a copy of an older version.)
+
+     "encrypted" NL encrypted-string
+
+       [Exactly once.]
+
+       An encrypted blob, whose format is discussed in [ENCRYPTED-DATA]
+       below. The blob is base-64 encoded and enclosed in -----BEGIN
+       MESSAGE---- and ----END MESSAGE---- wrappers.
+
+     "signature" SP signature NL
+
+       [exactly once, at end.]
+
+       A signature of all previous fields, using the signing key in the
+       hs-descriptor line. We use a separate key for signing, so that
+       the hidden service host does not need to have its private blinded
+       key online.
+
+
+2.5. Hidden service descriptors: encryption format [ENCRYPTED-DATA]
+
+   The encrypted part of the hidden service descriptor is encrypted and
+   authenticated with symmetric keys generated as follows:
+
+       salt = 16 random bytes
+
+       secret_input = nonce | blinded_public_key | subcredential |
+             INT_4(revision_counter)
+       keys = KDF(secret_input, salt, "hsdir-encrypted-data",
+                  S_KEY_LEN + S_IV_LEN + MAC_KEY_LEN)
+
+       SECRET_KEY = first S_KEY_LEN bytes of keys
+       SECRET_IV  = next S_IV_LEN bytes of keys
+       MAC_KEY    = last MAC_KEY_LEN bytes of keys
+
+   The encrypted data has the format:
+
+       SALT       (random bytes from above)       [16 bytes]
+       ENCRYPTED  The plaintext encrypted with S  [variable]
+       MAC        MAC of both above fields        [32 bytes]
+
+   The encryption format is ENCRYPTED =
+               STREAM(SECRET_IV,SECRET_KEY) xor Plaintext
+
+   Before encryption, the plaintext must be padded to a multiple of ???
+   bytes with NUL bytes. The plaintext must not be longer than ???
+   bytes.  [TODO: how much? Should this be a parameter?  What values in
+   practice is needed to hide how many intro points we have, and how
+   many might be legacy ones?]
+
+   The plaintext format is:
+
+     "create2-formats" SP formats NL
+
+      [Exactly once]
+
+      A space-separated list of integers denoting CREATE2 cell format
+      numbers that the server recognizes. Must include at least TAP and
+      ntor as described in tor-spec.txt. See tor-spec section 5.1 for a
+      list of recognized handshake types.
+
+     "authentication-required" SP types NL
+
+      [At most once]
+
+      A space-separated list of authentication types. A client that does
+      not support at least one of these authentication types will not be
+      able to contact the host. Recognized types are: 'password' and
+      'ed25519'. See [INTRO-AUTH] below.
+
+     At least once:
+
+        "introduction-point" SP link-specifiers NL
+
+          [Exactly once per introduction point at start of introduction
+            point section]
+
+          The link-specifiers is a base64 encoding of a link specifier
+          block in the format described in BUILDING-BLOCKS.
+
+        "auth-key" SP "ed25519" SP key SP certification NL
+
+          [Exactly once per introduction point]
+
+          Base-64 encoded introduction point authentication key that was
+          used to establish introduction point circuit, cross-certifying
+          the blinded public key key using the certification format of
+          proposal 220.
+
+        "enc-key" SP "ntor" SP key NL
+
+          [At most once per introduction point]
+
+          Base64-encoded curve25519 key used to encrypt request to
+          hidden service.
+
+          [TODO: I'd like to have a cross-certification here too.]
+
+        "enc-key" SP "legacy" NL key NL
+
+          [At most once per introduction point]
+
+          Base64-encoded RSA key, wrapped in "----BEGIN RSA PUBLIC
+          KEY-----" armor, for use with a legacy introduction point as
+          described in [LEGACY_EST_INTRO] and [LEGACY-INTRODUCE1] below.
+
+          Exactly one of the "enc-key ntor" and "enc-key legacy"
+          elements must be present for each introduction point.
+
+        [TODO: I'd like to have a cross-certification here too.]
+
+   Other encryption and authentication key formats are allowed; clients
+   should ignore ones they do not recognize.
+
+
+3. The introduction protocol
+
+   The introduction protocol proceeds in three steps.
+
+   First, a hidden service host builds an anonymous circuit to a Tor
+   node and registers that circuit as an introduction point.
+
+        [Between these steps, the hidden service publishes its
+        introduction points and associated keys, and the client fetches
+        them as described in section [HSDIR] above.]
+
+   Second, a client builds an anonymous circuit to the introduction
+   point, and sends an introduction request.
+
+   Third, the introduction point relays the introduction request along
+   the introduction circuit to the hidden service host, and acknowledges
+   the introduction request to the client.
+
+3.1. Registering an introduction point [REG_INTRO_POINT]
+
+3.1.1. Extensible ESTABLISH_INTRO protocol. [EST_INTRO]
+
+   When a hidden service is establishing a new introduction point, it
+   sends a ESTABLISH_INTRO cell with the following contents:
+
+     AUTH_KEY_TYPE    [1 byte]
+     AUTH_KEY_LEN     [1 byte]
+     AUTH_KEY         [AUTH_KEY_LEN bytes]
+     Any number of times:
+        EXT_FIELD_TYPE [1 byte]
+        EXT_FIELD_LEN  [1 byte]
+        EXT_FIELD      [EXTRA_FIELD_LEN bytes]
+     ZERO             [1 byte]
+     HANDSHAKE_AUTH   [MAC_LEN bytes]
+     SIGLEN           [1 byte]
+     SIG              [SIGLEN bytes]
+
+   The AUTH_KEY_TYPE field indicates the type of the introduction point
+   authentication key and the type of the MAC to use in for
+   HANDSHAKE_AUTH. Recognized types are:
+
+       [00, 01] -- Reserved for legacy introduction cells; see
+                   [LEGACY_EST_INTRO below]
+       [02] -- Ed25519; HMAC-SHA256.
+       [FF] -- Reserved for maintenance messages on existing
+               circuits; see MAINT_INTRO below.
+
+               [TODO: Should this just be a new relay cell type?
+                Matthew and George think so.]
+
+   The AUTH_KEY_LEN field determines the length of the AUTH_KEY
+   field. The AUTH_KEY field contains the public introduction point
+   authentication key.
+
+   The EXT_FIELD_TYPE, EXT_FIELD_LEN, EXT_FIELD entries are reserved for
+   future extensions to the introduction protocol. Extensions with
+   unrecognized EXT_FIELD_TYPE values must be ignored.
+
+   The ZERO field contains the byte zero; it marks the end of the
+   extension fields.
+
+   The HANDSHAKE_AUTH field contains the MAC of all earlier fields in
+   the cell using as its key the shared per-circuit material ("KH")
+   generated during the circuit extension protocol; see tor-spec.txt
+   section 5.2, "Setting circuit keys". It prevents replays of
+   ESTABLISH_INTRO cells.
+
+   SIGLEN is the length of the signature.
+
+   SIG is a signature, using AUTH_KEY, of all contents of the cell, up
+   to but not including SIG. These contents are prefixed with the string
+   "Tor establish-intro cell v1".
+
+   Upon receiving an ESTABLISH_INTRO cell, a Tor node first decodes the
+   key and the signature, and checks the signature. The node must reject
+   the ESTABLISH_INTRO cell and destroy the circuit in these cases:
+
+        * If the key type is unrecognized
+        * If the key is ill-formatted
+        * If the signature is incorrect
+        * If the HANDSHAKE_AUTH value is incorrect
+
+        * If the circuit is already a rendezvous circuit.
+        * If the circuit is already an introduction circuit.
+          [TODO: some scalability designs fail there.]
+        * If the key is already in use by another circuit.
+
+   Otherwise, the node must associate the key with the circuit, for use
+   later in INTRODUCE1 cells.
+
+   [TODO: The above will work fine with what we do today, but it will do
+   quite badly if we ever freak out and want to go back to RSA2048 or
+   bigger.  Do we care?]
+
+3.1.2. Registering an introduction point on a legacy Tor node [LEGACY_EST_INTRO]
+
+   Tor nodes should also support an older version of the ESTABLISH_INTRO
+   cell, first documented in rend-spec.txt. New hidden service hosts
+   must use this format when establishing introduction points at older
+   Tor nodes that do not support the format above in [EST_INTRO].
+
+   In this older protocol, an ESTABLISH_INTRO cell contains:
+
+        KEY_LENGTH     [2 bytes]
+        KEY            [KEY_LENGTH bytes]
+        HANDSHAKE_AUTH [20 bytes]
+        SIG            [variable, up to end of relay payload]
+
+   The KEY_LENGTH variable determines the length of the KEY field.
+
+   The KEY field is a ASN1-encoded RSA public key.
+
+   The HANDSHAKE_AUTH field contains the SHA1 digest of (KH |
+   "INTRODUCE").
+
+   The SIG field contains an RSA signature, using PKCS1 padding, of all
+   earlier fields.
+
+   Note that since the relay payload itself may be no more than 498
+   bytes long, the KEY_LENGTH field can never have a first byte other
+   than [00] or [01]. These values are used to distinguish legacy
+   ESTABLISH_INTRO cells from newer ones.
+
+   Older versions of Tor always use a 1024-bit RSA key for these
+   introduction authentication keys.
+
+   Newer hidden services MAY use RSA keys up 1904 bits. Any more than
+   that will not fit in a RELAY cell payload.
+
+3.1.3. Managing introduction circuits [MAINT_INTRO]
+
+   If the first byte of an ESTABLISH_INTRO cell is [FF], the cell's body
+   contains an administrative command for the circuit. The format of
+   such a command is:
+
+     Any number of times:
+       SUBCOMMAND_TYPE [2 bytes]
+       SUBCOMMAND_LEN  [2 bytes]
+       SUBCOMMAND      [COMMAND_LEN bytes]
+
+   Recognized SUBCOMMAND_TYPE values are:
+
+       [00 01] -- update encryption keys
+
+   [TODO: Matthew says, "This can be used to fork an intro point to
+    balance traffic over multiple hidden service servers while
+    maintaining the criteria for a valid ESTABLISH_INTRO
+    cell. -MF". Investigate.]
+
+   Unrecognized SUBCOMMAND_TYPE values should be ignored.
+
+3.1.3.1. Updating encryption keys (subcommand 0001) [UPDATE-KEYS-SUBCMD]
+
+   Hidden service hosts send this subcommand to set their initial
+   encryption keys or update the configured public encryption keys
+   associated with this circuit. This message must be sent after
+   establishing an introduction point, before the circuit can be
+   advertised.  These keys are given in the form:
+
+      NUMKEYS         [1 byte]
+      NUMKEYS times:
+        KEYTYPE         [1 byte]
+        KEYLEN          [1 byte]
+        KEY             [KEYLEN bytes]
+      COUNTER         [4 bytes]
+      SIGLEN          [1 byte]
+      SIGNATURE       [SIGLEN bytes.]
+
+   The KEYTYPE value [01] is for Curve25519 keys.
+
+   The COUNTER field is a monotonically increasing value across a given
+   introduction point authentication key.
+
+   The SIGNATURE must be generated with the introduction point
+   authentication key, and must cover the entire subcommand body,
+   prefixed with the string "Tor hidden service introduction encryption
+   keys v1".
+
+   [TODO: Nothing is done here to prove ownership of the encryption
+   keys. Does that matter?]
+
+   [TODO: The point here is to allow encryption keys to change while
+   maintaining an introduction point and not forcing a client to
+   download a new descriptor. I'm not sure if that's worth it. It makes
+   clients who have seen a key before distinguishable from ones who have
+   not.]
+
+   [Matthew says: "Repeat-client over long periods of time will always
+   be distinguishable. It may be better to simply expire intro points
+   than try to preserve forward-secrecy, though". Must find out what he
+   meant.]
+
+   Setting the encryption keys for a given circuit replaces the previous
+   keys for that circuit. Clients who attempt to connect using the old
+   key receive an INTRO_ACK cell with error code [00 02] as described in
+   section [INTRO_ACK] below.
+
+3.1.4. Acknowledging establishment of introduction point [INTRO_ESTABLISHED]
+
+   After setting up an introduction circuit, the introduction point
+   reports its status back to the hidden service host with an empty
+   INTRO_ESTABLISHED cell.
+
+    [TODO: make this cell type extensible. It should be able to include
+    data if that turns out to be needed.]
+
+3.2. Sending an INTRODUCE1 cell to the introduction point. [SEND_INTRO1]
+
+   In order to participate in the introduction protocol, a client must
+   know the following:
+
+     * An introduction point for a service.
+     * The introduction authentication key for that introduction point.
+     * The introduction encryption key for that introduction point.
+
+   The client sends an INTRODUCE1 cell to the introduction point,
+   containing an identifier for the service, an identifier for the
+   encryption key that the client intends to use, and an opaque blob to
+   be relayed to the hidden service host.
+
+   In reply, the introduction point sends an INTRODUCE_ACK cell back to
+   the client, either informing it that its request has been delivered,
+   or that its request will not succeed.
+
+3.2.1. INTRODUCE1 cell format [FMT_INTRO1]
+
+   An INTRODUCE1 cell has the following contents:
+
+     AUTH_KEYID      [32 bytes]
+     ENC_KEYID       [8 bytes]
+     Any number of times:
+       EXT_FIELD_TYPE [1 byte]
+       EXT_FIELD_LEN  [1 byte]
+       EXT_FIELD      [EXTRA_FIELD_LEN bytes]
+     ZERO             [1 byte]
+     ENCRYPTED        [Up to end of relay payload]
+
+   [TODO: Should we have a field to determine the type of ENCRYPTED, or
+   should we instead assume that there is exactly one encryption key per
+   encryption method? The latter is probably safer.]
+
+   Upon receiving an INTRODUCE1 cell, the introduction point checks
+   whether AUTH_KEYID and ENC_KEYID match a configured introduction
+   point authentication key and introduction point encryption key.  If
+   they do, the cell is relayed; if not, it is not.
+
+   The AUTH_KEYID for an Ed25519 public key is the public key itself.
+   The ENC_KEYID for a Curve25519 public key is the first 8 bytes of the
+   public key. (This key ID is safe to truncate, since all the keys are
+   generated by the hidden service host, and the ID is only valid
+   relative to a single AUTH_KEYID.)  The ENCRYPTED field is as
+   described in 3.3 below.
+
+   To relay an INTRODUCE1 cell, the introduction point sends an
+   INTRODUCE2 cell with exactly the same contents.
+
+3.2.2. INTRODUCE_ACK cell format. [INTRO_ACK]
+
+   An INTRODUCE_ACK cell has the following fields:
+     STATUS    [2 bytes]
+     Any number of times:
+       EXT_FIELD_TYPE [1 byte]
+       EXT_FIELD_LEN  [1 byte]
+       EXT_FIELD      [EXTRA_FIELD_LEN bytes]
+
+   Recognized status values are:
+     [00 00] -- Success: cell relayed to hidden service host.
+     [00 01] -- Failure: service ID not recognzied
+     [00 02] -- Failure: key ID not recognized
+     [00 03] -- Bad message format
+
+   Recognized extension field types:
+     [00 01] -- signed set of encryption keys
+
+   The extension field type 0001 is a signed set of encryption keys; its
+   body matches the body of the key update command in
+   [UPDATE-KEYS-CMD]. Whenever sending status [00 02], the introduction
+   point MUST send this extension field.
+
+3.2.3. Legacy formats [LEGACY-INTRODUCE1]
+
+   When the ESTABLISH_INTRO cell format of [LEGACY_EST_INTRO] is used,
+   INTRODUCE1 cells are of the form:
+
+     AUTH_KEYID_HASH  [20 bytes]
+     ENC_KEYID        [8 bytes]
+     Any number of times:
+       EXT_FIELD_TYPE [1 byte]
+       EXT_FIELD_LEN  [1 byte]
+       EXT_FIELD      [EXTRA_FIELD_LEN bytes]
+     ZERO             [1 byte]
+     ENCRYPTED        [Up to end of relay payload]
+
+   Here, AUTH_KEYID_HASH is the hash of the introduction point
+   authentication key used to establish the introduction.
+
+   Because of limitations in older versions of Tor, the relay payload
+   size for these INTRODUCE1 cells must always be at least 246 bytes, or
+   they will be rejected as invalid.
+
+3.3. Processing an INTRODUCE2 cell at the hidden service. [PROCESS_INTRO2]
+
+   Upon receiving an INTRODUCE2 cell, the hidden service host checks
+   whether the AUTH_KEYID/AUTH_KEYID_HASH field and the ENC_KEYID fields
+   are as expected, and match the configured authentication and
+   encryption key(s) on that circuit.
+
+   The service host then checks whether it has received a cell with
+   these contents before. If it has, it silently drops it as a
+   replay. (It must maintain a replay cache for as long as it accepts
+   cells with the same encryption key.)
+
+   If the cell is not a replay, it decrypts the ENCRYPTED field,
+   establishes a shared key with the client, and authenticates the whole
+   contents of the cell as having been unmodified since they left the
+   client. There may be multiple ways of decrypting the ENCRYTPED field,
+   depending on the chosen type of the encryption key. Requirements for
+   an introduction handshake protocol are described in
+   [INTRO-HANDSHAKE-REQS]. We specify one below in section
+   [NTOR-WITH-EXTRA-DATA].
+
+   The decrypted plaintext must have the form:
+
+      REND_TOKEN                                 [20 bytes]
+      Any number of times:
+          EXT_FIELD_TYPE                         [1 byte]
+          EXT_FIELD_LEN                          [1 byte]
+          EXT_FIELD                              [EXTRA_FIELD_LEN bytes]
+      ZERO                                       [1 byte]
+      ONION_KEY_TYPE                             [2 bytes]
+      ONION_KEY                                  [depends on ONION_KEY_TYPE]
+      NSPEC      (Number of link specifiers)     [1 byte]
+      NSPEC times:
+          LSTYPE (Link specifier type)           [1 byte]
+          LSLEN  (Link specifier length)         [1 byte]
+          LSPEC  (Link specifier)                [LSLEN bytes]
+      PAD        (optional padding)              [up to end of plaintext]
+
+
+   Upon processing this plaintext, the hidden service makes sure that
+   any required authentication is present in the extension fields, and
+   then extends a rendezvous circuit to the node described in the LSPEC
+   fields, using the ONION_KEY to complete the extension. As mentioned
+   in [BUILDING-BLOCKS], the "TLS-over-TCP, IPv4" and "Legacy node
+   identity" specifiers must be present.
+
+   The hidden service SHOULD NOT reject any LSTYPE fields which it
+   doesn't recognize; instead, it should use them verbatim in its EXTEND
+   request to the rendezvous point.
+
+   The ONION_KEY_TYPE field is one of:
+
+      [01] TAP-RSA-1024:  ONION_KEY is 128 bytes long.
+      [02] NTOR:          ONION_KEY is 32 bytes long.
+
+   The ONION_KEY field describes the onion key that must be used when
+   extending to the rendezvous point. It must be of a type listed as
+   supported in the hidden service descriptor.
+
+   Upon receiving a well-formed INTRODUCE2 cell, the hidden service host
+   will have:
+
+     * The information needed to connect to the client's chosen
+       rendezvous point.
+     * The second half of a handshake to authenticate and establish a
+       shared key with the hidden service client.
+     * A set of shared keys to use for end-to-end encryption.
+
+3.3.1. Introduction handshake encryption requirements [INTRO-HANDSHAKE-REQS]
+
+   When decoding the encrypted information in an INTRODUCE2 cell, a
+   hidden service host must be able to:
+
+     * Decrypt additional information included in the INTRODUCE2 cell,
+       to include the rendezvous token and the information needed to
+       extend to the rendezvous point.
+
+     * Establish a set of shared keys for use with the client.
+
+     * Authenticate that the cell has not been modified since the client
+       generated it.
+
+   Note that the old TAP-derived protocol of the previous hidden service
+   design achieved the first two requirements, but not the third.
+
+3.3.2. Example encryption handshake: ntor with extra data [NTOR-WITH-EXTRA-DATA]
+
+   This is a variant of the ntor handshake (see tor-spec.txt, section
+   5.1.4; see proposal 216; and see "Anonymity and one-way
+   authentication in key-exchange protocols" by Goldberg, Stebila, and
+   Ustaoglu).
+
+   It behaves the same as the ntor handshake, except that, in addition
+   to negotiating forward secure keys, it also provides a means for
+   encrypting non-forward-secure data to the server (in this case, to
+   the hidden service host) as part of the handshake.
+
+   Notation here is as in section 5.1.4 of tor-spec.txt, which defines
+   the ntor handshake.
+
+   The PROTOID for this variant is
+   "hidden-service-ntor-curve25519-sha256-1".  Define the tweak value
+   t_hsenc, and the tag value m_hsexpand as:
+
+      t_hsenc    = PROTOID | ":hs_key_extract"
+      m_hsexpand = PROTOID | ":hs_key_expand"
+
+   To make an INTRODUCE cell, the client must know a public encryption
+   key B for the hidden service on this introduction circuit. The client
+   generates a single-use keypair:
+             x,X = KEYGEN()
+   and computes:
+             secret_hs_input = EXP(B,x) | AUTH_KEYID | X | B | PROTOID
+             info = m_hsexpand | subcredential
+             hs_keys = HKDF(secret_hs_input, t_hsenc, info,
+                            S_KEY_LEN+MAC_LEN)
+             ENC_KEY = hs_keys[0:S_KEY_LEN]
+             MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
+
+   and sends, as the ENCRYPTED part of the INTRODUCE1 cell:
+
+          CLIENT_PK                [G_LENGTH bytes]
+          ENCRYPTED_DATA           [Padded to length of plaintext]
+          MAC                      [MAC_LEN bytes]
+
+
+   Substituting those fields into the INTRODUCE1 cell body format
+   described in [FMT_INTRO1] above, we have
+
+            AUTH_KEYID                  [32 bytes]
+            ENC_KEYID                   [8 bytes]
+            Any number of times:
+               EXT_FIELD_TYPE           [1 byte]
+               EXT_FIELD_LEN            [1 byte]
+               EXT_FIELD                [EXTRA_FIELD_LEN bytes]
+               ZERO                     [1 byte]
+            ENCRYPTED:
+               CLIENT_PK                [G_LENGTH bytes]
+               ENCRYPTED_DATA           [Padded to length of plaintext]
+               MAC                      [MAC_LEN bytes]
+
+
+   (This format is as documented in [FMT_INTRO1] above, except that here
+   we describe how to build the ENCRYPTED portion. If the introduction
+   point is running an older Tor that does not support this protocol,
+   the first field is replaced by a 20-byte AUTH_KEYID_HASH field as
+   described in [LEGACY-INTRODUCE1].)
+
+   Here, the encryption key plays the role of B in the regular ntor
+   handshake, and the AUTH_KEYID field plays the role of the node ID.
+   The CLIENT_PK field is the public key X. The ENCRYPTED_DATA field is
+   the message plaintext, encrypted with the symmetric key ENC_KEY. The
+   MAC field is a MAC of all of the cell from the AUTH_KEYID through the
+   end of ENCRYPTED_DATA, using the MAC_KEY value as its key.
+
+   To process this format, the hidden service checks PK_VALID(CLIENT_PK)
+   as necessary, and then computes ENC_KEY and MAC_KEY as the client did
+   above, except using EXP(CLIENT_PK,b) in the calculation of
+   secret_hs_input. The service host then checks whether the MAC is
+   correct. If it is invalid, it drops the cell. Otherwise, it computes
+   the plaintext by decrypting ENCRYPTED_DATA.
+
+   The hidden service host now completes the service side of the
+   extended ntor handshake, as described in tor-spec.txt section 5.1.4,
+   with the modified PROTOID as given above. To be explicit, the hidden
+   service host generates a keypair of y,Y = KEYGEN(), and uses its
+   introduction point encryption key 'b' to computes:
+
+      xb = EXP(X,b)
+
+      secret_hs_input = xb | AUTH_KEYID | X | B | PROTOID
+      info = m_hsexpand | subcredential
+      hs_keys = HKDF(secret_hs_input, t_hsenc, info,
+                     S_KEY_LEN+MAC_LEN)
+      HS_DEC_KEY = hs_keys[0:S_KEY_LEN]
+      HS_MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
+
+      (The above are used to check the MAC and then decrypt the
+      encrypted data.)
+
+      ntor_secret_input = EXP(X,y) | xb | ID | B | X | Y | PROTOID
+      NTOR_KEY_SEED = H(secret_input, t_key)
+      verify = H(secret_input, t_verify)
+      auth_input = verify | ID | B | Y | X | PROTOID | "Server"
+
+      (The above are used to finish the ntor handshake.)
+
+   The server's handshake reply is:
+       SERVER_PK   Y                       [G_LENGTH bytes]
+       AUTH        H(auth_input, t_mac)    [H_LENGTH bytes]
+
+   These faileds can be send to the client in a RENDEZVOUS1 cell.
+   (See [JOIN_REND] below.)
+
+   The hidden service host now also knows the keys generated by the
+   handshake, which it will use to encrypt and authenticate data
+   end-to-end between the client and the server. These keys are as
+   computed in tor-spec.txt section 5.1.4.
+
+3.4. Authentication during the introduction phase. [INTRO-AUTH]
+
+   Hidden services may restrict access only to authorized users.  One
+   mechanism to do so is the credential mechanism, where only users who
+   know the credential for a hidden service may connect at all. For more
+   fine-grained conntrol, a hidden service can be configured with
+   password-based or public-key-based authentication.
+
+3.4.1. Password-based authentication.
+
+   To authenticate with a password, the user must include an extension
+   field in the encrypted part of the INTRODUCE cell with an
+   EXT_FIELD_TYPE type of [01] and the contents:
+
+     Username [00] Password.
+
+   The username may not include any [00] bytes. The password may.
+
+   On the server side, the password MUST be stored hashed and salted,
+   ideally with scrypt or something better.
+
+3.4.2. Ed25519-based authentication.
+
+   To authenticate with an Ed25519 private key, the user must include an
+   extension field in the encrypted part of the INTRODUCE cell with an
+   EXT_FIELD_TYPE type of [02] and the contents:
+
+        Nonce     [16 bytes]
+        Pubkey    [32 bytes]
+        Signature [64 bytes]
+
+   Nonce is a random value. Pubkey is the public key that will be used
+   to authenticate. [TODO: should this be an identifier for the public
+   key instead?]  Signature is the signature, using Ed25519, of:
+
+        "Hidserv-userauth-ed25519"
+        Nonce       (same as above)
+        Pubkey      (same as above)
+        AUTH_KEYID  (As in the INTRODUCE1 cell)
+        ENC_KEYID   (As in the INTRODUCE1 cell)
+
+   The hidden service host checks this by seeing whether it recognizes
+   and would accept a signature from the provided public key. If it
+   would, then it checks whether the signature is correct. If it is,
+   then the correct user has authenticated.
+
+   Replay prevention on the whole cell is sufficient to prevent replays
+   on the authentication.
+
+   Users SHOULD NOT use the same public key with multiple hidden
+   services.
+
+4. The rendezvous protocol
+
+   Before connecting to a hidden service, the client first builds a
+   circuit to an arbitrarily chosen Tor node (known as the rendezvous
+   point), and sends an ESTABLISH_RENDEZVOUS cell. The hidden service
+   later connects to the same node and sends a RENDEZVOUS cell. Once
+   this has occurred, the relay forwards the contents of the RENDEZVOUS
+   cell to the client, and joins the two circuits together.
+
+4.1. Establishing a rendezvous point [EST_REND_POINT]
+
+   The client sends the rendezvous point a
+   RELAY_COMMAND_ESTABLISH_RENDEZVOUS cell containing a 20-byte value.
+            RENDEZVOUS_COOKIE         [20 bytes]
+
+   Rendezvous points MUST ignore any extra bytes in an
+   ESTABLISH_RENDEZVOUS message. (Older versions of Tor did not.)
+
+   The rendezvous cookie is an arbitrary 20-byte value, chosen randomly
+   by the client. The client SHOULD choose a new rendezvous cookie for
+   each new connection attempt. If the rendezvous cookie is already in
+   use on an existing circuit, the rendezvous point should reject it and
+   destroy the circuit.
+
+   Upon receiving a ESTABLISH_RENDEZVOUS cell, the rendezvous point
+   associates the cookie with the circuit on which it was sent. It
+   replies to the client with an empty RENDEZVOUS_ESTABLISHED cell to
+   indicate success.  [TODO: make this extensible]
+
+   The client MUST NOT use the circuit which sent the cell for any
+   purpose other than rendezvous with the given location-hidden service.
+
+   The client should establish a rendezvous point BEFORE trying to
+   connect to a hidden service.
+
+4.2. Joining to a rendezvous point [JOIN_REND]
+
+   To complete a rendezvous, the hidden service host builds a circuit to
+   the rendezvous point and sends a RENDEZVOUS1 cell containing:
+
+       RENDEZVOUS_COOKIE          [20 bytes]
+       HANDSHAKE_INFO             [variable; depends on handshake type
+                                   used.]
+
+   If the cookie matches the rendezvous cookie set on any
+   not-yet-connected circuit on the rendezvous point, the rendezvous
+   point connects the two circuits, and sends a RENDEZVOUS2 cell to the
+   client containing the contents of the RENDEZVOUS1 cell.
+
+   Upon receiving the RENDEZVOUS2 cell, the client verifies that the
+   HANDSHAKE_INFO correctly completes a handshake, and uses the
+   handshake output to derive shared keys for use on the circuit.
+
+   [TODO: Should we encrypt HANDSHAKE_INFO as we did INTRODUCE2
+   contents? It's not necessary, but it could be wise. Similarly, we
+   should make it extensible.]
+
+4.3. Using legacy hosts as rendezvous points
+
+   The behavior of ESTABLISH_RENDEZVOUS is unchanged from older versions
+   of this protocol, except that relays should now ignore unexpected
+   bytes at the end.
+
+   Old versions of Tor required that RENDEZVOUS cell payloads be exactly
+   168 bytes long. All shorter rendezvous payloads should be padded to
+   this length with [00] bytes.
+
+5. Encrypting data between client and host
+
+   A successfully completed handshake, as embedded in the
+   INTRODUCE/RENDEZVOUS cells, gives the client and hidden service host
+   a shared set of keys Kf, Kb, Df, Db, which they use for sending
+   end-to-end traffic encryption and authentication as in the regular
+   Tor relay encryption protocol, applying encryption with these keys
+   before other encryption, and decrypting with these keys before other
+   encryption. The client encrypts with Kf and decrypts with Kb; the
+   service host does the opposite.
+
+6. Open Questions:
+
+   Scaling hidden services is hard. There are on-going discussions that
+   you might be able to help with. See [SCALING-REFS].
+
+   How can we improve the HSDir unpredictability design proposed in
+   [SHAREDRANDOM]? See [SHAREDRANDOM-REFS] for discussion.
+
+   How can hidden service addresses become memorable while retaining
+   their self-authenticating and decentralized nature? See
+   [HUMANE-HSADDRESSES-REFS] for some proposals; many more are possible.
+
+   Hidden Services are pretty slow. Both because of the lengthy setup
+   procedure and because the final circuit has 6 hops. How can we make
+   the Hidden Service protocol faster? See [PERFORMANCE-REFS] for some
+   suggestions.
+
+References:
+
+[KEYBLIND-REFS]:
+        https://trac.torproject.org/projects/tor/ticket/8106
+        https://lists.torproject.org/pipermail/tor-dev/2012-September/004026.html
+
+[SHAREDRANDOM-REFS]:
+        https://trac.torproject.org/projects/tor/ticket/8244
+        https://lists.torproject.org/pipermail/tor-dev/2013-November/005847.html
+        https://lists.torproject.org/pipermail/tor-talk/2013-November/031230.html
+
+[SCALING-REFS]:
+        https://lists.torproject.org/pipermail/tor-dev/2013-October/005556.html
+
+[HUMANE-HSADDRESSES-REFS]:
+        https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/ideas/xxx-onion-nyms.txt
+        http://archives.seul.org/or/dev/Dec-2011/msg00034.html
+
+[PERFORMANCE-REFS]:
+        "Improving Efficiency and Simplicity of Tor circuit
+        establishment and hidden services" by Overlier, L., and
+        P. Syverson
+
+        [TODO: Need more here! Do we have any? :( ]
+
+[ATTACK-REFS]:
+        "Trawling for Tor Hidden Services: Detection, Measurement,
+        Deanonymization" by Alex Biryukov, Ivan Pustogarov,
+        Ralf-Philipp Weinmann
+
+        "Locating Hidden Servers" by Lasse Øverlier and Paul
+        Syverson
+
+[ED25519-REFS]:
+        "High-speed high-security signatures" by Daniel
+        J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and
+        Bo-Yin Yang. http://cr.yp.to/papers.html#ed25519
+
+
+Appendix A. Signature scheme with key blinding [KEYBLIND]
+
+  As described in [IMD:DIST] and [SUBCRED] above, we require a "key
+  blinding" system that works (roughly) as follows:
+
+        There is a master keypair (sk, pk).
+
+        Given the keypair and a nonce n, there is a derivation function
+        that gives a new blinded keypair (sk_n, pk_n).  This keypair can
+        be used for signing.
+
+        Given only the public key and the nonce, there is a function
+        that gives pk_n.
+
+        Without knowing pk, it is not possible to derive pk_n; without
+        knowing sk, it is not possible to derive sk_n.
+
+        It's possible to check that a signature make with sk_n while
+        knowing only pk_n.
+
+        Someone who sees a large number of blinded public keys and
+        signatures made using those public keys can't tell which
+        signatures and which blinded keys were derived from the same
+        master keypair.
+
+        You can't forge signatures.
+
+        [TODO: Insert a more rigorous definition and better references.]
+
+
+  We propose the following scheme for key blinding, based on Ed25519.
+
+  (This is an ECC group, so remember that scalar multiplication is the
+  trapdoor function, and it's defined in terms of iterated point
+  addition. See the Ed25519 paper [Reference ED25519-REFS] for a fairly
+  clear writeup.)
+
+  Let the basepoint be written as B. Assume B has prime order l, so
+  lB=0. Let a master keypair be written as (a,A), where a is the private
+  key and A is the public key (A=aB).
+
+  To derive the key for a nonce N and an optional secret s, compute the
+  blinding factor h as H(A | s, B, N), and let:
+
+      private key for the period:   a' = h a
+      public key for the period:    A' = h' A = (ha)B
+
+  Generating a signature of M: given a deterministic random-looking r
+  (see EdDSA paper), take R=rB, S=r+hash(R,A',M)ah mod l. Send signature
+  (R,S) and public key A'.
+
+  Verifying the signature: Check whether SB = R+hash(R,A',M)A'.
+
+  (If the signature is valid,
+       SB = (r + hash(R,A',M)ah)B
+          = rB + (hash(R,A',M)ah)B
+          = R + hash(R,A',M)A' )
+
+  See [KEYBLIND-REFS] for an extensive discussion on this scheme and
+  possible alternatives. I've transcribed this from a description by
+  Tanja Lange at the end of the thread. [TODO: We'll want a proof for
+  this.]
+
+  (To use this with Tor, set N = INT_8(period-number) | INT_8(Start of
+  period in seconds since epoch).)
+
+Appendix B. Selecting nodes [PICKNODES]
+
+  Picking introduction points
+  Picking rendezvous points
+  Building paths
+  Reusing circuits
+
+  (TODO: This needs a writeup)
+
+Appendix C. Recommendations for searching for vanity .onions [VANITY]
+
+  EDITORIAL NOTE: The author thinks that it's silly to brute-force the
+  keyspace for a key that, when base-32 encoded, spells out the name of
+  your website. It also feels a bit dangerous to me. If you train your
+  users to connect to
+
+      llamanymityx4fi3l6x2gyzmtmgxjyqyorj9qsb5r543izcwymle.onion
+
+  I worry that you're making it easier for somebody to trick them into
+  connecting to
+
+      llamanymityb4sqi0ta0tsw6uovyhwlezkcrmczeuzdvfauuemle.onion
+
+  Nevertheless, people are probably going to try to do this, so here's a
+  decent algorithm to use.
+
+  To search for a public key with some criterion X:
+
+        Generate a random (sk,pk) pair.
+
+        While pk does not satisfy X:
+
+            Add the number 1 to sk
+            Add the scalar B to pk
+
+        Return sk, pk.
+
+  This algorithm is safe [source: djb, personal communication] [TODO:
+  Make sure I understood correctly!] so long as only the final (sk,pk)
+  pair is used, and all previous values are discarded.
+
+  To parallelize this algorithm, start with an independent (sk,pk) pair
+  generated for each independent thread, and let each search proceed
+  independently.
+
+Appendix D. Numeric values reserved in this document
+
+  [TODO: collect all the lists of commands and values mentioned above]
diff --git a/proposals/225-strawman-shared-rand.txt b/proposals/225-strawman-shared-rand.txt
new file mode 100644
index 0000000..4062ef1
--- /dev/null
+++ b/proposals/225-strawman-shared-rand.txt
@@ -0,0 +1,113 @@
+Filename: 225-strawman-shared-rand.txt
+Title: Strawman proposal: commit-and-reveal shared rng
+Author: Nick Mathewson
+Created: 2013-11-29
+Status: Draft
+
+1. Introduction
+
+  This is a strawman proposal: I don't think we should actually build
+  it.  It's just a simple writeup of the more trivial commit-then-reveal
+  protocol for generating a shared random value.  It's insecure to the
+  extent that an adversary who controls b of the authorities gets to
+  choose among 2^b outcomes for the result of the protocol.
+
+  See proposal 224, section HASHRING for some motivation of why we want
+  one of these in Tor.
+
+  Let's do better!
+
+  [TODO: Are we really stuck with Tor's nasty metaformat here?]
+
+2. The protocol
+
+  Here's a protocol for producing a shared random value. It should run
+  less frequently than the directory consensus algorithm. It runs in
+  these phases.
+
+    1. COMMITMENT
+    2. REVEAL
+    3. COMPUTE SHARED RANDOM
+
+  It should be implemented by software other than Tor, which should be
+  okay for authorities.
+
+  Note: This is not a great protocol. It has a number of failure
+  modes. Better protocols seem hard to implement, though, and it ought
+  to be possible to drop in a replacement here, if we do it right.
+
+  At the start of phase 1, each participating authority publishes a
+  statement of the form:
+
+      shared-random 1
+      shared-random-type commit
+      signing-key-certification (certification here; see proposal 220)
+      commitment-key-certification (certification here; see proposal 220)
+      published YYYY-MM-DD HH:MM:SS
+      period-start YYYY-MM-DD HH:MM:SS
+      attempt INT
+      commitment sha512 C
+      signature (made with commitment key; see proposal 220)
+
+  The signing key is the one used for consensus votes, signed by the
+  directory authority identity key. The commitment key is used for this
+  protocol only. The signature is made with the commitment key. The
+  period-start value is the start of the period for which the shared
+  random value should be in use. The attempt value starts at 1, and
+  increments by 1 for each time that the protocol fails.
+
+  The other fields should be self-explanatory.
+
+  The commitment value C is a base64-encoded SHA-512 hash of a 256-bit
+  random value R.
+
+  During the rest of phase 1, every authority collects the commitments
+  from other authorities, and publishes them to other authorities, as
+  they do today with directory votes.
+
+  At the start of phase 2, each participating authority publishes:
+
+      shared-random 1
+      shared-random-type reveal
+      signing-key-certification (certification here; see proposal 220)
+      commitment-key-certification (certification here; see proposal 220)
+      received-commitment ID sig
+      received-commitment ID sig
+      published YYYY-MM-DD HH:MM:SS
+      period-start YYYY-MM-DD HH:MM:SS
+      attempt INT
+      commitment sha512 C
+      reveal R
+      signature (made with commitment key; see proposal 220)
+
+  The R value is the one used to generate C. The received-commitment
+  lines are the signatures on the documents from other authorities in
+  phase 1. All other fields are as in the commitments.
+
+  During the rest of phase 2, every authority collects the
+  reveals from other authorities, as above with commitments.
+
+  At the start of phase 3, each participating authority either has a
+  reveal from every authority that it received a commitment from, or it
+  does not. Each participating authority then says
+
+      shared-random 1
+      shared-random-type finish
+      signing-key-certification (certification here; see proposal 220)
+      commitment-key-certification (certification here; see proposal 220)
+      received-commitment ID sig R
+      received-commitment ID sig R ...
+      published YYYY-MM-DD HH:MM:SS
+      period-start YYYY-MM-DD HH:MM:SS
+      attempt INT
+      consensus C
+      signature (made with commitment key; see proposal 220)
+
+  Where C = SHA256(ID | R | ID | R | ID | R | ...) where the ID
+  values appear in ascending order and the R values appear after
+  their corresponding ID values.
+
+  See [SHAREDRANDOM-REFS] for more discussion here.
+
+  (TODO: should this be its own spec?  If so, does it have to use our
+  regular metaformat or can it use something less sucky?)