September 2015 - tor-commits - lists.torproject.org

[translation/tor-messenger-otrproperties] Update translations for tor-messenger-otrproperties
by translation＠torproject.org 25 Sep '15

25 Sep '15

commit 1e0d05e4d9393cabf825011b3307890c6d5155c9 Author: Translation commit bot <translation(a)torproject.org> Date: Fri Sep 25 12:16:40 2015 +0000 Update translations for tor-messenger-otrproperties --- sq/otr.properties | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/sq/otr.properties b/sq/otr.properties index 8216e88..ada3ed7 100644 --- a/sq/otr.properties +++ b/sq/otr.properties @@ -22,10 +22,10 @@ error.not_priv=Ju dërguat të dhëna të shifruara tek %S, që nuk i priste ato error.unreadable=Ju transmetuat një mesazh të shifruar të palexueshëm. error.malformed=Ju transmetuat një mesazh të dhënash të keqformuar. resent=[i ridërguar] -tlv.disconnected=%S has ended their private conversation with you; you should do the same. -query.msg=%S has requested an Off-the Record private conversation. However, you do not have a plugin to support that. See http://otr.cypherpunks.ca/ for more information. -trust.unused=Unused -trust.not_private=Not Private -trust.unverified=Unverified +tlv.disconnected=%S e ka përfunduar bisedën e vet private me ju; duhet të bëni të njëjtën gjë. +query.msg=%S ka kërkuar një bisedë private Jashtë Regjistrimit. Sidoqoftë, ju nuk dispononi një plugin që ta bëni këtë. Shihni http://otr.cypherpunks.ca/ për më shumë informacion. +trust.unused=E papërdorur +trust.not_private=Joprivate +trust.unverified=E paverifikuar trust.private=Private -trust.finished=Finished +trust.finished=E përfunduar

1 0

[translation/tor-messenger-authproperties_completed] Update translations for tor-messenger-authproperties_completed
by translation＠torproject.org 25 Sep '15

25 Sep '15

commit 6dd0818bf2fe4fc01a8bc9d878c55c349969b87d Author: Translation commit bot <translation(a)torproject.org> Date: Fri Sep 25 12:16:22 2015 +0000 Update translations for tor-messenger-authproperties_completed --- sq/auth.properties | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sq/auth.properties b/sq/auth.properties index bab9878..1d65fcb 100644 --- a/sq/auth.properties +++ b/sq/auth.properties @@ -1,4 +1,4 @@ -auth.title=Verifikoni identitetin e %S's +auth.title=Verifikoni identitetin e %S. auth.yourFingerprint=Gjurmë gishti për ju, %S:\n%S auth.theirFingerprint=Gjurma e gishtit e pandehur për %S:\n%S auth.help=Verifikimi i identitetit të një kontakti ndihmon për t'u siguruar se personi me të cilin po flisni është ai që pretendon se është.

1 0

[translation/tor-messenger-authproperties] Update translations for tor-messenger-authproperties
by translation＠torproject.org 25 Sep '15

25 Sep '15

commit 025af4d70b8793c78c2a8bb4098f51e0d9097107 Author: Translation commit bot <translation(a)torproject.org> Date: Fri Sep 25 12:16:17 2015 +0000 Update translations for tor-messenger-authproperties --- sq/auth.properties | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sq/auth.properties b/sq/auth.properties index bab9878..1d65fcb 100644 --- a/sq/auth.properties +++ b/sq/auth.properties @@ -1,4 +1,4 @@ -auth.title=Verifikoni identitetin e %S's +auth.title=Verifikoni identitetin e %S. auth.yourFingerprint=Gjurmë gishti për ju, %S:\n%S auth.theirFingerprint=Gjurma e gishtit e pandehur për %S:\n%S auth.help=Verifikimi i identitetit të një kontakti ndihmon për t'u siguruar se personi me të cilin po flisni është ai që pretendon se është.

1 0

[translation/tails-misc_completed] Update translations for tails-misc_completed
by translation＠torproject.org 25 Sep '15

25 Sep '15

commit 8893819428edb8035541f5d1bfec9544db4d5dfc Author: Translation commit bot <translation(a)torproject.org> Date: Fri Sep 25 12:15:45 2015 +0000 Update translations for tails-misc_completed --- sq.po | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sq.po b/sq.po index f53c300..7b67a26 100644 --- a/sq.po +++ b/sq.po @@ -9,7 +9,7 @@ msgstr "" "Project-Id-Version: The Tor Project\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2015-09-20 19:32+0200\n" -"PO-Revision-Date: 2015-09-24 19:36+0000\n" +"PO-Revision-Date: 2015-09-25 11:52+0000\n" "Last-Translator: Bujar Tafili\n" "Language-Team: Albanian (http://www.transifex.com/otf/torproject/language/sq/)\n" "MIME-Version: 1.0\n"

1 0

[translation/tails-misc] Update translations for tails-misc
by translation＠torproject.org 25 Sep '15

25 Sep '15

commit 7361e36775c7c07981d207ea682ace6f9e7b888d Author: Translation commit bot <translation(a)torproject.org> Date: Fri Sep 25 12:15:41 2015 +0000 Update translations for tails-misc --- sq.po | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sq.po b/sq.po index f53c300..7b67a26 100644 --- a/sq.po +++ b/sq.po @@ -9,7 +9,7 @@ msgstr "" "Project-Id-Version: The Tor Project\n" "Report-Msgid-Bugs-To: \n" "POT-Creation-Date: 2015-09-20 19:32+0200\n" -"PO-Revision-Date: 2015-09-24 19:36+0000\n" +"PO-Revision-Date: 2015-09-25 11:52+0000\n" "Last-Translator: Bujar Tafili\n" "Language-Team: Albanian (http://www.transifex.com/otf/torproject/language/sq/)\n" "MIME-Version: 1.0\n"

1 0

[torspec/master] Add mikeperry's padding negotiation proposal and give it a number.
by isis＠torproject.org 25 Sep '15

25 Sep '15

commit 91e207e91d0375273004ecf16364c073e3e82043 Author: Isis Lovecruft <isis(a)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-paddin… +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-paddin… -2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf -3. https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses

1 0

[torspec/master] Merge remote-tracking branch 'tpo-mikeperry/padding_negotiation-squashed'
by isis＠torproject.org 25 Sep '15

25 Sep '15

commit 45407cd6ad108aeae9d11e2df6db902d0fbb20b1 Merge: 887d1c1 8ee79e0 Author: Isis Lovecruft <isis(a)torproject.org> Date: Fri Sep 25 11:33:16 2015 +0000 Merge remote-tracking branch 'tpo-mikeperry/padding_negotiation-squashed' proposals/xxx-padding-negotiation.txt | 628 +++++++++++++++++++++++++++++++++ 1 file changed, 628 insertions(+)

1 0

[torspec/master] Add overhead accounting information.
by isis＠torproject.org 25 Sep '15

25 Sep '15

commit 8ee79e004dd83830446002a7fb0b1689c90130cb Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Sun Sep 13 19:32:39 2015 -0700 Add overhead accounting information. Also fix a typo pointed out by Marc Juarez, and perform some other misc cleanups. --- proposals/xxx-padding-negotiation.txt | 49 +++++++++++++++++++++++++++++---- 1 file changed, 43 insertions(+), 6 deletions(-) diff --git a/proposals/xxx-padding-negotiation.txt b/proposals/xxx-padding-negotiation.txt index b7d4e75..a42bd6c 100644 --- a/proposals/xxx-padding-negotiation.txt +++ b/proposals/xxx-padding-negotiation.txt @@ -192,6 +192,8 @@ specified in Trunnel as follows: /* 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]; @@ -224,6 +226,8 @@ specified in Trunnel as follows: /* 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]; @@ -253,6 +257,7 @@ specified in Trunnel as follows: 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 @@ -264,7 +269,10 @@ specified in Trunnel as follows: }; /* This is the full payload of a RELAY_COMMAND_PADDING_ADAPTIVE - * cell. */ + * 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 @@ -346,7 +354,7 @@ 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 -upstream, where as "RECV" means packets destined towards the client. +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. @@ -489,7 +497,7 @@ possible. The risks from this proposal are primarily DoS/resource exhaustion, and side channels. -4.1. Rate limiting +4.1. Rate limiting and accounting Fully client-requested padding introduces a vector for resource amplification attacks and general network overload due to @@ -523,9 +531,38 @@ padding requests should be ignored: XXX: Should we cap padding at these rates, or fully disable it once they're crossed? Probably cap? -Proposal 251 introduced extra-info accounting at relays to enable us to -measure the total overhead of both link and circuit-level padding at -various relays. +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

1 0

[torspec/master] Update proposal based on Teor's comments.
by isis＠torproject.org 25 Sep '15

25 Sep '15

commit 69c95087851a09602034b6614a0cc0cfa53f03a9 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Sun Sep 13 18:39:32 2015 -0700 Update proposal based on Teor's comments. Changes: * A zero machines.transition_burst_events means an immediate transition to the burst state. * Added RELAY_PADDING_TRANSITION_EVENT_BINS_EMPTY to allow a state transition when the bins become empty. * Change remove_tokens to allow client to specify removal direction for non-padding packets. * Make RELAY_COMMAND_PADDING_SCHEDULE take a variable number of scheduled times. * Increase and clarify rate limits. --- proposals/xxx-padding-negotiation.txt | 62 ++++++++++++++++++++++++--------- 1 file changed, 45 insertions(+), 17 deletions(-) diff --git a/proposals/xxx-padding-negotiation.txt b/proposals/xxx-padding-negotiation.txt index 0292f22..b7d4e75 100644 --- a/proposals/xxx-padding-negotiation.txt +++ b/proposals/xxx-padding-negotiation.txt @@ -106,11 +106,13 @@ 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[80]; + u32 when_send[schedule_length]; /* Number of cells to send at time point sum(when_send[0..i]) */ - u16 num_cells[80]; + 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 @@ -124,6 +126,10 @@ 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 @@ -175,6 +181,13 @@ specified in Trunnel as follows: 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 @@ -205,7 +218,7 @@ specified in Trunnel as follows: /* If true, remove tokens from the histogram upon padding and * non-padding activity. */ - u8 remove_toks IN [0,1]; + u8 remove_tokens IN [0..3]; }; /* This histogram encodes a delay distribution representing the @@ -237,7 +250,7 @@ specified in Trunnel as follows: /* If true, remove tokens from the histogram upon padding and non-padding activity. */ - u8 remove_toks IN [0,1]; + u8 remove_tokens IN [0..3]; }; struct adaptive_padding_machine { @@ -253,6 +266,9 @@ specified in Trunnel as follows: /* This is the full payload of a RELAY_COMMAND_PADDING_ADAPTIVE * cell. */ 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]; @@ -268,7 +284,9 @@ 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. +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 @@ -382,7 +400,7 @@ n = histogram_len-1 INFINITY_BIN = n a[0] = start_usec; -b[0] = start_usec + max_sec*USEC_PER_SEC/2^(n); +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) @@ -416,18 +434,25 @@ accuracy to larger timescales (where accuracy is not as important). 3.2.4. Token removal and refill -If the remove_tok field is set to true for a given state's histogram, -then whenever a padding packet is sent, the corresponding histogram -bin's token count is decremented by one. +If 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 the nearest non-empty bin corresponding to +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. +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 @@ -484,18 +509,19 @@ padding requests should be ignored: (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: 100 + - Default: 120 * CircuitPaddingLimitCount - The number of padding cells that must be transmitted before the ratio limit is applied. - - Default: 500 + - Default: 5000 * CircuitPaddingLimitTime - The time period in seconds over which to count padding cells for - application of the ratio limit. + 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? +they're crossed? Probably cap? Proposal 251 introduced extra-info accounting at relays to enable us to measure the total overhead of both link and circuit-level padding at @@ -548,16 +574,18 @@ 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 +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: This is bad. We need to add padding-level flow control windows :( +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-paddin… 2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf +3. https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses

1 0

[torspec/master] Note potential memory exhaustion DoS.
by isis＠torproject.org 25 Sep '15

25 Sep '15

commit 2b0eb5172f7d3effae6d3aabb2e15efd36926b1d Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Fri Sep 11 17:09:28 2015 -0700 Note potential memory exhaustion DoS. Also clarify terminology and address some formatting issues. --- proposals/xxx-padding-negotiation.txt | 184 ++++++++++++++++++++------------- 1 file changed, 113 insertions(+), 71 deletions(-) diff --git a/proposals/xxx-padding-negotiation.txt b/proposals/xxx-padding-negotiation.txt index 005045a..4202540 100644 --- a/proposals/xxx-padding-negotiation.txt +++ b/proposals/xxx-padding-negotiation.txt @@ -26,19 +26,23 @@ 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 urgently needed to defend against a malicious or +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. Right now, the only case where link-level padding is known -to defend against any realistic attacker is for low-resolution -netflow-based attacks (see Proposal 251[1]). +externally, such as for low-resolution netflow-based attacks (see +Proposal 251[1]). -In that scenario, the primary mechanism we need is a way for mobile -clients to tell their Guards to stop padding, or to pad less often. The -following Trunnel payloads should cover the needed parameters: +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; @@ -49,9 +53,9 @@ following Trunnel payloads should cover the needed parameters: u8 command IN [CELL_PADDING_COMMAND_STOP]; }; - /* This command tells the relay to alter its min and max timeout - range values, and send padding at that rate (resuming if - stopped). */ + /* 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]; @@ -63,25 +67,28 @@ following Trunnel payloads should cover the needed parameters: u16 ito_high_ms; }; -More complicated forms of link padding can still be specified using -the primitives in Section 3, by using "leaky pipe" topology to send -the RELAY commands to the Guard node instead of to later nodes in the -circuit. +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 end-to-end padding, we need two types of additional features: the +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 "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. +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) @@ -92,7 +99,8 @@ 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. +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: @@ -121,8 +129,9 @@ with 100 cells in 3*MAX_INT microseconds from the receipt of this cell. The following message is a generalization of the Adaptive Padding defense specified in "Timing Attacks and Defenses"[2]. -The message encodes either one or two state machines, each of which -contain two histograms ("Burst" and "Gap") governing their behavior. +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. @@ -141,25 +150,34 @@ 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). -Note that our generalization of the Adaptive Padding state machine -actually gives clients full control over the state transition events, -even allowing them to specify a single-state state machine if desired. -See Sections 3.2.1 and 3.2.2 for details. +The 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 padding to start or stop from a given state. */ + * 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; - /* - This encodes a histogram delay distribution representing the - probability of sending a single RELAY_DROP cell after a given - delay in response to a non-padding cell. + /* 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. */ struct burst_state { u8 histogram_len IN [2..51]; @@ -167,35 +185,31 @@ specified in Trunnel as follows: 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. + /* 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. + /* 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. - */ + /* This is a bitfield that specifies which direction and types + * of traffic that cause us to transition to the Gap state. */ u8 transition_gap_events; - /* Should we remove tokens from the histogram as packets are sent? */ + /* If true, remove tokens from the histogram upon padding and + * non-padding activity. */ u8 remove_toks IN [0,1]; }; - /* - 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. + /* 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. */ struct gap_state { u8 histogram_len IN [2..51]; @@ -204,31 +218,31 @@ specified in Trunnel as follows: 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). */ + * 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). */ + * 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. + /* This is a bitfield that specifies which direction and types + * of traffic that cause us to remain in the gap state: Cancel the + * pending padding packet (if any), and schedule another padding + * packet from our histogram. */ u8 transition_reschedule_events; - /* Should we remove tokens from the histogram as packets are sent? */ + /* If true, remove tokens from the histogram upon padding and + non-padding activity. */ u8 remove_toks IN [0,1]; }; struct adaptive_padding_machine { /* This is a bitfield which specifies which direction and types - of traffic should cause us to transition to the burst - state (and schedule a packet from the burst histogram). */ + * 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; @@ -236,7 +250,7 @@ specified in Trunnel as follows: }; /* This is the full payload of a RELAY_COMMAND_PADDING_ADAPTIVE - cell. */ + * cell. */ struct relay_command_padding_adaptive { u8 num_machines IN [1,2]; @@ -307,16 +321,24 @@ 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. +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. -The histograms that the client uses locally will likely differ from the -ones it sends to the upstream relay. +On the client, the "SENT" direction means packets destined towards the +upstream, 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: +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; @@ -338,6 +360,10 @@ 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 @@ -413,11 +439,18 @@ Actual optimal histogram and state transition construction for different traffic types is expected to be a topic for further research. Intuitively, the burst state is used to detect when the line is idle -(and should therefore have few or no tokens in low histogram bins), and -the gap state is used to fill in otherwise idle periods with artificial +(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). However, more complicated -interactions are also possible. +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 @@ -425,7 +458,7 @@ interactions are also possible. The risks from this proposal are primarily DoS/resource exhaustion, and side channels. -4.1. Traffic handling +4.1. Rate limiting Fully client-requested padding introduces a vector for resource amplification attacks and general network overload due to @@ -509,6 +542,15 @@ 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: This is bad. We need to add padding-level flow control windows :( + ------------------- 1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-paddin…

1 0