onion.c 25.9 KB
Newer Older
1
/* Copyright 2001,2002,2003 Roger Dingledine, Matej Pfajfar. */
2
3
/* See LICENSE for licensing information */
/* $Id$ */
Roger Dingledine's avatar
Roger Dingledine committed
4

5
6
7
8
9
/**
 * \file onion.c
 * \brief Functions to handle onion parsing/creation and handle cpaths.
 **/

Roger Dingledine's avatar
Roger Dingledine committed
10
11
#include "or.h"

Nick Mathewson's avatar
Nick Mathewson committed
12
13
/* prototypes for smartlist operations from routerlist.h
 * They're here to prevent precedence issues with the .h files
14
15
 */
void router_add_running_routers_to_smartlist(smartlist_t *sl);
16
void add_nickname_list_to_smartlist(smartlist_t *sl, char *list);
17

18
extern or_options_t options; /**< command-line and config-file options */
19

20
static int count_acceptable_routers(smartlist_t *routers);
Roger Dingledine's avatar
Roger Dingledine committed
21

22
23
24
25
26
27
28
29
/** Decide whether the first bit of the circuit ID will be
 * 0 or 1, to avoid conflicts where each side randomly chooses
 * the same circuit ID.
 *
 * Return CIRC_ID_TYPE_LOWER if local_nick is NULL, or if
 * local_nick is lexographically smaller than remote_nick.
 * Else return CIRC_ID_TYPE_HIGHER.
 */
30
int decide_circ_id_type(char *local_nick, char *remote_nick) {
31
  int result;
Roger Dingledine's avatar
Roger Dingledine committed
32

Roger Dingledine's avatar
Roger Dingledine committed
33
  tor_assert(remote_nick);
34
  if(!local_nick)
35
    return CIRC_ID_TYPE_LOWER;
36
  result = strcasecmp(local_nick, remote_nick);
Roger Dingledine's avatar
Roger Dingledine committed
37
  tor_assert(result);
38
  if(result < 0)
39
40
    return CIRC_ID_TYPE_LOWER;
  return CIRC_ID_TYPE_HIGHER;
Roger Dingledine's avatar
Roger Dingledine committed
41
42
}

Roger Dingledine's avatar
Roger Dingledine committed
43
44
45
46
47
struct onion_queue_t {
  circuit_t *circ;
  struct onion_queue_t *next;
};

48
/** global (within this file) variables used by the next few functions */
49
50
static struct onion_queue_t *ol_list=NULL;
static struct onion_queue_t *ol_tail=NULL;
51
/** length of ol_list */
52
53
static int ol_length=0;

54
55
56
/** Add <b>circ</b> to the end of ol_list and return 0, except
 * if ol_list is too long, in which case do nothing and return -1.
 */
57
58
59
int onion_pending_add(circuit_t *circ) {
  struct onion_queue_t *tmp;

Roger Dingledine's avatar
Roger Dingledine committed
60
  tmp = tor_malloc(sizeof(struct onion_queue_t));
61
  tmp->circ = circ;
Roger Dingledine's avatar
Roger Dingledine committed
62
  tmp->next = NULL;
63
64

  if(!ol_tail) {
Roger Dingledine's avatar
Roger Dingledine committed
65
66
    tor_assert(!ol_list);
    tor_assert(!ol_length);
67
68
69
70
71
72
    ol_list = tmp;
    ol_tail = tmp;
    ol_length++;
    return 0;
  }

Roger Dingledine's avatar
Roger Dingledine committed
73
74
  tor_assert(ol_list);
  tor_assert(!ol_tail->next);
75
76

  if(ol_length >= options.MaxOnionsPending) {
Roger Dingledine's avatar
Roger Dingledine committed
77
    log_fn(LOG_WARN,"Already have %d onions queued. Closing.", ol_length);
78
79
80
81
82
83
84
85
86
87
88
    free(tmp);
    return -1;
  }

  ol_length++;
  ol_tail->next = tmp;
  ol_tail = tmp;
  return 0;

}

89
90
91
/** Remove the first item from ol_list and return it, or return
 * NULL if the list is empty.
 */
Roger Dingledine's avatar
Roger Dingledine committed
92
circuit_t *onion_next_task(void) {
93
  circuit_t *circ;
94
95

  if(!ol_list)
Roger Dingledine's avatar
Roger Dingledine committed
96
    return NULL; /* no onions pending, we're done */
97

Roger Dingledine's avatar
Roger Dingledine committed
98
99
100
  tor_assert(ol_list->circ);
  tor_assert(ol_list->circ->p_conn); /* make sure it's still valid */
  tor_assert(ol_length > 0);
101
102
103
  circ = ol_list->circ;
  onion_pending_remove(ol_list->circ);
  return circ;
104
105
}

106
107
/** Go through ol_list, find the onion_queue_t element which points to
 * circ, remove and free that element. Leave circ itself alone.
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 */
void onion_pending_remove(circuit_t *circ) {
  struct onion_queue_t *tmpo, *victim;

  if(!ol_list)
    return; /* nothing here. */

  /* first check to see if it's the first entry */
  tmpo = ol_list;
  if(tmpo->circ == circ) {
    /* it's the first one. remove it from the list. */
    ol_list = tmpo->next;
    if(!ol_list)
      ol_tail = NULL;
    ol_length--;
    victim = tmpo;
  } else { /* we need to hunt through the rest of the list */
    for( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ;
    if(!tmpo->next) {
127
      log_fn(LOG_DEBUG,"circ (p_circ_id %d) not in list, probably at cpuworker.",circ->p_circ_id);
128
129
130
131
132
133
134
135
136
137
138
139
      return;
    }
    /* now we know tmpo->next->circ == circ */
    victim = tmpo->next;
    tmpo->next = victim->next;
    if(ol_tail == victim)
      ol_tail = tmpo;
    ol_length--;
  }

  /* now victim points to the element that needs to be removed */

Roger Dingledine's avatar
Roger Dingledine committed
140
  free(victim);
141
142
}

143
144
145
/** Given a response payload and keys, initialize, then send a created
 * cell back.
 */
146
int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *keys) {
147
  cell_t cell;
148
  crypt_path_t *tmp_cpath;
149

Nick Mathewson's avatar
Nick Mathewson committed
150
  tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
151

152
153
  memset(&cell, 0, sizeof(cell_t));
  cell.command = CELL_CREATED;
154
  cell.circ_id = circ->p_circ_id;
155
156

  circ->state = CIRCUIT_STATE_OPEN;
Roger Dingledine's avatar
Roger Dingledine committed
157

Roger Dingledine's avatar
Roger Dingledine committed
158
  log_fn(LOG_DEBUG,"Entering.");
159

160
  memcpy(cell.payload, payload, ONIONSKIN_REPLY_LEN);
Roger Dingledine's avatar
Roger Dingledine committed
161

162
163
  log_fn(LOG_INFO,"init digest forward 0x%.8x, backward 0x%.8x.",
         (unsigned int)*(uint32_t*)(keys), (unsigned int)*(uint32_t*)(keys+20));
164
165
166
  if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
    log_fn(LOG_WARN,"Circuit initialization failed");
    tor_free(tmp_cpath);
Roger Dingledine's avatar
Roger Dingledine committed
167
168
    return -1;
  }
169
170
171
172
173
  circ->n_digest = tmp_cpath->f_digest;
  circ->n_crypto = tmp_cpath->f_crypto;
  circ->p_digest = tmp_cpath->b_digest;
  circ->p_crypto = tmp_cpath->b_crypto;
  tor_free(tmp_cpath);
Roger Dingledine's avatar
Roger Dingledine committed
174

175
  memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
176

Nick Mathewson's avatar
Nick Mathewson committed
177
  connection_or_write_cell_to_buf(&cell, circ->p_conn);
Roger Dingledine's avatar
Roger Dingledine committed
178
  log_fn(LOG_DEBUG,"Finished sending 'created' cell.");
Roger Dingledine's avatar
Roger Dingledine committed
179
180
181
182

  return 0;
}

183
extern int has_fetched_directory; /**< from main.c */
184

185
186
187
188
189
190
/** Choose a length for a circuit of purpose <b>purpose</b>.
 * Default length is 3 + the number of endpoints that would give something
 * away. If the routerlist <b>routers</b> doesn't have enough routers
 * to handle the desired path length, return as large a path length as
 * is feasible, except if it's less than 2, in which case return -1.
 */
191
static int new_route_len(double cw, uint8_t purpose, smartlist_t *routers) {
192
  int num_acceptable_routers;
193
  int routelen;
194

Roger Dingledine's avatar
Roger Dingledine committed
195
  tor_assert((cw >= 0) && (cw < 1) && routers); /* valid parameters */
196

197
198
199
#ifdef TOR_PERF
  routelen = 2;
#else
200
201
  if(purpose == CIRCUIT_PURPOSE_C_GENERAL)
    routelen = 3;
202
  else if(purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
203
    routelen = 4;
204
205
  else if(purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND)
    routelen = 3;
206
  else if(purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
207
208
    routelen = 3;
  else if(purpose == CIRCUIT_PURPOSE_S_CONNECT_REND)
209
210
211
212
213
    routelen = 4;
  else {
    log_fn(LOG_WARN,"Unhandled purpose %d", purpose);
    return -1;
  }
214
215
#endif
#if 0
216
  for(routelen = 3; ; routelen++) { /* 3, increment until coinflip says we're done */
217
218
    if (crypto_pseudo_rand_int(255) >= cw*255) /* don't extend */
      break;
Roger Dingledine's avatar
Roger Dingledine committed
219
  }
220
#endif
221
222
  log_fn(LOG_DEBUG,"Chosen route length %d (%d routers available).",routelen,
         smartlist_len(routers));
Roger Dingledine's avatar
Roger Dingledine committed
223

224
  num_acceptable_routers = count_acceptable_routers(routers);
225

226
  if(num_acceptable_routers < 2) {
227
228
    log_fn(LOG_INFO,"Not enough acceptable routers (%d). Discarding this circuit.",
           num_acceptable_routers);
229
    return -1;
230
231
  }

232
  if(num_acceptable_routers < routelen) {
Roger Dingledine's avatar
Roger Dingledine committed
233
234
    log_fn(LOG_INFO,"Not enough routers: cutting routelen from %d to %d.",
           routelen, num_acceptable_routers);
235
    routelen = num_acceptable_routers;
Roger Dingledine's avatar
Roger Dingledine committed
236
  }
237

238
  return routelen;
239
240
}

241
242
243
244
245
246
247
248
/** Return a pointer to a suitable router to be the exit node for the
 * general-purpose circuit we're about to build.
 *
 * Look through the connection array, and choose a router that maximizes
 * the number of pending streams that can exit from this router.
 *
 * Return NULL if we can't find any suitable routers.
 */
249
static routerinfo_t *choose_good_exit_server_general(routerlist_t *dir)
250
251
252
253
254
255
256
{
  int *n_supported;
  int i, j;
  int n_pending_connections = 0;
  connection_t **carray;
  int n_connections;
  int best_support = -1;
257
  int n_best_support=0;
258
  smartlist_t *sl, *preferredexits, *excludedexits;
259
  routerinfo_t *router;
Roger Dingledine's avatar
Roger Dingledine committed
260

261
262
  get_connection_array(&carray, &n_connections);

263
264
265
  /* Count how many connections are waiting for a circuit to be built.
   * We use this for log messages now, but in the future we may depend on it.
   */
266
  for (i = 0; i < n_connections; ++i) {
267
268
    if (carray[i]->type == CONN_TYPE_AP &&
        carray[i]->state == AP_CONN_STATE_CIRCUIT_WAIT &&
269
270
        !carray[i]->marked_for_close &&
        !circuit_stream_is_being_handled(carray[i]))
271
272
273
274
      ++n_pending_connections;
  }
  log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
         n_pending_connections);
275
276
277
278
  /* Now we count, for each of the routers in the directory, how many
   * of the pending connections could possibly exit from that
   * router (n_supported[i]). (We can't be sure about cases where we
   * don't know the IP address of the pending connection.)
279
   */
280
281
282
  n_supported = tor_malloc(sizeof(int)*smartlist_len(dir->routers));
  for (i = 0; i < smartlist_len(dir->routers); ++i) { /* iterate over routers */
    router = smartlist_get(dir->routers, i);
283
284
285
286
287
288
289
290
    if(router_is_me(router)) {
      n_supported[i] = -1;
      log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
      /* XXX there's probably a reverse predecessor attack here, but
       * it's slow. should we take this out? -RD
       */
      continue;
    }
291
    if(!router->is_running) {
292
      n_supported[i] = -1;
293
      log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- directory says it's not running.",
294
             router->nickname, i);
295
296
      continue; /* skip routers that are known to be down */
    }
297
    if(router_exit_policy_rejects_all(router)) {
298
      n_supported[i] = -1;
299
      log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
300
             router->nickname, i);
301
      continue; /* skip routers that reject all */
302
    }
303
    n_supported[i] = 0;
304
    for (j = 0; j < n_connections; ++j) { /* iterate over connections */
305
      if (carray[j]->type != CONN_TYPE_AP ||
306
          carray[j]->state != AP_CONN_STATE_CIRCUIT_WAIT ||
307
308
          carray[j]->marked_for_close ||
          circuit_stream_is_being_handled(carray[j]))
309
        continue; /* Skip everything but APs in CIRCUIT_WAIT */
310
      switch (connection_ap_can_use_exit(carray[j], router))
311
        {
312
        case ADDR_POLICY_REJECTED:
313
          log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
314
                 router->nickname, i);
315
          break; /* would be rejected; try next connection */
316
317
        case ADDR_POLICY_ACCEPTED:
        case ADDR_POLICY_UNKNOWN:
318
          ++n_supported[i];
319
          log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
320
                 router->nickname, i, n_supported[i]);
321
        }
322
    } /* End looping over connections. */
Roger Dingledine's avatar
Roger Dingledine committed
323
    if (n_supported[i] > best_support) {
324
325
      /* If this router is better than previous ones, remember its index
       * and goodness, and start counting how many routers are this good. */
326
      best_support = n_supported[i]; n_best_support=1;
327
      log_fn(LOG_DEBUG,"%s is new best supported option so far.",
328
             router->nickname);
329
    } else if (n_supported[i] == best_support) {
330
331
      /* If this router is _as good_ as the best one, just increment the
       * count of equally good routers.*/
332
333
334
      ++n_best_support;
    }
  }
335
336
  log_fn(LOG_INFO, "Found %d servers that might support %d/%d pending connections.",
         n_best_support, best_support, n_pending_connections);
Roger Dingledine's avatar
Roger Dingledine committed
337

338
  preferredexits = smartlist_create();
Roger Dingledine's avatar
Roger Dingledine committed
339
340
  add_nickname_list_to_smartlist(preferredexits,options.ExitNodes);

341
  excludedexits = smartlist_create();
342
  add_nickname_list_to_smartlist(excludedexits,options.ExcludeNodes);
343

344
  sl = smartlist_create();
345

346
347
  /* If any routers definitely support any pending connections, choose one
   * at random. */
348
  if (best_support > 0) {
349
    for (i = 0; i < smartlist_len(dir->routers); i++)
Roger Dingledine's avatar
Roger Dingledine committed
350
      if (n_supported[i] == best_support)
351
        smartlist_add(sl, smartlist_get(dir->routers, i));
352

353
    smartlist_subtract(sl,excludedexits);
Roger Dingledine's avatar
Roger Dingledine committed
354
355
    if (smartlist_overlap(sl,preferredexits))
      smartlist_intersect(sl,preferredexits);
356
    router = smartlist_choose(sl);
357
358
359
  } else {
    /* Either there are no pending connections, or no routers even seem to
     * possibly support any of them.  Choose a router at random. */
360
    if (best_support == -1) {
361
362
      log(LOG_WARN, "All routers are down or middleman -- choosing a doomed exit at random.");
    }
363
    for(i = 0; i < smartlist_len(dir->routers); i++)
364
      if(n_supported[i] != -1)
365
        smartlist_add(sl, smartlist_get(dir->routers, i));
366

367
368
369
370
371
    smartlist_subtract(sl,excludedexits);
    if (smartlist_overlap(sl,preferredexits))
      smartlist_intersect(sl,preferredexits);
    router = smartlist_choose(sl);
  }
372

Roger Dingledine's avatar
Roger Dingledine committed
373
  smartlist_free(preferredexits);
374
  smartlist_free(excludedexits);
375
  smartlist_free(sl);
376
  tor_free(n_supported);
377
  if(router) {
378
    log_fn(LOG_INFO, "Chose exit server '%s'", router->nickname);
379
    return router;
380
  }
381
  log_fn(LOG_WARN, "No exit routers seem to be running; can't choose an exit.");
Nick Mathewson's avatar
Nick Mathewson committed
382
  return NULL;
383
384
}

385
386
387
388
389
390
391
392
393
394
/** Return a pointer to a suitable router to be the exit node for the
 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
 * if no router is suitable).
 *
 * For general-purpose circuits, pass it off to
 * choose_good_exit_server_general()
 *
 * For client-side rendezvous circuits, choose a random node, weighted
 * toward the preferences in 'options'.
 */
395
396
static routerinfo_t *choose_good_exit_server(uint8_t purpose, routerlist_t *dir)
{
397
398
399
400
401
  routerinfo_t *r;
  switch(purpose) {
    case CIRCUIT_PURPOSE_C_GENERAL:
      return choose_good_exit_server_general(dir);
    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
402
      r = router_choose_random_node(dir, options.RendNodes, options.RendExcludeNodes, NULL);
403
404
405
      return r;
    default:
      log_fn(LOG_WARN,"unhandled purpose %d", purpose);
Roger Dingledine's avatar
Roger Dingledine committed
406
      tor_assert(0);
407
  }
Roger Dingledine's avatar
Roger Dingledine committed
408
  return NULL; /* never reached */
409
410
}

411
412
413
414
/** Allocate a cpath_build_state_t, populate it based on
 * <b>purpose</b> and <b>exit_nickname</b> (if specified), and
 * return it.
 */
415
416
cpath_build_state_t *onion_new_cpath_build_state(uint8_t purpose,
                                                 const char *exit_nickname) {
417
  routerlist_t *rl;
418
419
  int r;
  cpath_build_state_t *info;
420
421
  routerinfo_t *exit;

422
  router_get_routerlist(&rl);
423
  r = new_route_len(options.PathlenCoinWeight, purpose, rl->routers);
Roger Dingledine's avatar
Roger Dingledine committed
424
  if (r < 0)
425
    return NULL;
426
  info = tor_malloc_zero(sizeof(cpath_build_state_t));
427
  info->desired_path_len = r;
428
429
430
431
  if(exit_nickname) { /* the circuit-builder pre-requested one */
    log_fn(LOG_INFO,"Using requested exit node '%s'", exit_nickname);
    info->chosen_exit = tor_strdup(exit_nickname);
  } else { /* we have to decide one */
432
    exit = choose_good_exit_server(purpose, rl);
433
    if(!exit) {
434
      log_fn(LOG_WARN,"failed to choose an exit server");
435
436
437
438
439
      tor_free(info);
      return NULL;
    }
    info->chosen_exit = tor_strdup(exit->nickname);
  }
440
  return info;
441
442
}

443
444
445
446
/** Return the number of routers in <b>routers</b> that are currently up
 * and available for building circuits through. Count sets of twins only
 * once.
 */
447
448
static int count_acceptable_routers(smartlist_t *routers) {
  int i, j, n;
449
  int num=0;
450
  connection_t *conn;
451
  routerinfo_t *r, *r2;
452

453
454
455
  n = smartlist_len(routers);
  for(i=0;i<n;i++) {
    r = smartlist_get(routers, i);
456
457
    log_fn(LOG_DEBUG,"Contemplating whether router %d (%s) is a new option...",
           i, r->nickname);
458
    if(r->is_running == 0) {
459
460
461
      log_fn(LOG_DEBUG,"Nope, the directory says %d is not running.",i);
      goto next_i_loop;
    }
462
    if(options.ORPort) {
463
      conn = connection_exact_get_by_addr_port(r->addr, r->or_port);
464
      if(!conn || conn->type != CONN_TYPE_OR || conn->state != OR_CONN_STATE_OPEN) {
465
        log_fn(LOG_DEBUG,"Nope, %d is not connected.",i);
466
467
        goto next_i_loop;
      }
468
469
    }
    for(j=0;j<i;j++) {
470
471
      r2 = smartlist_get(routers, j);
      if(!crypto_pk_cmp_keys(r->onion_pkey, r2->onion_pkey)) {
472
        /* these guys are twins. so we've already counted him. */
473
        log_fn(LOG_DEBUG,"Nope, %d is a twin of %d.",i,j);
474
475
476
477
        goto next_i_loop;
      }
    }
    num++;
478
    log_fn(LOG_DEBUG,"I like %d. num_acceptable_routers now %d.",i, num);
479
    next_i_loop:
480
      ; /* C requires an explicit statement after the label */
481
482
483
484
485
  }

  return num;
}

486
487
488
/** Go through smartlist <b>sl</b> of routers, and remove all elements that
 * have the same onion key as twin.
 */
489
490
491
492
493
494
495
static void remove_twins_from_smartlist(smartlist_t *sl, routerinfo_t *twin) {
  int i;
  routerinfo_t *r;

  if(twin == NULL)
    return;

Nick Mathewson's avatar
Nick Mathewson committed
496
497
  for(i=0; i < smartlist_len(sl); i++) {
    r = smartlist_get(sl,i);
498
    if (!crypto_pk_cmp_keys(r->onion_pkey, twin->onion_pkey)) {
Nick Mathewson's avatar
Nick Mathewson committed
499
      smartlist_del(sl,i--);
500
501
502
503
    }
  }
}

504
505
506
507
/** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
 *
 * This function is used to extend cpath by another hop.
 */
508
509
510
511
512
513
514
515
516
517
518
519
520
void onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
{
  if (*head_ptr) {
    new_hop->next = (*head_ptr);
    new_hop->prev = (*head_ptr)->prev;
    (*head_ptr)->prev->next = new_hop;
    (*head_ptr)->prev = new_hop;
  } else {
    *head_ptr = new_hop;
    new_hop->prev = new_hop->next = new_hop;
  }
}

521
522
523
524
525
526
/** Choose a suitable next hop in the cpath <b>head_ptr</b>,
 * based on <b>state</b>. Add the hop info to head_ptr, and return a
 * pointer to the chosen router in <b>router_out</b>.
 */
int onion_extend_cpath(crypt_path_t **head_ptr, cpath_build_state_t
                       *state, routerinfo_t **router_out)
527
528
529
{
  int cur_len;
  crypt_path_t *cpath, *hop;
530
  routerinfo_t *r;
531
  routerinfo_t *choice;
532
  int i;
533
  smartlist_t *sl, *excludednodes;
534

Roger Dingledine's avatar
Roger Dingledine committed
535
536
  tor_assert(head_ptr);
  tor_assert(router_out);
537

538
539
540
541
542
543
544
  if (!*head_ptr) {
    cur_len = 0;
  } else {
    cur_len = 1;
    for (cpath = *head_ptr; cpath->next != *head_ptr; cpath = cpath->next) {
      ++cur_len;
    }
545
  }
Roger Dingledine's avatar
Roger Dingledine committed
546
547
  if (cur_len >= state->desired_path_len) {
    log_fn(LOG_DEBUG, "Path is complete: %d steps long",
548
           state->desired_path_len);
Roger Dingledine's avatar
Roger Dingledine committed
549
    return 1;
550
  }
551
  log_fn(LOG_DEBUG, "Path is %d long; we want %d", cur_len,
552
         state->desired_path_len);
553

554
  excludednodes = smartlist_create();
555
  add_nickname_list_to_smartlist(excludednodes,options.ExcludeNodes);
556

557
  if(cur_len == state->desired_path_len - 1) { /* Picking last node */
558
559
    log_fn(LOG_DEBUG, "Contemplating last hop: choice already made: %s",
           state->chosen_exit);
560
    choice = router_get_by_nickname(state->chosen_exit);
561
    smartlist_free(excludednodes);
562
    if(!choice) {
563
      log_fn(LOG_WARN,"Our chosen exit %s is no longer in the directory? Discarding this circuit.",
564
565
566
             state->chosen_exit);
      return -1;
    }
567
568
  } else if(cur_len == 0) { /* picking first node */
    /* try the nodes in EntryNodes first */
569
    sl = smartlist_create();
570
    add_nickname_list_to_smartlist(sl,options.EntryNodes);
571
    /* XXX one day, consider picking chosen_exit knowing what's in EntryNodes */
572
    remove_twins_from_smartlist(sl,router_get_by_nickname(state->chosen_exit));
573
    remove_twins_from_smartlist(sl,router_get_my_routerinfo());
574
    smartlist_subtract(sl,excludednodes);
575
576
577
    choice = smartlist_choose(sl);
    smartlist_free(sl);
    if(!choice) {
578
      sl = smartlist_create();
579
580
      router_add_running_routers_to_smartlist(sl);
      remove_twins_from_smartlist(sl,router_get_by_nickname(state->chosen_exit));
581
      remove_twins_from_smartlist(sl,router_get_my_routerinfo());
582
      smartlist_subtract(sl,excludednodes);
583
584
585
      choice = smartlist_choose(sl);
      smartlist_free(sl);
    }
586
    smartlist_free(excludednodes);
587
    if(!choice) {
588
      log_fn(LOG_WARN,"No acceptable routers while picking entry node. Discarding this circuit.");
589
590
      return -1;
    }
591
592
  } else {
    log_fn(LOG_DEBUG, "Contemplating intermediate hop: random choice.");
593
    sl = smartlist_create();
594
595
    router_add_running_routers_to_smartlist(sl);
    remove_twins_from_smartlist(sl,router_get_by_nickname(state->chosen_exit));
596
    remove_twins_from_smartlist(sl,router_get_my_routerinfo());
597
598
    for (i = 0, cpath = *head_ptr; i < cur_len; ++i, cpath=cpath->next) {
      r = router_get_by_addr_port(cpath->addr, cpath->port);
Roger Dingledine's avatar
Roger Dingledine committed
599
      tor_assert(r);
600
601
      remove_twins_from_smartlist(sl,r);
    }
602
    smartlist_subtract(sl,excludednodes);
603
604
    choice = smartlist_choose(sl);
    smartlist_free(sl);
605
    smartlist_free(excludednodes);
606
    if(!choice) {
607
      log_fn(LOG_WARN,"No acceptable routers while picking intermediate node. Discarding this circuit.");
608
609
      return -1;
    }
610
  }
Roger Dingledine's avatar
Roger Dingledine committed
611

612
613
  log_fn(LOG_DEBUG,"Chose router %s for hop %d (exit is %s)",
         choice->nickname, cur_len, state->chosen_exit);
Roger Dingledine's avatar
Roger Dingledine committed
614

615
  hop = tor_malloc_zero(sizeof(crypt_path_t));
616
617

  /* link hop into the cpath, at the end. */
618
  onion_append_to_cpath(head_ptr, hop);
619

620
  hop->state = CPATH_STATE_CLOSED;
Roger Dingledine's avatar
Roger Dingledine committed
621

622
623
  hop->port = choice->or_port;
  hop->addr = choice->addr;
Roger Dingledine's avatar
Roger Dingledine committed
624

625
626
  hop->package_window = CIRCWINDOW_START;
  hop->deliver_window = CIRCWINDOW_START;
627

Roger Dingledine's avatar
Roger Dingledine committed
628
  log_fn(LOG_DEBUG, "Extended circuit path with %s for hop %d",
629
         choice->nickname, cur_len);
Roger Dingledine's avatar
Roger Dingledine committed
630

631
  *router_out = choice;
632
  return 0;
633
634
}

635
636
/*----------------------------------------------------------------------*/

637
638
639
640
641
642
643
/** Given a router's 128 byte public key,
 * stores the following in onion_skin_out:
 *   - [42 bytes] OAEP padding
 *   - [16 bytes] Symmetric key for encrypting blob past RSA
 *   - [70 bytes] g^x part 1 (inside the RSA)
 *   - [58 bytes] g^x part 2 (symmetrically encrypted)
 *
644
645
 * Stores the DH private key into handshake_state_out for later completion
 * of the handshake.
646
 *
647
 * The meeting point/cookies and auth are zeroed out for now.
648
649
 */
int
650
onion_skin_create(crypto_pk_env_t *dest_router_key,
651
                  crypto_dh_env_t **handshake_state_out,
652
                  char *onion_skin_out) /* Must be ONIONSKIN_CHALLENGE_LEN bytes */
653
{
654
  char *challenge = NULL;
655
656
657
658
  crypto_dh_env_t *dh = NULL;
  int dhbytes, pkbytes;

  *handshake_state_out = NULL;
659
  memset(onion_skin_out, 0, ONIONSKIN_CHALLENGE_LEN);
660
661
662

  if (!(dh = crypto_dh_new()))
    goto err;
663

664
  dhbytes = crypto_dh_get_bytes(dh);
665
  pkbytes = crypto_pk_keysize(dest_router_key);
Roger Dingledine's avatar
Roger Dingledine committed
666
667
  tor_assert(dhbytes == 128);
  tor_assert(pkbytes == 128);
668
  challenge = tor_malloc_zero(DH_KEY_LEN);
669

670
  if (crypto_dh_get_public(dh, challenge, dhbytes))
671
672
    goto err;

673
674
675
676
677
#ifdef DEBUG_ONION_SKINS
#define PA(a,n) \
  { int _i; for (_i = 0; _i<n; ++_i) printf("%02x ",((int)(a)[_i])&0xFF); }

  printf("Client: client g^x:");
678
  PA(challenge+16,3);
679
  printf("...");
680
  PA(challenge+141,3);
681
682
683
  puts("");

  printf("Client: client symkey:");
684
  PA(challenge+0,16);
685
  puts("");
686
687
#endif

688
  /* set meeting point, meeting cookie, etc here. Leave zero for now. */
689
  if (crypto_pk_public_hybrid_encrypt(dest_router_key, challenge,
690
691
                                      DH_KEY_LEN,
                                  onion_skin_out, PK_PKCS1_OAEP_PADDING, 1)<0)
692
    goto err;
Roger Dingledine's avatar
Roger Dingledine committed
693

694
  tor_free(challenge);
695
  *handshake_state_out = dh;
696

697
698
  return 0;
 err:
699
  tor_free(challenge);
700
701
702
703
  if (dh) crypto_dh_free(dh);
  return -1;
}

704
/** Given an encrypted DH public key as generated by onion_skin_create,
705
706
707
 * and the private key for this onion router, generate the reply (128-byte
 * DH plus the first 20 bytes of shared key material), and store the
 * next key_out_len bytes of key material in key_out.
708
709
 */
int
710
onion_skin_server_handshake(char *onion_skin, /* ONIONSKIN_CHALLENGE_LEN bytes */
711
                            crypto_pk_env_t *private_key,
712
                            crypto_pk_env_t *prev_private_key,
713
                            char *handshake_reply_out, /* ONIONSKIN_REPLY_LEN bytes */
714
715
716
                            char *key_out,
                            int key_out_len)
{
717
  char challenge[ONIONSKIN_CHALLENGE_LEN];
718
  crypto_dh_env_t *dh = NULL;
719
  int len;
720
  char *key_material=NULL;
721
722
  int i;
  crypto_pk_env_t *k;
Roger Dingledine's avatar
Roger Dingledine committed
723

724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
  len = -1;
  for (i=0;i<2;++i) {
    k = i==0?private_key:prev_private_key;
    if (!k)
      break;
    len = crypto_pk_private_hybrid_decrypt(k,
                                           onion_skin, ONIONSKIN_CHALLENGE_LEN,
                                           challenge, PK_PKCS1_OAEP_PADDING);
    if (len>0)
      break;
  }
  if (len<0) {
    log_fn(LOG_WARN, "Couldn't decrypt onionskin");
    goto err;
  } else if (len != DH_KEY_LEN) {
    log_fn(LOG_WARN, "Unexpected onionskin length after decryption: %d",
           len);
741
    goto err;
742
  }
Roger Dingledine's avatar
Roger Dingledine committed
743

744
  dh = crypto_dh_new();
745
  if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN))
746
747
    goto err;

748
749
750
751
752
753
754
755
#ifdef DEBUG_ONION_SKINS
  printf("Server: server g^y:");
  PA(handshake_reply_out+0,3);
  printf("...");
  PA(handshake_reply_out+125,3);
  puts("");
#endif

756
757
758
  key_material = tor_malloc(DIGEST_LEN+key_out_len);
  len = crypto_dh_compute_secret(dh, challenge, DH_KEY_LEN,
                                 key_material, DIGEST_LEN+key_out_len);
759
  if (len < 0)
760
761
    goto err;

762
  /* send back H(K|0) as proof that we learned K. */
763
  memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
764
765

  /* use the rest of the key material for our shared keys, digests, etc */
766
  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
767

768
#ifdef DEBUG_ONION_SKINS
769
770
771
  printf("Server: key material:");
  PA(buf, DH_KEY_LEN);
  puts("");
772
773
774
775
776
  printf("Server: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

777
  tor_free(key_material);
778
779
780
  crypto_dh_free(dh);
  return 0;
 err:
781
  tor_free(key_material);
782
783
784
785
786
  if (dh) crypto_dh_free(dh);

  return -1;
}

787
/** Finish the client side of the DH handshake.
788
789
790
791
792
 * Given the 128 byte DH reply + 20 byte hash as generated by
 * onion_skin_server_handshake and the handshake state generated by
 * onion_skin_create, verify H(K) with the first 20 bytes of shared
 * key material, then generate key_out_len more bytes of shared key
 * material and store them in key_out.
793
794
795
796
797
 *
 * After the invocation, call crypto_dh_free on handshake_state.
 */
int
onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
798
                            char *handshake_reply, /* Must be ONIONSKIN_REPLY_LEN bytes */
799
                            char *key_out,
800
                            int key_out_len)
801
{
802
  int len;
803
  char *key_material=NULL;
Roger Dingledine's avatar
Roger Dingledine committed
804
  tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
Roger Dingledine's avatar
Roger Dingledine committed
805

806
807
808
809
810
811
812
813
#ifdef DEBUG_ONION_SKINS
  printf("Client: server g^y:");
  PA(handshake_reply+0,3);
  printf("...");
  PA(handshake_reply+125,3);
  puts("");
#endif

814
  key_material = tor_malloc(20+key_out_len);
815
  len = crypto_dh_compute_secret(handshake_state, handshake_reply, DH_KEY_LEN,
816
                                 key_material, 20+key_out_len);
817
  if (len < 0)
818
    return -1;
Roger Dingledine's avatar
Roger Dingledine committed
819

820
821
822
823
824
825
826
827
828
829
  if(memcmp(key_material, handshake_reply+DH_KEY_LEN, 20)) {
    /* H(K) does *not* match. Something fishy. */
    tor_free(key_material);
    log_fn(LOG_WARN,"Digest DOES NOT MATCH on onion handshake. Bug or attack.");
    return -1;
  }

  /* use the rest of the key material for our shared keys, digests, etc */
  memcpy(key_out, key_material+20, key_out_len);

830
831
832
833
834
835
#ifdef DEBUG_ONION_SKINS
  printf("Client: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

836
  tor_free(key_material);
837
838
839
  return 0;
}

840
841
842
843
844
845
846
/*
  Local Variables:
  mode:c
  indent-tabs-mode:nil
  c-basic-offset:2
  End:
*/