[tor-dev] Proposal 300: Walking Onions: Scaling and Saving Bandwidth

Michael Rogers michael at briarproject.org
Tue Feb 5 17:44:13 UTC 2019

Argh, I'm really sorry, I thought I'd reached the end of the proposal
but my questions were addressed further down. Sorry for the noise.


On 05/02/2019 17:42, Michael Rogers wrote:
> I'm very happy to see this proposal! Two quick questions about relay
> selection:
> * Can a client specify that it wants an exit node whose policy allows
> something unusual, e.g. exiting to a port that's not allowed by the
> default policy? If not, does the client need to keep picking exit nodes
> until it gets a SNIP with a suitable policy?
> * Similarly, if a client has restrictions on the guard nodes it can
> connect to (fascist firewall or IPv4/v6 restrictions, for example), does
> it need to keep picking guards via the directory fallback circuit until
> it gets a suitable one?
> In both cases, perhaps a client with unusual requirements could first
> download the consensus, find a relay matching its requirements, then
> send that relay's index in its extend cell, so the relay receiving the
> extend cell wouldn't know whether the index was picked randomly by a
> client with no special requirements, or non-randomly by a client with
> special requirements?
> I think this would allow the majority of clients to save bandwidth by
> not downloading the consensus, without allowing relays to distinguish
> the minority of clients with unusual exit/guard requirements. (The
> presence of the full consensus on disk would indicate that the client
> had unusual exit/guard requirements at some point, however.)
> Cheers,
> Michael
> On 05/02/2019 17:02, Nick Mathewson wrote:
>> Filename: 300-walking-onions.txt
>> Title: Walking Onions: Scaling and Saving Bandwidth
>> Author: Nick Mathewson
>> Created: 5-Feb-2019
>> Status: Draft
>> 0. Status
>>    This proposal describes a mechanism called "Walking Onions" for
>>    scaling the Tor network and reducing the amount of client bandwidth
>>    used to maintain a client's view of the Tor network.
>>    This is a draft proposal; there are problems left to be solved and
>>    questions left to be answered.  Once those parts are done, we can
>>    fill in section 4 with the final details of the design.
>> 1. Introduction
>>    In the current Tor network design, we assume that every client has a
>>    complete view of all the relays in the network.  To achieve this,
>>    clients download consensus directories at regular intervals, and
>>    download descriptors for every relay listed in the directory.
>>    The substitution of microdescriptors for regular descriptors
>>    (proposal 158) and the use of consensus diffs (proposal 140) have
>>    lowered the bytes that clients must dedicate to directory operations.
>>    But we still face the problem that, if we force each client to know
>>    about every relay in the network, each client's directory traffic
>>    will grow linearly with the number of relays in the network.
>>    Another drawback in our current system is that client directory
>>    traffic is front-loaded: clients need to fetch an entire directory
>>    before they begin building circuits.  This places extra delays on
>>    clients, and extra load on the network.
>>    To anonymize the world, we will need to scale to a much larger number
>>    of relays and clients: requiring clients to know about every relay in
>>    the set simply won't scale, and requiring every new client to download
>>    a large document is also problematic.
>>    There are obvious responses here, and some other anonymity tools have
>>    taken them.  It's possible to have a client only use a fraction of
>>    the relays in a network--but doing so opens the client to _epistemic
>>    attacks_, in which the difference in clients' views of the
>>    network is used to partition their traffic.  It's also possible to
>>    move the problem of selecting relays from the client to the relays
>>    themselves, and let each relay select the next relay in turn--but
>>    this choice opens the client to _route capture attacks_, in which a
>>    malicious relay selects only other malicious relays.
>>    In this proposal, I'll describe a design for eliminating up-front
>>    client directory downloads.  Clients still choose relays at random,
>>    but without ever having to hold a list of all the relays. This design
>>    does not require clients to trust relays any more than they do today,
>>    or open clients to epistemic attacks.
>>    I hope to maintain feature parity with the current Tor design; I'll
>>    list the places in which I haven't figured out how to do so yet.
>>    I'm naming this design "walking onions".  The walking onion (Allium x
>>    proliferum) reproduces by growing tiny little bulbs at the
>>    end of a long stalk.  When the stalk gets too top-heavy, it flops
>>    over, and the little bulbs start growing somewhere new.
>>    The rest of this document will run as follows.  In section 2, I'll
>>    explain the ideas behind the "walking onions" design, and how they
>>    can eliminate the need for regular directory downloads.  In section 3, I'll
>>    answer a number of follow-up questions that arise, and explain how to
>>    keep various features in Tor working.  Section 4 (not yet written)
>>    will elaborate all the details needed to turn this proposal into a
>>    concrete set of specification changes.
>> 2. Overview
>> 2.1. Recapping proposal 141
>>    Back in Proposal 141 ("Download server descriptors on demand"), Peter
>>    Palfrader proposed an idea for eliminating ahead-of-time descriptor
>>    downloads.  Instead of fetching all the descriptors in advance, a
>>    client would fetch the descriptor for each relay in its path right
>>    before extending the circuit to that relay.  For example, if a client
>>    has a circuit from A->B and wants to extend the circuit to C, the
>>    client asks B for C's descriptor, and then extends the circuit to C.
>>    (Note that the client needs to fetch the descriptor every time it
>>    extends the circuit, so that an observer can't tell whether the
>>    client already had the descriptor or not.)
>>    There are a couple of limitations for this design:
>>       * It still requires clients to download a consensus.
>>       * It introduces a extra round-trip to each hop of the circuit
>>         extension process.
>>    I'll show how to solve these problems in the two sections below.
>> 2.2. An observation about the ntor handshake.
>>    I'll start with an observation about our current circuit extension
>>    handshake, ntor: it should not actually be necessary to know a
>>    relay's onion key before extending to it.
>>    Right now, the client sends:
>>          NODEID     (The relay's identity)
>>          KEYID      (The relay's public onion key)
>>          CLIENT_PK  (a diffie-hellman public key)
>>    and the relay responds with:
>>          SERVER_PK  (a diffie-hellman public key)
>>          AUTH       (a function of the relay's private keys and
>>                      *all* of the public keys.)
>>    Both parties generate shared symmetric keys from the same inputs
>>    that are are used to create the AUTH value.
>>    The important insight here is that we could easily change
>>    this handshake so that the client sends only CLIENT_PK, and receives
>>    NODEID and KEYID as part of the response.
>>    In other words, the client needs to know the relay's onion key to
>>    _complete_ the handshake, but doesn't actually need to know the
>>    relay's onion key in order to _initiate_ the handshake.
>>    This is the insight that will let us save a round trip:  When the
>>    client goes to extend a circuit from A->B to C, it can send B a
>>    request to extend to C and retrieve C's descriptor in a single step.
>>    Specifically, the client sends only CLIENT_PK, and relay B can include C's
>>    keys as part of the EXTENDED cell.
>> 2.3. Extending by certified index
>>    Now I'll explain how the client can avoid having to download a
>>    list of relays entirely.
>>    First, let's look at how a client chooses a random relay today.
>>    First, the client puts all of the relays in a list, and computes a
>>    weighted bandwidth for each one. For example, suppose the relay
>>    identities are R1, R2, R3, R4, and R5, and their bandwidth weights
>>    are 50, 40, 30, 20, and 10.  The client makes a table like this:
>>       Relay   Weight     Range of index values
>>       R1      50         0..49
>>       R2      40         50..89
>>       R3      30         90..119
>>       R4      20         120..139
>>       R5      10         140..149
>>    To choose a random relay, the client picks a random index value
>>    between 0 and 149 inclusive, and looks up the corresponding relay in
>>    the table.  For example, if the client's random number is 77, it will
>>    choose R2.  If its random number is 137, it chooses R4.
>>    The key observation for the "walking onions" design is that the
>>    client doesn't actually need to construct this table itself.
>>    Instead, we will have this table be constructed by the authorities
>>    and distributed to all the relays.
>>    Here's how it works: let's have the authorities make a new kind of
>>    consensus-like thing.  We'll call it an Efficient Network Directory
>>    with Individually Verifiable Entries, or "ENDIVE" for short.  This
>>    will differ from the client's index table above in two ways.  First,
>>    every entry in the ENDIVE is normalized so that the bandwidth
>>    weights maximum index is 2^32-1:
>>        Relay      Normalized weight    Range of index values
>>        R1         0x55555546           0x00000000..0x55555545
>>        R2         0x44444438           0x55555546..0x9999997d
>>        R3         0x3333332a           0x9999997e..0xcccccca7
>>        R4         0x2222221c           0xcccccca8..0xeeeeeec3
>>        R5         0x1111113c           0xeeeeeec4..0xffffffff
>>    Second, every entry in the ENDIVE is timestamped and signed by the
>>    authorities independently, so that when a client sees a line from the
>>    table above, it can verify that it came from an authentic ENDIVE.
>>    When a client has chosen a random index, one of these entries will
>>    prove to the client that a given relay corresponds to that index.
>>    Because of this property, we'll be calling these entries "Separable
>>    Network Index Proofs", or "SNIP"s for short.
>>    For example, a single SNIP from the table above might consist of:
>>      * A range of times during which this SNIP is valid
>>      * R1's identity
>>      * R1's ntor onion key
>>      * R1's address
>>      * The index range 0x00000000..0x55555545
>>      * A signature of all of the above, by a number of authorities
>>    Let's put it together. Suppose that the client has a circuit from
>>    A->B, and it wants to extend to a random relay, chosen randomly
>>    weighted by bandwidth.
>>    1. The client picks a random index value between 0 and 2**32 - 1.  It
>>       sends that index to relay B in its EXTEND cell, along with a
>>       g^x value for the ntor handshake.
>>       Note: the client doesn't send an address or identity for the next
>>       relay, since it doesn't know what relay it has chosen!  (The
>>       combination of an index and a g^x value is what I'm calling a
>>       "walking onion".)
>>    2. Now, relay B looks up the index in its most recent ENDIVE, to
>>       learn which relay the client selected.
>>       (For example, suppose that the client's random index value is
>>       0x50000001.  This index value falls between 0x00000000 and
>>       0x55555546 in the table above, so the relay B sees that the client
>>       has chosen R1 as its next hop.)
>>    3. Relay B sends a create cell to R1 as usual.  When it gets a
>>       CREATED reply, it includes the authority-signed SNIP for
>>       R1 as part of the EXTENDED cell.
>>    4. As part of verifying the handshake, the client verifies that the
>>       SNIP was signed by enough authorities, that its timestamp
>>       is recent enough, and that it actually corresponds to the
>>       random index that the client selected.
>>    Notice the properties we have with this design:
>>        - Clients can extend circuits without having a list of all the
>>          relays.
>>        - Because the client's random index needs to match a routing
>>          entry signed by the authorities, the client is still selecting
>>          a relay randomly by weight.  A hostile relay cannot choose
>>          which relay to send the client.
>>    On a failure to extend, a relay should still report the routing entry
>>    for the other relay that it couldn't connect to.  As before, a client
>>    will start a new circuit if a partially constructed circuit is a
>>    partial failure.
>>    We could achieve a reliability/security tradeoff by letting clients
>>    offer the relay a choice of two or more indices to extend to.
>>    This would help reliability, but give the relay more influence over
>>    the path.  We'd need to analyze this impact.
>>    In the next section, I'll discuss a bunch of details that we need to
>>    straighten out in order to make this design work.
>> 3. Sorting out the details.
>> 3.1. Will these routing entries fit in EXTEND2 and EXTENDED2 cells?
>>    The EXTEND2 cell is probably big enough for this design.  The random
>>    index that the client sends can be a new "link specifier" type,
>>    replacing the IP and identity link specifiers.
>>    The EXTENDED2 cell is likely to need to grow here.  We'll need to
>>    implement proposal 249 ("Allow CREATE cells with >505 bytes of
>>    handshake data") so that EXTEND2 and EXTENDED2 cells can be larger.
>> 3.2. How should SNIPs be signed?
>>    We have a few options, and I'd like to look into the possibilities
>>    here more closely.
>>    The simplest possibility is to use **multiple signatures** on each
>>    SNIP, the way we do today for consensuses.  These signatures should
>>    be made using medium-term Ed25519 keys from the authorities.  At a
>>    cost of 64 bytes per signature, at 9 authorities, we would need 576
>>    bytes for each SNIP.  These signatures could be batch-verified to
>>    save time at the client side.  Since generating a signature takes
>>    around 20 usec on my mediocre laptop, authorities should be able to
>>    generate this many signatures fairly easily.
>>    Another possibility is to use a **threshold signature** on each SNIP,
>>    so that the authorities collaboratively generate a short signature
>>    that the clients can verify.  There are multiple threshold signature
>>    schemes that we could consider here, though I haven't yet found one
>>    that looks perfect.
>>    Another possibility is to use organize the SNIPs in a **merkle tree
>>    with a signed root**.  For this design, clients could download the
>>    signed root periodically, and receive the hash-path from the signed
>>    root to the SNIP.  This design might help with
>>    certificate-transparency-style designs, and it would be necessary if we
>>    ever want to move to a postquantum signature algorithm that requires
>>    large signatures.
>>    Another possibility (due to a conversation among Chelsea Komlo, Sajin
>>    Sasy, and Ian Goldberg), is to *use SNARKs*.  (Why not?  All the cool
>>    kids are doing it!)  For this, we'd have the clients download a
>>    signed hash of the ENDIVE periodically, and have the authorities
>>    generate a SNARK for each SNIP, proving its presence in that
>>    document.
>> 3.3. How can we detect authority misbehavior?
>>    We might want to take countermeasures against the possibility that a
>>    quorum of corrupt or compromised authorities give some relays a
>>    different set of SNIPs than they give other relays.
>>    If we incorporate a merkle tree or a hash chain in the design, we can
>>    use mechanisms similar to certificate transparency to ensure that the
>>    authorities have a consistent log of all the entries that they have
>>    ever handed out.
>> 3.4. How many types of weighted node selection are there, and how do we
>>      handle them?
>>    Right now, there are multiple weights that we use in Tor:
>>       * Weight for exit
>>       * Weight for guard
>>       * Weight for middle node
>>    We also filter nodes for several properties, such as flags they have.
>>    To reproduce this behavior, we should enumerate the various weights
>>    and filters that we use, and (if there are not too many) create a
>>    separate index for each.  For example, the Guard index would weight
>>    every node for selection as guard, assigning 0 weight to non-Guard
>>    nodes.  The Exit index would weight every node for selection as an
>>    exit, assigning 0 weight to non-Exit nodes.
>>    When choosing a relay, the client would have to specify which index
>>    to use.  We could either have a separate (labeled) set of SNIPs
>>    entries for each index, or we could have each SNIP have a separate
>>    (labeled) index range for each index.
>>    REGRESSION: the client's choice of which index to use would leak the
>>    next router's position and purpose in the circuit.  This information
>>    is something that we believe relays can infer now, but it's not a
>>    desired feature that they can.
>> 3.5. Does this design break onion service introduce handshakes?
>>    In rend-spec-v3.txt section 3.3.2, we specify a variant of ntor for
>>    use in INTRODUCE2 handshakes.  It allows the client to send encrypted
>>    data as part of its initial ntor handshake, but requires the client
>>    to know the onion service's onion key before it sends its initial
>>    handshake.
>>    That won't be a problem for us here, though: we still require clients
>>    to fetch onion service descriptors before contacting a onion
>>    service.
>> 3.6. How does the onion service directory work here?
>>    The onion service directory is implemented as a hash ring, where
>>    each relay's position in the hash ring is decided by a hash of its
>>    identity, the current date, and a shared random value that the
>>    authorities compute each day.
>>    To implement this hash ring using walking onions, we would need to
>>    have an extra index based not on bandwidth, but on position in the
>>    hash ring.  Then onion services and clients could build a circuit,
>>    then extend it one more hop specifying their desired index in the
>>    hash ring.
>>    We could either have a command to retrieve a trio of hashring-based
>>    routing entries by index, or to retrieve (or connect to?) the n'th item
>>    after a given hashring entry.
>> 3.7. How can clients choose guard nodes?
>>    We can reuse the fallback directories here.  A newly bootstrapping
>>    client would connect to a fallback directory, then build a three-hop
>>    circuit, and finally extend the three-hop circuit by indexing to a
>>    random guard node.  The random guard node's SNIP would
>>    contain the information that the client needs to build real circuits
>>    through that guard in the future.  Because the client would be
>>    building a three-hop circuit, the fallback directory would not learn
>>    the client's guards.
>>    (Note that even if the extend attempt fails, we should still pick the
>>    node as a possible guard based on its router entry, so that other
>>    nodes can't veto our choice of guards.)
>> 3.8. Does the walking onions design preclude postquantum circuit handshakes?
>>    Not at all!  Both proposal 263 (ntru) and proposal 270 (newhope) work
>>    by having the client generate an ephemeral key as part of its initial
>>    handshake.  The client does not need to know the relay's onion key to
>>    do this, so we can still integrate those proposals with this one.
>> 3.9. Does the walking onions design stop us from changing the network
>>      topology?
>>    For Tor to continue to scale, we will someday need to accept that not
>>    every relay can be simultaneously connected to every other relay.
>>    Therefore, we will need to move from our current clique topology
>>    assumption to some other topology.
>>    There are also proposals to change node selection rules to generate
>>    routes providing better performance, or improved resistance to local
>>    adversaries.
>>    We can, I think, implement this kind of proposal by changing the way
>>    that ENDIVEs are generated.  Instead giving every relay the same
>>    ENDIVE, the authorities would generate different ENDIVEs for
>>    different relays, depending on the probability distribution of which
>>    relay should be chosen after which in the network topology.  In the
>>    extreme case, this would produce O(n) ENDIVEs and O(n^2) SNIPs.  In
>>    practice, I hope that we could do better by having the network
>>    topology be non-clique, and by having many relays share the same
>>    distribution of successors.
>> 3.10. How can clients handle exit policies?
>>    This is an unsolved challenge.  If the client tells the middle relay
>>    its target port, it leaks information inappropriately.
>>    One possibility is to try to gather exit policies into common
>>    categories, such as "most ports supported" and "most common ports
>>    supported".
>>    Another (inefficient) possibility is for clients to keep trying exits
>>    until they find one that works.
>>    Another (inefficient) possibility is to require that clients who use
>>    unusual ports fall back to the old mechanism for route selection.
>> 3.11. Can this approach support families?
>>    This is an unsolved challenge.
>>    One (inefficient) possibility is for clients to generate circuits and
>>    discard those that use multiple relays in the same family.
>>    One (not quite compatible) possibility is for the authorities to sort
>>    the ENDIVE so that relays in the same family are adjacent to
>>    one another.  The index-bounds part of each SNIP would also
>>    have to include the bounds of the family.  This approach is not quite
>>    compatible with the status quo, because it prevents relays from
>>    belonging to more than one family.
>>    One interesting possibility (due to Chelsea Komlo, Sajin Sasy, and
>>    Ian Goldberg) is for the middle node to take responsibility for
>>    family enforcement. In this design, the client might offer the middle
>>    node multiple options for the next relay's index, and the middle node
>>    would choose the first such relay that is neither in its family nor
>>    its predecessor's family.  We'd need to look for a way to make sure
>>    that the middle node wasn't biasing the path selection.
>>    (TODO: come up with more ideas here.)
>> 3.12. Can walking onions support IP-based and country-based restrictions?
>>    This is an unsolved challenge.
>>    If the user's restrictions do not exclude most paths, one
>>    (inefficient) possibility is for the user to generate paths until
>>    they generate one that they like.  This idea becomes inefficient
>>    if the user is excluding most paths.
>>    Another (inefficient and fingerprintable) possibility is to require
>>    that clients who use complex path restrictions fall back to the old
>>    mechanism for route selection.
>>    (TODO: come up with better ideas here.)
>> 3.13. What scaling problems have we not solved with this design?
>>    The walking onions design doesn't solve (on its own) the problem that
>>    the authorities need to know about every relay, and arrange to have
>>    every relay tested.
>>    The walking onions design doesn't solve (on its own) the problem that
>>    relays need to have a list of all the relays.  (But see section 3.9
>>    above.)
>> 3.14. Should we still have clients download a consensus when they're
>>       using walking onions?
>>    There are some fields in the current consensus directory documents
>>    that the clients will still need, like the list of supported
>>    protocols and network parameters.  A client that uses walking onions
>>    should download a new flavor of consensus document that contains only
>>    these fields, and does not list any relays.  In some signature
>>    schemes, this consensus would contain a digest of the ENDIVE -- see
>>    3.2 above.
>>    (Note that this document would be a "consensus document" but not a
>>    "consensus directory", since it doesn't list any relays.)
>> 4. Putting it all together
>>    [This is the section where, in a later version of this proposal, I
>>    would specify the exact behavior and data formats to be used here.
>>    Right now, I'd say we're too early in the design phase.]
>> A.1. Acknowledgments
>>    Thanks to Peter Palfrader for his original design in proposal 141,
>>    and to the designers of PIR-Tor, both of which inspired aspects of
>>    this Walking Onions design.
>>    Thanks to Chelsea Komlo, Sajin Sasy, and Ian Goldberg for feedback on
>>    an earlier version of this design.
>>    Thanks to David Goulet, Teor, and George Kadianakis for commentary on
>>    earlier versions of this draft.
>> A.2. Additional ideas
>>    Teor notes that there are ways to try to get this idea to apply to
>>    one-pass circuit construction, something like the old onion design.
>>    We might be able to derive indices and keys from the same seeds,
>>    even.  I don't see a way to do this without losing forward secrecy,
>>    but it might be worth looking at harder.
>> _______________________________________________
>> tor-dev mailing list
>> tor-dev at lists.torproject.org
>> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>> _______________________________________________
>> tor-dev mailing list
>> tor-dev at lists.torproject.org
>> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0x11044FD19FC527CC.asc
Type: application/pgp-keys
Size: 17118 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20190205/df618bd0/attachment-0001.key>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20190205/df618bd0/attachment-0001.sig>

More information about the tor-dev mailing list