doc/HACKING/CircuitPaddingQuickStart.md

   1 # A Padding Machine from Scratch
   2
   3 A quickstart guide by Tobias Pulls.
   4
   5 This document describes the process of building a "padding machine" in tor's new
   6 circuit padding framework from scratch. Notes were taken as part of porting
   7 [Adaptive Padding Early
   8 (APE)](https://www.cs.kau.se/pulls/hot/thebasketcase-ape/) from basket2 to the
   9 circuit padding framework. The goal is just to document the process and provide
  10 useful pointers along the way, not create a useful machine.
  11
  12 The quick and dirty plan is to:
  13 1. clone and compile tor
  14 2. use newly built tor in TB and at small (non-exit) relay we run
  15 3. add a bare-bones APE padding machine
  16 4. run the machine, inspect logs for activity
  17 5. port APE's state machine without thinking much about parameters
  18
  19 ## Clone and compile tor
  20
  21 ```console
  22 $ git clone https://git.torproject.org/tor.git
  23 $ cd tor
  24 $ git checkout tor-0.4.1.5
  25 ```
  26 Above we use the tag for tor-0.4.1.5 where the circuit padding framework was
  27 released. Note that this version of the framework is missing many features and
  28 fixes that have since been merged to origin/master. If you need the newest
  29 framework features, you should use that master instead.
  30
  31 ```console
  32 $ sh autogen.sh
  33 $ ./configure
  34 $ make
  35 ```
  36 When you run `./configure` you'll be told of missing dependencies and packages
  37 to install on debian-based distributions. Important: if you plan to run `tor` on
  38 a relay as part of the real Tor network and your server runs a distribution that
  39 uses systemd, then I'd recommend that you `apt install dpkg dpkg-dev
  40 libevent-dev libssl-dev asciidoc quilt dh-apparmor libseccomp-dev dh-systemd
  41 libsystemd-dev pkg-config dh-autoreconf libfakeroot zlib1g zlib1g-dev automake
  42 liblzma-dev libzstd-dev` and ensure that tor has systemd support enabled:
  43 `./configure --enable-systemd`. Without this, on a recent Ubuntu, my tor service
  44 was forcefully restarted (SIGINT interrupt) by systemd every five minutes.
  45
  46 If you want to install on your localsystem, run `make install`. For our case we
  47 just want the tor binary at `src/app/tor`.
  48
  49 ## Use tor in TB and at a relay
  50
  51 Download and install a fresh Tor Browser (TB) from torproject.org. Make sure it
  52 works. From the command line, relative to the folder created when you extracted
  53 TB, run `./Browser/start-tor-browser --verbose` to get some basic log output.
  54 Note the version of tor, in my case, `Tor 0.4.0.5 (git-bf071e34aa26e096)` as
  55 part of TB 8.5.4. Shut down TB, copy the `tor` binary that you compiled earlier
  56 and replace `Browser/TorBrowser/Tor/tor`. Start TB from the command line again,
  57 you should see a different version, in my case `Tor 0.4.1.5
  58 (git-439ca48989ece545)`.
  59
  60 The relay we run is also on linux, and `tor` is located at `/usr/bin/tor`. To
  61 view relevant logs since last boot `sudo journalctl -b /usr/bin/tor`, where we
  62 find `Tor 0.4.0.5 running on Linux`. Copy the locally compiled `tor` to the
  63 relay at a temporary location and then make sure it's ownership and access
  64 rights are identical to `/usr/bin/tor`. Next, shut down the running tor service
  65 with `sudo service tor stop`, wait for it to stop (typically 30s), copy our
  66 locally compiled tor to replace `/usr/bin/tor` then start the service again.
  67 Checking the logs we see `or 0.4.1.5 (git-439ca48989ece545)`.
  68
  69 Repeatedly shutting down a relay is detrimental to the network and should be
  70 avoided. Sorry about that.
  71
  72 We have one more step left before we move on the machine: configure TB to always
  73 use our middle relay. Edit `Browser/TorBrowser/Data/Tor/torrc` and set
  74 `MiddleNodes <fingerprint>`, where `<fingerprint>` is the fingerprint of the
  75 relay. Start TB, visit a website, and manually confirm that the middle is used
  76 by looking at the circuit display.
  77
  78 ## Add a bare-bones APE padding machine
  79
  80 Now the fun part. We have several resources at our disposal (mind that links
  81 might be broken in the future, just search for the headings):
  82 - The official [Circuit Padding Developer
  83   Documentation](https://storm.torproject.org/shared/ChieH_sLU93313A2gopZYT3x2waJ41hz5Hn2uG1Uuh7).
  84 - Notes we made on the [implementation of the circuit padding
  85   framework](https://github.com/pylls/padding-machines-for-tor/blob/master/notes/circuit-padding-framework.md).
  86 - The implementation of the current circuit padding machines in tor:
  87   [circuitpadding.c](https://gitweb.torproject.org/tor.git/tree/src/core/or/circuitpadding_machines.c)
  88   and
  89   [circuitpadding_machines.h](https://gitweb.torproject.org/tor.git/tree/src/core/or/circuitpadding_machines.h).
  90
  91 Please consult the above links for details. Moving forward, the focus is to
  92 describe what was done, not necessarily explaining all the details why.
  93
  94 Since we plan to make changes to tor, create a new branch `git checkout -b
  95 circuit-padding-ape-machine tor-0.4.1.5`.
  96
  97 We start with declaring two functions, one for the machine at the client and one
  98 at the relay, in `circuitpadding_machines.h`:
  99
 100 ```c
 101 void circpad_machine_relay_wf_ape(smartlist_t *machines_sl);
 102 void circpad_machine_client_wf_ape(smartlist_t *machines_sl);
 103 ```
 104
 105 The definitions go into `circuitpadding_machines.c`:
 106
 107 ```c
 108 /**************** Adaptive Padding Early (APE) machine ****************/
 109
 110 /**
 111  * Create a relay-side padding machine based on the APE design.
 112  */
 113 void
 114 circpad_machine_relay_wf_ape(smartlist_t *machines_sl)
 115 {
 116   circpad_machine_spec_t *relay_machine
 117   = tor_malloc_zero(sizeof(circpad_machine_spec_t));
 118
 119   relay_machine->name = "relay_wf_ape";
 120   relay_machine->is_origin_side = 0; // relay-side
 121
 122   // Pad to/from the middle relay, only when the circuit has streams
 123   relay_machine->target_hopnum = 2;
 124   relay_machine->conditions.min_hops = 2;
 125   relay_machine->conditions.state_mask = CIRCPAD_CIRC_STREAMS;
 126
 127   // limits to help guard against excessive padding
 128   relay_machine->allowed_padding_count = 1;
 129   relay_machine->max_padding_percent = 1;
 130
 131   // one state to start with: START (-> END, never takes a slot in states)
 132   circpad_machine_states_init(relay_machine, 1);
 133   relay_machine->states[CIRCPAD_STATE_START].
 134     next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
 135     CIRCPAD_STATE_END;
 136
 137   // register the machine
 138   relay_machine->machine_num = smartlist_len(machines_sl);
 139   circpad_register_padding_machine(relay_machine, machines_sl);
 140
 141   log_info(LD_CIRC,
 142            "Registered relay WF APE padding machine (%u)",
 143            relay_machine->machine_num);
 144 }
 145
 146 /**
 147  * Create a client-side padding machine based on the APE design.
 148  */
 149 void
 150 circpad_machine_client_wf_ape(smartlist_t *machines_sl)
 151 {
 152     circpad_machine_spec_t *client_machine
 153   = tor_malloc_zero(sizeof(circpad_machine_spec_t));
 154
 155   client_machine->name = "client_wf_ape";
 156   client_machine->is_origin_side = 1; // client-side
 157
 158   /** Pad to/from the middle relay, only when the circuit has streams, and only
 159   * for general purpose circuits (typical for web browsing)
 160   */
 161   client_machine->target_hopnum = 2;
 162   client_machine->conditions.min_hops = 2;
 163   client_machine->conditions.state_mask = CIRCPAD_CIRC_STREAMS;
 164   client_machine->conditions.purpose_mask =
 165     circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_GENERAL);
 166
 167   // limits to help guard against excessive padding
 168   client_machine->allowed_padding_count = 1;
 169   client_machine->max_padding_percent = 1;
 170
 171   // one state to start with: START (-> END, never takes a slot in states)
 172   circpad_machine_states_init(client_machine, 1);
 173   client_machine->states[CIRCPAD_STATE_START].
 174     next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
 175     CIRCPAD_STATE_END;
 176
 177   client_machine->machine_num = smartlist_len(machines_sl);
 178   circpad_register_padding_machine(client_machine, machines_sl);
 179   log_info(LD_CIRC,
 180            "Registered client WF APE padding machine (%u)",
 181            client_machine->machine_num);
 182 }
 183 ```
 184
 185 We also have to modify `circpad_machines_init()` in `circuitpadding.c` to
 186 register our machines:
 187
 188 ```c
 189 /* Register machines for the APE WF defense */
 190 circpad_machine_client_wf_ape(origin_padding_machines);
 191 circpad_machine_relay_wf_ape(relay_padding_machines);
 192 ```
 193
 194 We run `make` to get a new `tor` binary and copy it to our local TB.
 195
 196 ## Run the machine
 197
 198 To be able
 199 to view circuit info events in the console as we launch TB, we add `Log
 200 [circ]info notice stdout` to `torrc` of TB.
 201
 202 Running TB to visit example.com we first find in the log:
 203
 204 ```
 205 Aug 30 18:36:43.000 [info] circpad_machine_client_hide_intro_circuits(): Registered client intro point hiding padding machine (0)
 206 Aug 30 18:36:43.000 [info] circpad_machine_relay_hide_intro_circuits(): Registered relay intro circuit hiding padding machine (0)
 207 Aug 30 18:36:43.000 [info] circpad_machine_client_hide_rend_circuits(): Registered client rendezvous circuit hiding padding machine (1)
 208 Aug 30 18:36:43.000 [info] circpad_machine_relay_hide_rend_circuits(): Registered relay rendezvous circuit hiding padding machine (1)
 209 Aug 30 18:36:43.000 [info] circpad_machine_client_wf_ape(): Registered client WF APE padding machine (2)
 210 Aug 30 18:36:43.000 [info] circpad_machine_relay_wf_ape(): Registered relay WF APE padding machine (2)
 211 ```
 212
 213 All good, our machine is running. Looking further we find:
 214
 215 ```
 216 Aug 30 18:36:55.000 [info] circpad_setup_machine_on_circ(): Registering machine client_wf_ape to origin circ 2 (5)
 217 Aug 30 18:36:55.000 [info] circpad_node_supports_padding(): Checking padding: supported
 218 Aug 30 18:36:55.000 [info] circpad_negotiate_padding(): Negotiating padding on circuit 2 (5), command 2
 219 Aug 30 18:36:55.000 [info] circpad_machine_spec_transition(): Circuit 2 circpad machine 0 transitioning from 0 to 65535
 220 Aug 30 18:36:55.000 [info] circpad_machine_spec_transitioned_to_end(): Padding machine in end state on circuit 2 (5)
 221 Aug 30 18:36:55.000 [info] circpad_circuit_machineinfo_free_idx(): Freeing padding info idx 0 on circuit 2 (5)
 222 Aug 30 18:36:55.000 [info] circpad_handle_padding_negotiated(): Middle node did not accept our padding request on circuit 2 (5)
 223 ```
 224 We see that our middle support padding (since we upgraded to tor-0.4.1.5), that
 225 we attempt to negotiate, our machine starts on the client, transitions to the
 226 end state, and is freed. The last line shows that the middle doesn't have a
 227 padding machine that can run.
 228
 229 Next, we follow the same steps as earlier and replace the modified `tor` at our
 230 middle relay. We don't update the logging there to avoid logging on the info
 231 level on the live network. Looking at the client log again we see that
 232 negotiation works as before except for the last line: it's missing, so the
 233 machine is running at the middle as well.
 234
 235 ## Implementing the APE state machine
 236
 237 Porting is fairly straightforward: define the states for all machines, add two
 238 more machines (for the receive portion of WTFP-PAD, beyond AP), and pick
 239 reasonable parameters for the distributions (I completely winged it now, as when
 240 implementing APE). The [circuit-padding-ape-machine
 241 branch](https://github.com/pylls/tor/tree/circuit-padding-ape-machine) contains
 242 the commits for the full machines with plenty of comments.
 243
 244 Some comments on the process:
 245
 246 - `tor-0.4.1.5` did not support two machines on the same circuit, the following
 247   fix had to be made: https://bugs.torproject.org/tpo/core/tor/31111 .
 248   The good news is that everything else seems to work after the small change in
 249   the fix.
 250 - APE randomizes its distributions. Currently, this can only be done during
 251   start of `tor`. This makes sense in the censorship circumvention setting
 252   (`obfs4`), less so for WF defenses: further randomizing each circuit is likely
 253   a PITA for attackers with few downsides.
 254 - it was annoying to figure out that the lack of systemd support in my compiled
 255   tor caused systemd to interrupt (SIGINT) my tor process at the middle relay
 256   every five minutes. Updated build steps above to hopefully save others the
 257   pain.
 258 - there's for sure some bug on relays when sending padding cells too early (?).
 259   It can happen with some probability with the APE implementation due to
 260   `circpad_machine_relay_wf_ape_send()`. Will investigate next.
 261 - Moving the registration of machines from the definition of the machines to
 262   `circpad_machines_init()` makes sense, as suggested in the circuit padding doc
 263   draft.
 264
 265 Remember that APE is just a proof-of-concept and we make zero claims about its
 266 ability to withstand WF attacks, in particular those based on deep learning.