- tor-dev - lists.torproject.org

Effect of padding on end to end correlation false positive rate
by s7r 20 Oct '15

20 Oct '15

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hello, I have an idea which I want to put into a proposal, but need a clarification first so I won't be working on something which doesn't make a big difference. I am describing something like a Sybil attack where the adversary runs relays, gets lucky and is selected in a certain position of a certain rendezvous circuit and can do an end to end correlation of the traffic (both ends). This is different from one end correlation or website fingerprinting attack. For this scenario: HS -> Guard -> Middle1 -> Middle2 -> RDV -> MiddleC -> GuardC -> Client If the client is the attacker, and Middle1 is an evil relay colluding with him, and it was selected 2nd hop in a rendezvous circuit that connects the HS with the attacker (rendezvous is not colluding), he can learn the guard of the hidden service. The client (attacker) can send traffic over that circuit until he gathers enough data to make a fair assumption about where the traffic is coming from (identify the guard of that HS). I am not sure if there will even be a nonzero false positive rate in this context. Confirmation needed for these assumptions, this is what I think after reading: [0],[1]. Does this change with padding? If yes, how? For the same scenario described above, if padding is used, will the attacker have to own the entire path to the guard (Middle1 and Middle2 in the same circuit, since the rest of the path is under his control to select anyway), in order to make a reasonable guess on which might be the guard he is interested in? Or can he make the difference between the real traffic and the padding / dummy traffic and have the same results as with no padding? [0]: https://blog.torproject.org/blog/one-cell-enough [1]: https://blog.torproject.org/blog/traffic-correlation-using-netflows -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (MingW32) iQEcBAEBCAAGBQJWIU5yAAoJEIN/pSyBJlsRlj4H+wcAc958SazmoXgYTtJisK5R dgcWZILgnYTYg17ub8Y3Hsgh0YjJyEgwgXV/r6ftNNir8kMSn3t+KMFAt9OpVhOJ 4W0f3E/X18viJNn3Pcb3FDc41sXxpwMVdUd337wGzqaNb8wsCARspmkDv9gdsLje GTTrz2MUa6lWyZHEuJMp02W2pkPVr48UnOsd0S0lyiDM3uxAAQyEtS9XwQyd+hBE KgLG7DHgwOnNzpBeQYJ5KlTzWi6j/NGxXcnHWcuWkq32ZG/gQsw6I43BNV9DMs6r 3UJbrdHsYJKDq8I16Ir0fblaOjsxmU7cEZZioOVngmw8wG6KevGI7fYKsEcqAhk= =CJly -----END PGP SIGNATURE-----

2 1

ResearchEthics
by grarpamp 19 Oct '15

19 Oct '15

https://trac.torproject.org/projects/tor/wiki/doc/ResearchEthics Any number of problems and obstacles to legitimate research areas exist with this... " Examples of unacceptable research activity It is not acceptable to run an HSDir, harvest onion addresses, and do a Web crawl of those onion services. Don't set up exit relays to sniff, or tamper with exit traffic. " Assuming such bans, how is one supposed to legitimately research and report on the real makeup of onion or exit space? These are significant unanswered questions regarding tor use. Concentrate not on bans, which will be ignored by both legit and illegit researchers anyways, but on proper design for data handling and minimization, particularly being sensitive to the tor users and operators involved lest that data become compromised at any stage before final anonymization and wiping.

5 7

Time-to-first-byte on trac.torproject.org
by Virgil Griffith 19 Oct '15

19 Oct '15

I started using Trac a bit more and the slowness is a little unpleasant. Here are some stats: http://www.webpagetest.org/result/151019_RW_387/ The time-to-first-byte is *painful* on both the first load as well as reload. Are there some ways we could improve this? If it's sever-power I'm willing to contribute to a fund for it, but my first thought is that more internal caching needs to be turned on within Trac. Common queries like the frontpage shouldn't be this difficult. But they are inherently this difficult, then we should at least spread it out among multiple machines. -V

1 0

Another Virtual Network Environment needs your I/O
by Rob van der Hoeven 18 Oct '15

18 Oct '15

Hi folks, During this hot summer I did some cool programming which resulted in... Another Virtual Network Environment (avne) AVNE is a small Linux program that runs other programs inside a virtual network environment. All network traffic from this environment is intercepted and forwarded to the Tor network. Interception is transparent and is guaranteed to be 100% effective. To forward network traffic you can simply type avne followed by a program name. Examples: avne bash avne ip link avne iceweasel -P avne -no-remote avne chromium --disable-cache avne wget https://blog.torproject.org/ Because the network interception takes place at the IP-level, no special Tor configuration is needed. In theory all TCP-clients should now be able to use the Tor network. AVNE is currently in the alpha phase of development. It works quite well, but for the for the first beta version I need input from this community. First of all I want to know if there are programs that do not work with avne. I tested with firefox, chromium, wget etc. and encountered no problems. The second question I have is: are there programs / protocols which should be blocked by avne? For example: I think its a bad idea to support unencrypted POP3. Of course I am also interested in bug-reports and your ideas for improvement. On my blog I wrote an article about avne that explains the technologies it uses (User Space Networking and Lightweight virtualization), and also gives an overview of its implementation. You can find the article here: https://hoevenstein.nl/another-virtual-network-environment The source code can be downloaded at: https://hoevenstein.nl/downloads An on-line viewable version of the code is at: https://hoevenstein.nl/source-code-avne-c Hope you like the ideas and code. And of course, your feedback is much appreciated! Rob. https://hoevenstein.nl

2 5

Re: [tor-dev] Crux: Privacy-preserving statistics for Tor
by Vasilios Mavroudis 18 Oct '15

18 Oct '15

Hi, so you were right the databases were corrupt, but they shouldn't have been there in the first place. :-) I didn't want to include large files in the git repo (~120mb in total), so there is a generation script in the tools directory (now added). I added some instructions on the readme file too. Of course, this procedure is done only once. I tried it and it should work now, but let me know if there is still a problem. There is a plan to optimize the way the pre-computed values are used, and this could potentially shrink the size of the databases by a lot. Vasilis On 17 October 2015 at 15:56, str4d <str4d(a)i2pmail.org> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA512 > > str4d wrote: > > Vasilios Mavroudis wrote: > >> Hello, > > > >> I would like to introduce our project "Crux", which enables the > >> computation of privacy preserving statistics on sensitive data. > >> The project was developed at University College London (UCL) by > >> me, in close collaboration with George Danezis. > > > > This is fantastic work. Haven't read all of your thesis yet, but > > it looks similar to the stats collection system that we ran for a > > while inside I2P, but with the privacy protections that I wanted it > > to have. Well done! > > > > > >> "Crux" was designed with Tor hidden services in mind (in > >> accordance with this > >> <https://research.torproject.org/techreports/hidden-service-stats-201 > 5 > > > >> > - -04-28.pdf> > > > > > > Tor > >> Tech Report), but it can be applied on various kinds of data > >> (given an appropriate parser). > > > > Excellent. I want to use this in I2P :) > > > > > >> It supports three statistics (i.e. mean, median, variance) and > >> its threat model is compatible Tor's (see technical document > >> below). > > > > I will look into this, but I doubt there will be any > > insurmountable incompatibilities with I2P's threat model. > > > >> Currently, we don't have a parser specific for the data > >> collected by the Tor relays, but we plan to keep adding > >> functionality. > > > >> The source code can be found here: > >> https://github.com/mavroudisv/Crux The theoretical background, > >> threat model, security argument and technical details can be > >> found here: link <http://mavroudisv.eu/files/thesis.pdf> > > > > > >> Ideas, comments, feedback much appreciated! > > > > Firstly: needs more docs. I shouldn't have to read your entire > > thesis in order to figure out how to run it :P The README is a good > > start, but the command parameters need clarification/definitions, > > and it is not at all obvious how the relays work. An XLS file is > > also mentioned without explanation. > > I have now tried running the code, but the "unit test" run by > authority.py fails because bsbdb.btopen() returns an empty dict. I > don't know if this is because the table files are broken or because of > a local issue with my setup (I am using a virtualenv, but I get the > same empty dict when I try to open the tables manually outside the > virtualenv). I am not going to try and fix the latter on my own, > because bsddb is deprecated since Python 2.6, so you shouldn't really > be using it :) (But it must be something else, because I tried using > bsddb3 instead and that also returns an empty dict). > > str4d > > > > > Secondly, you could probably simplify configuration by managing > > hidden service connections yourself. I believe the Stem library can > > do this? I2P has a python library that can be used to listen on and > > connect to I2P Destinations, with a socket-like interface. > > > > It's not clear to me from your thesis whether you plan to merge > > the relay component into the Tor relay code (and have the Tor > > relays talk directly to the query processors), or have your relays > > running separately and interfacing with the Tor relays to fetch > > stats. This will potentially alter how it would be used with other > > networks. In I2P's case I'd imagine it would be easiest (in terms > > of usability by those setting up relays) to write an I2P plugin in > > Java that performs the relay role, but I wouldn't want to be > > duplicating a lot of logic that subsequently needs to be kept > > in-sync with upstream :) > > > > str4d > > > > > >> Vasilis > > > > > > > >> _______________________________________________ tor-dev mailing > >> list tor-dev(a)lists.torproject.org > >> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > > > > _______________________________________________ tor-dev mailing > > list tor-dev(a)lists.torproject.org > > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > > > -----BEGIN PGP SIGNATURE----- > > iQIcBAEBCgAGBQJWItIgAAoJEBO17ljAn7PglsQP/3tOrL9EZfYMb5fxxVI6/wJm > qDvA8RpbEJDhoMjOc9sLNyMVgvGGPxEdma8I/R8H37yIPOp2GJg82MoXfUk+AGFe > 5ZIIXwf2EzHH0RFLRI5xaQ4DW3Ru1yIzH+E3vhuGclL87YRKnAM0xkMQcueR5xo5 > /ETe9TI7oPCdETI4J6iFoM+Ob9qsRiEVeuT5HEFFKwQhBvl0NSpfMHV9ftuxQHuu > I2B9jomnBdzF9OXnSQrYXg3ho2rxX4hO1TZfQHg5DgHvkt8TQYQM3cwdGE7/rsqC > d4+kBW2RuAz68wq+fLPeeZ2U2ff2QqmDLqVyUJvpP5RqeUcv66J/iYm7md886tTc > palwVGodKiTJ6DBM0z1K97x6Sl1jJXEAkZQAr2yQ8jrC/BJqQRPu2vHeZILqbMEQ > UU3JLjIk/Jc2RGK6zitvj4kTrLdfACEQMYy3brQUawZhaM42QNQgb3LQq1bJXzUo > vISZckX/CVfF+R63oO085LYOO7oTLyY3EhA1PCXiV09Usl/To66Oh4AVYtz/lPLH > 6uoWR/ic5X9gFIXt1t+617+i/L/ILMfqkqN7GzoSbQ8QfyBJrjIikuj575M7AH3o > RuhRYHUTmaCRL+9niDFG/mSVGBxBqiSfW1eS5pGE3hIAcLQd0eFT/38HRdonkfLP > Ug5ihMFSKfKmCIljQ6mm > =jDmS > -----END PGP SIGNATURE----- >

1 0

Hello, I can't use Google Search Engine Service through Tor proxy.
by Li Xiaodong 18 Oct '15

18 Oct '15

*Hello, I can't use Google Search Engine Service through Tor proxy. Google asked me to enter a Verification Code. After I entered the Verification Code, Google asked me enter a new Verification Code. Could you please communicate this problem to Google Corporation? Could you please suggest to Google Corporation that it should allow Tor users to normally use Google Search Engine Service? Thank you very much for your help. I really appreciate it.*

2 1

Re: [tor-dev] Crux: Privacy-preserving statistics for Tor
by str4d 17 Oct '15

17 Oct '15

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 str4d wrote: > Vasilios Mavroudis wrote: >> Hello, > >> I would like to introduce our project "Crux", which enables the >> computation of privacy preserving statistics on sensitive data. >> The project was developed at University College London (UCL) by >> me, in close collaboration with George Danezis. > > This is fantastic work. Haven't read all of your thesis yet, but > it looks similar to the stats collection system that we ran for a > while inside I2P, but with the privacy protections that I wanted it > to have. Well done! > > >> "Crux" was designed with Tor hidden services in mind (in >> accordance with this >> <https://research.torproject.org/techreports/hidden-service-stats-201 5 > >> - -04-28.pdf> > > > Tor >> Tech Report), but it can be applied on various kinds of data >> (given an appropriate parser). > > Excellent. I want to use this in I2P :) > > >> It supports three statistics (i.e. mean, median, variance) and >> its threat model is compatible Tor's (see technical document >> below). > > I will look into this, but I doubt there will be any > insurmountable incompatibilities with I2P's threat model. > >> Currently, we don't have a parser specific for the data >> collected by the Tor relays, but we plan to keep adding >> functionality. > >> The source code can be found here: >> https://github.com/mavroudisv/Crux The theoretical background, >> threat model, security argument and technical details can be >> found here: link <http://mavroudisv.eu/files/thesis.pdf> > > >> Ideas, comments, feedback much appreciated! > > Firstly: needs more docs. I shouldn't have to read your entire > thesis in order to figure out how to run it :P The README is a good > start, but the command parameters need clarification/definitions, > and it is not at all obvious how the relays work. An XLS file is > also mentioned without explanation. I have now tried running the code, but the "unit test" run by authority.py fails because bsbdb.btopen() returns an empty dict. I don't know if this is because the table files are broken or because of a local issue with my setup (I am using a virtualenv, but I get the same empty dict when I try to open the tables manually outside the virtualenv). I am not going to try and fix the latter on my own, because bsddb is deprecated since Python 2.6, so you shouldn't really be using it :) (But it must be something else, because I tried using bsddb3 instead and that also returns an empty dict). str4d > > Secondly, you could probably simplify configuration by managing > hidden service connections yourself. I believe the Stem library can > do this? I2P has a python library that can be used to listen on and > connect to I2P Destinations, with a socket-like interface. > > It's not clear to me from your thesis whether you plan to merge > the relay component into the Tor relay code (and have the Tor > relays talk directly to the query processors), or have your relays > running separately and interfacing with the Tor relays to fetch > stats. This will potentially alter how it would be used with other > networks. In I2P's case I'd imagine it would be easiest (in terms > of usability by those setting up relays) to write an I2P plugin in > Java that performs the relay role, but I wouldn't want to be > duplicating a lot of logic that subsequently needs to be kept > in-sync with upstream :) > > str4d > > >> Vasilis > > > >> _______________________________________________ tor-dev mailing >> list tor-dev(a)lists.torproject.org >> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > > _______________________________________________ tor-dev mailing > list tor-dev(a)lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > -----BEGIN PGP SIGNATURE----- iQIcBAEBCgAGBQJWItIgAAoJEBO17ljAn7PglsQP/3tOrL9EZfYMb5fxxVI6/wJm qDvA8RpbEJDhoMjOc9sLNyMVgvGGPxEdma8I/R8H37yIPOp2GJg82MoXfUk+AGFe 5ZIIXwf2EzHH0RFLRI5xaQ4DW3Ru1yIzH+E3vhuGclL87YRKnAM0xkMQcueR5xo5 /ETe9TI7oPCdETI4J6iFoM+Ob9qsRiEVeuT5HEFFKwQhBvl0NSpfMHV9ftuxQHuu I2B9jomnBdzF9OXnSQrYXg3ho2rxX4hO1TZfQHg5DgHvkt8TQYQM3cwdGE7/rsqC d4+kBW2RuAz68wq+fLPeeZ2U2ff2QqmDLqVyUJvpP5RqeUcv66J/iYm7md886tTc palwVGodKiTJ6DBM0z1K97x6Sl1jJXEAkZQAr2yQ8jrC/BJqQRPu2vHeZILqbMEQ UU3JLjIk/Jc2RGK6zitvj4kTrLdfACEQMYy3brQUawZhaM42QNQgb3LQq1bJXzUo vISZckX/CVfF+R63oO085LYOO7oTLyY3EhA1PCXiV09Usl/To66Oh4AVYtz/lPLH 6uoWR/ic5X9gFIXt1t+617+i/L/ILMfqkqN7GzoSbQ8QfyBJrjIikuj575M7AH3o RuhRYHUTmaCRL+9niDFG/mSVGBxBqiSfW1eS5pGE3hIAcLQd0eFT/38HRdonkfLP Ug5ihMFSKfKmCIljQ6mm =jDmS -----END PGP SIGNATURE-----

1 0

Tor Environment Variables
by Dewayne Hicks 16 Oct '15

16 Oct '15

Hi, Is there a specific page (wiki/docs) that details all of the Tor environment variables for Linux? Ideally this would also map to TBB preferences access via about:config. The topic has been mentioned occasionally on the issue tracker [1] but the actual variables are spread out over a number of pages and it's not clear if the lists are complete. Thanks [1]: https://trac.torproject.org/projects/tor/ticket/13005

1 0

Trac priorities and severities
by David Goulet 15 Oct '15

15 Oct '15

Hello tor-dev! While 028 bug triaging, we realized that we *really* need priorities to not be a banana field deprive of useful meaning. If you are unaware or don't remember, the priority field in a trac ticket can be: blocker critical major normal minor trivial Those are "severities" *NOT* priorities. Now I propose the following: 1) I take those above and copy them to the already existing but empty severity field. They seem reasonable and we are used to them. 2) Rename all priorities to something more meaninful: blocker --> Immediate criticial --> Very High major --> High normal --> Medium minor --> Low trivial --> Very Low 3) World trac domination! This could get confusing for some tickets after that but at least we can transition towards using the Severity field from now on. Anyone object or think it's a bad bad idea? This is very little work for lots of benefits so I don't want to get into a massive reorg. or bike-shedding the naming convention. I would be open though to drop the "Very [High|Low]" field but that could make some tickets with less semantic. I'll let that sync for some days before doing anything. Let's not wait anymore and take back our Trac system! Freeeeeeeeeedom!!!!! Cheers! David

6 8

Proposal: Padding Negotiation
by Mike Perry 14 Oct '15

14 Oct '15

Here's a proposal describing some padding negotiation cell primitives that should be useful to defend against website traffic fingerprinting, hidden service circuit fingerprinting, and probably just about any other traffic analysis attack under the sun. The proposal is in my git remote at: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/xxx… ============================== 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 { /* Number of microseconds before sending cells (cumulative) */ u32 when_send[80]; /* Number of cells to send at time point sum(when_send[0..i]) */ u16 num_cells[80]; /* Adaptivity: If 1, and server-originating cells arrive before the next when_send time, then decrement the next non-zero when_send index, so we don't send a padding cell then, too */ 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. 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; /* 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]; 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_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. */ 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_toks IN [0,1]; }; struct adaptive_padding_machine { /* This is a bitfield which specifies which direction and types * of traffic should cause us to transition to the burst * state (and schedule a packet from the burst histogram). */ u8 transition_burst_events; struct burst_state burst; struct gap_state gap; }; /* This is the full payload of a RELAY_COMMAND_PADDING_ADAPTIVE * cell. */ struct relay_command_padding_adaptive { 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. 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 Start state. 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. 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 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 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].gap.transition_reschedule_events = RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT; machines[0].gap.transition_burst_events = RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT; The rest of the transition fields would be 0. Adding additional transition flags will either increase or decrease the amount of padding sent, depending on their placement. 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); 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_tok field is set to true for a given state's histogram, then whenever a padding packet is sent, the corresponding histogram bin's token count is decremented by one. If a packet matching the current state's transition_reschedule_events bitmask arrives from the server before the chosen padding timer expires, then a token is removed from the nearest non-empty bin corresponding to the delay since the last packet was sent, and the padding packet timer is re-sampled from the histogram. If the entire histogram becomes empty, it is then refilled to the original values. 3.2.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 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: 100 * CircuitPaddingLimitCount - The number of padding cells that must be transmitted before the ratio limit is applied. - Default: 500 * CircuitPaddingLimitTime - The time period in seconds over which to count padding cells for application of the ratio limit. - Default: 60 XXX: Should we cap padding at these rates, or fully disable it once they're crossed? Proposal 251 introduced extra-info accounting at relays to enable us to measure the total overhead of both link and circuit-level padding at various relays. 4.2. 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. ------------------- 1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-paddin… 2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf -- Mike Perry

3 3