On 12 Sep 2015, at 10:34, Mike Perry <mikeperry@torproject.org> wrote:

Here's a proposal describing some padding negotiation cell primitives that
should be useful to defend against website traffic fingerprinting, hidden
service circuit fingerprinting, and probably just about any other traffic
analysis attack under the sun.

The proposal is in my git remote at:
https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/xxx-padding-negotiation.txt?h=padding_negotiation

==============================

Filename: xxx-padding-negotiation.txt
Title: Padding Negotiation
Authors: Mike Perry
Created: 01 September 2015
Status: Draft


...


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 {
      /* Number of microseconds before sending cells (cumulative) */
      u32 when_send[80];

      /* Number of cells to send at time point sum(when_send[0..i]) */
      u16 num_cells[80];

      /* 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.

3.2. Adaptive Padding message (RELAY_COMMAND_PADDING_ADAPTIVE)

...

3.2.4. Token removal and refill

If the remove_tok field is set to true 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 the nearest non-empty bin corresponding to
the delay since the last packet was sent, and the padding packet timer
is re-sampled from the histogram.

If the entire histogram becomes empty, it is then refilled to the
original values.

...