November 2018 - tor-commits - lists.torproject.org

[torspec/master] Prop 254: Describe token generation more clearly
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit acd4a89c1c81d0de37c57313e31ffca7413ae511 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Mon Nov 5 23:17:14 2018 +0000 Prop 254: Describe token generation more clearly I hope... --- proposals/254-padding-negotiation.txt | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index d950446..f166d5f 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -155,13 +155,14 @@ distribution that is encoded into bins of exponentially increasing width. The first bin of the histogram (bin 0) has 0 width, with a delay value of start_usec+rtt_estimate (from the machine definition, and rtt estimate above). -The bin before the "infinity bin" has a time value of -start_usec+rtt_estimate+range_sec*USEC_PER_SEC. - -The bins between these two points are exponentially spaced, so that smaller -bin indexes represent narrower time ranges, doubling up until the last bin -range of [(start_usec+rtt_estimate+range_sec*USEC_PER_SEC)/2, -start_usec+rtt_estimate+range_sec*USEC_PER_SEC). +The remaining bins are exponentially spaced, starting at this offset and +covering the range of the histogram, which is range_sec*USEC_PER_SEC. + +The intermediate bins thus divide the timespan range_sec*USEC_PER_SEC with +offset start_usec+rtt_estimate, so that smaller bin indexes represent narrower +time ranges, doubling up until the last bin. The last bin before the "infinity +bin" thus covers [start_usec+rtt_estimate+range_sec*USEC_PER_SEC/2, +CIRCPAD_DELAY_INFINITE). This exponentially increasing bin width allows the histograms to most accurately represent small interpacket delay (where accuracy is needed), and

1 0

[torspec/master] Proposal 254 updates from asn's review.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit 1dd7f1ff78fcb69121130cbd802b0b8b527ffc63 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Mon Nov 5 19:45:05 2018 +0000 Proposal 254 updates from asn's review. --- proposals/254-padding-negotiation.txt | 85 ++++++++++++++++++----------------- 1 file changed, 44 insertions(+), 41 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index b9ecc05..d950446 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -74,6 +74,10 @@ 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. +Because the above link-level padding only sends padding cells if the link is +idle, it can be used in combination with the more complicated circuit-level +padding below, without compounding overhead effects. + 3. End-to-end circuit padding @@ -90,16 +94,27 @@ consensus, and custom research machines can be listed in Torrc. Circuits can have either one or two state machines at both the origin and at a specified middle hop. -Each state machine can contain up to three states ("Start", "Burst" and -"Gap") governing their behavior. Not all states need to be used. +Each state machine can contain up to three states ("Start", "Burst" and "Gap") +governing their behavior, as well as an "END" state. Not all states need to be +used. Each state of a padding machine specifies either: * A histogram describing inter-arrival cell delays; OR * A parameterized delay probability distribution for inter-arrival cell delays In either case, the lower bound of the delay probability distribution can be -specified as a parameter, or it can be learned by measuring the RTT of the -circuit. +specified as the start_usec parameter, and/or it can be learned by measuring +the RTT of the circuit at the middle node. For client-side machines, RTT +measurement is always set to 0. RTT measurement at the middle node is +calculated by measuring the difference between the time of arrival of an +received cell (ie: away from origin) and the time of arrival of a sent cell +(ie: towards origin). The RTT is continually updated so long as two cells do +not arrive back-to-back in either direction. If the most recent measured RTT +value is larger than our measured value so far, this larger value is used. If +the most recent measured RTT value is lower than our measured value so far, it +is averaged with our current measured value. (We favor longer RTTs slightly in +this way, because circuits are growing away from the middle node and becoming +longer). If the histogram is used, it has an additional special "infinity" bin that means "infinite delay". @@ -128,54 +143,39 @@ When an event causes a transition to a state (or back to the same state), a delay is sampled from the histogram or delay distribution, and padding cell is scheduled to be sent after that delay. -If a non-padding cell is sent before the timer, the timer is cancelled and a +If a non-padding cell is sent before the timer, the timer is canceled and a new padding delay is chosen. 3.1.1. Histogram Specification If a histogram is used by a state (as opposed to a fixed parameterized distribution), then each of the histograms' fields represent a probability -distribution that is expanded into bins representing time periods a[i]..b[i] -as follows: +distribution that is encoded into bins of exponentially increasing width. + +The first bin of the histogram (bin 0) has 0 width, with a delay value of +start_usec+rtt_estimate (from the machine definition, and rtt estimate above). -start_usec,max_sec,histogram_len initialized from appropriate histogram -body. +The bin before the "infinity bin" has a time value of +start_usec+rtt_estimate+range_sec*USEC_PER_SEC. -n = histogram_len-1 -INFINITY_BIN = n +The bins between these two points are exponentially spaced, so that smaller +bin indexes represent narrower time ranges, doubling up until the last bin +range of [(start_usec+rtt_estimate+range_sec*USEC_PER_SEC)/2, +start_usec+rtt_estimate+range_sec*USEC_PER_SEC). -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) -} +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). 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). + * Select a bin weighted by the number of tokens in its index compared to + the total. + * If the infinity bin is selected, do not schedule padding. + * If bin 0 is selected, schedule padding at exactly its time value. + * For other bins, uniformly sample a time value between this bin and + the next bin, and schedule padding then. 3.1.2 Histogram Token Removal @@ -262,7 +262,10 @@ a RELAY_COMMAND_PADDING_NEGOTIATED with the following format: }; The 'machine_type' field should be the same as the one from the -PADDING_NEGOTIATE cell. +PADDING_NEGOTIATE cell. This is because, as an optimization, new machines can +be installed at the client side immediately after tearing down an old machine. +If the response machine type does not match the current machine type, the +response was for a previous machine, and can be ignored. If the response field is CIRCPAD_RESPONSE_OK, padding was successfully negotiated. If it is CIRCPAD_RESPONSE_ERR, the machine is torn down and we do

1 0

[torspec/master] Update Proposal #254 with latest circuit padding plans.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit 3fed83a38d9d85cab6d0437184f3b8909ca0266b Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Mon Oct 29 19:45:58 2018 +0000 Update Proposal #254 with latest circuit padding plans. --- proposals/254-padding-negotiation.txt | 620 ++++++++++------------------------ 1 file changed, 181 insertions(+), 439 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index ca5ad14..3b2c883 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -71,331 +71,65 @@ 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 +For circuit-level padding, we need the ability to schedule a statistical distribution of arbitrary padding to overlay on top of non-padding traffic (aka "Adaptive Padding"). -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. +The statistical mechanisms that define padding are known as padding +machines. Padding machines can be hardcoded in Tor, specified in the +consensus, and custom research machines can be listed in Torrc. -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. Padding Machines -3.1. Fixed-schedule padding message (RELAY_COMMAND_PADDING_SCHEDULE) +Circuits can have either one or two state machines at both the origin and at a +specified middle hop. -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. +Each state machine can contain up to three states ("Start", "Burst" and +"Gap") governing their behavior. Not all states need to be used. -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. +Each state of a padding machine specifies either: + * A histogram describing inter-arrival cell delays; OR + * A parameterized distribution for inter-arrival cell delays -The RELAY_COMMAND_PADDING_SCHEDULE body is specified in Trunnel as -follows: +In either case, the lower bound of the delay distribution can be specified as +a parameter, or it can be learned by measuring the RTT of the circuit. - struct relay_padding_schedule { - u8 schedule_length IN [1..80]; +If the histogram is used, it has an additional special "infinity" bin that +means "infinite delay". - /* 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 +The state can also provide an optional parameterized distribution that +specifies how many total cells (or how many padding cells) can be sent on the +circuit while the machine is in this state, before it transitions to a new state. -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; +Each state of a padding machine can react to the following cell events: + * Non-padding cell received + * Padding cell received + * Non-padding cell sent + * Padding cell sent - machines[0].burst.transition_reschedule_events = - RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT; +Additionally, padding machines emit the following internal events to themselves: + * Infinity bin was selected + * The histogram bins are empty + * The length count for this state was exceeded - machines[0].burst.transition_gap_events = - RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT; +Each state of the padding machine specifies a set of these events that cause +it to cancel any pending padding, and a set of events that cause it to +transition to another state, or transition back itself. - machines[0].burst.transition_start_events = - RELAY_PADDING_TRANSITION_EVENT_INFINITY; +When an event causes a transition to a state (or back to the same state), a +delay is sampled from the histogram or delay distribution, and padding cell is +scheduled to be sent after that delay. - machines[0].gap.transition_reschedule_events = - RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT; +If a non-padding cell is sent before the timer, the timer is cancelled and a +new padding delay is chosen. - machines[0].gap.transition_burst_events = - RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT | - RELAY_PADDING_TRANSITION_EVENT_INFINITY; +3.1.1. Histogram Specification -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: +If a histogram is used by a state (as opposed to a fixed parameterized +distribution), then each of the histograms' fields represent a probability +distribution that is expanded into bins representing time periods a[i]..b[i] +as follows: start_usec,max_sec,histogram_len initialized from appropriate histogram body. @@ -436,42 +170,100 @@ 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 +3.1.2 Histogram Token Removal -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. +Tokens can be optionally removed from histogram bins whenever a padding or +non-padding packet is sent. With this token removal, the histogram functions +as an overall target delay distribution for the machine while it is in that +state. -If 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. +If token removal is enabled, when a padding packet is sent, a token is removed +from the bin corresponding to the target delay. When a non-padding packet is +sent, the actual delay from the previous packet is calculated, and the +histogram bin corresponding to that delay is inspected. If that bin has +tokens remaining, it is decremented. + +If the bin has no tokens left, the state removes a token from a different bin, +as specified in its token removal rule. The following token removal options +are defined: + * None -- Never remove any tokens + * Exact -- Only remove from the target bin, if it is empty, ignore it. + * Higher -- Remove from the next higher non-empty bin + * Lower -- Remove from the next higher non-empty bin + * Closest -- Remove from the closest non-empty bin by index + * Closest_time -- Remove from the closest non-empty bin by index, by time + +When all bins are empty in a histogram, the padding machine emits the internal +"bins empty" event to itself. + +3.2. Machine Selection + +Clients will select which of the defined available padding machines to use +based on the conditions that these machines specify. These conditions include: + * How many hops the circuit must be in order for the machine to apply + * If the machine requires vanguards to be enabled to apply + * The state the circuit must be in for machines to apply (building, + relay early cells remaining, opened, streams currently attached). + * If the circuit purpose matches a set of purposes for the machine. + * If the target hop of the machine supports circuit padding. + +Clients will only select machines whose conditions fully match given circuits. + +3.3. Machine Neogitation + +When a machine is selected, the client uses leaky-pipe delivery to send a +RELAY_COMMAND_PADDING_NEGOTIATE to the target hop of the machine, using the +following trunnel relay cell payload format: + + /** + * This command tells the relay to alter its min and max netflow + * timeout range values, and send padding at that rate (resuming + * if stopped). */ + struct circpad_negotiate { + u8 version IN [0]; + u8 command IN [CIRCPAD_COMMAND_START, CIRCPAD_COMMAND_STOP]; + + /** Machine type is left unbounded because we can specify + * new machines in the consensus */ + u8 machine_type; + }; -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. +Upon receipt of a RELAY_COMMAND_PADDING_NEGOTIATE cell, the middle node sends +a RELAY_COMMAND_PADDING_NEGOTIATED with the following format: + /** + * This command tells the relay to alter its min and max netflow + * timeout range values, and send padding at that rate (resuming + * if stopped). */ + struct circpad_negotiated { + u8 version IN [0]; + u8 command IN [CIRCPAD_COMMAND_START, CIRCPAD_COMMAND_STOP]; + u8 response IN [CIRCPAD_RESPONSE_OK, CIRCPAD_RESPONSE_ERR]; + + /** Machine type is left unbounded because we can specify + * new machines in the consensus */ + u8 machine_type; + }; -If the 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). +If the response field is CIRCPAD_RESPONSE_OK, padding was successfully +negotiated. If it is CIRCPAD_RESPONSE_ERR, the machine is torn down and we do +not pad. -3.2.5. Constructing the histograms +4. Examples of Padding Machines -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. +In the original WTF-PAD design[2], the state machines are used as follows: -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. +The "Burst" histogram specifies the delay probabilities for sending a +padding packet after the arrival of a non-padding data packet. -Actual optimal histogram and state transition construction for different -traffic types is expected to be a topic for further research. +The "Gap" histogram specifies the delay probabilities for sending +another padding packet after a padding packet was just sent from this +node. This self-triggering property of the "Gap" histogram allows the +construction of multi-packet padding trains using a simple statistical +distribution. + +Both "Gap" and "Burst" histograms each have a special "Infinity" bin, +which means "We have decided not to send a packet". Intuitively, the burst state is used to detect when the line is idle (and should therefore have few or no tokens in low histogram bins). The @@ -481,76 +273,71 @@ 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). +possibly some also at higher bins). In this way, the gap state either +generates entirely fake streams of cells, or extends real streams with +additional cells. + +The Adaptive Padding Early implementation[3] uses parameterized distributions +instead of histograms, but otherwise uses the states in the same way. + +It should be noted that due to our generalization of these states and their +transition possibilities, more complicated interactions are also possible. For +example, it is possible to simulate circuit extension, so that all circuits +appear to continue to extend up until the RELAY_EARLY cell count is depleted. -It should be noted that due to our generalization of these states and -their transition possibilities, more complicated interactions are also -possible. +It is also possible to create machines that simulate traffic on unused +circuits, or mimic onion service activity on clients that aren't otherwise +using onion services. -4. Security considerations and mitigations +5. Security considerations and mitigations The risks from this proposal are primarily DoS/resource exhaustion, and side channels. -4.1. Rate limiting and accounting +5.1. Rate limiting -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. +Current research[2,3] indicates that padding should be be effective against +website traffic fingerprinting at overhead rates of 50-60%. Circuit setup +behavior can be concealed with far less overhead. We recommend that three consensus parameters be used in the event that the network is being overloaded from padding to such a degree that padding requests should be ignored: - * 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 + * circpad_max_machine_padding_pct + - The maximum ratio of sent padding traffic to sent non-padding traffic + (expressed as a percent) to allow on a padding machine before ceasing + to pad. Ex: 75 means 75 padding packets for every 100 + non-padding+padding packets. This definition is consistent with the + overhead values in Proposal #265. + * circpad_machine_allowed_cells - 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 + per-machine ratio limit is applied. + * circpad_max_global_padding_pct + - The maximum ratio of sent padding traffic to sent non-padding traffic + (expressed as a percent) to allow globally at a client or relay + before ceasing to pad. Ex: 75 means 75 padding packets for every 100 + non-padding+padding packets. This definition is consistent with the + overhead values in Proposal #265. + +Additionally, each machine can specify its own per-machine limits for +the allowed cell counters and padding overhead percentages. -XXX: Should we cap padding at these rates, or fully disable it once -they're crossed? Probably cap? +When either global or machine limits are reached, padding is no longer +scheduled. The machine simply becomes idle until the overhead drops below +the threshold. + +5.2. Overhead accounting In order to monitor the quantity of padding to decide if we should alter these limits in the consensus, every node will publish the following values in a padding-counts line in its extra-info descriptor: - * 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. + * read_drop_cell_count + - The number of RELAY_DROP cells read by this relay. + * write_drop_cell_count + - The number of RELAY_DROP cells sent by this relay. Each of these counters will be rounded to the nearest 10,000 cells. This rounding parameter will also be listed in the extra-info descriptor line, in @@ -560,65 +347,20 @@ 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 +5.3. 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. +padding from clients, all of the padding negotiation commands are only +valid in the outgoing (from the client/OP) direction. -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! +Similarly, to prevent relays from sending malicious padding from arbitrary +circuit positions, if RELAY_DROP cells arrive from a hop other than that +with which padding was negotiated, this cell is counted as invalid for +purposes of CIRC_BW control port fields, allowing the vanguards addon to +close the circuit upon detecting this activity. ------------------- 1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-paddin… -2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf -3. https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses +2. https://www.cs.kau.se/pulls/hot/thebasketcase-wtfpad/ +3. https://www.cs.kau.se/pulls/hot/thebasketcase-ape/

1 0

[torspec/master] fixup! Update Proposal #254 with latest circuit padding plans.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit a697137e91ed319eae0ef8155c919249b1b75e86 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Mon Oct 29 21:20:16 2018 +0000 fixup! Update Proposal #254 with latest circuit padding plans. Update padding consensus param limits. --- proposals/254-padding-negotiation.txt | 22 ++++++++-------------- 1 file changed, 8 insertions(+), 14 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index 3b2c883..94d8287 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -305,21 +305,15 @@ We recommend that three consensus parameters be used in the event that the network is being overloaded from padding to such a degree that padding requests should be ignored: - * circpad_max_machine_padding_pct - - The maximum ratio of sent padding traffic to sent non-padding traffic - (expressed as a percent) to allow on a padding machine before ceasing - to pad. Ex: 75 means 75 padding packets for every 100 - non-padding+padding packets. This definition is consistent with the - overhead values in Proposal #265. - * circpad_machine_allowed_cells + * circpad_global_max_padding_pct + - The maximum percent of sent padding traffic out of total traffic + to allow in a tor process before ceasing to pad. Ex: 75 means + 75 padding packets for every 100 non-padding+padding packets. + This definition is consistent with the overhead values in Proposal + #265, though it does not take node position into account. + * circpad_global_allowed_cells - The number of padding cells that must be transmitted before the - per-machine ratio limit is applied. - * circpad_max_global_padding_pct - - The maximum ratio of sent padding traffic to sent non-padding traffic - (expressed as a percent) to allow globally at a client or relay - before ceasing to pad. Ex: 75 means 75 padding packets for every 100 - non-padding+padding packets. This definition is consistent with the - overhead values in Proposal #265. + global ratio limit is applied. Additionally, each machine can specify its own per-machine limits for the allowed cell counters and padding overhead percentages.

1 0

[torspec/master] Clarify prop#254 in some parts.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit ab37543cfb16219f6632ce13691bc7c395300645 Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Oct 30 18:00:03 2018 +0200 Clarify prop#254 in some parts. Also kill some trailing whitespace. --- proposals/254-padding-negotiation.txt | 34 +++++++++++++++++++++++++++------- 1 file changed, 27 insertions(+), 7 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index 94d8287..b9ecc05 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -63,6 +63,12 @@ parameters: u16 ito_high_ms; }; +After the above cell is received, the guard should use the 'ito_low_ms' and +'ito_high_ms' values as the minimum and maximum values (respectively) for +inactivity before it decides to pad the channel. The actual timeout value is +randomly chosen between those two values through an appropriate probability +distribution (see proposal251 for the netflow padding protocol). + 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 @@ -89,10 +95,11 @@ Each state machine can contain up to three states ("Start", "Burst" and Each state of a padding machine specifies either: * A histogram describing inter-arrival cell delays; OR - * A parameterized distribution for inter-arrival cell delays + * A parameterized delay probability distribution for inter-arrival cell delays -In either case, the lower bound of the delay distribution can be specified as -a parameter, or it can be learned by measuring the RTT of the circuit. +In either case, the lower bound of the delay probability distribution can be +specified as a parameter, or it can be learned by measuring the RTT of the +circuit. If the histogram is used, it has an additional special "infinity" bin that means "infinite delay". @@ -196,7 +203,7 @@ are defined: When all bins are empty in a histogram, the padding machine emits the internal "bins empty" event to itself. -3.2. Machine Selection +3.2. State Machine Selection Clients will select which of the defined available padding machines to use based on the conditions that these machines specify. These conditions include: @@ -209,7 +216,16 @@ based on the conditions that these machines specify. These conditions include: Clients will only select machines whose conditions fully match given circuits. -3.3. Machine Neogitation +A machine is represented by a positive number that can be thought of as a "menu +option" through the list of padding machines. The currently supported padding +state machines are: + + [1]: CIRCPAD_MACHINE_CIRC_SETUP + + A padding machine that obscures the initial circuit setup in an + attempt to hide onion services. + +3.3. Machine Negotiation When a machine is selected, the client uses leaky-pipe delivery to send a RELAY_COMMAND_PADDING_NEGOTIATE to the target hop of the machine, using the @@ -222,7 +238,7 @@ following trunnel relay cell payload format: struct circpad_negotiate { u8 version IN [0]; u8 command IN [CIRCPAD_COMMAND_START, CIRCPAD_COMMAND_STOP]; - + /** Machine type is left unbounded because we can specify * new machines in the consensus */ u8 machine_type; @@ -230,6 +246,7 @@ following trunnel relay cell payload format: Upon receipt of a RELAY_COMMAND_PADDING_NEGOTIATE cell, the middle node sends a RELAY_COMMAND_PADDING_NEGOTIATED with the following format: + /** * This command tells the relay to alter its min and max netflow * timeout range values, and send padding at that rate (resuming @@ -238,12 +255,15 @@ a RELAY_COMMAND_PADDING_NEGOTIATED with the following format: u8 version IN [0]; u8 command IN [CIRCPAD_COMMAND_START, CIRCPAD_COMMAND_STOP]; u8 response IN [CIRCPAD_RESPONSE_OK, CIRCPAD_RESPONSE_ERR]; - + /** Machine type is left unbounded because we can specify * new machines in the consensus */ u8 machine_type; }; +The 'machine_type' field should be the same as the one from the +PADDING_NEGOTIATE cell. + If the response field is CIRCPAD_RESPONSE_OK, padding was successfully negotiated. If it is CIRCPAD_RESPONSE_ERR, the machine is torn down and we do not pad.

1 0

[torspec/master] Prop #254: Use range_usec instead of range_sec.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit a66d8a650f6ab540fb6b63d09dc737e59eefb67a Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 6 01:20:32 2018 +0000 Prop #254: Use range_usec instead of range_sec. --- proposals/254-padding-negotiation.txt | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index f166d5f..e569dcc 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -156,13 +156,12 @@ The first bin of the histogram (bin 0) has 0 width, with a delay value of start_usec+rtt_estimate (from the machine definition, and rtt estimate above). The remaining bins are exponentially spaced, starting at this offset and -covering the range of the histogram, which is range_sec*USEC_PER_SEC. +covering the range of the histogram, which is range_usec. -The intermediate bins thus divide the timespan range_sec*USEC_PER_SEC with -offset start_usec+rtt_estimate, so that smaller bin indexes represent narrower -time ranges, doubling up until the last bin. The last bin before the "infinity -bin" thus covers [start_usec+rtt_estimate+range_sec*USEC_PER_SEC/2, -CIRCPAD_DELAY_INFINITE). +The intermediate bins thus divide the timespan range_usec with offset +start_usec+rtt_estimate, so that smaller bin indexes represent narrower time +ranges, doubling up until the last bin. The last bin before the "infinity bin" +thus covers [start_usec+rtt_estimate+range_usec/2, CIRCPAD_DELAY_INFINITE). This exponentially increasing bin width allows the histograms to most accurately represent small interpacket delay (where accuracy is needed), and

1 0

[torspec/master] Merge remote-tracking branch 'tor-github/pr/41'
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit 9d8c044057807abfd9407d2b23acf6b95b142c1d Merge: 14881dc 98e6c66 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Nov 6 15:25:52 2018 -0500 Merge remote-tracking branch 'tor-github/pr/41' proposals/254-padding-negotiation.txt | 717 ++++++++++++---------------------- 1 file changed, 242 insertions(+), 475 deletions(-)

1 0

[torspec/master] Prop #254: Clarify special cases for bin 0 and inf bin-1.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit 470bde64e6d1161b0bcf0b266aa67ecbdd016774 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 6 01:23:10 2018 +0000 Prop #254: Clarify special cases for bin 0 and inf bin-1. --- proposals/254-padding-negotiation.txt | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index e569dcc..8cad35d 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -161,7 +161,8 @@ covering the range of the histogram, which is range_usec. The intermediate bins thus divide the timespan range_usec with offset start_usec+rtt_estimate, so that smaller bin indexes represent narrower time ranges, doubling up until the last bin. The last bin before the "infinity bin" -thus covers [start_usec+rtt_estimate+range_usec/2, CIRCPAD_DELAY_INFINITE). +thus covers [start_usec+rtt_estimate+range_usec/2, +start_usec+rtt_estimate+range_usec). This exponentially increasing bin width allows the histograms to most accurately represent small interpacket delay (where accuracy is needed), and @@ -203,6 +204,12 @@ are defined: When all bins are empty in a histogram, the padding machine emits the internal "bins empty" event to itself. +Bin 0 and the bin before the infinity bin both have special rules for purposes +of token removal. While removing tokens, all values less than bin 0 are +treated as part of bin 0, and all values greater than +start_usec+rtt_estimate+range_sec are treated as part of the bin before the +infinity bin. + 3.2. State Machine Selection Clients will select which of the defined available padding machines to use

1 0

[torspec/master] Prop #254: The infinity bin is also special.
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit 98e6c6637424fd1a887550a7336f193f6b84d50a Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue Nov 6 01:25:45 2018 +0000 Prop #254: The infinity bin is also special. --- proposals/254-padding-negotiation.txt | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/proposals/254-padding-negotiation.txt b/proposals/254-padding-negotiation.txt index 8cad35d..19ab6ce 100644 --- a/proposals/254-padding-negotiation.txt +++ b/proposals/254-padding-negotiation.txt @@ -201,14 +201,15 @@ are defined: * Closest -- Remove from the closest non-empty bin by index * Closest_time -- Remove from the closest non-empty bin by index, by time -When all bins are empty in a histogram, the padding machine emits the internal -"bins empty" event to itself. +When all bins exept the infinity bin are empty in a histogram, the padding +machine emits the internal "bins empty" event to itself. Bin 0 and the bin before the infinity bin both have special rules for purposes of token removal. While removing tokens, all values less than bin 0 are treated as part of bin 0, and all values greater than start_usec+rtt_estimate+range_sec are treated as part of the bin before the -infinity bin. +infinity bin. Tokens are not removed from the infinity bin when non-padding is +sent. (They are only removed when an "infinite" delay is chosen). 3.2. State Machine Selection

1 0

[tor/maint-0.3.5] Notify systemd of ShutdownWaitLength
by nickm＠torproject.org 06 Nov '18

06 Nov '18

commit 0d6d3e1f265609e8e74bf970a5d578300c465617 Author: Alex Xu (Hello71) <alex_y_xu(a)yahoo.ca> Date: Thu Oct 18 19:54:49 2018 -0400 Notify systemd of ShutdownWaitLength --- changes/ticket28113 | 3 +++ src/or/hibernate.c | 20 ++++++++++++++++++++ 2 files changed, 23 insertions(+) diff --git a/changes/ticket28113 b/changes/ticket28113 new file mode 100644 index 000000000..2585514b8 --- /dev/null +++ b/changes/ticket28113 @@ -0,0 +1,3 @@ + o Minor bugfixes (relay shutdown, systemd): + - Notify systemd of ShutdownWaitLength so it can be set to longer than + systemd's TimeoutStopSec. Fixes bug 28113; bugfix on 0.2.6.2-alpha. diff --git a/src/or/hibernate.c b/src/or/hibernate.c index e3c80b5f1..a59d52f3d 100644 --- a/src/or/hibernate.c +++ b/src/or/hibernate.c @@ -837,6 +837,26 @@ hibernate_begin(hibernate_state_t new_state, time_t now) "connections, and will shut down in %d seconds. Interrupt " "again to exit now.", options->ShutdownWaitLength); shutdown_time = time(NULL) + options->ShutdownWaitLength; +#ifdef HAVE_SYSTEMD + /* tell systemd that we may need more than the default 90 seconds to shut + * down so they don't kill us. add some extra time to actually finish + * shutting down, otherwise systemd will kill us immediately after the + * EXTEND_TIMEOUT_USEC expires. this is an *upper* limit; tor will probably + * only take one or two more seconds, but assume that maybe we got swapped + * out and it takes a little while longer. + * + * as of writing, this is a no-op with all-defaults: ShutdownWaitLength is + * 30 seconds, so this will extend the timeout to 60 seconds. + * default systemd DefaultTimeoutStopSec is 90 seconds, so systemd will + * wait (up to) 90 seconds anyways. + * + * 2^31 usec = ~2147 sec = ~35 min. probably nobody will actually set + * ShutdownWaitLength to more than that, but use a longer type so we don't + * need to think about UB on overflow + */ + sd_notifyf(0, "EXTEND_TIMEOUT_USEC=%" PRIu64, + ((uint64_t)(options->ShutdownWaitLength) + 30) * TOR_USEC_PER_SEC); +#endif } else { /* soft limit reached */ hibernate_end_time = interval_end_time; }

1 0