path: root/proposals/254-padding-negotiation.txt

Filename: 254-padding-negotiation.txt
Title: Padding Negotiation
Authors: Mike Perry
Created: 01 September 2015
Status: Needs-Revision


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 payload should cover the needed
parameters:

  const CHANNELPADDING_COMMAND_STOP = 1;
  const CHANNELPADDING_COMMAND_START = 2;

  /* The start command tells the relay to alter its min and max netflow
     timeout range values, and send padding at that rate (resuming
     if stopped). The stop command tells the relay to stop sending
     link-level padding. */
  struct channelpadding_negotiate {
    u8 version IN [0];
    u8 command IN [CHANNELPADDING_COMMAND_START, CHANNELPADDING_COMMAND_STOP];

    /* Min must not be lower than the current consensus parameter
       nf_ito_low. Ignored if command is stop. */
    u16 ito_low_ms;

    /* Max must not be lower than ito_low_ms. Ignored if command is stop. */
    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 the ability to schedule a statistical
distribution of arbitrary padding to overlay on top of non-padding
traffic (aka "Adaptive Padding").

The statistical mechanisms that define padding are known as padding
machines. Padding machines can be hardcoded in Tor, specified in the
consensus, and custom research machines can be listed in Torrc.

3.1. Padding Machines

Circuits can have either one or two state machines at both the origin and at a
specified middle hop.

Each state machine can contain up to three states ("Start", "Burst" and
"Gap") governing their behavior. Not all states need to be used.

Each state of a padding machine specifies either:
  * A histogram describing inter-arrival cell delays; OR
  * A parameterized distribution for inter-arrival cell delays

In either case, the lower bound of the delay distribution can be specified as
a parameter, or it can be learned by measuring the RTT of the circuit.

If the histogram is used, it has an additional special "infinity" bin that
means "infinite delay".

The state can also provide an optional parameterized distribution that
specifies how many total cells (or how many padding cells) can be sent on the
circuit while the machine is in this state, before it transitions to a new
state.

Each state of a padding machine can react to the following cell events:
  * Non-padding cell received
  * Padding cell received
  * Non-padding cell sent
  * Padding cell sent

Additionally, padding machines emit the following internal events to themselves:
  * Infinity bin was selected
  * The histogram bins are empty
  * The length count for this state was exceeded

Each state of the padding machine specifies a set of these events that cause
it to cancel any pending padding, and a set of events that cause it to
transition to another state, or transition back itself.

When an event causes a transition to a state (or back to the same state), a
delay is sampled from the histogram or delay distribution, and padding cell is
scheduled to be sent after that delay.

If a non-padding cell is sent before the timer, the timer is cancelled and a
new padding delay is chosen.

3.1.1. Histogram Specification

If a histogram is used by a state (as opposed to a fixed parameterized
distribution), then 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.1.2 Histogram Token Removal

Tokens can be optionally removed from histogram bins whenever a padding or
non-padding packet is sent. With this token removal, the histogram functions
as an overall target delay distribution for the machine while it is in that
state.

If token removal is enabled, when a padding packet is sent, a token is removed
from the bin corresponding to the target delay. When a non-padding packet is
sent, the actual delay from the previous packet is calculated, and the
histogram bin corresponding to that delay is inspected.  If that bin has
tokens remaining, it is decremented.

If the bin has no tokens left, the state removes a token from a different bin,
as specified in its token removal rule. The following token removal options
are defined:
  * None -- Never remove any tokens
  * Exact -- Only remove from the target bin, if it is empty, ignore it.
  * Higher -- Remove from the next higher non-empty bin
  * Lower -- Remove from the next higher non-empty bin
  * Closest -- Remove from the closest non-empty bin by index
  * Closest_time -- Remove from the closest non-empty bin by index, by time

When all bins are empty in a histogram, the padding machine emits the internal
"bins empty" event to itself.

3.2. Machine Selection

Clients will select which of the defined available padding machines to use
based on the conditions that these machines specify. These conditions include:
  * How many hops the circuit must be in order for the machine to apply
  * If the machine requires vanguards to be enabled to apply
  * The state the circuit must be in for machines to apply (building,
    relay early cells remaining, opened, streams currently attached).
  * If the circuit purpose matches a set of purposes for the machine.
  * If the target hop of the machine supports circuit padding.

Clients will only select machines whose conditions fully match given circuits.

3.3. Machine Neogitation

When a machine is selected, the client uses leaky-pipe delivery to send a
RELAY_COMMAND_PADDING_NEGOTIATE to the target hop of the machine, using the
following trunnel relay cell payload format:

  /**
   * 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 circpad_negotiate {
    u8 version IN [0];
    u8 command IN [CIRCPAD_COMMAND_START, CIRCPAD_COMMAND_STOP];
  
    /** Machine type is left unbounded because we can specify
     * new machines in the consensus */
    u8 machine_type;
  };

Upon receipt of a RELAY_COMMAND_PADDING_NEGOTIATE cell, the middle node sends
a RELAY_COMMAND_PADDING_NEGOTIATED with the following format:
  /**
   * 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 circpad_negotiated {
    u8 version IN [0];
    u8 command IN [CIRCPAD_COMMAND_START, CIRCPAD_COMMAND_STOP];
    u8 response IN [CIRCPAD_RESPONSE_OK, CIRCPAD_RESPONSE_ERR];
  
    /** Machine type is left unbounded because we can specify
     * new machines in the consensus */
    u8 machine_type;
  };

If the response field is CIRCPAD_RESPONSE_OK, padding was successfully
negotiated. If it is CIRCPAD_RESPONSE_ERR, the machine is torn down and we do
not pad.


4. Examples of Padding Machines

In the original WTF-PAD design[2], the state machines are used as follows:

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".

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). In this way, the gap state either
generates entirely fake streams of cells, or extends real streams with
additional cells.

The Adaptive Padding Early implementation[3] uses parameterized distributions
instead of histograms, but otherwise uses the states in the same way.

It should be noted that due to our generalization of these states and their
transition possibilities, more complicated interactions are also possible. For
example, it is possible to simulate circuit extension, so that all circuits
appear to continue to extend up until the RELAY_EARLY cell count is depleted.

It is also possible to create machines that simulate traffic on unused
circuits, or mimic onion service activity on clients that aren't otherwise
using onion services.


5. Security considerations and mitigations

The risks from this proposal are primarily DoS/resource exhaustion, and
side channels.

5.1. Rate limiting

Current research[2,3] indicates that padding should be be effective against
website traffic fingerprinting at overhead rates of 50-60%. Circuit setup
behavior can be concealed with far less overhead.

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:

  * circpad_global_max_padding_pct
    - The maximum percent of sent padding traffic out of total traffic
      to allow in a tor process before ceasing to pad. Ex: 75 means
      75 padding packets for every 100 non-padding+padding packets.
      This definition is consistent with the overhead values in Proposal
      #265, though it does not take node position into account.
  * circpad_global_allowed_cells
    - The number of padding cells that must be transmitted before the
      global ratio limit is applied.

Additionally, each machine can specify its own per-machine limits for
the allowed cell counters and padding overhead percentages.

When either global or machine limits are reached, padding is no longer
scheduled. The machine simply becomes idle until the overhead drops below
the threshold.

5.2. Overhead accounting

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:

 * read_drop_cell_count
   - The number of RELAY_DROP cells read by this relay.
 * write_drop_cell_count
   - The number of RELAY_DROP cells sent 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.

5.3. Side channels

In order to prevent relays from introducing side channels by requesting
padding from clients, all of the padding negotiation commands are only
valid in the outgoing (from the client/OP) direction.

Similarly, to prevent relays from sending malicious padding from arbitrary
circuit positions, if RELAY_DROP cells arrive from a hop other than that
with which padding was negotiated, this cell is counted as invalid for
purposes of CIRC_BW control port fields, allowing the vanguards addon to
close the circuit upon detecting this activity.

-------------------

1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-padding.txt
2. https://www.cs.kau.se/pulls/hot/thebasketcase-wtfpad/
3. https://www.cs.kau.se/pulls/hot/thebasketcase-ape/