commit 91e207e91d0375273004ecf16364c073e3e82043 Author: Isis Lovecruft isis@torproject.org Date: Fri Sep 25 11:40:28 2015 +0000
Add mikeperry's padding negotiation proposal and give it a number. --- proposals/000-index.txt | 2 + proposals/254-padding-negotiation.txt | 628 +++++++++++++++++++++++++++++++++ proposals/proposal-status.txt | 6 + proposals/xxx-padding-negotiation.txt | 628 --------------------------------- 4 files changed, 636 insertions(+), 628 deletions(-)
diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 0460e87..c1f42e2 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -174,6 +174,7 @@ Proposals by number: 251 Padding for netflow record resolution reduction [DRAFT] 252 Single Onion Services [DRAFT] 253 Out of Band Circuit HMACs [DRAFT] +254 Padding Negotiation [DRAFT]
Proposals by status: @@ -195,6 +196,7 @@ Proposals by status: 251 Padding for netflow record resolution reduction 252 Single Onion Services 253 Out of Band Circuit HMACs + 254 Padding Negotiation NEEDS-REVISION: 190 Bridge Client Authorization Based on a Shared Secret OPEN: 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... +2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf +3. https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses diff --git a/proposals/proposal-status.txt b/proposals/proposal-status.txt index 6ca1bda..36627b7 100644 --- a/proposals/proposal-status.txt +++ b/proposals/proposal-status.txt @@ -441,3 +441,9 @@ again to remind me! circuit point-to-point so as to better resist or detect some kinds of tagging attacks. (9/2015)
+254 Padding Negotiation [DRAFT] + + Describes general mechanisms and new cells/commands for requesting + various types of padding between clients and relays, for use in defending + against both website traffic fingerprinting as well as hidden service + circuit setup fingerprinting. (9/2015) diff --git a/proposals/xxx-padding-negotiation.txt b/proposals/xxx-padding-negotiation.txt deleted file mode 100644 index a42bd6c..0000000 --- a/proposals/xxx-padding-negotiation.txt +++ /dev/null @@ -1,628 +0,0 @@ -Filename: xxx-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... -2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf -3. https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses