From 91e207e91d0375273004ecf16364c073e3e82043 Mon Sep 17 00:00:00 2001 From: Isis Lovecruft Date: Fri, 25 Sep 2015 11:40:28 +0000 Subject: Add mikeperry's padding negotiation proposal and give it a number. --- proposals/254-padding-negotiation.txt | 628 ++++++++++++++++++++++++++++++++++ 1 file changed, 628 insertions(+) create mode 100644 proposals/254-padding-negotiation.txt (limited to 'proposals/254-padding-negotiation.txt') 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 -- cgit v1.2.3-54-g00ecf