Add mikeperry's padding negotiation proposal and give it a number.

1 files changed, 628 insertions, 0 deletions

diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt
new file mode 100644
index 0000000..e4da004
--- /dev/null
+++ b/proposals/254-padding-negotiation.txt
@@ -0,0 +1,628 @@
+Filename: 254-padding-negotiation.txt
+Title: Padding Negotiation
+Authors: Mike Perry
+Created: 01 September 2015
+Status: Draft
+
+
+0. Overview
+
+This proposal aims to describe mechanisms for requesting various types
+of padding from relays.
+
+These padding primitives are general enough to use to defend against
+both website traffic fingerprinting as well as hidden service circuit
+setup fingerprinting.
+
+
+1. Motivation
+
+Tor already supports both link-level padding via (CELL_PADDING cell
+types), as well as circuit-level padding (via RELAY_COMMAND_DROP relay
+cells).
+
+Unfortunately, there is no way for clients to request padding from
+relays, or request that relays not send them padding to conserve
+bandwidth. This proposal aims to create a mechanism for clients to do
+both of these.
+
+It also establishes consensus parameters to limit the amount of padding
+that relays will send, to prevent custom wingnut clients from requesting
+too much.
+
+
+2. Link-level padding
+
+Padding is most useful if it can defend against a malicious or
+compromised guard node. However, link-level padding is still useful to
+defend against an adversary that can merely observe a Guard node
+externally, such as for low-resolution netflow-based attacks (see
+Proposal 251[1]).
+
+In that scenario, the primary negotiation mechanism we need is a way for
+mobile clients to tell their Guards to stop padding, or to pad less
+often. The following Trunnel payloads should cover the needed
+parameters:
+
+    const CELL_PADDING_COMMAND_STOP = 1;
+    const CELL_PADDING_COMMAND_START = 2;
+
+    /* This command tells the relay to stop sending any periodic
+       CELL_PADDING cells. */
+    struct cell_padding_stop {
+      u8 command IN [CELL_PADDING_COMMAND_STOP];
+    };
+
+    /* This command tells the relay to alter its min and max netflow
+       timeout range values, and send padding at that rate (resuming
+       if stopped). */
+    struct cell_padding_start {
+      u8 command IN [CELL_PADDING_COMMAND_START];
+
+      /* Min must not be lower than the current consensus parameter
+         nf_ito_low. */
+      u16 ito_low_ms;
+
+      /* Max must not be lower than ito_low_ms */
+      u16 ito_high_ms;
+    };
+
+More complicated forms of link-level padding can still be specified
+using the primitives in Section 3, by using "leaky pipe" topology to
+send the RELAY commands to the Guard node instead of to later nodes in
+the circuit.
+
+
+3. End-to-end circuit padding
+
+For circuit-level padding, we need two types of additional features: the
+ability to schedule additional incoming cells at one or more fixed
+points in the future, and the ability to schedule a statistical
+distribution of arbitrary padding to overlay on top of non-padding
+traffic (aka "Adaptive Padding").
+
+In both cases, these messages will be sent from clients to middle nodes
+using the "leaky pipe" property of the 'recognized' field of RELAY
+cells, allowing padding to originate from middle nodes on a circuit in a
+way that is not detectable from the Guard node.
+
+This same mechanism can also be used to request padding from the Guard
+node itself, to achieve link-level padding without the additional
+overhead requirements on middle nodes.
+
+3.1. Fixed-schedule padding message (RELAY_COMMAND_PADDING_SCHEDULE)
+
+The fixed schedule padding will be encoded in a
+RELAY_COMMAND_PADDING_SCHEDULE cell. It specifies a set of up to 80
+fixed time points in the future to send cells.
+
+XXX: 80 timers is a lot to allow every client to create. We may want to
+have something that checks this structure to ensure it actually
+schedules no more than N in practice, until we figure out how to
+optimize either libevent or timer scheduling/packet delivery. See also
+Section 4.3.
+
+The RELAY_COMMAND_PADDING_SCHEDULE body is specified in Trunnel as
+follows:
+
+    struct relay_padding_schedule {
+       u8 schedule_length IN [1..80];
+
+       /* Number of microseconds before sending cells (cumulative) */
+       u32 when_send[schedule_length];
+
+       /* Number of cells to send at time point sum(when_send[0..i]) */
+       u16 num_cells[schedule_length];
+
+       /* Adaptivity: If 1, and server-originating cells arrive before the
+          next when_send time, then decrement the next non-zero when_send
+          index, so we don't send a padding cell then, too */
+       u8 adaptive IN [0,1];
+    };
+
+To allow both high-resolution time values, and the ability to specify
+timeout values far in the future, the time values are cumulative. In
+other words, sending a cell with when_send = [MAX_INT, MAX_INT, MAX_INT,
+0...] and num_cells = [0, 0, 100, 0...] would cause the relay to reply
+with 100 cells in 3*MAX_INT microseconds from the receipt of this cell.
+
+This scheduled padding is non-periodic. For any forms of periodic
+padding, implementations should use the RELAY_COMMAND_PADDING_ADAPTIVE
+cell from Section 3.2 instead.
+
+3.2. Adaptive Padding message (RELAY_COMMAND_PADDING_ADAPTIVE)
+
+The following message is a generalization of the Adaptive Padding
+defense specified in "Timing Attacks and Defenses"[2].
+
+The message encodes either one or two state machines, each of which can
+contain one or two histograms ("Burst" and "Gap") governing their
+behavior.
+
+The "Burst" histogram specifies the delay probabilities for sending a
+padding packet after the arrival of a non-padding data packet.
+
+The "Gap" histogram specifies the delay probabilities for sending
+another padding packet after a padding packet was just sent from this
+node. This self-triggering property of the "Gap" histogram allows the
+construction of multi-packet padding trains using a simple statistical
+distribution.
+
+Both "Gap" and "Burst" histograms each have a special "Infinity" bin,
+which means "We have decided not to send a packet".
+
+Each histogram is combined with state transition information, which
+allows a client to specify the types of incoming packets that cause the
+state machine to decide to schedule padding cells (and/or when to cease
+scheduling them).
+
+The client also maintains its own local histogram state machine(s), for
+reacting to traffic on its end.
+
+Note that our generalization of the Adaptive Padding state machine also
+gives clients full control over the state transition events, even
+allowing them to specify a single-state Burst-only state machine if
+desired. See Sections 3.2.1 and 3.2.2 for details.
+
+The histograms and the associated state machine packet layout is
+specified in Trunnel as follows:
+
+    /* These constants form a bitfield to specify the types of events
+     * that can cause transitions between state machine states.
+     *
+     * Note that SENT and RECV are relative to this endpoint. For
+     * relays, SENT means packets destined towards the client and
+     * RECV means packets destined towards the relay. On the client,
+     * SENT means packets destined towards the relay, where as RECV
+     * means packets destined towards the client.
+     */
+    const RELAY_PADDING_TRANSITION_EVENT_NONPADDING_RECV = 1;
+    const RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT = 2;
+    const RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT = 4;
+    const RELAY_PADDING_TRANSITION_EVENT_PADDING_RECV = 8;
+    const RELAY_PADDING_TRANSITION_EVENT_INFINITY = 16;
+    const RELAY_PADDING_TRANSITION_EVENT_BINS_EMPTY = 32;
+
+    /* Token Removal rules. Enum, not bitfield. */
+    const RELAY_PADDING_REMOVE_NO_TOKENS = 0;
+    const RELAY_PADDING_REMOVE_LOWER_TOKENS = 1;
+    const RELAY_PADDING_REMOVE_HIGHER_TOKENS = 2;
+    const RELAY_PADDING_REMOVE_CLOSEST_TOKENS = 3;
+
+    /* This payload encodes a histogram delay distribution representing
+     * the probability of sending a single RELAY_DROP cell after a
+     * given delay in response to a non-padding cell.
+     *
+     * Payload max size: 113 bytes
+     */
+    struct burst_state {
+      u8 histogram_len IN [2..51];
+      u16 histogram[histogram_len];
+      u32 start_usec;
+      u16 max_sec;
+
+      /* This is a bitfield that specifies which direction and types
+       * of traffic that cause us to abort our scheduled packet and
+       * return to waiting for another event from transition_burst_events.
+       */
+      u8 transition_start_events;
+
+      /* This is a bitfield that specifies which direction and types
+       * of traffic that cause us to remain in the burst state: Cancel the
+       * pending padding packet (if any), and schedule another padding
+       * packet from our histogram.
+       */
+      u8 transition_reschedule_events;
+
+      /* This is a bitfield that specifies which direction and types
+       * of traffic that cause us to transition to the Gap state. */
+      u8 transition_gap_events;
+
+      /* If true, remove tokens from the histogram upon padding and
+       * non-padding activity. */
+      u8 remove_tokens IN [0..3];
+    };
+
+    /* This histogram encodes a delay distribution representing the
+     * probability of sending a single additional padding packet after
+     * sending a padding packet that originated at this hop.
+     *
+     * Payload max size: 113 bytes
+     */
+    struct gap_state {
+      u8 histogram_len IN [2..51];
+      u16 histogram[histogram_len];
+      u32 start_usec;
+      u16 max_sec;
+
+      /* This is a bitfield which specifies which direction and types
+       * of traffic should cause us to transition back to the start
+       * state (ie: abort scheduling packets completely). */
+      u8 transition_start_events;
+
+      /* This is a bitfield which specifies which direction and types
+       * of traffic should cause us to transition back to the burst
+       * state (and schedule a packet from the burst histogram). */
+      u8 transition_burst_events;
+
+      /* This is a bitfield that specifies which direction and types
+       * of traffic that cause us to remain in the gap state: Cancel the
+       * pending padding packet (if any), and schedule another padding
+       * packet from our histogram.
+       */
+      u8 transition_reschedule_events;
+
+      /* If true, remove tokens from the histogram upon padding and
+         non-padding activity. */
+      u8 remove_tokens IN [0..3];
+    };
+
+    /* Payload max size: 227 bytes */
+    struct adaptive_padding_machine {
+      /* This is a bitfield which specifies which direction and types
+       * of traffic should cause us to transition to the burst
+       * state (and schedule a packet from the burst histogram). */
+       u8 transition_burst_events;
+
+       struct burst_state burst;
+       struct gap_state gap;
+    };
+
+    /* This is the full payload of a RELAY_COMMAND_PADDING_ADAPTIVE
+     * cell.
+     *
+     * Payload max size: 455 bytes
+     */
+    struct relay_command_padding_adaptive {
+       /* Technically, we could allow more than 2 state machines here,
+          but only two are sure to fit. More than 2 seems excessive
+          anyway. */
+       u8 num_machines IN [1,2];
+
+       struct adaptive_padding_machine machines[num_machines];
+    };
+
+3.2.1. Histogram state machine operation
+
+Each of pair of histograms ("Burst" and "Gap") together form a state
+machine whose transitions are governed by incoming traffic and/or
+locally generated padding traffic.
+
+Each state machine has a Start state S, a Burst state B, and a Gap state
+G.
+
+The state machine starts idle (state S) until it receives a packet of a
+type that matches the bitmask in machines[i].transition_burst_events. If
+machines[i].transition_burst_events is 0, transition to the burst state
+happens immediately.
+
+This causes it to enter burst mode (state B), in which a delay t is
+sampled from the Burst histogram, and a timer is scheduled to count down
+until either another matching packet arrives, or t expires. If the
+"Infinity" time is sampled from this histogram, the machine returns to
+the lowest state with the INFINITY event bit set.
+
+If a packet that matches machines[i].burst.transition_start_events
+arrives before t expires, the machine transitions back to the Start
+state.
+
+If a packet that matches machines[i].burst.transition_reschedule_events
+arrives before t expires, a new delay is sampled and the process is
+repeated again, i.e.  it remains in burst mode.
+
+Otherwise, if t expires, a padding message is sent to the other end.
+
+If a packet that matches machines[i].burst.transition_gap_events
+arrives (or is sent), the machine transitions to the Gap state G.
+
+In state G, the machine samples from the Gap histogram and sends padding
+messages when the time it samples expires. If an infinite delay is
+sampled while being in state G we jump back to state B or S,
+depending upon the usage of the infinity event bitmask.
+
+If a packet arrives that matches gap.transition_start_events, the
+machine transitions back to the Start state.
+
+If a packet arrives that matches gap.transition_burst_events, the
+machine transitions back to the Burst state.
+
+If a packet arrives that matches
+machines[i].gap.transition_reschedule_events, the machine remains in G
+but schedules a new padding time from its Gap histogram.
+
+In the event that a malicious or buggy client specifies conflicting
+state transition rules with the same bits in multiple transition
+bitmasks, the transition rules of a state that specify transition to
+earlier states take priority. So burst.transition_start_events
+takes priority over burst.transition_reschedule_events, and both of
+these take priority over burst.transition_gap_events.
+
+Similarly, gap.transition_start_events takes priority over
+gap.transition_burst_events, and gap.transition_burst_events takes
+priority over gap.transition_reschedule_events.
+
+In our generalization of Adaptive Padding, either histogram may actually
+be self-scheduling (by setting the bit
+RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT in their
+transition_reschedule_events). This allows the client to create a
+single-state machine if desired.
+
+Clients are expected to maintain their own local version of the state
+machines, for reacting to their own locally generated traffic, in
+addition to sending one or more state machines to the middle relay. The
+histograms that the client uses locally will differ from the ones it
+sends to the upstream relay.
+
+On the client, the "SENT" direction means packets destined towards the
+relay, where as "RECV" means packets destined towards the client.
+However, on the relay, the "SENT" direction means packets destined
+towards the client, where as "RECV" means packets destined towards the
+relay.
+
+3.2.2. The original Adaptive Padding algorithm
+
+As we have noted, the state machines above represent a generalization of
+the original Adaptive Padding algorithm. To implement the original
+behavior, the following flags should be set in both the client and
+the relay state machines:
+
+ num_machines = 1;
+
+ machines[0].transition_burst_events =
+    RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT;
+
+ machines[0].burst.transition_reschedule_events =
+    RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT;
+
+ machines[0].burst.transition_gap_events =
+    RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT;
+
+ machines[0].burst.transition_start_events =
+    RELAY_PADDING_TRANSITION_EVENT_INFINITY;
+
+ machines[0].gap.transition_reschedule_events =
+    RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT;
+
+ machines[0].gap.transition_burst_events =
+    RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT |
+    RELAY_PADDING_TRANSITION_EVENT_INFINITY;
+
+The rest of the transition fields would be 0.
+
+Adding additional transition flags will either increase or decrease the
+amount of padding sent, depending on their placement.
+
+The second machine slot is provided in the event that it proves useful
+to have separate state machines reacting to both sent and received
+traffic.
+
+3.2.3. Histogram decoding/representation
+
+Each of the histograms' fields represent a probability distribution that
+is expanded into bins representing time periods a[i]..b[i] as follows:
+
+start_usec,max_sec,histogram_len initialized from appropriate histogram
+body.
+
+n = histogram_len-1
+INFINITY_BIN = n
+
+a[0] = start_usec;
+b[0] = start_usec + max_sec*USEC_PER_SEC/2^(n-1);
+for(i=1; i < n; i++) {
+  a[i] = start_usec + max_sec*USEC_PER_SEC/2^(n-i)
+  b[i] = start_usec + max_sec*USEC_PER_SEC/2^(n-i-1)
+}
+
+To sample the delay time to send a padding packet, perform the
+following:
+
+  i = 0;
+  curr_weight = histogram[0];
+
+  tot_weight = sum(histogram);
+  bin_choice = crypto_rand_int(tot_weight);
+
+  while (curr_weight < bin_choice) {
+    curr_weight += histogram[i];
+    i++;
+  }
+
+  if (i == INFINITY_BIN)
+    return; // Don't send a padding packet
+
+  // Sample uniformly between a[i] and b[i]
+  send_padding_packet_at = a[i] + crypto_rand_int(b[i] - a[i]);
+
+In this way, the bin widths are exponentially increasing in width, where
+the width is set at max_sec/2^(n-i) seconds. This exponentially
+increasing bin width allows the histograms to most accurately represent
+small interpacket delay (where accuracy is needed), and devote less
+accuracy to larger timescales (where accuracy is not as important).
+
+3.2.4. Token removal and refill
+
+If the remove_tokens field is set to a non-zero value for a given
+state's histogram, then whenever a padding packet is sent, the
+corresponding histogram bin's token count is decremented by one.
+
+If a packet matching the current state's transition_reschedule_events
+bitmask arrives from the server before the chosen padding timer expires,
+then a token is removed from a non-empty bin corresponding to
+the delay since the last packet was sent, and the padding packet timer
+is re-sampled from the histogram.
+
+The three enums for the remove_tokens field govern if we take the token
+out of the nearest lower non-empty bin, the nearest higher non-empty
+bin, or simply the closest non-empty bin.
+
+If the entire histogram becomes empty, it is then refilled to the
+original values. This refill happens prior to any state transitions due
+to RELAY_PADDING_TRANSITION_EVENT_BINS_EMPTY (but obviously does not
+prevent the transition from happening).
+
+
+3.2.5. Constructing the histograms
+
+Care must be taken when constructing the histograms themselves, since
+their non-uniform widths means that the actual underlying probability
+distribution needs to be both normalized for total number of tokens, as
+well as the non-uniform histogram bin widths.
+
+Care should also be taken with interaction with the token removal rules
+from Section 3.2.4. Obviously using a large number of tokens will cause
+token removal to have much less of an impact upon the adaptive nature of
+the padding in the face of existing traffic.
+
+Actual optimal histogram and state transition construction for different
+traffic types is expected to be a topic for further research.
+
+Intuitively, the burst state is used to detect when the line is idle
+(and should therefore have few or no tokens in low histogram bins). The
+lack of tokens in the low histogram bins causes the system to remain in
+the burst state until the actual application traffic either slows,
+stalls, or has a gap.
+
+The gap state is used to fill in otherwise idle periods with artificial
+payloads from the server (and should have many tokens in low bins, and
+possibly some also at higher bins).
+
+It should be noted that due to our generalization of these states and
+their transition possibilities, more complicated interactions are also
+possible.
+
+
+4. Security considerations and mitigations
+
+The risks from this proposal are primarily DoS/resource exhaustion, and
+side channels.
+
+4.1. Rate limiting and accounting
+
+Fully client-requested padding introduces a vector for resource
+amplification attacks and general network overload due to
+overly-aggressive client implementations requesting too much padding.
+
+Current research indicates that this form of statistical padding should
+be effective at overhead rates of 50-60%. This suggests that clients
+that use more padding than this are likely to be overly aggressive in
+their behavior.
+
+We recommend that three consensus parameters be used in the event that
+the network is being overloaded from padding to such a degree that
+padding requests should be ignored:
+
+  * CircuitPaddingMaxRatio
+    - The maximum ratio of padding traffic to non-padding traffic
+      (expressed as a percent) to allow on a circuit before ceasing
+      to pad. Ex: 75 means 75 padding packets for every 100 non-padding
+      packets.
+    - Default: 120
+  * CircuitPaddingLimitCount
+    - The number of padding cells that must be transmitted before the
+      ratio limit is applied.
+    - Default: 5000
+  * CircuitPaddingLimitTime
+    - The time period in seconds over which to count padding cells for
+      application of the ratio limit (ie: reset the limit count this
+      often).
+    - Default: 60
+
+XXX: Should we cap padding at these rates, or fully disable it once
+they're crossed? Probably cap?
+
+In order to monitor the quantity of padding to decide if we should alter
+these limits in the consensus, every node will publish the following
+values in a padding-counts line in its extra-info descriptor:
+
+ * write-drop-multihop
+   - The number of RELAY_DROP cells sent by this relay to a next hop
+     that is listed in the consensus.
+ * write-drop-onehop
+   - The number of RELAY_DROP cells sent by this relay to a next hop
+     that is not listed in the consensus.
+ * write-pad
+   - The number of CELL_PADDING cells sent by this relay.
+ * write-total
+   - The total number of cells sent by this relay.
+ * read-drop-multihop
+   - The number of RELAY_DROP cells read by this relay from a hop
+     that is listed in the consensus.
+ * read-drop-onehop
+   - The number of RELAY_DROP cells read by this relay from a hop
+     that is not listed in the consensus.
+ * read-pad
+   - The number of CELL_PADDING cells read by this relay.
+ * read-total
+   - The total number of cells read by this relay.
+
+Each of these counters will be rounded to the nearest 10,000 cells. This
+rounding parameter will also be listed in the extra-info descriptor line, in
+case we change it in a later release.
+
+In the future, we may decide to introduce Laplace Noise in a similar
+manner to the hidden service statistics, to further obscure padding
+quantities.
+
+4.2. Malicious state machines
+
+The state machine capabilities of RELAY_COMMAND_PADDING_ADAPTIVE are
+very flexible, and as a result may specify conflicting or
+non-deterministic state transitions.
+
+We believe that the rules in Section 3.2.1 for prioritizing transitions
+towards lower states remove any possibility of non-deterministic
+transitions.
+
+However, because of self-triggering property that allows the state
+machines to schedule more padding packets after sending their own
+locally generated padding packets, care must be taken with the
+interaction with the rate limiting rules in Section 4.1. If the limits
+in section 4.1 are exceeded, the state machines should stop, rather than
+continually poll themselves trying to transmit packets and being blocked
+by the rate limiter at another layer.
+
+4.3. Libevent timer exhaustion
+
+As mentioned in section 3.1, scheduled padding may create an excessive
+number of libevent timers. Care should be taken in the implementation to
+devise a way to prevent clients from sending padding requests
+specifically designed to impact the ability of relays to function by
+causing too many timers to be scheduled at once.
+
+XXX: Can we suggest any specifics here? I can imagine a few ways of
+lazily scheduling timers only when they are close to their expiry time,
+and other ways of minimizing the number of pending timer callbacks at a
+given time, but I am not sure which would be best for libevent.
+
+4.4. Side channels
+
+In order to prevent relays from introducing side channels by requesting
+padding from clients, all of these commands should only be valid in the
+outgoing (from the client/OP) direction.
+
+Clients should perform accounting on the amount of padding that they
+receive, and if it exceeds the amount that they have requested, they
+alert the user of a potentially misbehaving node, and/or close the
+circuit.
+
+Similarly, if RELAY_DROP cells arrive from the last hop of a circuit,
+rather than from the expected interior node, clients should alert the
+user of the possibility of that circuit endpoint introducing a
+side-channel attack, and/or close the circuit.
+
+4.5. Memory exhaustion
+
+Because interior nodes do not have information on the current circuits
+SENDME windows, it is possible for malicious clients to consume the
+buffers of relays by specifying padding, and then not reading from the
+associated circuits.
+
+XXX: Tor already had a few flow-control related DoS's in the past[3]. Is
+that defense sufficient here without any mods? It seems like it may be!
+
+-------------------
+
+1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-padding.txt
+2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf
+3. https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses