Merge remote-tracking branch 'tor-github/pr/1033'

9 files changed, 861 insertions, 95 deletions

diff --git a/changes/ticket28634 b/changes/ticket28634
new file mode 100644
index 0000000000..7ba05e5c55
--- /dev/null
+++ b/changes/ticket28634
@@ -0,0 +1,10 @@
+  o Major features (Circuit padding):
+    - Onion service clients will now add padding cells to the initial portions
+      of their INTRODUCE and RENDEZVOUS circuits, to make those circuits'
+      traffic patterns look more like general purpose Exit traffic. The
+      overhead for this is 2 extra cells in each direction for RENDEZVOUS
+      circuits, and 1 extra upstream cell and 10 downstream cells for INTRODUCE
+      circuits. This will only be enabled if the circuit's middle node supports
+      this feature, too. (Clients may specify fixed middle nodes with the MiddleNodes
+      torrc directive, and may force-disable this feature with the CircuitPadding
+      torrc directive). Closes ticket 28634.
diff --git a/scripts/maint/practracker/exceptions.txt b/scripts/maint/practracker/exceptions.txt
index 4cee5453f0..896180156b 100644
--- a/scripts/maint/practracker/exceptions.txt
+++ b/scripts/maint/practracker/exceptions.txt
@@ -290,3 +290,5 @@ problem function-size /src/tools/tor-resolve.c:build_socks5_resolve_request() 10
 problem function-size /src/tools/tor-resolve.c:do_resolve() 175
 problem function-size /src/tools/tor-resolve.c:main() 112
 problem function-size /src/core/or/circuitpadding.c:circpad_machine_schedule_padding() 107
+problem function-size /src/core/or/circuitpadding_machines.c:circpad_machine_relay_hide_intro_circuits() 104
+problem function-size /src/core/or/circuitpadding_machines.c:circpad_machine_client_hide_rend_circuits() 112
diff --git a/src/app/main/shutdown.c b/src/app/main/shutdown.c
index 1871717ad5..e4dcaa1324 100644
--- a/src/app/main/shutdown.c
+++ b/src/app/main/shutdown.c
@@ -139,6 +139,7 @@ tor_free_all(int postfork)
   dos_free_all();
   circuitmux_ewma_free_all();
   accounting_free_all();
+  circpad_free_all();
 
   if (!postfork) {
     config_free_all();
diff --git a/src/core/include.am b/src/core/include.am
index f722b70481..66ce2c9650 100644
--- a/src/core/include.am
+++ b/src/core/include.am
@@ -37,6 +37,7 @@ LIBTOR_APP_A_SOURCES = 				\
 	src/core/or/circuitmux.c		\
 	src/core/or/circuitmux_ewma.c		\
 	src/core/or/circuitpadding.c		\
+	src/core/or/circuitpadding_machines.c		\
 	src/core/or/circuitstats.c		\
 	src/core/or/circuituse.c		\
 	src/core/or/crypt_path.c		\
@@ -247,6 +248,7 @@ noinst_HEADERS +=					\
 	src/core/or/circuitmux_ewma.h			\
 	src/core/or/circuitstats.h			\
 	src/core/or/circuitpadding.h			\
+	src/core/or/circuitpadding_machines.h			\
 	src/core/or/circuituse.h			\
 	src/core/or/command.h				\
 	src/core/or/connection_edge.h			\
diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c
index ddf28ea624..b2315d822f 100644
--- a/src/core/or/circuitpadding.c
+++ b/src/core/or/circuitpadding.c
@@ -37,6 +37,13 @@
  * When a padding machine reaches the END state, it gets wiped from the circuit
  * so that other padding machines can take over if needed (see
  * circpad_machine_spec_transitioned_to_end()).
+ *
+ ****************************
+ * General notes:
+ *
+ * All used machines should be heap allocated and placed into
+ * origin_padding_machines/relay_padding_machines so that they get correctly
+ * cleaned up by the circpad_free_all() function.
  **/
 
 #define CIRCUITPADDING_PRIVATE
@@ -46,6 +53,7 @@
 #include "lib/math/prob_distr.h"
 #include "core/or/or.h"
 #include "core/or/circuitpadding.h"
+#include "core/or/circuitpadding_machines.h"
 #include "core/or/circuitlist.h"
 #include "core/or/circuituse.h"
 #include "core/mainloop/netstatus.h"
@@ -72,8 +80,6 @@
 
 #include "app/config/config.h"
 
-static inline circpad_purpose_mask_t circpad_circ_purpose_to_mask(uint8_t
-                                          circ_purpose);
 static inline circpad_circuit_state_t circpad_circuit_state(
                                         origin_circuit_t *circ);
 static void circpad_setup_machine_on_circ(circuit_t *on_circ,
@@ -126,34 +132,6 @@ STATIC smartlist_t *relay_padding_machines = NULL;
 #define FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END } STMT_END ;
 
 /**
- * Return a human-readable description for a circuit padding state.
- */
-static const char *
-circpad_state_to_string(circpad_statenum_t state)
-{
-  const char *descr;
-
-  switch (state) {
-  case CIRCPAD_STATE_START:
-    descr = "START";
-    break;
-  case CIRCPAD_STATE_BURST:
-    descr = "BURST";
-    break;
-  case CIRCPAD_STATE_GAP:
-    descr = "GAP";
-    break;
-  case CIRCPAD_STATE_END:
-    descr = "END";
-    break;
-  default:
-    descr = "CUSTOM"; // XXX: Just return # in static char buf?
-  }
-
-  return descr;
-}
-
-/**
  * Free the machineinfo at an index
  */
 static void
@@ -485,7 +463,10 @@ circpad_machine_setup_tokens(circpad_machine_runtime_t *mi)
   const circpad_state_t *state = circpad_machine_current_state(mi);
 
   /* If this state doesn't exist, or doesn't have token removal,
-   * free any previous state's histogram, and bail */
+   * free any previous state's runtime histogram, and bail.
+   *
+   * If we don't have a token removal strategy, we also don't need a runtime
+   * histogram and we rely on the immutable one in machine_spec_t. */
   if (!state || state->token_removal == CIRCPAD_TOKEN_REMOVAL_NONE) {
     if (mi->histogram) {
       tor_free(mi->histogram);
@@ -525,9 +506,14 @@ circpad_choose_state_length(circpad_machine_runtime_t *mi)
   length = circpad_distribution_sample(state->length_dist);
   length = MAX(0, length);
   length += state->start_length;
-  length = MIN(length, state->max_length);
+
+  if (state->max_length) {
+    length = MIN(length, state->max_length);
+  }
 
   mi->state_length = clamp_double_to_int64(length);
+
+  log_info(LD_CIRC, "State length sampled to %"PRIu64".", mi->state_length);
 }
 
 /**
@@ -595,6 +581,11 @@ circpad_machine_sample_delay(circpad_machine_runtime_t *mi)
     histogram_total_tokens = state->histogram_total_tokens;
   }
 
+  /* If we are out of tokens, don't schedule padding. */
+  if (!histogram_total_tokens) {
+    return CIRCPAD_DELAY_INFINITE;
+  }
+
   bin_choice = crypto_fast_rng_get_uint64(get_thread_fast_rng(),
                                           histogram_total_tokens);
 
@@ -897,7 +888,7 @@ circpad_machine_remove_closest_token(circpad_machine_runtime_t *mi,
       bin_to_remove = lower;
     }
     mi->histogram[bin_to_remove]--;
-    log_debug(LD_GENERAL, "Removing token from bin %d", bin_to_remove);
+    log_debug(LD_CIRC, "Removing token from bin %d", bin_to_remove);
     return;
   } else {
     if (current - lower > higher - current) {
@@ -1207,14 +1198,16 @@ circpad_send_padding_cell_for_callback(circpad_machine_runtime_t *mi)
     circpad_send_command_to_hop(TO_ORIGIN_CIRCUIT(mi->on_circ),
                                 CIRCPAD_GET_MACHINE(mi)->target_hopnum,
                                 RELAY_COMMAND_DROP, NULL, 0);
-    log_fn(LOG_INFO,LD_CIRC, "Callback: Sending padding to origin circuit %u.",
-           TO_ORIGIN_CIRCUIT(mi->on_circ)->global_identifier);
+    log_info(LD_CIRC, "Callback: Sending padding to origin circuit %u"
+             " (%d) [length: %"PRIu64"]",
+             TO_ORIGIN_CIRCUIT(mi->on_circ)->global_identifier,
+             mi->on_circ->purpose, mi->state_length);
   } else {
     // If we're a non-origin circ, we can just send from here as if we're the
     // edge.
     if (TO_OR_CIRCUIT(circ)->p_chan_cells.n <= circpad_max_circ_queued_cells) {
-      log_fn(LOG_INFO,LD_CIRC,
-             "Callback: Sending padding to non-origin circuit.");
+      log_info(LD_CIRC, "Callback: Sending padding to circuit (%d)"
+               " [length: %"PRIu64"]", mi->on_circ->purpose, mi->state_length);
       relay_send_command_from_edge(0, mi->on_circ, RELAY_COMMAND_DROP, NULL,
                                    0, NULL);
       rep_hist_padding_count_write(PADDING_TYPE_DROP);
@@ -1582,9 +1575,8 @@ circpad_machine_spec_transition,(circpad_machine_runtime_t *mi,
      * a transition to itself. All non-specified events are ignored.
      */
     log_fn(LOG_INFO, LD_CIRC,
-           "Circpad machine %d transitioning from %s to %s",
-            mi->machine_index, circpad_state_to_string(mi->current_state),
-            circpad_state_to_string(s));
+           "Circpad machine %d transitioning from %u to %u",
+           mi->machine_index, mi->current_state, s);
 
     /* If this is not the same state, switch and init tokens,
      * otherwise just reschedule padding. */
@@ -1734,13 +1726,12 @@ circpad_estimate_circ_rtt_on_send(circuit_t *circ,
      * to back. Stop estimating RTT in this case. Note that we only
      * stop RTT update if the circuit is opened, to allow for RTT estimates
      * of var cells during circ setup. */
-    mi->stop_rtt_update = 1;
-
-    if (!mi->rtt_estimate_usec) {
+    if (!mi->rtt_estimate_usec && !mi->stop_rtt_update) {
       static ratelim_t rtt_lim = RATELIM_INIT(600);
       log_fn_ratelim(&rtt_lim,LOG_NOTICE,LD_BUG,
         "Circuit sent two cells back to back before estimating RTT.");
     }
+    mi->stop_rtt_update = 1;
   }
 }
 
@@ -1976,7 +1967,6 @@ circpad_circuit_state(origin_circuit_t *circ)
  * Convert a normal circuit purpose into a bitmask that we can
  * use for determining matching circuits.
  */
-static inline
 circpad_purpose_mask_t
 circpad_circ_purpose_to_mask(uint8_t circ_purpose)
 {
@@ -2019,7 +2009,8 @@ circpad_shutdown_old_machines(origin_circuit_t *on_circ)
 }
 
 /**
- * Negotiate new machines that would apply to this circuit.
+ * Negotiate new machines that would apply to this circuit, given the machines
+ * inside <b>machines_sl</b>.
  *
  * This function checks to see if we have any free machine indexes,
  * and for each free machine index, it initializes the most recently
@@ -2027,14 +2018,15 @@ circpad_shutdown_old_machines(origin_circuit_t *on_circ)
  * index and circuit conditions, and negotiates it with the appropriate
  * middle relay.
  */
-static void
-circpad_add_matching_machines(origin_circuit_t *on_circ)
+STATIC void
+circpad_add_matching_machines(origin_circuit_t *on_circ,
+                              smartlist_t *machines_sl)
 {
   circuit_t *circ = TO_CIRCUIT(on_circ);
 
 #ifdef TOR_UNIT_TESTS
   /* Tests don't have to init our padding machines */
-  if (!origin_padding_machines)
+  if (!machines_sl)
     return;
 #endif
 
@@ -2051,7 +2043,7 @@ circpad_add_matching_machines(origin_circuit_t *on_circ)
     /* We have a free machine index. Check the origin padding
      * machines in reverse order, so that more recently added
      * machines take priority over older ones. */
-    SMARTLIST_FOREACH_REVERSE_BEGIN(origin_padding_machines,
+    SMARTLIST_FOREACH_REVERSE_BEGIN(machines_sl,
                                     circpad_machine_spec_t *,
                                     machine) {
       /* Machine definitions have a specific target machine index.
@@ -2079,6 +2071,7 @@ circpad_add_matching_machines(origin_circuit_t *on_circ)
         if (circpad_negotiate_padding(on_circ, machine->machine_num,
                                   machine->target_hopnum,
                                   CIRCPAD_COMMAND_START) < 0) {
+          log_info(LD_CIRC, "Padding not negotiated. Cleaning machine");
           circpad_circuit_machineinfo_free_idx(circ, i);
           circ->padding_machine[i] = NULL;
           on_circ->padding_negotiation_failed = 1;
@@ -2102,7 +2095,7 @@ circpad_machine_event_circ_added_hop(origin_circuit_t *on_circ)
 {
   /* Since our padding conditions do not specify a max_hops,
    * all we can do is add machines here */
-  circpad_add_matching_machines(on_circ);
+  circpad_add_matching_machines(on_circ, origin_padding_machines);
 }
 
 /**
@@ -2115,7 +2108,7 @@ void
 circpad_machine_event_circ_built(origin_circuit_t *circ)
 {
   circpad_shutdown_old_machines(circ);
-  circpad_add_matching_machines(circ);
+  circpad_add_matching_machines(circ, origin_padding_machines);
 }
 
 /**
@@ -2128,7 +2121,7 @@ void
 circpad_machine_event_circ_purpose_changed(origin_circuit_t *circ)
 {
   circpad_shutdown_old_machines(circ);
-  circpad_add_matching_machines(circ);
+  circpad_add_matching_machines(circ, origin_padding_machines);
 }
 
 /**
@@ -2142,7 +2135,7 @@ void
 circpad_machine_event_circ_has_no_relay_early(origin_circuit_t *circ)
 {
   circpad_shutdown_old_machines(circ);
-  circpad_add_matching_machines(circ);
+  circpad_add_matching_machines(circ, origin_padding_machines);
 }
 
 /**
@@ -2157,7 +2150,7 @@ void
 circpad_machine_event_circ_has_streams(origin_circuit_t *circ)
 {
   circpad_shutdown_old_machines(circ);
-  circpad_add_matching_machines(circ);
+  circpad_add_matching_machines(circ, origin_padding_machines);
 }
 
 /**
@@ -2172,7 +2165,7 @@ void
 circpad_machine_event_circ_has_no_streams(origin_circuit_t *circ)
 {
   circpad_shutdown_old_machines(circ);
-  circpad_add_matching_machines(circ);
+  circpad_add_matching_machines(circ, origin_padding_machines);
 }
 
 /**
@@ -2253,13 +2246,6 @@ circpad_deliver_recognized_relay_cell_events(circuit_t *circ,
                                              uint8_t relay_command,
                                              crypt_path_t *layer_hint)
 {
-  /* Padding negotiate cells are ignored by the state machines
-   * for simplicity. */
-  if (relay_command == RELAY_COMMAND_PADDING_NEGOTIATE ||
-      relay_command == RELAY_COMMAND_PADDING_NEGOTIATED) {
-    return;
-  }
-
   if (relay_command == RELAY_COMMAND_DROP) {
     rep_hist_padding_count_read(PADDING_TYPE_DROP);
 
@@ -2296,16 +2282,12 @@ void
 circpad_deliver_sent_relay_cell_events(circuit_t *circ,
                                        uint8_t relay_command)
 {
-  /* Padding negotiate cells are ignored by the state machines
-   * for simplicity. */
-  if (relay_command == RELAY_COMMAND_PADDING_NEGOTIATE ||
-      relay_command == RELAY_COMMAND_PADDING_NEGOTIATED) {
-    return;
-  }
-
   /* RELAY_COMMAND_DROP is the multi-hop (aka circuit-level) padding cell in
    * tor. (CELL_PADDING is a channel-level padding cell, which is not relayed
-   * or processed here) */
+   * or processed here).
+   *
+   * We do generate events for PADDING_NEGOTIATE and PADDING_NEGOTIATED cells.
+   */
   if (relay_command == RELAY_COMMAND_DROP) {
     /* Optimization: The event for RELAY_COMMAND_DROP is sent directly
      * from circpad_send_padding_cell_for_callback(). This is to avoid
@@ -2363,12 +2345,21 @@ circpad_setup_machine_on_circ(circuit_t *on_circ,
                       == NULL);
   tor_assert_nonfatal(on_circ->padding_info[machine->machine_index] == NULL);
 
+  /* Log message */
+  if (CIRCUIT_IS_ORIGIN(on_circ)) {
+    log_info(LD_CIRC, "Registering machine %s to origin circ %u (%d)",
+             machine->name,
+             TO_ORIGIN_CIRCUIT(on_circ)->global_identifier, on_circ->purpose);
+  } else {
+    log_info(LD_CIRC, "Registering machine %s to non-origin circ (%d)",
+             machine->name, on_circ->purpose);
+  }
+
   on_circ->padding_info[machine->machine_index] =
       circpad_circuit_machineinfo_new(on_circ, machine->machine_index);
   on_circ->padding_machine[machine->machine_index] = machine;
 }
 
-#ifdef TOR_UNIT_TESTS
 /** Validate a single state of a padding machine */
 static bool
 padding_machine_state_is_valid(const circpad_state_t *state)
@@ -2384,7 +2375,7 @@ padding_machine_state_is_valid(const circpad_state_t *state)
 
   /* We need at least two bins in a histogram */
   if (state->histogram_len < 2) {
-    log_warn(LD_GENERAL, "You can't have a histogram with less than 2 bins");
+    log_warn(LD_CIRC, "You can't have a histogram with less than 2 bins");
     return false;
   }
 
@@ -2394,7 +2385,7 @@ padding_machine_state_is_valid(const circpad_state_t *state)
     /* Check that histogram edges are strictly increasing. Ignore the first
      * edge since it can be zero. */
     if (prev_bin_edge >= state->histogram_edges[b] && b > 0) {
-      log_warn(LD_GENERAL, "Histogram edges are not increasing [%u/%u]",
+      log_warn(LD_CIRC, "Histogram edges are not increasing [%u/%u]",
                prev_bin_edge, state->histogram_edges[b]);
       return false;
     }
@@ -2406,7 +2397,7 @@ padding_machine_state_is_valid(const circpad_state_t *state)
   }
   /* Verify that the total number of tokens is correct */
   if (tokens_count != state->histogram_total_tokens) {
-    log_warn(LD_GENERAL, "Histogram token count is wrong [%u/%u]",
+    log_warn(LD_CIRC, "Histogram token count is wrong [%u/%u]",
              tokens_count, state->histogram_total_tokens);
     return false;
   }
@@ -2432,12 +2423,12 @@ padding_machine_is_valid(const circpad_machine_spec_t *machine)
 
 /* Validate and register <b>machine</b> into <b>machine_list</b>. If
  * <b>machine_list</b> is NULL, then just validate. */
-STATIC void
-register_padding_machine(circpad_machine_spec_t *machine,
-                         smartlist_t *machine_list)
+void
+circpad_register_padding_machine(circpad_machine_spec_t *machine,
+                                 smartlist_t *machine_list)
 {
   if (!padding_machine_is_valid(machine)) {
-    log_warn(LD_GENERAL, "Machine #%u is invalid. Ignoring.",
+    log_warn(LD_CIRC, "Machine #%u is invalid. Ignoring.",
              machine->machine_num);
     return;
   }
@@ -2447,6 +2438,7 @@ register_padding_machine(circpad_machine_spec_t *machine,
   }
 }
 
+#ifdef TOR_UNIT_TESTS
 /* These padding machines are only used for tests pending #28634. */
 static void
 circpad_circ_client_machine_init(void)
@@ -2499,7 +2491,8 @@ circpad_circ_client_machine_init(void)
   circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_total_tokens = 5;
 
   circ_client_machine->machine_num = smartlist_len(origin_padding_machines);
-  register_padding_machine(circ_client_machine, origin_padding_machines);
+  circpad_register_padding_machine(circ_client_machine,
+                                   origin_padding_machines);
 }
 
 static void
@@ -2599,7 +2592,8 @@ circpad_circ_responder_machine_init(void)
       CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC;
 
   circ_responder_machine->machine_num = smartlist_len(relay_padding_machines);
-  register_padding_machine(circ_responder_machine, relay_padding_machines);
+  circpad_register_padding_machine(circ_responder_machine,
+                                   relay_padding_machines);
 }
 #endif
 
@@ -2618,6 +2612,14 @@ circpad_machines_init(void)
   origin_padding_machines = smartlist_new();
   relay_padding_machines = smartlist_new();
 
+  /* Register machines for hiding client-side intro circuits */
+  circpad_machine_client_hide_intro_circuits(origin_padding_machines);
+  circpad_machine_relay_hide_intro_circuits(relay_padding_machines);
+
+  /* Register machines for hiding client-side rendezvous circuits */
+  circpad_machine_client_hide_rend_circuits(origin_padding_machines);
+  circpad_machine_relay_hide_rend_circuits(relay_padding_machines);
+
   // TODO: Parse machines from consensus and torrc
 #ifdef TOR_UNIT_TESTS
   circpad_circ_client_machine_init();
@@ -2668,8 +2670,8 @@ circpad_node_supports_padding(const node_t *node)
  * Returns node_t from the consensus for that hop, if it is opened.
  * Otherwise returns NULL.
  */
-static const node_t *
-circuit_get_nth_node(origin_circuit_t *circ, int hop)
+MOCK_IMPL(STATIC const node_t *,
+circuit_get_nth_node,(origin_circuit_t *circ, int hop))
 {
   crypt_path_t *iter = circuit_get_cpath_hop(circ, hop);
 
@@ -2732,8 +2734,8 @@ circpad_negotiate_padding(origin_circuit_t *circ,
         &type)) < 0)
     return -1;
 
-  log_fn(LOG_INFO,LD_CIRC, "Negotiating padding on circuit %u",
-         circ->global_identifier);
+  log_fn(LOG_INFO,LD_CIRC, "Negotiating padding on circuit %u (%d)",
+         circ->global_identifier, TO_CIRCUIT(circ)->purpose);
 
   return circpad_send_command_to_hop(circ, target_hopnum,
                                      RELAY_COMMAND_PADDING_NEGOTIATE,
@@ -2818,6 +2820,7 @@ circpad_handle_padding_negotiate(circuit_t *circ, cell_t *cell)
                             const circpad_machine_spec_t *, m) {
       if (m->machine_num == negotiate->machine_type) {
         circpad_setup_machine_on_circ(circ, m);
+        circpad_cell_event_nonpadding_received(circ);
         goto done;
       }
     } SMARTLIST_FOREACH_END(m);
@@ -2871,6 +2874,7 @@ circpad_handle_padding_negotiated(circuit_t *circ, cell_t *cell,
   }
 
   if (negotiated->command == CIRCPAD_COMMAND_STOP) {
+    log_info(LD_CIRC, "Received STOP command on PADDING_NEGOTIATED");
     /* There may not be a padding_info here if we shut down the
      * machine in circpad_shutdown_old_machines(). Or, if
      * circpad_add_matching_matchines() added a new machine,
@@ -2891,6 +2895,36 @@ circpad_handle_padding_negotiated(circuit_t *circ, cell_t *cell,
   return 0;
 }
 
+/** Free memory allocated by this machine spec. */
+STATIC void
+machine_spec_free_(circpad_machine_spec_t *m)
+{
+  if (!m) return;
+
+  tor_free(m->states);
+  tor_free(m);
+}
+
+/** Free all memory allocated by the circuitpadding subsystem. */
+void
+circpad_free_all(void)
+{
+  if (origin_padding_machines) {
+    SMARTLIST_FOREACH_BEGIN(origin_padding_machines,
+                            circpad_machine_spec_t *, m) {
+      machine_spec_free(m);
+    } SMARTLIST_FOREACH_END(m);
+    smartlist_free(origin_padding_machines);
+  }
+  if (relay_padding_machines) {
+    SMARTLIST_FOREACH_BEGIN(relay_padding_machines,
+                            circpad_machine_spec_t *, m) {
+      machine_spec_free(m);
+    } SMARTLIST_FOREACH_END(m);
+    smartlist_free(relay_padding_machines);
+  }
+}
+
 /* Serialization */
 // TODO: Should we use keyword=value here? Are there helpers for that?
 #if 0
diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h
index 277a78001e..0dc66246d9 100644
--- a/src/core/or/circuitpadding.h
+++ b/src/core/or/circuitpadding.h
@@ -603,6 +603,9 @@ typedef uint8_t circpad_machine_num_t;
 
 /** Global state machine structure from the consensus */
 typedef struct circpad_machine_spec_t {
+  /* Just a user-friendly machine name for logs */
+  const char *name;
+
   /** Global machine number */
   circpad_machine_num_t machine_num;
 
@@ -698,6 +701,8 @@ circpad_machine_event_circ_has_no_relay_early(struct origin_circuit_t *circ);
 
 void circpad_machines_init(void);
 void circpad_machines_free(void);
+void circpad_register_padding_machine(circpad_machine_spec_t *machine,
+                                      smartlist_t *machine_list);
 
 void circpad_machine_states_init(circpad_machine_spec_t *machine,
                                  circpad_statenum_t num_states);
@@ -726,6 +731,8 @@ bool circpad_padding_negotiated(struct circuit_t *circ,
                            uint8_t command,
                            uint8_t response);
 
+circpad_purpose_mask_t circpad_circ_purpose_to_mask(uint8_t circ_purpose);
+
 MOCK_DECL(circpad_decision_t,
 circpad_machine_schedule_padding,(circpad_machine_runtime_t *));
 
@@ -736,7 +743,13 @@ circpad_machine_spec_transition, (circpad_machine_runtime_t *mi,
 circpad_decision_t circpad_send_padding_cell_for_callback(
                                  circpad_machine_runtime_t *mi);
 
+void circpad_free_all(void);
+
 #ifdef CIRCUITPADDING_PRIVATE
+STATIC void  machine_spec_free_(circpad_machine_spec_t *m);
+#define machine_spec_free(chan) \
+  FREE_AND_NULL(circpad_machine_spec_t,machine_spec_free_, (m))
+
 STATIC circpad_delay_t
 circpad_machine_sample_delay(circpad_machine_runtime_t *mi);
 
@@ -773,17 +786,21 @@ circpad_send_command_to_hop,(struct origin_circuit_t *circ, uint8_t hopnum,
                              uint8_t relay_command, const uint8_t *payload,
                              ssize_t payload_len));
 
+MOCK_DECL(STATIC const node_t *,
+circuit_get_nth_node,(origin_circuit_t *circ, int hop));
+
 STATIC circpad_delay_t
 histogram_get_bin_upper_bound(const circpad_machine_runtime_t *mi,
                               circpad_hist_index_t bin);
 
+STATIC void
+circpad_add_matching_machines(origin_circuit_t *on_circ,
+                              smartlist_t *machines_sl);
+
 #ifdef TOR_UNIT_TESTS
 extern smartlist_t *origin_padding_machines;
 extern smartlist_t *relay_padding_machines;
 
-STATIC void
-register_padding_machine(circpad_machine_spec_t *machine,
-                         smartlist_t *machine_list);
 #endif
 
 #endif
diff --git a/src/core/or/circuitpadding_machines.c b/src/core/or/circuitpadding_machines.c
new file mode 100644
index 0000000000..75d2614aca
--- /dev/null
+++ b/src/core/or/circuitpadding_machines.c
@@ -0,0 +1,458 @@
+/* Copyright (c) 2019 The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file circuitpadding_machines.c
+ * \brief Circuit padding state machines
+ *
+ * \detail
+ *
+ * Introduce circuit padding machines that will be used by Tor circuits, as
+ * specified by proposal 302 "Hiding onion service clients using padding".
+ *
+ * Right now this file introduces two machines that aim to hide the client-side
+ * of onion service circuits against naive classifiers like the ones from the
+ * "Circuit Fingerprinting Attacks: Passive Deanonymization of Tor Hidden
+ * Services" paper from USENIX. By naive classifiers we mean classifiers that
+ * use basic features like "circuit construction circuits" and "incoming and
+ * outgoing cell counts" and "duration of activity".
+ *
+ * In particular, these machines aim to be lightweight and protect against
+ * these basic classifiers. They don't aim to protect against more advanced
+ * attacks that use deep learning or even correlate various circuit
+ * construction events together. Machines that fool such advanced classifiers
+ * are also possible, but they can't be so lightweight and might require more
+ * WTF-PAD features. So for now we opt for the following two machines:
+ *
+ * Client-side introduction circuit hiding machine:
+ *
+ *    This machine hides client-side introduction circuits by making their
+ *    circuit consruction sequence look like normal general circuits that
+ *    download directory information. Furthermore, the circuits are kept open
+ *    until all the padding has been sent, since intro circuits are usually
+ *    very short lived and this act as a distinguisher. For more info see
+ *    circpad_machine_client_hide_intro_circuits() and the sec.
+ *
+ * Client-side rendezvous circuit hiding machine:
+ *
+ *    This machine hides client-side rendezvous circuits by making their
+ *    circuit construction sequence look like normal general circuits. For more
+ *    details see circpad_machine_client_hide_rend_circuits() and the spec.
+ *
+ * TODO: These are simple machines that carefully manipulate the cells of the
+ *   initial circuit setup procedure to make them look like general
+ *   circuits. In the future, more states can be baked into their state machine
+ *   to do more advanced obfuscation.
+ **/
+
+#define CIRCUITPADDING_MACHINES_PRIVATE
+
+#include "core/or/or.h"
+#include "feature/nodelist/networkstatus.h"
+
+#include "lib/crypt_ops/crypto_rand.h"
+
+#include "core/or/circuitlist.h"
+
+#include "core/or/circuitpadding_machines.h"
+#include "core/or/circuitpadding.h"
+
+/** Create a client-side padding machine that aims to hide IP circuits. In
+ *  particular, it keeps intro circuits alive until a bunch of fake traffic has
+ *  been pushed through.
+ */
+void
+circpad_machine_client_hide_intro_circuits(smartlist_t *machines_sl)
+{
+  circpad_machine_spec_t *client_machine
+      = tor_malloc_zero(sizeof(circpad_machine_spec_t));
+
+  client_machine->name = "client_ip_circ";
+
+  client_machine->conditions.state_mask = CIRCPAD_CIRC_OPENED;
+  client_machine->target_hopnum = 2;
+
+  /* This is a client machine */
+  client_machine->is_origin_side = 1;
+
+  /* We only want to pad introduction circuits, and we want to start padding
+   * only after the INTRODUCE1 cell has been sent, so set the purposes
+   * appropriately.
+   *
+   * In particular we want introduction circuits to blend as much as possible
+   * with general circuits. Most general circuits have the following initial
+   * relay cell sequence (outgoing cells marked in [brackets]):
+   *
+   * [EXTEND2] -> EXTENDED2 -> [EXTEND2] -> EXTENDED2 -> [BEGIN] -> CONNECTED
+   *   -> [DATA] -> [DATA] -> DATA -> DATA...(inbound data cells continue)
+   *
+   * Whereas normal introduction circuits usually look like:
+   *
+   * [EXTEND2] -> EXTENDED2 -> [EXTEND2] -> EXTENDED2 -> [EXTEND2] -> EXTENDED2
+   *   -> [INTRO1] -> INTRODUCE_ACK
+   *
+   * This means that up to the sixth cell (first line of each sequence above),
+   * both general and intro circuits have identical cell sequences. After that
+   * we want to mimic the second line sequence of
+   *   -> [DATA] -> [DATA] -> DATA -> DATA...(inbound data cells continue)
+   *
+   * We achieve this by starting padding INTRODUCE1 has been sent. With padding
+   * negotiation cells, in the common case of the second line looks like:
+   *   -> [INTRO1] -> [PADDING_NEGOTIATE] -> PADDING_NEGOTIATED -> INTRO_ACK
+   *
+   * Then, the middle node will send between INTRO_MACHINE_MINIMUM_PADDING and
+   * INTRO_MACHINE_MAXIMUM_PADDING cells, to match the "...(inbound data cells
+   * continue)" portion of the trace (aka the rest of an HTTPS response body).
+   */
+  client_machine->conditions.purpose_mask =
+    circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT)|
+    circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_INTRODUCE_ACKED)|
+    circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_CIRCUIT_PADDING);
+
+  /* Keep the circuit alive even after the introduction has been finished,
+   * otherwise the short-term lifetime of the circuit will blow our cover */
+  client_machine->manage_circ_lifetime = 1;
+
+  /* Set padding machine limits to help guard against excessive padding */
+  client_machine->allowed_padding_count = INTRO_MACHINE_MAXIMUM_PADDING;
+  client_machine->max_padding_percent = 1;
+
+  /* Two states: START, OBFUSCATE_CIRC_SETUP (and END) */
+  circpad_machine_states_init(client_machine, 2);
+
+  /* For the origin-side machine, we transition to OBFUSCATE_CIRC_SETUP after
+   * sending PADDING_NEGOTIATE, and we stay there (without sending any padding)
+   * until we receive a STOP from the other side. */
+  client_machine->states[CIRCPAD_STATE_START].
+    next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
+    CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP;
+
+  /* origin-side machine has no event reactions while in
+   * CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP, so no more state transitions here. */
+
+  /* The client side should never send padding, so it does not need
+   * to specify token removal, or a histogram definition or state lengths.
+   * That is all controlled by the middle node. */
+
+  /* Register the machine */
+  client_machine->machine_num = smartlist_len(machines_sl);
+  circpad_register_padding_machine(client_machine, machines_sl);
+
+  log_info(LD_CIRC,
+           "Registered client intro point hiding padding machine (%u)",
+           client_machine->machine_num);
+}
+
+/** Create a relay-side padding machine that aims to hide IP circuits. See
+ *  comments on the function above for more details on the workings of the
+ *  machine. */
+void
+circpad_machine_relay_hide_intro_circuits(smartlist_t *machines_sl)
+{
+  circpad_machine_spec_t *relay_machine
+      = tor_malloc_zero(sizeof(circpad_machine_spec_t));
+
+  relay_machine->name = "relay_ip_circ";
+
+  relay_machine->conditions.state_mask = CIRCPAD_CIRC_OPENED;
+  relay_machine->target_hopnum = 2;
+
+  /* This is a relay-side machine */
+  relay_machine->is_origin_side = 0;
+
+  /* We want to negotiate END from this side after all our padding is done, so
+   * that the origin-side machine goes into END state, and eventually closes
+   * the circuit. */
+  relay_machine->should_negotiate_end = 1;
+
+  /* Set padding machine limits to help guard against excessive padding */
+  relay_machine->allowed_padding_count = INTRO_MACHINE_MAXIMUM_PADDING;
+  relay_machine->max_padding_percent = 1;
+
+  /* Two states: START, OBFUSCATE_CIRC_SETUP (and END) */
+  circpad_machine_states_init(relay_machine, 2);
+
+  /* For the relay-side machine, we want to transition
+   * START -> OBFUSCATE_CIRC_SETUP upon first non-padding
+   * cell sent (PADDING_NEGOTIATED in this case).  */
+  relay_machine->states[CIRCPAD_STATE_START].
+    next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
+    CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP;
+
+  /* For the relay-side, we want to transition from OBFUSCATE_CIRC_SETUP to END
+   * state when the length finishes. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+      next_state[CIRCPAD_EVENT_LENGTH_COUNT] = CIRCPAD_STATE_END;
+
+  /* Now let's define the OBF -> OBF transitions that maintain our padding
+   * flow:
+   *
+   * For the relay-side machine, we want to keep on sending padding bytes even
+   * when nothing else happens on this circuit. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    next_state[CIRCPAD_EVENT_PADDING_SENT] =
+    CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP;
+  /* For the relay-side machine, we need this transition so that we re-enter
+     the state, after PADDING_NEGOTIATED is sent. Otherwise, the remove token
+     function will disable the timer, and nothing will restart it since there
+     is no other motion on an intro circuit. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
+    CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP;
+
+  /* Token removal strategy for OBFUSCATE_CIRC_SETUP state: Don't
+   * remove any tokens.
+   *
+   * We rely on the state length sampling and not token removal, to avoid
+   * the mallocs required to copy the histograms for token removal,
+   * and to avoid monotime calls needed to determine histogram
+   * bins for token removal. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    token_removal = CIRCPAD_TOKEN_REMOVAL_NONE;
+
+  /* Figure out the length of the OBFUSCATE_CIRC_SETUP state so that it's
+   * randomized. The relay side will send between INTRO_MACHINE_MINIMUM_PADDING
+   * and INTRO_MACHINE_MAXIMUM_PADDING padding cells towards the client. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.type = CIRCPAD_DIST_UNIFORM;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.param1 = INTRO_MACHINE_MINIMUM_PADDING;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.param2 = INTRO_MACHINE_MAXIMUM_PADDING;
+
+  /* Configure histogram */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+     histogram_len = 2;
+
+  /* For the relay-side machine we want to batch padding instantly to pretend
+   * its an incoming directory download. So set the histogram edges tight:
+   * (1, 10ms, infinity). */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_edges[0] = 1000;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_edges[1] = 10000;
+
+  /* We put all our tokens in bin 0, which means we want 100% probability
+   * for choosing a inter-packet delay of between 1000 and 10000 microseconds
+   * (1 to 10ms). Since we only have 1 bin, it doesn't matter how many tokens
+   * there are, 1000 out of 1000 is 100% */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram[0] = 1000;
+
+  /* just one bin, so setup the total tokens */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_total_tokens =
+      relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].histogram[0];
+
+  /* Register the machine */
+  relay_machine->machine_num = smartlist_len(machines_sl);
+  circpad_register_padding_machine(relay_machine, machines_sl);
+
+  log_info(LD_CIRC,
+           "Registered relay intro circuit hiding padding machine (%u)",
+           relay_machine->machine_num);
+}
+
+/************************** Rendezvous-circuit machine ***********************/
+
+/** Create a client-side padding machine that aims to hide rendezvous
+ *  circuits.*/
+void
+circpad_machine_client_hide_rend_circuits(smartlist_t *machines_sl)
+{
+  circpad_machine_spec_t *client_machine
+      = tor_malloc_zero(sizeof(circpad_machine_spec_t));
+
+  client_machine->name = "client_rp_circ";
+
+  /* Only pad after the circuit has been built and pad to the middle */
+  client_machine->conditions.state_mask = CIRCPAD_CIRC_OPENED;
+  client_machine->target_hopnum = 2;
+
+  /* This is a client machine */
+  client_machine->is_origin_side = 1;
+
+  /* We only want to pad rendezvous circuits, and we want to start padding only
+   * after the rendezvous circuit has been established.
+   *
+   * Following a similar argument as for intro circuits, we are aiming for
+   * padded rendezvous circuits to blend in with the initial cell sequence of
+   * general circuits which usually look like this:
+   *
+   * [EXTEND2] -> EXTENDED2 -> [EXTEND2] -> EXTENDED2 -> [BEGIN] -> CONNECTED
+   *    -> [DATA] -> [DATA] -> DATA -> DATA...(incoming cells continue)
+   *
+   * Whereas normal rendezvous circuits usually look like:
+   *
+   * [EXTEND2] -> EXTENDED2 -> [EXTEND2] -> EXTENDED2 -> [EST_REND] -> REND_EST
+   *    -> REND2 -> [BEGIN]
+   *
+   * This means that up to the sixth cell (in the first line), both general and
+   * rend circuits have identical cell sequences.
+   *
+   * After that we want to mimic a [DATA] -> [DATA] -> DATA -> DATA sequence.
+   *
+   * With padding negotiation right after the REND_ESTABLISHED, the sequence
+   * becomes:
+   *
+   * [EXTEND2] -> EXTENDED2 -> [EXTEND2] -> EXTENDED2 -> [EST_REND] -> REND_EST
+   *    -> [PADDING_NEGOTIATE] -> [DROP] -> PADDING_NEGOTIATED -> DROP...
+   *
+   * After which normal application DATA cells continue on the circuit.
+   *
+   * Hence this way we make rendezvous circuits look like general circuits up
+   * till the end of the circuit setup. */
+  client_machine->conditions.purpose_mask =
+    circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_REND_JOINED)|
+    circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_REND_READY)|
+    circpad_circ_purpose_to_mask(CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED);
+
+  /* Set padding machine limits to help guard against excessive padding */
+  client_machine->allowed_padding_count = 1;
+  client_machine->max_padding_percent = 1;
+
+  /* Two states: START, OBFUSCATE_CIRC_SETUP (and END) */
+  circpad_machine_states_init(client_machine, 2);
+
+  /* START -> OBFUSCATE_CIRC_SETUP transition upon sending the first
+   * non-padding cell (which is PADDING_NEGOTIATE) */
+  client_machine->states[CIRCPAD_STATE_START].
+    next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
+    CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP;
+
+  /* OBFUSCATE_CIRC_SETUP -> END transition when we send our first
+   * padding packet and/or hit the state length (the state length is 1). */
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+      next_state[CIRCPAD_EVENT_PADDING_RECV] = CIRCPAD_STATE_END;
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+      next_state[CIRCPAD_EVENT_LENGTH_COUNT] = CIRCPAD_STATE_END;
+
+  /* Don't use a token removal strategy since we don't want to use monotime
+   * functions and we want to avoid mallocing histogram copies. We want
+   * this machine to be light. */
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    token_removal = CIRCPAD_TOKEN_REMOVAL_NONE;
+
+  /* Instead, to control the volume of padding (we just want to send a single
+   * padding cell) we will use a static state length. We just want one token,
+   * since we want to make the following pattern:
+   * [PADDING_NEGOTIATE] -> [DROP] -> PADDING_NEGOTIATED -> DROP */
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.type = CIRCPAD_DIST_UNIFORM;
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.param1 = 1;
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.param2 = 2; // rand(1,2) is always 1
+
+  /* Histogram is: (0 msecs, 1 msec, infinity). We want this to be fast so
+   * that we send our outgoing [DROP] before the PADDING_NEGOTIATED comes
+   * back from the relay side. */
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_len = 2;
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_edges[0] = 0;
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_edges[1] = 1000;
+
+  /* We want a 100% probability of choosing an inter-packet delay of
+   * between 0 and 1ms. Since we don't use token removal,
+   * the number of tokens does not matter. (And also, state_length
+   * governs how many packets we send). */
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram[0] = 1;
+  client_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_total_tokens = 1;
+
+  /* Register the machine */
+  client_machine->machine_num = smartlist_len(machines_sl);
+  circpad_register_padding_machine(client_machine, machines_sl);
+
+  log_info(LD_CIRC,
+           "Registered client rendezvous circuit hiding padding machine (%u)",
+           client_machine->machine_num);
+}
+
+/** Create a relay-side padding machine that aims to hide IP circuits.
+ *
+ *  This is meant to follow the client-side machine.
+ */
+void
+circpad_machine_relay_hide_rend_circuits(smartlist_t *machines_sl)
+{
+  circpad_machine_spec_t *relay_machine
+    = tor_malloc_zero(sizeof(circpad_machine_spec_t));
+
+  relay_machine->name = "relay_rp_circ";
+
+  /* Only pad after the circuit has been built and pad to the middle */
+  relay_machine->conditions.min_hops = 2;
+  relay_machine->conditions.state_mask = CIRCPAD_CIRC_OPENED;
+  relay_machine->target_hopnum = 2;
+
+  /* This is a relay-side machine */
+  relay_machine->is_origin_side = 0;
+
+  /* Set padding machine limits to help guard against excessive padding */
+  relay_machine->allowed_padding_count = 1;
+  relay_machine->max_padding_percent = 1;
+
+  /* Two states: START, OBFUSCATE_CIRC_SETUP (and END) */
+  circpad_machine_states_init(relay_machine, 2);
+
+  /* START -> OBFUSCATE_CIRC_SETUP transition upon sending the first
+   * non-padding cell (which is PADDING_NEGOTIATED) */
+  relay_machine->states[CIRCPAD_STATE_START].
+    next_state[CIRCPAD_EVENT_NONPADDING_SENT] =
+    CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP;
+
+  /* OBFUSCATE_CIRC_SETUP -> END transition when we send our first
+   * padding packet and/or hit the state length (the state length is 1). */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+      next_state[CIRCPAD_EVENT_PADDING_RECV] = CIRCPAD_STATE_END;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+      next_state[CIRCPAD_EVENT_LENGTH_COUNT] = CIRCPAD_STATE_END;
+
+  /* Don't use a token removal strategy since we don't want to use monotime
+   * functions and we want to avoid mallocing histogram copies. We want
+   * this machine to be light. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    token_removal = CIRCPAD_TOKEN_REMOVAL_NONE;
+
+  /* Instead, to control the volume of padding (we just want to send a single
+   * padding cell) we will use a static state length. We just want one token,
+   * since we want to make the following pattern:
+   * [PADDING_NEGOTIATE] -> [DROP] -> PADDING_NEGOTIATED -> DROP */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.type = CIRCPAD_DIST_UNIFORM;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.param1 = 1;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    length_dist.param2 = 2; // rand(1,2) is always 1
+
+  /* Histogram is: (0 msecs, 1 msec, infinity). We want this to be fast so
+   * that the outgoing DROP cell is sent immediately after the
+   * PADDING_NEGOTIATED. */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_len = 2;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_edges[0] = 0;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_edges[1] = 1000;
+
+  /* We want a 100% probability of choosing an inter-packet delay of
+   * between 0 and 1ms. Since we don't use token removal,
+   * the number of tokens does not matter. (And also, state_length
+   * governs how many packets we send). */
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram[0] = 1;
+  relay_machine->states[CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP].
+    histogram_total_tokens = 1;
+
+  /* Register the machine */
+  relay_machine->machine_num = smartlist_len(machines_sl);
+  circpad_register_padding_machine(relay_machine, machines_sl);
+
+  log_info(LD_CIRC,
+           "Registered relay rendezvous circuit hiding padding machine (%u)",
+           relay_machine->machine_num);
+}
diff --git a/src/core/or/circuitpadding_machines.h b/src/core/or/circuitpadding_machines.h
new file mode 100644
index 0000000000..c44a70f2cc
--- /dev/null
+++ b/src/core/or/circuitpadding_machines.h
@@ -0,0 +1,35 @@
+/* Copyright (c) 2018 The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file circuitpadding_machines.h
+ * \brief Header file for circuitpadding_machines.c.
+ **/
+
+#ifndef TOR_CIRCUITPADDING_MACHINES_H
+#define TOR_CIRCUITPADDING_MACHINES_H
+
+void circpad_machine_relay_hide_intro_circuits(smartlist_t *machines_sl);
+void circpad_machine_client_hide_intro_circuits(smartlist_t *machines_sl);
+void circpad_machine_relay_hide_rend_circuits(smartlist_t *machines_sl);
+void circpad_machine_client_hide_rend_circuits(smartlist_t *machines_sl);
+
+#ifdef CIRCUITPADDING_MACHINES_PRIVATE
+
+/** State of the padding machines that actually sends padding */
+#define CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP CIRCPAD_STATE_BURST
+
+/** Constants defining the amount of padding that a machine will send to hide
+ *  HS circuits. The actual value is sampled uniformly random between the
+ *  min/max values.
+ */
+
+/** Minimum number of relay-side padding cells to be sent by this machine */
+#define INTRO_MACHINE_MINIMUM_PADDING 7
+/** Maximum number of relay-side padding cells to be sent by this machine.
+ *  The actual value will be sampled between the min and max.*/
+#define INTRO_MACHINE_MAXIMUM_PADDING 10
+
+#endif
+
+#endif
diff --git a/src/test/test_circuitpadding.c b/src/test/test_circuitpadding.c
index bd6697922e..ca65438430 100644
--- a/src/test/test_circuitpadding.c
+++ b/src/test/test_circuitpadding.c
@@ -1,6 +1,7 @@
 #define TOR_CHANNEL_INTERNAL_
 #define TOR_TIMERS_PRIVATE
 #define CIRCUITPADDING_PRIVATE
+#define CIRCUITPADDING_MACHINES_PRIVATE
 #define NETWORKSTATUS_PRIVATE
 #define CRYPT_PATH_PRIVATE
 
@@ -19,6 +20,7 @@
 #include "core/or/circuitlist.h"
 #include "core/or/circuitbuild.h"
 #include "core/or/circuitpadding.h"
+#include "core/or/circuitpadding_machines.h"
 #include "core/mainloop/netstatus.h"
 #include "core/crypto/relay_crypto.h"
 #include "core/or/protover.h"
@@ -112,6 +114,15 @@ node_get_by_id_mock(const char *identity_digest)
   return NULL;
 }
 
+static const node_t *
+circuit_get_nth_node_mock(origin_circuit_t *circ, int hop)
+{
+  (void) circ;
+  (void) hop;
+
+  return &padding_node;
+}
+
 static or_circuit_t *
 new_fake_orcirc(channel_t *nchan, channel_t *pchan)
 {
@@ -415,6 +426,8 @@ helper_create_basic_machine(void)
   /* Start, burst */
   circpad_machine_states_init(&circ_client_machine, 2);
 
+  circ_client_machine.name = "basic";
+
   circ_client_machine.states[CIRCPAD_STATE_START].
       next_state[CIRCPAD_EVENT_NONPADDING_RECV] = CIRCPAD_STATE_BURST;
   circ_client_machine.states[CIRCPAD_STATE_START].use_rtt_estimate = 1;
@@ -1759,7 +1772,7 @@ helper_create_conditional_machines(void)
   add->conditions.state_mask = CIRCPAD_CIRC_BUILDING|
            CIRCPAD_CIRC_NO_STREAMS|CIRCPAD_CIRC_HAS_RELAY_EARLY;
   add->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL;
-  register_padding_machine(add, origin_padding_machines);
+  circpad_register_padding_machine(add, origin_padding_machines);
 
   add = helper_create_conditional_machine();
   add->machine_num = 3;
@@ -1778,15 +1791,15 @@ helper_create_conditional_machines(void)
   add->conditions.state_mask = CIRCPAD_CIRC_OPENED|
            CIRCPAD_CIRC_STREAMS|CIRCPAD_CIRC_HAS_NO_RELAY_EARLY;
   add->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL;
-  register_padding_machine(add, origin_padding_machines);
+  circpad_register_padding_machine(add, origin_padding_machines);
 
   add = helper_create_conditional_machine();
   add->machine_num = 2;
-  register_padding_machine(add, relay_padding_machines);
+  circpad_register_padding_machine(add, relay_padding_machines);
 
   add = helper_create_conditional_machine();
   add->machine_num = 3;
-  register_padding_machine(add, relay_padding_machines);
+  circpad_register_padding_machine(add, relay_padding_machines);
 }
 
 void
@@ -2650,8 +2663,8 @@ test_circuitpadding_reduce_disable(void *arg)
   simulate_single_hop_extend(client_side, relay_side, 1);
 
   /* Verify that machine #0 is added */
-  tt_int_op(client_side->padding_machine[0]->machine_num, OP_EQ, 0);
-  tt_int_op(relay_side->padding_machine[0]->machine_num, OP_EQ, 0);
+  tt_int_op(client_side->padding_machine[0]->machine_num, OP_EQ, 2);
+  tt_int_op(relay_side->padding_machine[0]->machine_num, OP_EQ, 2);
 
   tt_int_op(
     circpad_machine_reached_padding_limit(client_side->padding_info[0]),
@@ -2696,8 +2709,8 @@ test_circuitpadding_reduce_disable(void *arg)
   simulate_single_hop_extend(client_side, relay_side, 1);
 
   /* Verify that machine #0 is added */
-  tt_int_op(client_side->padding_machine[0]->machine_num, OP_EQ, 0);
-  tt_int_op(relay_side->padding_machine[0]->machine_num, OP_EQ, 0);
+  tt_int_op(client_side->padding_machine[0]->machine_num, OP_EQ, 2);
+  tt_int_op(relay_side->padding_machine[0]->machine_num, OP_EQ, 2);
 
   tt_int_op(
     circpad_machine_reached_padding_limit(client_side->padding_info[0]),
@@ -2917,6 +2930,199 @@ test_circuitpadding_manage_circuit_lifetime(void *arg)
   UNMOCK(tor_gettimeofday);
 }
 
+/** Helper for the test_circuitpadding_hs_machines test:
+ *
+ *  - Create a client and relay circuit.
+ *  - Setup right circuit purpose and attach a machine to the client circuit.
+ *  - Verify that state transitions work as intended and state length gets
+ *    enforced.
+ *
+ *  This function is able to do this test both for intro and rend circuits
+ *  depending on the value of <b>test_intro_circs</b>.
+ */
+static void
+helper_test_hs_machines(bool test_intro_circs)
+{
+  /* Setup the circuits */
+  origin_circuit_t *origin_client_side = origin_circuit_new();
+  client_side = TO_CIRCUIT(origin_client_side);
+  client_side->purpose = CIRCUIT_PURPOSE_C_GENERAL;
+
+  dummy_channel.cmux = circuitmux_alloc();
+  relay_side = TO_CIRCUIT(new_fake_orcirc(&dummy_channel, &dummy_channel));
+  relay_side->purpose = CIRCUIT_PURPOSE_OR;
+
+  /* extend the client circ to two hops */
+  simulate_single_hop_extend(client_side, relay_side, 1);
+  simulate_single_hop_extend(client_side, relay_side, 1);
+
+  /* machines only apply on opened circuits */
+  origin_client_side->has_opened = 1;
+
+  /************************************/
+
+  /* Attaching the client machine now won't work here because of a wrong
+   * purpose */
+  tt_assert(!client_side->padding_machine[0]);
+  circpad_add_matching_machines(origin_client_side, origin_padding_machines);
+  tt_assert(!client_side->padding_machine[0]);
+
+  /* Change the purpose, see the machine getting attached */
+  client_side->purpose = test_intro_circs ?
+    CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT : CIRCUIT_PURPOSE_C_REND_JOINED;
+  circpad_add_matching_machines(origin_client_side, origin_padding_machines);
+  tt_ptr_op(client_side->padding_info[0], OP_NE, NULL);
+  tt_ptr_op(client_side->padding_machine[0], OP_NE, NULL);
+
+  tt_ptr_op(relay_side->padding_info[0], OP_NE, NULL);
+  tt_ptr_op(relay_side->padding_machine[0], OP_NE, NULL);
+
+  /* Verify that the right machine is attached */
+  tt_str_op(client_side->padding_machine[0]->name, OP_EQ,
+            test_intro_circs ? "client_ip_circ" : "client_rp_circ");
+  tt_str_op(relay_side->padding_machine[0]->name, OP_EQ,
+            test_intro_circs ? "relay_ip_circ": "relay_rp_circ");
+
+  /***********************************/
+
+  /* Intro machines are at START state, but rend machines have already skipped
+   * to OBFUSCATE_CIRC_SETUP because of the sent PADDING_NEGOTIATE. */
+  tt_int_op(client_side->padding_info[0]->current_state, OP_EQ,
+            CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP);
+  tt_int_op(relay_side->padding_info[0]->current_state, OP_EQ,
+            CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP);
+
+  /*Send non-padding to move the machines from START to OBFUSCATE_CIRC_SETUP */
+  circpad_cell_event_nonpadding_received(client_side);
+  circpad_cell_event_nonpadding_received(relay_side);
+  tt_int_op(client_side->padding_info[0]->current_state, OP_EQ,
+            CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP);
+  tt_int_op(relay_side->padding_info[0]->current_state, OP_EQ,
+            CIRCPAD_STATE_OBFUSCATE_CIRC_SETUP);
+
+  /* Check that the state lengths have been sampled and are within range */
+  circpad_machine_runtime_t *client_machine_runtime =
+    client_side->padding_info[0];
+  circpad_machine_runtime_t *relay_machine_runtime =
+    relay_side->padding_info[0];
+
+  if (test_intro_circs) {
+    /* on the client side, we don't send any padding so
+     * state length is not set */
+    tt_int_op(client_machine_runtime->state_length, OP_EQ, -1);
+    /* relay side has state limits. check them */
+    tt_int_op(relay_machine_runtime->state_length, OP_GE,
+              INTRO_MACHINE_MINIMUM_PADDING);
+    tt_int_op(relay_machine_runtime->state_length, OP_LT,
+              INTRO_MACHINE_MAXIMUM_PADDING);
+  } else {
+    tt_int_op(client_machine_runtime->state_length, OP_EQ, 1);
+    tt_int_op(relay_machine_runtime->state_length, OP_EQ, 1);
+  }
+
+  if (test_intro_circs) {
+    int i;
+    /* Send state_length worth of padding from the relay and see that the
+     * client state goes to END */
+    for (i = (int) relay_machine_runtime->state_length ; i > 0 ; i--) {
+      circpad_send_padding_cell_for_callback(relay_machine_runtime);
+    }
+    /* See that the machine has been teared down after all the length has been
+     * exhausted (the padding info should now be null on both sides) */
+    tt_ptr_op(relay_side->padding_info[0], OP_EQ, NULL);
+    tt_ptr_op(client_side->padding_info[0], OP_EQ, NULL);
+  } else {
+    int i;
+    /* Send state_length worth of padding and see that the state goes to END */
+    for (i = (int) client_machine_runtime->state_length ; i > 0 ; i--) {
+      circpad_send_padding_cell_for_callback(client_machine_runtime);
+    }
+    /* See that the machine has been teared down after all the length has been
+     * exhausted. */
+    tt_int_op(client_side->padding_info[0]->current_state, OP_EQ,
+              CIRCPAD_STATE_END);
+  }
+
+ done:
+  free_fake_orcirc(relay_side);
+  circuitmux_detach_all_circuits(dummy_channel.cmux, NULL);
+  circuitmux_free(dummy_channel.cmux);
+  free_fake_origin_circuit(TO_ORIGIN_CIRCUIT(client_side));
+}
+
+/** Test that the HS circuit padding machines work as intended. */
+static void
+test_circuitpadding_hs_machines(void *arg)
+{
+  (void)arg;
+
+  /* Test logic:
+   *
+   * 1) Register the HS machines, which aim to hide the presense of
+   *    onion service traffic on the client-side
+   *
+   * 2) Call helper_test_hs_machines() to perform tests for the intro circuit
+   *    machines and for the rend circuit machines.
+  */
+
+  MOCK(circuitmux_attach_circuit, circuitmux_attach_circuit_mock);
+  MOCK(circuit_package_relay_cell, circuit_package_relay_cell_mock);
+  MOCK(circuit_get_nth_node, circuit_get_nth_node_mock);
+  MOCK(circpad_machine_schedule_padding,circpad_machine_schedule_padding_mock);
+
+  origin_padding_machines = smartlist_new();
+  relay_padding_machines = smartlist_new();
+
+  nodes_init();
+
+  monotime_init();
+  monotime_enable_test_mocking();
+  monotime_set_mock_time_nsec(1*TOR_NSEC_PER_USEC);
+  monotime_coarse_set_mock_time_nsec(1*TOR_NSEC_PER_USEC);
+  curr_mocked_time = 1*TOR_NSEC_PER_USEC;
+
+  timers_initialize();
+
+  /* This is needed so that we are not considered to be dormant */
+  note_user_activity(20);
+
+  /************************************/
+
+  /* Register the HS machines */
+  circpad_machine_client_hide_intro_circuits(origin_padding_machines);
+  circpad_machine_client_hide_rend_circuits(origin_padding_machines);
+  circpad_machine_relay_hide_intro_circuits(relay_padding_machines);
+  circpad_machine_relay_hide_rend_circuits(relay_padding_machines);
+
+  /***********************************/
+
+  /* Do the tests for the intro circuit machines */
+  helper_test_hs_machines(true);
+  /* Do the tests for the rend circuit machines */
+  helper_test_hs_machines(false);
+
+  timers_shutdown();
+  monotime_disable_test_mocking();
+
+  SMARTLIST_FOREACH_BEGIN(origin_padding_machines,
+                          circpad_machine_spec_t *, m) {
+    machine_spec_free(m);
+  } SMARTLIST_FOREACH_END(m);
+
+  SMARTLIST_FOREACH_BEGIN(relay_padding_machines,
+                          circpad_machine_spec_t *, m) {
+    machine_spec_free(m);
+  } SMARTLIST_FOREACH_END(m);
+
+  smartlist_free(origin_padding_machines);
+  smartlist_free(relay_padding_machines);
+
+  UNMOCK(circuitmux_attach_circuit);
+  UNMOCK(circuit_package_relay_cell);
+  UNMOCK(circuit_get_nth_node);
+  UNMOCK(circpad_machine_schedule_padding);
+}
+
 #define TEST_CIRCUITPADDING(name, flags) \
     { #name, test_##name, (flags), NULL, NULL }
 
@@ -2939,5 +3145,6 @@ struct testcase_t circuitpadding_tests[] = {
   TEST_CIRCUITPADDING(circuitpadding_closest_token_removal_usec, TT_FORK),
   TEST_CIRCUITPADDING(circuitpadding_token_removal_exact, TT_FORK),
   TEST_CIRCUITPADDING(circuitpadding_manage_circuit_lifetime, TT_FORK),
+  TEST_CIRCUITPADDING(circuitpadding_hs_machines, TT_FORK),
   END_OF_TESTCASES
 };