commit 9703c86274bdeac3e7dde5c571210660e782dc5d Author: Mike Perry <mikeperry-git@torproject.org> Date: Fri Sep 11 15:12:24 2015 -0700 Generalize state transition capability. Also allow the histograms to be variable in size. --- proposals/xxx-padding-negotiation.txt | 261 ++++++++++++++++++++++++--------- 1 file changed, 192 insertions(+), 69 deletions(-) diff --git a/proposals/xxx-padding-negotiation.txt b/proposals/xxx-padding-negotiation.txt index 66d8991..005045a 100644 --- a/proposals/xxx-padding-negotiation.txt +++ b/proposals/xxx-padding-negotiation.txt @@ -34,7 +34,7 @@ compromised guard node. However, link-level padding is still useful to defend against an adversary that can merely observe a Guard node externally. Right now, the only case where link-level padding is known to defend against any realistic attacker is for low-resolution -netflow-based attacks. +netflow-based attacks (see Proposal 251[1]). In that scenario, the primary mechanism we need is a way for mobile clients to tell their Guards to stop padding, or to pad less often. The @@ -50,7 +50,8 @@ following Trunnel payloads should cover the needed parameters: }; /* This command tells the relay to alter its min and max timeout - range values, and if needed, send + range values, and send padding at that rate (resuming if + stopped). */ struct cell_padding_start { u8 command IN [CELL_PADDING_COMMAND_START]; @@ -62,9 +63,10 @@ following Trunnel payloads should cover the needed parameters: u16 ito_high_ms; }; -If more scenarios are discovered, future command numbers could be used -to include the end-to-end padding command payloads below, or other -defense parameterizations. +More complicated forms of link 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 @@ -78,7 +80,8 @@ traffic (aka "Adaptive Padding"). In both cases, these messages will be sent from clients to middle nodes using "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. +that is not detectable from the Guard node. This same mechanism can also +be used to request padding from the Guard node itself. 3.1. Fixed-schedule padding message (RELAY_COMMAND_PADDING_SCHEDULE) @@ -100,7 +103,7 @@ follows: /* 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 */ @@ -112,11 +115,11 @@ 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) -The following message is derived from the Adaptive Padding defense -specified in "Timing Attacks and Defenses"[1]. +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 contain two histograms ("Burst" and "Gap") governing their behavior. @@ -133,37 +136,57 @@ distribution. Both "Gap" and "Burst" histograms each have a special "Infinity" bin, which means "We have decided not to send a packet". -Each histograms is combined with state transition information, which +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 histograms and the associated state machines are specified in -Trunnel as follows: +Note that our generalization of the Adaptive Padding state machine +actually gives clients full control over the state transition events, +even allowing them to specify a single-state 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 padding to start or stop from a given state. */ - const RELAY_PADDING_TRANSITION_EVENT_INFINITY_BIN = 0; // "Always set" 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_HISTOGRAM_INFINITY_BIN = 50; - /* + /* This 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. */ struct burst_state { - u16 histogram[51]; + 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 should cause us to schedule a padding packet - (and potentially transition to the Gap state). */ - u8 transition_events; + /* + 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; /* Should we remove tokens from the histogram as packets are sent? */ u8 remove_toks IN [0,1]; @@ -175,27 +198,39 @@ Trunnel as follows: sending a padding packet that originated at this hop. */ struct gap_state { - u16 histogram[51]; + u8 histogram_len IN [2..51]; + u16 histogram[histogram_len]; u32 start_usec; u16 max_sec; - /* - Integer value to add to the "Infinity" bin after each successive - padding packet is sent. Used to create an increasing likelihood - of hitting the termination condition with each successive padding - packet. */ - u16 decay_by; + /* 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. */ - u8 transition_events; + 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; /* Should we remove tokens from the histogram as packets are sent? */ u8 remove_toks IN [0,1]; }; 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; }; @@ -218,25 +253,57 @@ 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 burst.transition_events. +type that matches the bitmask in machines[i].transition_burst_events. 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. +until either another matching packet arrives, or t expires. If the +"Infinity" time is sampled from this histogram, the machine returns to +the Start state. -If a matching packet arrives before t expires, a new delay is sampled -and the process is repeated again, i.e. it remains in burst mode. +If a packet that matches machines[i].burst.transition_start_events +arrives before t expires, the machine transitions back to the Start +state. -Otherwise, a padding message is sent to the other end and the machine -switches to state G (Gap mode). In state G, the machine samples from the -Gap histogram and sends padding messages when the time it samples -expires. An infinite delay can be sampled from the histograms. When an -infinite delay is sampled while being in state G we jump back to state -B. Similarly, a transition to S occurs when we sample an infinite time -in B. +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. -Optionally, a transition from G to B can also occur upon receiving a -packet, as specified by gap.transition_events bitmask. +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. + +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 @@ -245,18 +312,49 @@ addition to sending one or more state machines to the middle relay. The histograms that the client uses locally will likely differ from the ones it sends to the upstream relay. -3.2.2. Histogram decoding/representation +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: + + 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].gap.transition_reschedule_events = + RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT; + + machines[0].gap.transition_burst_events = + RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT; + +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. + +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 initialized from appropriate histogram type. +start_usec,max_sec,histogram_len initialized from appropriate histogram +body. -a[0] = start_usec; -n = RELAY_PADDING_HISTOGRAM_INFINITY_BIN; +n = histogram_len-1 +INFINITY_BIN = n -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) +a[0] = start_usec; +b[0] = start_usec + max_sec*USEC_PER_SEC/2^(n); +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: @@ -272,11 +370,11 @@ following: i++; } - if (i == RELAY_PADDING_HISTOGRAM_INFINITY_BIN) + 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]); + 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 @@ -284,21 +382,22 @@ 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.3. Token removal and refill +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 non-padding packet 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 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. -3.2.4. Constructing the histograms +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 @@ -306,12 +405,19 @@ 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.3. Obviously using a large number of tokens will cause +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 construction for different traffic types is -expected to be a topic for further research. +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), and +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). However, more complicated +interactions are also possible. 4. Security considerations and mitigations @@ -356,8 +462,26 @@ Proposal 251 introduced extra-info accounting at relays to enable us to measure the total overhead of both link and circuit-level padding at various relays. -4.2. Libevent timer exhaustion - +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 @@ -369,7 +493,7 @@ 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.3. Side channels +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 @@ -384,9 +508,8 @@ 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. - - -------------------- - - -1. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf + +------------------- + +1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-padding... +2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf