channelpadding.c 28.4 KB
Newer Older
1
2
3
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Nick Mathewson's avatar
Nick Mathewson committed
4
 * Copyright (c) 2007-2018, The Tor Project, Inc. */
5
6
7
8
9
10
/* See LICENSE for licensing information */

/* TOR_CHANNEL_INTERNAL_ define needed for an O(1) implementation of
 * channelpadding_channel_to_channelinfo() */
#define TOR_CHANNEL_INTERNAL_

11
12
13
14
15
16
17
18
#include "core/or/or.h"
#include "core/or/channel.h"
#include "core/or/channelpadding.h"
#include "core/or/channeltls.h"
#include "app/config/config.h"
#include "feature/nodelist/networkstatus.h"
#include "core/mainloop/connection.h"
#include "core/or/connection_or.h"
19
#include "lib/crypt_ops/crypto_rand.h"
20
#include "core/mainloop/mainloop.h"
21
22
#include "feature/stats/rephist.h"
#include "feature/relay/router.h"
23
#include "lib/time/compat_time.h"
24
#include "feature/rend/rendservice.h"
25
#include "lib/evloop/timers.h"
26

27
28
#include "core/or/cell_st.h"
#include "core/or/or_connection_st.h"
29

30
31
STATIC int32_t channelpadding_get_netflow_inactive_timeout_ms(
                                                           const channel_t *);
32
33
34
35
36
37
STATIC int channelpadding_send_disable_command(channel_t *);
STATIC int64_t channelpadding_compute_time_until_pad_for_netflow(channel_t *);

/** The total number of pending channelpadding timers */
static uint64_t total_timers_pending;

38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/** These are cached consensus parameters for netflow */
/** The timeout lower bound that is allowed before sending padding */
static int consensus_nf_ito_low;
/** The timeout upper bound that is allowed before sending padding */
static int consensus_nf_ito_high;
/** The timeout lower bound that is allowed before sending reduced padding */
static int consensus_nf_ito_low_reduced;
/** The timeout upper bound that is allowed before sending reduced padding */
static int consensus_nf_ito_high_reduced;
/** The connection timeout between relays */
static int consensus_nf_conntimeout_relays;
/** The connection timeout for client connections */
static int consensus_nf_conntimeout_clients;
/** Should we pad before circuits are actually used for client data? */
static int consensus_nf_pad_before_usage;
/** Should we pad relay-to-relay connections? */
static int consensus_nf_pad_relays;
55
56
/** Should we pad rosos connections? */
static int consensus_nf_pad_single_onion;
57

58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define TOR_MSEC_PER_SEC 1000
#define TOR_USEC_PER_MSEC 1000

/**
 * How often do we get called by the connection housekeeping (ie: once
 * per second) */
#define TOR_HOUSEKEEPING_CALLBACK_MSEC 1000
/**
 * Additional extra time buffer on the housekeeping callback, since
 * it can be delayed. This extra slack is used to decide if we should
 * schedule a timer or wait for the next callback. */
#define TOR_HOUSEKEEPING_CALLBACK_SLACK_MSEC 100

/**
 * This macro tells us if either end of the channel is connected to a client.
 * (If we're not a server, we're definitely a client. If the channel thinks
74
 *  it's a client, use that. Then finally verify in the consensus).
75
76
 */
#define CHANNEL_IS_CLIENT(chan, options) \
77
  (!public_server_mode((options)) || channel_is_client(chan) || \
78
79
      !connection_or_digest_is_known_relay((chan)->identity_digest))

80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * This function is called to update cached consensus parameters every time
 * there is a consensus update. This allows us to move the consensus param
 * search off of the critical path, so it does not need to be evaluated
 * for every single connection, every second.
 */
void
channelpadding_new_consensus_params(networkstatus_t *ns)
{
#define DFLT_NETFLOW_INACTIVE_KEEPALIVE_LOW 1500
#define DFLT_NETFLOW_INACTIVE_KEEPALIVE_HIGH 9500
#define DFLT_NETFLOW_INACTIVE_KEEPALIVE_MIN 0
#define DFLT_NETFLOW_INACTIVE_KEEPALIVE_MAX 60000
  consensus_nf_ito_low = networkstatus_get_param(ns, "nf_ito_low",
      DFLT_NETFLOW_INACTIVE_KEEPALIVE_LOW,
      DFLT_NETFLOW_INACTIVE_KEEPALIVE_MIN,
      DFLT_NETFLOW_INACTIVE_KEEPALIVE_MAX);
97
  consensus_nf_ito_high = networkstatus_get_param(ns, "nf_ito_high",
98
99
100
101
102
103
104
105
106
      DFLT_NETFLOW_INACTIVE_KEEPALIVE_HIGH,
      consensus_nf_ito_low,
      DFLT_NETFLOW_INACTIVE_KEEPALIVE_MAX);

#define DFLT_NETFLOW_REDUCED_KEEPALIVE_LOW 9000
#define DFLT_NETFLOW_REDUCED_KEEPALIVE_HIGH 14000
#define DFLT_NETFLOW_REDUCED_KEEPALIVE_MIN 0
#define DFLT_NETFLOW_REDUCED_KEEPALIVE_MAX 60000
  consensus_nf_ito_low_reduced =
107
    networkstatus_get_param(ns, "nf_ito_low_reduced",
108
109
110
111
112
        DFLT_NETFLOW_REDUCED_KEEPALIVE_LOW,
        DFLT_NETFLOW_REDUCED_KEEPALIVE_MIN,
        DFLT_NETFLOW_REDUCED_KEEPALIVE_MAX);

  consensus_nf_ito_high_reduced =
113
    networkstatus_get_param(ns, "nf_ito_high_reduced",
114
115
116
117
118
119
120
121
        DFLT_NETFLOW_REDUCED_KEEPALIVE_HIGH,
        consensus_nf_ito_low_reduced,
        DFLT_NETFLOW_REDUCED_KEEPALIVE_MAX);

#define CONNTIMEOUT_RELAYS_DFLT (60*60) // 1 hour
#define CONNTIMEOUT_RELAYS_MIN 60
#define CONNTIMEOUT_RELAYS_MAX (7*24*60*60) // 1 week
  consensus_nf_conntimeout_relays =
122
    networkstatus_get_param(ns, "nf_conntimeout_relays",
123
124
125
126
127
128
129
130
        CONNTIMEOUT_RELAYS_DFLT,
        CONNTIMEOUT_RELAYS_MIN,
        CONNTIMEOUT_RELAYS_MAX);

#define CIRCTIMEOUT_CLIENTS_DFLT (30*60) // 30 minutes
#define CIRCTIMEOUT_CLIENTS_MIN 60
#define CIRCTIMEOUT_CLIENTS_MAX (24*60*60) // 24 hours
  consensus_nf_conntimeout_clients =
131
    networkstatus_get_param(ns, "nf_conntimeout_clients",
132
133
134
135
136
        CIRCTIMEOUT_CLIENTS_DFLT,
        CIRCTIMEOUT_CLIENTS_MIN,
        CIRCTIMEOUT_CLIENTS_MAX);

  consensus_nf_pad_before_usage =
137
    networkstatus_get_param(ns, "nf_pad_before_usage", 1, 0, 1);
138
139

  consensus_nf_pad_relays =
140
    networkstatus_get_param(ns, "nf_pad_relays", 0, 0, 1);
141
142

  consensus_nf_pad_single_onion =
143
144
145
    networkstatus_get_param(ns,
                            CHANNELPADDING_SOS_PARAM,
                            CHANNELPADDING_SOS_DEFAULT, 0, 1);
146
147
}

148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/**
 * Get a random netflow inactive timeout keepalive period in milliseconds,
 * the range for which is determined by consensus parameters, negotiation,
 * configuration, or default values. The consensus parameters enforce the
 * minimum possible value, to avoid excessively frequent padding.
 *
 * The ranges for this value were chosen to be low enough to ensure that
 * routers do not emit a new netflow record for a connection due to it
 * being idle.
 *
 * Specific timeout values for major routers are listed in Proposal 251.
 * No major router appeared capable of setting an inactive timeout below 10
 * seconds, so we set the defaults below that value, since we can always
 * scale back if it ends up being too much padding.
 *
 * Returns the next timeout period (in milliseconds) after which we should
 * send a padding packet, or 0 if padding is disabled.
 */
166
STATIC int32_t
167
168
channelpadding_get_netflow_inactive_timeout_ms(const channel_t *chan)
{
169
170
  int low_timeout = consensus_nf_ito_low;
  int high_timeout = consensus_nf_ito_high;
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
  int X1, X2;

  if (low_timeout == 0 && low_timeout == high_timeout)
    return 0; // No padding

  /* If we have negotiated different timeout values, use those, but
   * don't allow them to be lower than the consensus ones */
  if (chan->padding_timeout_low_ms && chan->padding_timeout_high_ms) {
    low_timeout = MAX(low_timeout, chan->padding_timeout_low_ms);
    high_timeout = MAX(high_timeout, chan->padding_timeout_high_ms);
  }

  if (low_timeout == high_timeout)
    return low_timeout; // No randomization

  /*
   * This MAX() hack is here because we apply the timeout on both the client
   * and the server. This creates the situation where the total time before
   * sending a packet in either direction is actually
   * min(client_timeout,server_timeout).
   *
   * If X is a random variable uniform from 0..R-1 (where R=high-low),
   * then Y=max(X,X) has Prob(Y == i) = (2.0*i + 1)/(R*R).
   *
   * If we create a third random variable Z=min(Y,Y), then it turns out that
   * Exp[Z] ~= Exp[X]. Here's a table:
   *
   *    R     Exp[X]    Exp[Z]    Exp[min(X,X)]   Exp[max(X,X)]
   *  2000     999.5    1066        666.2           1332.8
   *  3000    1499.5    1599.5      999.5           1999.5
   *  5000    2499.5    2666       1666.2           3332.8
   *  6000    2999.5    3199.5     1999.5           3999.5
   *  7000    3499.5    3732.8     2332.8           4666.2
   *  8000    3999.5    4266.2     2666.2           5332.8
   *  10000   4999.5    5328       3332.8           6666.2
   *  15000   7499.5    7995       4999.5           9999.5
   *  20000   9900.5    10661      6666.2           13332.8
   *
   * In other words, this hack makes it so that when both the client and
   * the guard are sending this padding, then the averages work out closer
   * to the midpoint of the range, making the overhead easier to tune.
   * If only one endpoint is padding (for example: if the relay does not
   * support padding, but the client has set ConnectionPadding 1; or
   * if the relay does support padding, but the client has set
   * ReducedConnectionPadding 1), then the defense will still prevent
   * record splitting, but with less overhead than the midpoint
   * (as seen by the Exp[max(X,X)] column).
   *
   * To calculate average padding packet frequency (and thus overhead),
   * index into the table by picking a row based on R = high-low. Then,
   * use the appropriate column (Exp[Z] for two-sided padding, and
   * Exp[max(X,X)] for one-sided padding). Finally, take this value
   * and add it to the low timeout value. This value is the average
   * frequency which padding packets will be sent.
   */

  X1 = crypto_rand_int(high_timeout - low_timeout);
  X2 = crypto_rand_int(high_timeout - low_timeout);
  return low_timeout + MAX(X1, X2);
}

/**
 * Update this channel's padding settings based on the PADDING_NEGOTIATE
 * contents.
 *
 * Returns -1 on error; 1 on success.
 */
int
channelpadding_update_padding_for_channel(channel_t *chan,
                const channelpadding_negotiate_t *pad_vars)
{
  if (pad_vars->version != 0) {
    static ratelim_t version_limit = RATELIM_INIT(600);

    log_fn_ratelim(&version_limit,LOG_PROTOCOL_WARN,LD_PROTOCOL,
           "Got a PADDING_NEGOTIATE cell with an unknown version. Ignoring.");
    return -1;
  }

  // We should not allow malicious relays to disable or reduce padding for
  // us as clients. In fact, we should only accept this cell at all if we're
252
  // operating as a relay. Bridges should not accept it from relays, either
253
254
  // (only from their clients).
  if ((get_options()->BridgeRelay &&
255
       connection_or_digest_is_known_relay(chan->identity_digest)) ||
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
      !get_options()->ORPort_set) {
    static ratelim_t relay_limit = RATELIM_INIT(600);

    log_fn_ratelim(&relay_limit,LOG_PROTOCOL_WARN,LD_PROTOCOL,
           "Got a PADDING_NEGOTIATE from relay at %s (%s). "
           "This should not happen.",
           chan->get_remote_descr(chan, 0),
           hex_str(chan->identity_digest, DIGEST_LEN));
    return -1;
  }

  chan->padding_enabled = (pad_vars->command == CHANNELPADDING_COMMAND_START);

  /* Min must not be lower than the current consensus parameter
     nf_ito_low. */
271
272
  chan->padding_timeout_low_ms = MAX(consensus_nf_ito_low,
                                     pad_vars->ito_low_ms);
273
274
275

  /* Max must not be lower than ito_low_ms */
  chan->padding_timeout_high_ms = MAX(chan->padding_timeout_low_ms,
276
                                      pad_vars->ito_high_ms);
277
278

  log_fn(LOG_INFO,LD_OR,
279
         "Negotiated padding=%d, lo=%d, hi=%d on %"PRIu64,
280
281
         chan->padding_enabled, chan->padding_timeout_low_ms,
         chan->padding_timeout_high_ms,
282
         (chan->global_identifier));
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308

  return 1;
}

/**
 * Sends a CELL_PADDING_NEGOTIATE on the channel to tell the other side not
 * to send padding.
 *
 * Returns -1 on error, 0 on success.
 */
STATIC int
channelpadding_send_disable_command(channel_t *chan)
{
  channelpadding_negotiate_t disable;
  cell_t cell;

  tor_assert(BASE_CHAN_TO_TLS(chan)->conn->link_proto >=
             MIN_LINK_PROTO_FOR_CHANNEL_PADDING);

  memset(&cell, 0, sizeof(cell_t));
  memset(&disable, 0, sizeof(channelpadding_negotiate_t));
  cell.command = CELL_PADDING_NEGOTIATE;

  channelpadding_negotiate_set_command(&disable, CHANNELPADDING_COMMAND_STOP);

  if (channelpadding_negotiate_encode(cell.payload, CELL_PAYLOAD_SIZE,
309
                                      &disable) < 0)
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
    return -1;

  if (chan->write_cell(chan, &cell) == 1)
    return 0;
  else
    return -1;
}

/**
 * Sends a CELL_PADDING_NEGOTIATE on the channel to tell the other side to
 * resume sending padding at some rate.
 *
 * Returns -1 on error, 0 on success.
 */
int
channelpadding_send_enable_command(channel_t *chan, uint16_t low_timeout,
                                   uint16_t high_timeout)
{
  channelpadding_negotiate_t enable;
  cell_t cell;

  tor_assert(BASE_CHAN_TO_TLS(chan)->conn->link_proto >=
             MIN_LINK_PROTO_FOR_CHANNEL_PADDING);

  memset(&cell, 0, sizeof(cell_t));
  memset(&enable, 0, sizeof(channelpadding_negotiate_t));
  cell.command = CELL_PADDING_NEGOTIATE;

  channelpadding_negotiate_set_command(&enable, CHANNELPADDING_COMMAND_START);
  channelpadding_negotiate_set_ito_low_ms(&enable, low_timeout);
  channelpadding_negotiate_set_ito_high_ms(&enable, high_timeout);

  if (channelpadding_negotiate_encode(cell.payload, CELL_PAYLOAD_SIZE,
343
                                      &enable) < 0)
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
    return -1;

  if (chan->write_cell(chan, &cell) == 1)
    return 0;
  else
    return -1;
}

/**
 * Sends a CELL_PADDING cell on a channel if it has been idle since
 * our callback was scheduled.
 *
 * This function also clears the pending padding timer and the callback
 * flags.
 */
static void
channelpadding_send_padding_cell_for_callback(channel_t *chan)
{
  cell_t cell;

  /* Check that the channel is still valid and open */
  if (!chan || chan->state != CHANNEL_STATE_OPEN) {
    if (chan) chan->pending_padding_callback = 0;
    log_fn(LOG_INFO,LD_OR,
           "Scheduled a netflow padding cell, but connection already closed.");
    return;
  }

  /* We should have a pending callback flag set. */
  if (BUG(chan->pending_padding_callback == 0))
    return;

  chan->pending_padding_callback = 0;

378
  if (monotime_coarse_is_zero(&chan->next_padding_time) ||
379
380
      chan->has_queued_writes(chan) ||
      (chan->cmux && circuitmux_num_cells(chan->cmux))) {
381
    /* We must have been active before the timer fired */
382
    monotime_coarse_zero(&chan->next_padding_time);
383
384
385
386
    return;
  }

  {
387
388
    monotime_coarse_t now;
    monotime_coarse_get(&now);
389
390

    log_fn(LOG_INFO,LD_OR,
391
392
393
        "Sending netflow keepalive on %"PRIu64" to %s (%s) after "
        "%"PRId64" ms. Delta %"PRId64"ms",
        (chan->global_identifier),
394
395
        safe_str_client(chan->get_remote_descr(chan, 0)),
        safe_str_client(hex_str(chan->identity_digest, DIGEST_LEN)),
396
397
        (monotime_coarse_diff_msec(&chan->timestamp_xfer,&now)),
        (
398
                   monotime_coarse_diff_msec(&chan->next_padding_time,&now)));
399
400
401
  }

  /* Clear the timer */
402
  monotime_coarse_zero(&chan->next_padding_time);
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420

  /* Send the padding cell. This will cause the channel to get a
   * fresh timestamp_active */
  memset(&cell, 0, sizeof(cell));
  cell.command = CELL_PADDING;
  chan->write_cell(chan, &cell);
}

/**
 * tor_timer callback function for us to send padding on an idle channel.
 *
 * This function just obtains the channel from the callback handle, ensures
 * it is still valid, and then hands it off to
 * channelpadding_send_padding_cell_for_callback(), which checks if
 * the channel is still idle before sending padding.
 */
static void
channelpadding_send_padding_callback(tor_timer_t *timer, void *args,
421
                                     const struct monotime_t *when)
422
423
{
  channel_t *chan = channel_handle_get((struct channel_handle_t*)args);
424
  (void)timer; (void)when;
425
426
427
428

  if (chan && CHANNEL_CAN_HANDLE_CELLS(chan)) {
    /* Hrmm.. It might be nice to have an equivalent to assert_connection_ok
     * for channels. Then we could get rid of the channeltls dependency */
429
    tor_assert(TO_CONN(BASE_CHAN_TO_TLS(chan)->conn)->magic ==
430
               OR_CONNECTION_MAGIC);
431
    assert_connection_ok(TO_CONN(BASE_CHAN_TO_TLS(chan)->conn), approx_time());
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461

    channelpadding_send_padding_cell_for_callback(chan);
  } else {
     log_fn(LOG_INFO,LD_OR,
            "Channel closed while waiting for timer.");
  }

  total_timers_pending--;
}

/**
 * Schedules a callback to send padding on a channel in_ms milliseconds from
 * now.
 *
 * Returns CHANNELPADDING_WONTPAD on error, CHANNELPADDING_PADDING_SENT if we
 * sent the packet immediately without a timer, and
 * CHANNELPADDING_PADDING_SCHEDULED if we decided to schedule a timer.
 */
static channelpadding_decision_t
channelpadding_schedule_padding(channel_t *chan, int in_ms)
{
  struct timeval timeout;
  tor_assert(!chan->pending_padding_callback);

  if (in_ms <= 0) {
    chan->pending_padding_callback = 1;
    channelpadding_send_padding_cell_for_callback(chan);
    return CHANNELPADDING_PADDING_SENT;
  }

462
463
  timeout.tv_sec = in_ms/TOR_MSEC_PER_SEC;
  timeout.tv_usec = (in_ms%TOR_USEC_PER_MSEC)*TOR_USEC_PER_MSEC;
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503

  if (!chan->timer_handle) {
    chan->timer_handle = channel_handle_new(chan);
  }

  if (chan->padding_timer) {
    timer_set_cb(chan->padding_timer,
                 channelpadding_send_padding_callback,
                 chan->timer_handle);
  } else {
    chan->padding_timer = timer_new(channelpadding_send_padding_callback,
                                    chan->timer_handle);
  }
  timer_schedule(chan->padding_timer, &timeout);

  rep_hist_padding_count_timers(++total_timers_pending);

  chan->pending_padding_callback = 1;
  return CHANNELPADDING_PADDING_SCHEDULED;
}

/**
 * Calculates the number of milliseconds from now to schedule a padding cell.
 *
 * Returns the number of milliseconds from now (relative) to schedule the
 * padding callback. If the padding timer is more than 1.1 seconds in the
 * future, we return -1, to avoid scheduling excessive callbacks. If padding
 * is disabled in the consensus, we return -2.
 *
 * Side-effects: Updates chan->next_padding_time_ms, storing an (absolute, not
 * relative) millisecond representation of when we should send padding, unless
 * other activity happens first. This side-effect allows us to avoid
 * scheduling a libevent callback until we're within 1.1 seconds of the padding
 * time.
 */
#define CHANNELPADDING_TIME_LATER -1
#define CHANNELPADDING_TIME_DISABLED -2
STATIC int64_t
channelpadding_compute_time_until_pad_for_netflow(channel_t *chan)
{
504
505
  monotime_coarse_t now;
  monotime_coarse_get(&now);
506

507
  if (monotime_coarse_is_zero(&chan->next_padding_time)) {
508
    /* If the below line or crypto_rand_int() shows up on a profile,
509
     * we can avoid getting a timeout until we're at least nf_ito_lo
510
511
512
513
     * from a timeout window. That will prevent us from setting timers
     * on connections that were active up to 1.5 seconds ago.
     * Idle connections should only call this once every 5.5s on average
     * though, so that might be a micro-optimization for little gain. */
514
    int32_t padding_timeout =
515
516
517
518
519
        channelpadding_get_netflow_inactive_timeout_ms(chan);

    if (!padding_timeout)
      return CHANNELPADDING_TIME_DISABLED;

520
521
522
    monotime_coarse_add_msec(&chan->next_padding_time,
                             &chan->timestamp_xfer,
                             padding_timeout);
523
524
  }

525
526
527
  const int64_t ms_till_pad =
    monotime_coarse_diff_msec(&now, &chan->next_padding_time);

528
529
530
531
532
533
  /* If the next padding time is beyond the maximum possible consensus value,
   * then this indicates a clock jump, so just send padding now. This is
   * better than using monotonic time because we want to avoid the situation
   * where we wait around forever for monotonic time to move forward after
   * a clock jump far into the past.
   */
534
  if (ms_till_pad > DFLT_NETFLOW_INACTIVE_KEEPALIVE_MAX) {
535
536
    tor_fragile_assert();
    log_warn(LD_BUG,
537
        "Channel padding timeout scheduled %"PRId64"ms in the future. "
538
        "Did the monotonic clock just jump?",
539
        (ms_till_pad));
540
541
542
543
    return 0; /* Clock jumped: Send padding now */
  }

  /* If the timeout will expire before the next time we're called (1000ms
544
     from now, plus some slack), then calculate the number of milliseconds
545
546
547
     from now which we should send padding, so we can schedule a callback
     then.
   */
548
549
  if (ms_till_pad < (TOR_HOUSEKEEPING_CALLBACK_MSEC +
                       TOR_HOUSEKEEPING_CALLBACK_SLACK_MSEC)) {
550
551
552
553
554
555
556
557
558
    /* If the padding time is in the past, that means that libevent delayed
     * calling the once-per-second callback due to other work taking too long.
     * See https://bugs.torproject.org/22212 and
     * https://bugs.torproject.org/16585. This is a systemic problem
     * with being single-threaded, but let's emit a notice if this
     * is long enough in the past that we might have missed a netflow window,
     * and allowed a router to emit a netflow frame, just so we don't forget
     * about it entirely.. */
#define NETFLOW_MISSED_WINDOW (150000 - DFLT_NETFLOW_INACTIVE_KEEPALIVE_HIGH)
559
560
    if (ms_till_pad < 0) {
      int severity = (ms_till_pad < -NETFLOW_MISSED_WINDOW)
561
562
                      ? LOG_NOTICE : LOG_INFO;
      log_fn(severity, LD_OR,
563
564
              "Channel padding timeout scheduled %"PRId64"ms in the past. ",
             (-ms_till_pad));
565
566
567
      return 0; /* Clock jumped: Send padding now */
    }

568
    return ms_till_pad;
569
570
571
572
  }
  return CHANNELPADDING_TIME_LATER;
}

573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
/**
 * Returns a randomized value for channel idle timeout in seconds.
 * The channel idle timeout governs how quickly we close a channel
 * after its last circuit has disappeared.
 *
 * There are three classes of channels:
 *  1. Client+non-canonical. These live for 3-4.5 minutes
 *  2. relay to relay. These live for 45-75 min by default
 *  3. Reduced padding clients. These live for 1.5-2.25 minutes.
 *
 * Also allows the default relay-to-relay value to be controlled by the
 * consensus.
 */
unsigned int
channelpadding_get_channel_idle_timeout(const channel_t *chan,
                                        int is_canonical)
{
  const or_options_t *options = get_options();
  unsigned int timeout;

  /* Non-canonical and client channels only last for 3-4.5 min when idle */
Nick Mathewson's avatar
Nick Mathewson committed
594
  if (!is_canonical || CHANNEL_IS_CLIENT(chan, options)) {
595
596
597
598
599
#define CONNTIMEOUT_CLIENTS_BASE 180 // 3 to 4.5 min
    timeout = CONNTIMEOUT_CLIENTS_BASE
        + crypto_rand_int(CONNTIMEOUT_CLIENTS_BASE/2);
  } else { // Canonical relay-to-relay channels
    // 45..75min or consensus +/- 25%
600
    timeout = consensus_nf_conntimeout_relays;
601
602
603
604
605
606
607
608
609
610
611
612
613
    timeout = 3*timeout/4 + crypto_rand_int(timeout/2);
  }

  /* If ReducedConnectionPadding is set, we want to halve the duration of
   * the channel idle timeout, since reducing the additional time that
   * a channel stays open will reduce the total overhead for making
   * new channels. This reduction in overhead/channel expense
   * is important for mobile users. The option cannot be set by relays.
   *
   * We also don't reduce any values for timeout that the user explicitly
   * set.
   */
  if (options->ReducedConnectionPadding
614
      && !options->CircuitsAvailableTimeout) {
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
    timeout /= 2;
  }

  return timeout;
}

/**
 * This function controls how long we keep idle circuits open,
 * and how long we build predicted circuits. This behavior is under
 * the control of channelpadding because circuit availability is the
 * dominant factor in channel lifespan, which influences total padding
 * overhead.
 *
 * Returns a randomized number of seconds in a range from
 * CircuitsAvailableTimeout to 2*CircuitsAvailableTimeout. This value is halved
 * if ReducedConnectionPadding is set. The default value of
 * CircuitsAvailableTimeout can be controlled by the consensus.
 */
int
channelpadding_get_circuits_available_timeout(void)
{
  const or_options_t *options = get_options();
  int timeout = options->CircuitsAvailableTimeout;

  if (!timeout) {
640
    timeout = consensus_nf_conntimeout_clients;
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659

    /* If ReducedConnectionPadding is set, we want to halve the duration of
     * the channel idle timeout, since reducing the additional time that
     * a channel stays open will reduce the total overhead for making
     * new connections. This reduction in overhead/connection expense
     * is important for mobile users. The option cannot be set by relays.
     *
     * We also don't reduce any values for timeout that the user explicitly
     * set.
     */
    if (options->ReducedConnectionPadding) {
      // half the value to 15..30min by default
      timeout /= 2;
    }
  }

  // 30..60min by default
  timeout = timeout + crypto_rand_int(timeout);

660
661
  tor_assert(timeout >= 0);

662
663
664
  return timeout;
}

665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
/**
 * Calling this function on a channel causes it to tell the other side
 * not to send padding, and disables sending padding from this side as well.
 */
void
channelpadding_disable_padding_on_channel(channel_t *chan)
{
  chan->padding_enabled = 0;

  // Send cell to disable padding on the other end
  channelpadding_send_disable_command(chan);
}

/**
 * Calling this function on a channel causes it to tell the other side
 * not to send padding, and reduces the rate that padding is sent from
 * this side.
 */
void
channelpadding_reduce_padding_on_channel(channel_t *chan)
{
  /* Padding can be forced and reduced by clients, regardless of if
   * the channel supports it. So we check for support here before
   * sending any commands. */
  if (chan->padding_enabled) {
    channelpadding_send_disable_command(chan);
  }

693
694
  chan->padding_timeout_low_ms = consensus_nf_ito_low_reduced;
  chan->padding_timeout_high_ms = consensus_nf_ito_high_reduced;
695
696

  log_fn(LOG_INFO,LD_OR,
697
698
         "Reduced padding on channel %"PRIu64": lo=%d, hi=%d",
         (chan->global_identifier),
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
         chan->padding_timeout_low_ms, chan->padding_timeout_high_ms);
}

/**
 * This function is called once per second by run_connection_housekeeping(),
 * but only if the channel is still open, valid, and non-wedged.
 *
 * It decides if and when we should send a padding cell, and if needed,
 * schedules a callback to send that cell at the appropriate time.
 *
 * Returns an enum that represents the current padding decision state.
 * Return value is currently used only by unit tests.
 */
channelpadding_decision_t
channelpadding_decide_to_pad_channel(channel_t *chan)
{
  const or_options_t *options = get_options();

  /* Only pad open channels */
  if (chan->state != CHANNEL_STATE_OPEN)
    return CHANNELPADDING_WONTPAD;

  if (chan->channel_usage == CHANNEL_USED_FOR_FULL_CIRCS) {
722
    if (!consensus_nf_pad_before_usage)
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
      return CHANNELPADDING_WONTPAD;
  } else if (chan->channel_usage != CHANNEL_USED_FOR_USER_TRAFFIC) {
    return CHANNELPADDING_WONTPAD;
  }

  if (chan->pending_padding_callback)
    return CHANNELPADDING_PADDING_ALREADY_SCHEDULED;

  /* Don't pad the channel if we didn't negotiate it, but still
   * allow clients to force padding if options->ChannelPadding is
   * explicitly set to 1.
   */
  if (!chan->padding_enabled && options->ConnectionPadding != 1) {
    return CHANNELPADDING_WONTPAD;
  }

739
740
741
742
743
744
  if (rend_service_allow_non_anonymous_connection(options) &&
      !consensus_nf_pad_single_onion) {
    /* If the consensus just changed values, this channel may still
     * think padding is enabled. Negotiate it off. */
    if (chan->padding_enabled)
      channelpadding_disable_padding_on_channel(chan);
745
746

    return CHANNELPADDING_WONTPAD;
747
  }
748

749
750
751
752
753
  /* There should always be a cmux on the circuit. After that,
   * only schedule padding if there are no queued writes and no
   * queued cells in circuitmux queues. */
  if (chan->cmux && !chan->has_queued_writes(chan) &&
      !circuitmux_num_cells(chan->cmux)) {
754
755
    int is_client_channel = 0;

756
    if (CHANNEL_IS_CLIENT(chan, options)) {
757
758
759
760
761
762
       is_client_channel = 1;
    }

    /* If nf_pad_relays=1 is set in the consensus, we pad
     * on *all* idle connections, relay-relay or relay-client.
     * Otherwise pad only for client+bridge cons */
763
    if (is_client_channel || consensus_nf_pad_relays) {
764
765
766
767
768
769
770
771
772
      int64_t pad_time_ms =
          channelpadding_compute_time_until_pad_for_netflow(chan);

      if (pad_time_ms == CHANNELPADDING_TIME_DISABLED) {
        return CHANNELPADDING_WONTPAD;
      } else if (pad_time_ms == CHANNELPADDING_TIME_LATER) {
        chan->currently_padding = 1;
        return CHANNELPADDING_PADLATER;
      } else {
773
774
775
        if (BUG(pad_time_ms > INT_MAX)) {
          pad_time_ms = INT_MAX;
        }
776
777
778
779
780
781
       /* We have to schedule a callback because we're called exactly once per
        * second, but we don't want padding packets to go out exactly on an
        * integer multiple of seconds. This callback will only be scheduled
        * if we're within 1.1 seconds of the padding time.
        */
        chan->currently_padding = 1;
782
        return channelpadding_schedule_padding(chan, (int)pad_time_ms);
783
784
785
786
787
788
789
790
791
      }
    } else {
      chan->currently_padding = 0;
      return CHANNELPADDING_WONTPAD;
    }
  } else {
    return CHANNELPADDING_PADLATER;
  }
}