onion.c 15.7 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);
10
static int onionskin_process(circuit_t *circ);
Roger Dingledine's avatar
Roger Dingledine committed
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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; 
}

25
26
27
28
29
30
31
32
/* 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;

33
  tmp = tor_malloc(sizeof(struct onion_queue_t));
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  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) {
    log(LOG_INFO,"onion_pending_add(): Already have %d onions queued. Closing.", ol_length);
    free(tmp);
    return -1;
  }

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

}

int onion_pending_check(void) {
  if(ol_list)
    return 1;
  else
    return 0;
}

void onion_pending_process_one(void) {
70
  circuit_t *circ; 
71
72
73
74

  if(!ol_list)
    return; /* no onions pending, we're done */

75
  assert(ol_list->circ);
76
77
78
79
80
81
  if(!ol_list->circ->p_conn) {
    log(LOG_INFO,"onion_pending_process_one(): ol_list->circ->p_conn null, must have died?");
    onion_pending_remove(ol_list->circ);
    return; /* it died on us */
  }

82
  assert(ol_length > 0);
83
  circ = ol_list->circ;
84

85
  if(onionskin_process(circ) < 0) {
86
    log(LOG_DEBUG,"onion_pending_process_one(): Failed. Closing.");
87
88
    onion_pending_remove(circ);
    circuit_close(circ);
89
  } else {
90
    log(LOG_DEBUG,"onion_pending_process_one(): Succeeded.");
91
    onion_pending_remove(circ);
92
93
94
95
  }
  return;
}

96
97
/* go through ol_list, find the onion_queue_t element which points to
 * circ, remove and free that element. leave circ itself alone.
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 */
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) {
      log(LOG_WARNING,"onion_pending_remove(): circ (p_aci %d), not in list!",circ->p_aci);
      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); 
}

133
134
135
136
/* learn keys, initialize, then send a created cell back */
static int onionskin_process(circuit_t *circ) {
  unsigned char iv[16];
  unsigned char keys[32];
137
138
  cell_t cell;

139
  memset(iv, 0, 16);
140

141
142
143
  memset(&cell, 0, sizeof(cell_t));
  cell.command = CELL_CREATED;
  cell.aci = circ->p_aci;
144
  cell.length = DH_KEY_LEN;
145
146

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

148
149
  log(LOG_DEBUG,"onionskin_process(): Entering.");

150
  if(onion_skin_server_handshake(circ->onionskin, get_privatekey(),
151
152
    cell.payload, keys, 32) < 0) {
    log(LOG_ERR,"onionskin_process(): onion_skin_server_handshake failed.");
Roger Dingledine's avatar
Roger Dingledine committed
153
154
155
    return -1;
  }

156
157
158
  log(LOG_DEBUG,"onionskin_process: init cipher forward %d, backward %d.", *(int*)keys, *(int*)(keys+16));

  if (!(circ->n_crypto =
Nick Mathewson's avatar
src/or    
Nick Mathewson committed
159
        crypto_create_init_cipher(CIRCUIT_CIPHER,keys,iv,0))) {
160
    log(LOG_ERR,"Cipher initialization failed.");
Roger Dingledine's avatar
Roger Dingledine committed
161
162
163
    return -1;
  }

164
  if (!(circ->p_crypto =
Nick Mathewson's avatar
src/or    
Nick Mathewson committed
165
        crypto_create_init_cipher(CIRCUIT_CIPHER,keys+16,iv,1))) {
166
    log(LOG_ERR,"Cipher initialization failed.");
Roger Dingledine's avatar
Roger Dingledine committed
167
168
169
    return -1;
  }

170
  if(connection_write_cell_to_buf(&cell, circ->p_conn) < 0) {
Roger Dingledine's avatar
Roger Dingledine committed
171
172
    return -1;
  }
173
  log(LOG_DEBUG,"onionskin_process(): Finished sending 'created' cell.");
Roger Dingledine's avatar
Roger Dingledine committed
174
175
176
177

  return 0;
}

178
179
180
181
/* uses a weighted coin with weight cw to choose a route length */
int chooselen(double cw)
{
  int len = 2;
182
  uint8_t coin;
183
184
185
186
187
188
  
  if ((cw < 0) || (cw >= 1)) /* invalid parameter */
    return -1;
  
  while(1)
  {
189
    if (CRYPTO_PSEUDO_RAND_INT(coin))
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
      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
 */
205
unsigned int *new_route(double cw, routerinfo_t **rarray, int rarray_len, int *routelen)
206
{
207
  int i;
208
  int num_acceptable_routers;
209
  unsigned int *route;
210
  unsigned int oldchoice, choice;
211

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

214
215
  *routelen = chooselen(cw);
  if (*routelen == -1) {
Roger Dingledine's avatar
Roger Dingledine committed
216
217
218
    log(LOG_ERR,"Choosing route length failed.");
    return NULL;
  }
219
  log(LOG_DEBUG,"new_route(): Chosen route length %d.",*routelen);
Roger Dingledine's avatar
Roger Dingledine committed
220

221
222
  num_acceptable_routers = count_acceptable_routers(rarray, rarray_len);

223
224
225
226
227
  if(num_acceptable_routers < 2) {
    log(LOG_INFO,"new_route(): Not enough acceptable routers. Failing.");
    return NULL;
  }

228
  if(num_acceptable_routers < *routelen) {
229
    log(LOG_NOTICE,"new_route(): Cutting routelen from %d to %d.",*routelen, num_acceptable_routers);
230
    *routelen = num_acceptable_routers;
Roger Dingledine's avatar
Roger Dingledine committed
231
  }
232

233
  if(*routelen < 1) {
Roger Dingledine's avatar
Roger Dingledine committed
234
235
236
237
238
    log(LOG_ERR,"new_route(): Didn't find any acceptable routers. Failing.");
    return NULL;
  }

  /* allocate memory for the new route */
239
  route = (unsigned int *)tor_malloc(*routelen * sizeof(unsigned int));
Roger Dingledine's avatar
Roger Dingledine committed
240
241
 
  oldchoice = rarray_len;
242
  for(i=0;i<*routelen;i++) {
Roger Dingledine's avatar
Roger Dingledine committed
243
    log(LOG_DEBUG,"new_route(): Choosing hop %u.",i);
244
    if (CRYPTO_PSEUDO_RAND_INT(choice)) {
Roger Dingledine's avatar
Roger Dingledine committed
245
      free((void *)route);
246
247
248
      return NULL;
    }

249
    choice = choice % rarray_len;
Roger Dingledine's avatar
Roger Dingledine committed
250
    log(LOG_DEBUG,"new_route(): Contemplating router %u.",choice);
251
    if(choice == oldchoice ||
252
      (oldchoice < rarray_len && !crypto_pk_cmp_keys(rarray[choice]->pkey, rarray[oldchoice]->pkey)) ||
253
      (options.OnionRouter && !connection_twin_get_by_addr_port(rarray[choice]->addr, rarray[choice]->or_port))) {
Roger Dingledine's avatar
Roger Dingledine committed
254
255
256
257
      /* 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);
258
259
      i--;
      continue;  
260
    }
Roger Dingledine's avatar
Roger Dingledine committed
261
262
263
264
    log(LOG_DEBUG,"new_route(): Chosen router %u for hop %u.",choice,i);
    oldchoice = choice;
    route[i] = choice;
  }
265
   
Roger Dingledine's avatar
Roger Dingledine committed
266
  return route;
267
268
}

269
270
271
static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len) {
  int i, j;
  int num=0;
272
  connection_t *conn;
273
274
275

  for(i=0;i<rarray_len;i++) {
    log(LOG_DEBUG,"Contemplating whether router %d is a new option...",i);
276
    if(options.OnionRouter) {
277
278
279
280
281
      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;
      }
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
    }
    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;
}

299
300
301
302
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;
303
  directory_t *dir;
304
305
  routerinfo_t **rarray;
  int rarray_len;
306
307
  int i;
  crypt_path_t *hop;
308
  routerinfo_t *router;
309
  struct in_addr netaddr;
310

311
312
313
  router_get_directory(&dir);
  rarray = dir->routers;
  rarray_len = dir->n_routers;
314

315
316
317
318
  /* 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.");
319
320
    return NULL;
  }
321
322
323
324
  log(LOG_DEBUG,"onion_generate_cpath(): Chosen a route of length %u: ",routelen);

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

326
  for(i=0; i<routelen; i++) {
327
328
    netaddr.s_addr = htonl((rarray[route[i]])->addr);

329
    log(LOG_DEBUG,"onion_generate_cpath(): %u : %s:%u, %u/%u",routelen-i,
330
331
        inet_ntoa(netaddr),
        (rarray[route[i]])->or_port,
332
        (int) (rarray[route[i]])->pkey,
333
334
        crypto_pk_keysize((rarray[route[i]])->pkey));
  }
335

336
  /* create the cpath layer by layer, starting at the last hop */
337
338
  for (i=0;i<routelen;i++) {
    router = rarray[route[i]];
339

340
    /* build up the crypt_path */
341
    hop = (crypt_path_t *)tor_malloc(sizeof(crypt_path_t));
342
    memset(hop, 0, sizeof(crypt_path_t));
343

344
    /* link hop into the cpath, at the front */
345
    hop->next = cpath;
346
    hop->prev = NULL;
347
348
349
    hop->state = CPATH_STATE_CLOSED;
    if(cpath) {
      cpath->prev = hop;
350
    }
351
    cpath = hop;
352

353
354
    hop->port = rarray[route[i]]->or_port;
    hop->addr = rarray[route[i]]->addr;
355

356
357
358
    hop->package_window = CIRCWINDOW_START;
    hop->deliver_window = CIRCWINDOW_START;

359
    log(LOG_DEBUG,"onion_generate_cpath() : Building hop %u of crypt path.",i+1);
360
  }
361

362
  /* now link cpath->prev to the end of cpath */
363
364
365
  for(hop=cpath; hop->next; hop=hop->next) ;
  hop->next = cpath;
  cpath->prev = hop;
366

367
368
  free(route);
  return cpath;
369
370
}

371
372
/*----------------------------------------------------------------------*/

373
/* Given a router's public key, generates a 144-byte encrypted DH pubkey,
374
375
376
377
378
 * 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
379
 *   128 bytes of g^x for DH.
380
 * The first 128 bytes are RSA-encrypted with the server's public key,
381
 * and the last 16 are encrypted with the symmetric key.
382
383
 */
int
384
onion_skin_create(crypto_pk_env_t *dest_router_key,
385
                  crypto_dh_env_t **handshake_state_out,
386
                  char *onion_skin_out) /* Must be DH_ONIONSKIN_LEN bytes long */
387
388
389
390
391
392
393
394
{
  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;
395
  memset(onion_skin_out, 0, DH_ONIONSKIN_LEN);
396
  memset(iv, 0, 16);
397
398
399
400
401

  if (!(dh = crypto_dh_new()))
    goto err;
  
  dhbytes = crypto_dh_get_bytes(dh);
402
  pkbytes = crypto_pk_keysize(dest_router_key);
403
  assert(dhbytes+16 == DH_ONIONSKIN_LEN);
404
  pubkey = (char *)tor_malloc(dhbytes+16);
405
406
407

  if (crypto_rand(16, pubkey))
    goto err;
408
409
410
411
412
413
414
415
416
  
  /* 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; 
417
418
419
420

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

421
422
423
424
425
426
427
428
429
430
431
432
433
#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("");
434
435
#endif

Nick Mathewson's avatar
src/or    
Nick Mathewson committed
436
  cipher = crypto_create_init_cipher(ONION_CIPHER, pubkey, iv, 1);
437
438
439
440

  if (!cipher)
    goto err;

441
  if (crypto_pk_public_encrypt(dest_router_key, pubkey, pkbytes,
442
                               onion_skin_out, RSA_NO_PADDING)==-1)
443
444
    goto err;

445
  if (crypto_cipher_encrypt(cipher, pubkey+pkbytes, dhbytes+16-pkbytes,
446
447
448
449
450
451
                            onion_skin_out+pkbytes))
    goto err;

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

453
454
455
456
457
458
459
460
461
  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,
462
 * and the private key for this onion router, generate the 128-byte DH
463
464
465
 * reply, and key_out_len bytes of key material, stored in key_out.
 */
int
466
onion_skin_server_handshake(char *onion_skin, /* DH_ONIONSKIN_LEN bytes long */
467
                            crypto_pk_env_t *private_key,
468
                            char *handshake_reply_out, /* DH_KEY_LEN bytes long */
469
470
471
                            char *key_out,
                            int key_out_len)
{
472
  char buf[DH_ONIONSKIN_LEN];
473
474
475
476
  char iv[16];
  crypto_dh_env_t *dh = NULL;
  crypto_cipher_env_t *cipher = NULL;
  int pkbytes;
477
  int len;
478
479
480
481
482
483
  
  memset(iv, 0, 16);
  pkbytes = crypto_pk_keysize(private_key);

  if (crypto_pk_private_decrypt(private_key,
                                onion_skin, pkbytes,
484
                                buf, RSA_NO_PADDING) == -1)
485
    goto err;
486
  
487
488
489
490
#ifdef DEBUG_ONION_SKINS
  printf("Server: client symkey:");
  PA(buf+0,16);
  puts("");
491
#endif
492

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

495
  if (crypto_cipher_decrypt(cipher, onion_skin+pkbytes, DH_ONIONSKIN_LEN-pkbytes,
496
497
                            buf+pkbytes))
    goto err;
498

499
500
501
502
503
504
#ifdef DEBUG_ONION_SKINS
  printf("Server: client g^x:");
  PA(buf+16,3);
  printf("...");
  PA(buf+141,3);
  puts("");
505
#endif
506
507
  
  dh = crypto_dh_new();
508
  if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN))
509
510
    goto err;

511
512
513
514
515
516
517
518
#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
519
  len = crypto_dh_compute_secret(dh, buf+16, DH_KEY_LEN, key_out, key_out_len);
520
  if (len < 0)
521
522
    goto err;

523
#ifdef DEBUG_ONION_SKINS
524
525
526
  printf("Server: key material:");
  PA(buf, DH_KEY_LEN);
  puts("");
527
528
529
530
531
  printf("Server: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

532
533
534
535
536
537
538
539
540
541
542
  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.
543
 * Given the 128 byte DH reply as generated by onion_skin_server_handshake
544
545
546
547
548
549
550
 * 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,
551
                            char *handshake_reply,/* Must be DH_KEY_LEN bytes long*/
552
553
554
                            char *key_out,
                            int key_out_len) 
{
555
  int len;
556
  assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
557
  
558
559
560
561
562
563
564
565
#ifdef DEBUG_ONION_SKINS
  printf("Client: server g^y:");
  PA(handshake_reply+0,3);
  printf("...");
  PA(handshake_reply+125,3);
  puts("");
#endif

566
  len = crypto_dh_compute_secret(handshake_state, handshake_reply, DH_KEY_LEN,
Nick Mathewson's avatar
src/or    
Nick Mathewson committed
567
                                 key_out, key_out_len);
568
  if (len < 0)
569
570
    return -1;
  
571
572
573
574
575
576
#ifdef DEBUG_ONION_SKINS
  printf("Client: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

577
578
579
  return 0;
}

580
581
582
583
584
585
586
/*
  Local Variables:
  mode:c
  indent-tabs-mode:nil
  c-basic-offset:2
  End:
*/