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

#include "or.h"

7
extern or_options_t options; /* command-line and config-file options */
8

9
static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len);
Roger Dingledine's avatar
Roger Dingledine committed
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int decide_aci_type(uint32_t local_addr, uint16_t local_port,
                    uint32_t remote_addr, uint16_t remote_port) {

  if(local_addr > remote_addr)
    return ACI_TYPE_HIGHER;
  if(local_addr < remote_addr)
    return ACI_TYPE_LOWER;
  if(local_port > remote_port)
    return ACI_TYPE_HIGHER;
   /* else */
   return ACI_TYPE_LOWER; 
}

24
25
26
27
28
29
30
31
/* global (within this file) variables used by the next few functions */
static struct onion_queue_t *ol_list=NULL;
static struct onion_queue_t *ol_tail=NULL;
static int ol_length=0;

int onion_pending_add(circuit_t *circ) {
  struct onion_queue_t *tmp;

32
  tmp = tor_malloc(sizeof(struct onion_queue_t));
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
  memset(tmp, 0, sizeof(struct onion_queue_t));
  tmp->circ = circ;

  if(!ol_tail) {
    assert(!ol_list);
    assert(!ol_length);
    ol_list = tmp;
    ol_tail = tmp;
    ol_length++;
    return 0;
  }

  assert(ol_list);
  assert(!ol_tail->next);

  if(ol_length >= options.MaxOnionsPending) {
Roger Dingledine's avatar
Roger Dingledine committed
49
    log_fn(LOG_INFO,"Already have %d onions queued. Closing.", ol_length);
50
51
52
53
54
55
56
57
58
59
60
    free(tmp);
    return -1;
  }

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

}

Roger Dingledine's avatar
Roger Dingledine committed
61
circuit_t *onion_next_task(void) {
62
  circuit_t *circ;
63
64

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

67
  assert(ol_list->circ);
68
  if(!ol_list->circ->p_conn) {
Roger Dingledine's avatar
Roger Dingledine committed
69
    log_fn(LOG_INFO,"ol_list->circ->p_conn null, must have died?");
70
    onion_pending_remove(ol_list->circ);
Roger Dingledine's avatar
Roger Dingledine committed
71
    return onion_next_task(); /* recurse: how about the next one? */
72
73
  }

74
  assert(ol_length > 0);
75
76
77
  circ = ol_list->circ;
  onion_pending_remove(ol_list->circ);
  return circ;
78
79
}

80
81
/* go through ol_list, find the onion_queue_t element which points to
 * circ, remove and free that element. leave circ itself alone.
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 */
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) {
101
      log_fn(LOG_DEBUG,"circ (p_aci %d) not in list, probably at cpuworker.",circ->p_aci);
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
      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 */

  free(victim); 
}

Roger Dingledine's avatar
Roger Dingledine committed
117
/* given a response payload and keys, initialize, then send a created cell back */
118
int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *keys) {
119
  unsigned char iv[16];
120
121
  cell_t cell;

122
  memset(iv, 0, 16);
123

124
125
126
  memset(&cell, 0, sizeof(cell_t));
  cell.command = CELL_CREATED;
  cell.aci = circ->p_aci;
127
  cell.length = DH_KEY_LEN;
128
129

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

Roger Dingledine's avatar
Roger Dingledine committed
131
  log_fn(LOG_DEBUG,"Entering.");
132

Roger Dingledine's avatar
Roger Dingledine committed
133
  memcpy(cell.payload, payload, DH_KEY_LEN);
Roger Dingledine's avatar
Roger Dingledine committed
134

Roger Dingledine's avatar
Roger Dingledine committed
135
  log_fn(LOG_DEBUG,"init cipher forward %d, backward %d.", *(int*)keys, *(int*)(keys+16));
136
137

  if (!(circ->n_crypto =
Nick Mathewson's avatar
src/or    
Nick Mathewson committed
138
        crypto_create_init_cipher(CIRCUIT_CIPHER,keys,iv,0))) {
Roger Dingledine's avatar
Roger Dingledine committed
139
    log_fn(LOG_ERR,"Cipher initialization failed (n).");
Roger Dingledine's avatar
Roger Dingledine committed
140
141
142
    return -1;
  }

143
  if (!(circ->p_crypto =
Nick Mathewson's avatar
src/or    
Nick Mathewson committed
144
        crypto_create_init_cipher(CIRCUIT_CIPHER,keys+16,iv,1))) {
Roger Dingledine's avatar
Roger Dingledine committed
145
    log_fn(LOG_ERR,"Cipher initialization failed (p).");
Roger Dingledine's avatar
Roger Dingledine committed
146
147
148
    return -1;
  }

149
  if(connection_write_cell_to_buf(&cell, circ->p_conn) < 0) {
Roger Dingledine's avatar
Roger Dingledine committed
150
151
    return -1;
  }
Roger Dingledine's avatar
Roger Dingledine committed
152
  log_fn(LOG_DEBUG,"Finished sending 'created' cell.");
Roger Dingledine's avatar
Roger Dingledine committed
153
154
155
156

  return 0;
}

157
/* uses a weighted coin with weight cw to choose a route length */
Roger Dingledine's avatar
Roger Dingledine committed
158
static int chooselen(double cw) {
159
  int len = 2;
160
  uint8_t coin;
161
162
163
164
165
166
  
  if ((cw < 0) || (cw >= 1)) /* invalid parameter */
    return -1;
  
  while(1)
  {
167
    if (CRYPTO_PSEUDO_RAND_INT(coin))
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
      return -1;
    
    if (coin > cw*255) /* don't extend */
      break;
    else
      len++;
  }
  
  return len;
}

/* returns an array of pointers to routent that define a new route through the OR network
 * int cw is the coin weight to use when choosing the route 
 * order of routers is from last to first
 */
Roger Dingledine's avatar
Roger Dingledine committed
183
static unsigned int *new_route(double cw, routerinfo_t **rarray, int rarray_len, int *routelen) {
184
  int i;
185
  int num_acceptable_routers;
186
  unsigned int *route;
187
  unsigned int oldchoice, choice;
188

189
  assert((cw >= 0) && (cw < 1) && (rarray) && (routelen) ); /* valid parameters */
190

191
192
  *routelen = chooselen(cw);
  if (*routelen == -1) {
Roger Dingledine's avatar
Roger Dingledine committed
193
194
195
    log(LOG_ERR,"Choosing route length failed.");
    return NULL;
  }
196
  log(LOG_DEBUG,"new_route(): Chosen route length %d.",*routelen);
Roger Dingledine's avatar
Roger Dingledine committed
197

198
199
  num_acceptable_routers = count_acceptable_routers(rarray, rarray_len);

200
201
202
203
204
  if(num_acceptable_routers < 2) {
    log(LOG_INFO,"new_route(): Not enough acceptable routers. Failing.");
    return NULL;
  }

205
  if(num_acceptable_routers < *routelen) {
206
    log(LOG_NOTICE,"new_route(): Cutting routelen from %d to %d.",*routelen, num_acceptable_routers);
207
    *routelen = num_acceptable_routers;
Roger Dingledine's avatar
Roger Dingledine committed
208
  }
209

210
  if(*routelen < 1) {
Roger Dingledine's avatar
Roger Dingledine committed
211
212
213
214
215
    log(LOG_ERR,"new_route(): Didn't find any acceptable routers. Failing.");
    return NULL;
  }

  /* allocate memory for the new route */
216
  route = (unsigned int *)tor_malloc(*routelen * sizeof(unsigned int));
Roger Dingledine's avatar
Roger Dingledine committed
217
218
 
  oldchoice = rarray_len;
219
  for(i=0;i<*routelen;i++) {
Roger Dingledine's avatar
Roger Dingledine committed
220
    log(LOG_DEBUG,"new_route(): Choosing hop %u.",i);
221
    if (CRYPTO_PSEUDO_RAND_INT(choice)) {
Roger Dingledine's avatar
Roger Dingledine committed
222
      free((void *)route);
223
224
225
      return NULL;
    }

226
    choice = choice % rarray_len;
Roger Dingledine's avatar
Roger Dingledine committed
227
    log(LOG_DEBUG,"new_route(): Contemplating router %u.",choice);
228
    if(choice == oldchoice ||
229
      (oldchoice < rarray_len && !crypto_pk_cmp_keys(rarray[choice]->pkey, rarray[oldchoice]->pkey)) ||
230
      (options.OnionRouter && !connection_twin_get_by_addr_port(rarray[choice]->addr, rarray[choice]->or_port))) {
Roger Dingledine's avatar
Roger Dingledine committed
231
232
233
234
      /* Same router as last choice, or router twin,
       *   or no routers with that key are connected to us.
       * Try again. */
      log(LOG_DEBUG,"new_route(): Picked a router %d that won't work as next hop.",choice);
235
236
      i--;
      continue;  
237
    }
Roger Dingledine's avatar
Roger Dingledine committed
238
239
240
241
    log(LOG_DEBUG,"new_route(): Chosen router %u for hop %u.",choice,i);
    oldchoice = choice;
    route[i] = choice;
  }
242
   
Roger Dingledine's avatar
Roger Dingledine committed
243
  return route;
244
245
}

246
247
248
static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len) {
  int i, j;
  int num=0;
249
  connection_t *conn;
250
251
252

  for(i=0;i<rarray_len;i++) {
    log(LOG_DEBUG,"Contemplating whether router %d is a new option...",i);
253
    if(options.OnionRouter) {
254
255
256
257
258
      conn = connection_exact_get_by_addr_port(rarray[i]->addr, rarray[i]->or_port);
      if(!conn || conn->type != CONN_TYPE_OR || conn->state != OR_CONN_STATE_OPEN) {
        log(LOG_DEBUG,"Nope, %d is not connected.",i);
        goto next_i_loop;
      }
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
    }
    for(j=0;j<i;j++) {
      if(!crypto_pk_cmp_keys(rarray[i]->pkey, rarray[j]->pkey)) {
        /* these guys are twins. so we've already counted him. */
        log(LOG_DEBUG,"Nope, %d is a twin of %d.",i,j);
        goto next_i_loop;
      }
    }
    num++;
    log(LOG_DEBUG,"I like %d. num_acceptable_routers now %d.",i, num);
    next_i_loop:
      ; /* our compiler may need an explicit statement after the label */
  }

  return num;
}

276
277
278
279
crypt_path_t *onion_generate_cpath(routerinfo_t **firsthop) {
  int routelen; /* length of the route */
  unsigned int *route; /* hops in the route as an array of indexes into rarray */
  crypt_path_t *cpath=NULL;
280
  directory_t *dir;
281
282
  routerinfo_t **rarray;
  int rarray_len;
283
284
  int i;
  crypt_path_t *hop;
285
  routerinfo_t *router;
286
  struct in_addr netaddr;
287

288
289
290
  router_get_directory(&dir);
  rarray = dir->routers;
  rarray_len = dir->n_routers;
291

292
293
294
295
  /* choose a route */
  route = new_route(options.CoinWeight, rarray, rarray_len, &routelen);
  if (!route) {
    log(LOG_ERR,"onion_generate_cpath(): Error choosing a route through the OR network.");
296
297
    return NULL;
  }
298
299
300
301
  log(LOG_DEBUG,"onion_generate_cpath(): Chosen a route of length %u: ",routelen);

  *firsthop = rarray[route[routelen-1]];
  assert(*firsthop); /* should always be defined */
302

303
  for(i=0; i<routelen; i++) {
304
305
    netaddr.s_addr = htonl((rarray[route[i]])->addr);

306
    log(LOG_DEBUG,"onion_generate_cpath(): %u : %s:%u, %u/%u",routelen-i,
307
308
        inet_ntoa(netaddr),
        (rarray[route[i]])->or_port,
309
        (int) (rarray[route[i]])->pkey,
310
311
        crypto_pk_keysize((rarray[route[i]])->pkey));
  }
312

313
  /* create the cpath layer by layer, starting at the last hop */
314
315
  for (i=0;i<routelen;i++) {
    router = rarray[route[i]];
316

317
    /* build up the crypt_path */
318
    hop = (crypt_path_t *)tor_malloc(sizeof(crypt_path_t));
319
    memset(hop, 0, sizeof(crypt_path_t));
320

321
    /* link hop into the cpath, at the front */
322
    hop->next = cpath;
323
    hop->prev = NULL;
324
325
326
    hop->state = CPATH_STATE_CLOSED;
    if(cpath) {
      cpath->prev = hop;
327
    }
328
    cpath = hop;
329

330
331
    hop->port = rarray[route[i]]->or_port;
    hop->addr = rarray[route[i]]->addr;
332

333
334
335
    hop->package_window = CIRCWINDOW_START;
    hop->deliver_window = CIRCWINDOW_START;

336
    log(LOG_DEBUG,"onion_generate_cpath() : Building hop %u of crypt path.",i+1);
337
  }
338

339
  /* now link cpath->prev to the end of cpath */
340
341
342
  for(hop=cpath; hop->next; hop=hop->next) ;
  hop->next = cpath;
  cpath->prev = hop;
343

344
345
  free(route);
  return cpath;
346
347
}

348
349
/*----------------------------------------------------------------------*/

350
/* Given a router's public key, generates a 144-byte encrypted DH pubkey,
351
352
353
354
355
 * and stores it into onion_skin out.  Stores the DH private key into 
 * handshake_state_out for later completion of the handshake.
 *
 * The encrypted pubkey is formed as follows:
 *    16 bytes of symmetric key
356
 *   128 bytes of g^x for DH.
357
 * The first 128 bytes are RSA-encrypted with the server's public key,
358
 * and the last 16 are encrypted with the symmetric key.
359
360
 */
int
361
onion_skin_create(crypto_pk_env_t *dest_router_key,
362
                  crypto_dh_env_t **handshake_state_out,
363
                  char *onion_skin_out) /* Must be DH_ONIONSKIN_LEN bytes long */
364
365
366
367
368
369
370
371
{
  char iv[16];
  char *pubkey = NULL;
  crypto_dh_env_t *dh = NULL;
  crypto_cipher_env_t *cipher = NULL;
  int dhbytes, pkbytes;

  *handshake_state_out = NULL;
372
  memset(onion_skin_out, 0, DH_ONIONSKIN_LEN);
373
  memset(iv, 0, 16);
374
375
376
377
378

  if (!(dh = crypto_dh_new()))
    goto err;
  
  dhbytes = crypto_dh_get_bytes(dh);
379
  pkbytes = crypto_pk_keysize(dest_router_key);
380
  assert(dhbytes+16 == DH_ONIONSKIN_LEN);
381
  pubkey = (char *)tor_malloc(dhbytes+16);
382
383
384

  if (crypto_rand(16, pubkey))
    goto err;
385
386
387
388
389
390
391
392
393
  
  /* XXXX You can't just run around RSA-encrypting any bitstream: if it's
   *      greater than the RSA key, then OpenSSL will happily encrypt,
   *      and later decrypt to the wrong value.  So we set the first bit
   *      of 'pubkey' to 0.  This means that our symmetric key is really only
   *      127 bits long, but since it shouldn't be necessary to encrypt
   *      DH public keys values in the first place, we should be fine.
   */
  pubkey[0] &= 0x7f; 
394
395
396
397

  if (crypto_dh_get_public(dh, pubkey+16, dhbytes))
    goto err;

398
399
400
401
402
403
404
405
406
407
408
409
410
#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:");
  PA(pubkey+16,3);
  printf("...");
  PA(pubkey+141,3);
  puts("");

  printf("Client: client symkey:");
  PA(pubkey+0,16);
  puts("");
411
412
#endif

Nick Mathewson's avatar
src/or    
Nick Mathewson committed
413
  cipher = crypto_create_init_cipher(ONION_CIPHER, pubkey, iv, 1);
414
415
416
417

  if (!cipher)
    goto err;

418
  if (crypto_pk_public_encrypt(dest_router_key, pubkey, pkbytes,
419
                               onion_skin_out, RSA_NO_PADDING)==-1)
420
421
    goto err;

422
  if (crypto_cipher_encrypt(cipher, pubkey+pkbytes, dhbytes+16-pkbytes,
423
424
425
426
427
428
                            onion_skin_out+pkbytes))
    goto err;

  free(pubkey);
  crypto_free_cipher_env(cipher);
  *handshake_state_out = dh;
429

430
431
432
433
434
435
436
437
438
  return 0;
 err:
  if (pubkey) free(pubkey);
  if (dh) crypto_dh_free(dh);
  if (cipher) crypto_free_cipher_env(cipher);
  return -1;
}

/* Given an encrypted DH public key as generated by onion_skin_create,
439
 * and the private key for this onion router, generate the 128-byte DH
440
441
442
 * reply, and key_out_len bytes of key material, stored in key_out.
 */
int
443
onion_skin_server_handshake(char *onion_skin, /* DH_ONIONSKIN_LEN bytes long */
444
                            crypto_pk_env_t *private_key,
445
                            char *handshake_reply_out, /* DH_KEY_LEN bytes long */
446
447
448
                            char *key_out,
                            int key_out_len)
{
449
  char buf[DH_ONIONSKIN_LEN];
450
451
452
453
  char iv[16];
  crypto_dh_env_t *dh = NULL;
  crypto_cipher_env_t *cipher = NULL;
  int pkbytes;
454
  int len;
455
456
457
458
459
460
  
  memset(iv, 0, 16);
  pkbytes = crypto_pk_keysize(private_key);

  if (crypto_pk_private_decrypt(private_key,
                                onion_skin, pkbytes,
461
                                buf, RSA_NO_PADDING) == -1)
462
    goto err;
463
  
464
465
466
467
#ifdef DEBUG_ONION_SKINS
  printf("Server: client symkey:");
  PA(buf+0,16);
  puts("");
468
#endif
469

Nick Mathewson's avatar
src/or    
Nick Mathewson committed
470
  cipher = crypto_create_init_cipher(ONION_CIPHER, buf, iv, 0);
471

472
  if (crypto_cipher_decrypt(cipher, onion_skin+pkbytes, DH_ONIONSKIN_LEN-pkbytes,
473
474
                            buf+pkbytes))
    goto err;
475

476
477
478
479
480
481
#ifdef DEBUG_ONION_SKINS
  printf("Server: client g^x:");
  PA(buf+16,3);
  printf("...");
  PA(buf+141,3);
  puts("");
482
#endif
483
484
  
  dh = crypto_dh_new();
485
  if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN))
486
487
    goto err;

488
489
490
491
492
493
494
495
#ifdef DEBUG_ONION_SKINS
  printf("Server: server g^y:");
  PA(handshake_reply_out+0,3);
  printf("...");
  PA(handshake_reply_out+125,3);
  puts("");
#endif

Nick Mathewson's avatar
src/or    
Nick Mathewson committed
496
  len = crypto_dh_compute_secret(dh, buf+16, DH_KEY_LEN, key_out, key_out_len);
497
  if (len < 0)
498
499
    goto err;

500
#ifdef DEBUG_ONION_SKINS
501
502
503
  printf("Server: key material:");
  PA(buf, DH_KEY_LEN);
  puts("");
504
505
506
507
508
  printf("Server: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

509
510
511
512
513
514
515
516
517
518
519
  crypto_free_cipher_env(cipher);
  crypto_dh_free(dh);
  return 0;
 err:
  if (cipher) crypto_free_cipher_env(cipher);
  if (dh) crypto_dh_free(dh);

  return -1;
}

/* Finish the client side of the DH handshake.
520
 * Given the 128 byte DH reply as generated by onion_skin_server_handshake
521
522
523
524
525
526
527
 * and the handshake state generated by onion_skin_create, generate
 * key_out_len bytes of shared key material and store them in key_out.
 *
 * After the invocation, call crypto_dh_free on handshake_state.
 */
int
onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
528
                            char *handshake_reply,/* Must be DH_KEY_LEN bytes long*/
529
530
531
                            char *key_out,
                            int key_out_len) 
{
532
  int len;
533
  assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
534
  
535
536
537
538
539
540
541
542
#ifdef DEBUG_ONION_SKINS
  printf("Client: server g^y:");
  PA(handshake_reply+0,3);
  printf("...");
  PA(handshake_reply+125,3);
  puts("");
#endif

543
  len = crypto_dh_compute_secret(handshake_state, handshake_reply, DH_KEY_LEN,
Nick Mathewson's avatar
src/or    
Nick Mathewson committed
544
                                 key_out, key_out_len);
545
  if (len < 0)
546
547
    return -1;
  
548
549
550
551
552
553
#ifdef DEBUG_ONION_SKINS
  printf("Client: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

554
555
556
  return 0;
}

557
558
559
560
561
562
563
/*
  Local Variables:
  mode:c
  indent-tabs-mode:nil
  c-basic-offset:2
  End:
*/