onion.c 24.8 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 int global_role; /* from main.c */
8
extern or_options_t options; /* command-line and config-file options */
9

10
11
static int onion_process(circuit_t *circ);
static int onion_deliver_to_conn(aci_t aci, unsigned char *onion, uint32_t onionlen, connection_t *conn);
12
static int find_tracked_onion(unsigned char *onion, uint32_t onionlen);
Roger Dingledine's avatar
Roger Dingledine committed
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

27
28
29
30
31
32
33
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
70
71
72
/* 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;

  tmp = malloc(sizeof(struct onion_queue_t));
  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) {
  struct data_queue_t *tmpd;
73
  circuit_t *circ; 
74
75
76
77
78
79

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

  assert(ol_list->circ && ol_list->circ->p_conn);
  assert(ol_length > 0);
80
  circ = ol_list->circ;
81

82
  if(onion_process(circ) < 0) {
83
    log(LOG_DEBUG,"onion_pending_process_one(): Failed. Closing.");
84
85
    onion_pending_remove(circ);
    circuit_close(circ);
86
87
88
  } else {
    log(LOG_DEBUG,"onion_pending_process_one(): Succeeded. Delivering queued data cells.");
    for(tmpd = ol_list->data_cells; tmpd; tmpd=tmpd->next) {
89
      command_process_data_cell(tmpd->cell, circ->p_conn); 
90
    }
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
133
134
135
136
137
138
139
140
141
142
 */
void onion_pending_remove(circuit_t *circ) {
  struct onion_queue_t *tmpo, *victim;
  struct data_queue_t *tmpd;

  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 */

  /* first dump the attached data cells too, if any */
  while(victim->data_cells) {
    tmpd = victim->data_cells;
    victim->data_cells = tmpd->next;
    free(tmpd->cell);
    free(tmpd);
  }
 
  free(victim); 

}

143
struct data_queue_t *data_queue_add(struct data_queue_t *list, cell_t *cell) {
144
145
146
147
148
149
150
  struct data_queue_t *tmpd, *newd;

  newd = malloc(sizeof(struct data_queue_t));
  memset(newd, 0, sizeof(struct data_queue_t));
  newd->cell = malloc(sizeof(cell_t));
  memcpy(newd->cell, cell, sizeof(cell_t));

151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
  if(!list) {
    return newd;
  }
  for(tmpd = list; tmpd->next; tmpd=tmpd->next) ;
  /* now tmpd->next is null */
  tmpd->next = newd;
  return list;
}

/* a data cell has arrived for a circuit which is still pending. Find
 * the right entry in ol_list, and add it to the end of the 'data_cells'
 * list.
 */
void onion_pending_data_add(circuit_t *circ, cell_t *cell) {
  struct onion_queue_t *tmpo;

167
168
  for(tmpo=ol_list; tmpo; tmpo=tmpo->next) {
    if(tmpo->circ == circ) {
169
      tmpo->data_cells = data_queue_add(tmpo->data_cells, cell);
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
      return;
    }
  }
}

/* helper function for onion_process */
static int onion_deliver_to_conn(aci_t aci, unsigned char *onion, uint32_t onionlen, connection_t *conn) {
  char *buf;
  int buflen, dataleft;
  cell_t cell;
 
  assert(aci && onion && onionlen);
 
  buflen = onionlen+4;
  buf = malloc(buflen);
  if(!buf)
    return -1;
 
  log(LOG_DEBUG,"onion_deliver_to_conn(): Setting onion length to %u.",onionlen);
  *(uint32_t*)buf = htonl(onionlen);
190
  memcpy((buf+4),onion,onionlen);
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
 
  dataleft = buflen;
  while(dataleft > 0) {
    memset(&cell,0,sizeof(cell_t));
    cell.command = CELL_CREATE;
    cell.aci = aci;
    if(dataleft >= CELL_PAYLOAD_SIZE)
      cell.length = CELL_PAYLOAD_SIZE;
    else
      cell.length = dataleft;
    memcpy(cell.payload, buf+buflen-dataleft, cell.length);
    dataleft -= cell.length;
 
    log(LOG_DEBUG,"onion_deliver_to_conn(): Delivering create cell, payload %d bytes.",cell.length);
    if(connection_write_cell_to_buf(&cell, conn) < 0) {
      log(LOG_DEBUG,"onion_deliver_to_conn(): Could not buffer new create cells. Closing.");
      free(buf);
      return -1;
    }
  }
  free(buf);
  return 0;
}

static int onion_process(circuit_t *circ) {
  connection_t *n_conn;
  int retval;
Roger Dingledine's avatar
Roger Dingledine committed
218
  aci_t aci_type;
219
220
221
222
  struct sockaddr_in me; /* my router identity */

  if(learn_my_address(&me) < 0)
    return -1;
Roger Dingledine's avatar
Roger Dingledine committed
223

224
225
  /* decrypt it in-place */
  if(decrypt_onion(circ->onion,circ->onionlen,getprivatekey()) < 0) {
Roger Dingledine's avatar
Roger Dingledine committed
226
227
228
229
230
231
    log(LOG_DEBUG,"command_process_create_cell(): decrypt_onion() failed, closing circuit.");
    return -1;
  }
  log(LOG_DEBUG,"command_process_create_cell(): Onion decrypted.");

  /* check freshness */
232
  if (ntohl(*(uint32_t *)(circ->onion+8)) < (uint32_t)time(NULL)) /* expired onion */
Roger Dingledine's avatar
Roger Dingledine committed
233
234
235
236
237
  { 
    log(LOG_NOTICE,"I have just received an expired onion. This could be a replay attack.");
    return -1;
  }

238
  aci_type = decide_aci_type(ntohl(me.sin_addr.s_addr), ntohs(me.sin_port),
239
             ntohl(*(uint32_t *)(circ->onion+4)),ntohs(*(uint16_t *)(circ->onion+2)));
Roger Dingledine's avatar
Roger Dingledine committed
240
241
242
243
244
245
      
  if(circuit_init(circ, aci_type) < 0) { 
    log(LOG_ERR,"process_onion(): init_circuit() failed.");
    return -1;
  }

246
247
  /* check for replay. at the same time, add it to the pile of tracked onions. */
  if(find_tracked_onion(circ->onion, circ->onionlen)) {
Roger Dingledine's avatar
Roger Dingledine committed
248
249
250
251
    log(LOG_NOTICE,"process_onion(): I have just received a replayed onion. This could be a replay attack.");
    return -1;
  }

252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
  /* now we must send create cells to the next router */
  if(circ->n_addr && circ->n_port) {
    n_conn = connection_twin_get_by_addr_port(circ->n_addr,circ->n_port);
    if(!n_conn || n_conn->type != CONN_TYPE_OR) {
      /* i've disabled making connections through OPs, but it's definitely
       * possible here. I'm not sure if it would be a bug or a feature. -RD
       */
      /* note also that this will close circuits where the onion has the same
       * router twice in a row in the path. i think that's ok. -RD
       */
      log(LOG_DEBUG,"command_process_create_cell(): Next router not connected. Closing.");
      return -1;
    }

    circ->n_addr = n_conn->addr; /* these are different if we found a twin instead */
    circ->n_port = n_conn->port;

    circ->n_conn = n_conn;
    log(LOG_DEBUG,"command_process_create_cell(): n_conn is %s:%u",n_conn->address,n_conn->port);

    /* send the CREATE cells on to the next hop  */
273
    pad_onion(circ->onion, circ->onionlen, ONION_LAYER_SIZE);
274
275
276
    log(LOG_DEBUG,"command_process_create_cell(): Padded the onion with random data.");

    retval = onion_deliver_to_conn(circ->n_aci, circ->onion, circ->onionlen, n_conn); 
277
    free(circ->onion);
278
279
280
281
282
283
    circ->onion = NULL;
    if (retval == -1) {
      log(LOG_DEBUG,"command_process_create_cell(): Could not deliver the onion to next conn. Closing.");
      return -1;
    }
  } else { /* this is destined for an exit */
284
285
    log(LOG_DEBUG,"command_process_create_cell(): create cell reached exit. Circuit established.");
#if 0
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
    log(LOG_DEBUG,"command_process_create_cell(): Creating new exit connection.");
    n_conn = connection_new(CONN_TYPE_EXIT);
    if(!n_conn) {
      log(LOG_DEBUG,"command_process_create_cell(): connection_new failed. Closing.");
      return -1;
    }
    n_conn->state = EXIT_CONN_STATE_CONNECTING_WAIT;
    n_conn->receiver_bucket = -1; /* edge connections don't do receiver buckets */
    n_conn->bandwidth = -1;
    n_conn->s = -1; /* not yet valid */
    if(connection_add(n_conn) < 0) { /* no space, forget it */
      log(LOG_DEBUG,"command_process_create_cell(): connection_add failed. Closing.");
      connection_free(n_conn);
      return -1;
    }
    circ->n_conn = n_conn;
302
#endif
303
  }
Roger Dingledine's avatar
Roger Dingledine committed
304
305
306
  return 0;
}

307
308
309
310
311
312
313
314
315
316
317
318
/* uses a weighted coin with weight cw to choose a route length */
int chooselen(double cw)
{
  int len = 2;
  int retval = 0;
  unsigned char coin;
  
  if ((cw < 0) || (cw >= 1)) /* invalid parameter */
    return -1;
  
  while(1)
  {
319
320
    retval = crypto_pseudo_rand(1, &coin);
    if (retval)
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
      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
 */
336
unsigned int *new_route(double cw, routerinfo_t **rarray, int rarray_len, int *routelen)
337
{
Roger Dingledine's avatar
Roger Dingledine committed
338
339
  int i, j;
  int num_acceptable_routers = 0;
340
341
342
  unsigned int *route = NULL;
  unsigned int oldchoice, choice;
  
343
  assert((cw >= 0) && (cw < 1) && (rarray) && (routelen) ); /* valid parameters */
344

345
346
  *routelen = chooselen(cw);
  if (*routelen == -1) {
Roger Dingledine's avatar
Roger Dingledine committed
347
348
349
    log(LOG_ERR,"Choosing route length failed.");
    return NULL;
  }
350
  log(LOG_DEBUG,"new_route(): Chosen route length %d.",*routelen);
Roger Dingledine's avatar
Roger Dingledine committed
351
352

  for(i=0;i<rarray_len;i++) {
353
354
355
    log(LOG_DEBUG,"Contemplating whether router %d is a new option...",i);
    if( (global_role & ROLE_OR_CONNECT_ALL) &&
      !connection_exact_get_by_addr_port(rarray[i]->addr, rarray[i]->or_port)) {
Roger Dingledine's avatar
Roger Dingledine committed
356
357
358
359
      log(LOG_DEBUG,"Nope, %d is not connected.",i);
      goto next_i_loop;
    }
    for(j=0;j<i;j++) {
360
      if(!crypto_pk_cmp_keys(rarray[i]->pkey, rarray[j]->pkey)) {
Roger Dingledine's avatar
Roger Dingledine committed
361
362
363
364
        /* 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;
      }
365
    }
Roger Dingledine's avatar
Roger Dingledine committed
366
367
368
    num_acceptable_routers++;
    log(LOG_DEBUG,"I like %d. num_acceptable_routers now %d.",i, num_acceptable_routers);
    next_i_loop:
369
      ; /* our compiler may need an explicit statement after the label */
Roger Dingledine's avatar
Roger Dingledine committed
370
371
  }
      
372
373
374
  if(num_acceptable_routers < *routelen) {
    log(LOG_DEBUG,"new_route(): Cutting routelen from %d to %d.",*routelen, num_acceptable_routers);
    *routelen = num_acceptable_routers;
Roger Dingledine's avatar
Roger Dingledine committed
375
  }
376

377
  if(*routelen < 1) {
Roger Dingledine's avatar
Roger Dingledine committed
378
379
380
381
382
    log(LOG_ERR,"new_route(): Didn't find any acceptable routers. Failing.");
    return NULL;
  }

  /* allocate memory for the new route */
383
  route = (unsigned int *)malloc(*routelen * sizeof(unsigned int));
Roger Dingledine's avatar
Roger Dingledine committed
384
385
386
387
388
389
  if (!route) {
    log(LOG_ERR,"Memory allocation failed.");
    return NULL;
  }
 
  oldchoice = rarray_len;
390
  for(i=0;i<*routelen;i++) {
Roger Dingledine's avatar
Roger Dingledine committed
391
    log(LOG_DEBUG,"new_route(): Choosing hop %u.",i);
392
    if(crypto_pseudo_rand(sizeof(unsigned int),(unsigned char *)&choice)) {
Roger Dingledine's avatar
Roger Dingledine committed
393
      free((void *)route);
394
395
396
      return NULL;
    }

Roger Dingledine's avatar
Roger Dingledine committed
397
398
    choice = choice % (rarray_len);
    log(LOG_DEBUG,"new_route(): Contemplating router %u.",choice);
399
    if(choice == oldchoice ||
400
      (oldchoice < rarray_len && !crypto_pk_cmp_keys(rarray[choice]->pkey, rarray[oldchoice]->pkey)) ||
401
      ((global_role & ROLE_OR_CONNECT_ALL) && !connection_twin_get_by_addr_port(rarray[choice]->addr, rarray[choice]->or_port))) {
Roger Dingledine's avatar
Roger Dingledine committed
402
403
404
405
      /* 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);
406
407
      i--;
      continue;  
408
    }
Roger Dingledine's avatar
Roger Dingledine committed
409
410
411
412
    log(LOG_DEBUG,"new_route(): Chosen router %u for hop %u.",choice,i);
    oldchoice = choice;
    route[i] = choice;
  }
413
   
Roger Dingledine's avatar
Roger Dingledine committed
414
  return route;
415
416
}

417
418
419
420
421
422
423
424
crypto_cipher_env_t *
create_onion_cipher(int cipher_type, char *key, char *iv, int encrypt_mode)
{
  switch (cipher_type) {
    case ONION_CIPHER_DES:
      cipher_type = CRYPTO_CIPHER_DES;
      break;
    case ONION_CIPHER_RC4 :
425
      cipher_type = CRYPTO_CIPHER_RC4;
426
427
428
429
430
431
432
433
434
435
436
      break;
    case ONION_CIPHER_IDENTITY :
      cipher_type = CRYPTO_CIPHER_IDENTITY;
      break;
    default:
      log(LOG_ERR, "Unknown cipher type %d", cipher_type);
      return NULL;
  }
  return crypto_create_init_cipher(cipher_type, key, iv, encrypt_mode);
}

437
438
/* creates a new onion from route, stores it and its length into buf and len respectively */
unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int *route, int routelen, int *len, crypt_path_t **cpath)
439
440
{
  int i,j;
441
  char *layer;
442
  crypt_path_t *hop = NULL;
443
  unsigned char *buf;
444
  routerinfo_t *router;
445
  unsigned char iv[16];
446
  struct in_addr netaddr;
447

448
  assert(rarray && route && len && routelen);
449

450
  /* calculate the size of the onion */
451
452
  *len = routelen * ONION_LAYER_SIZE + ONION_PADDING_SIZE;
  /* 28 bytes per layer + 100 bytes padding for the innermost layer */
453
  log(LOG_DEBUG,"create_onion() : Size of the onion is %u.",*len);
454
    
455
  /* allocate memory for the onion */
456
457
  buf = malloc(*len);
  if(!buf) {
458
459
460
461
    log(LOG_ERR,"Error allocating memory.");
    return NULL;
  }
  log(LOG_DEBUG,"create_onion() : Allocated memory for the onion.");
462
    
463
  for(i=0; i<routelen; i++) {
464
465
466
467
468
469
470
471
    netaddr.s_addr = htonl((rarray[route[i]])->addr);

    log(LOG_DEBUG,"create_onion(): %u : %s:%u, %u/%u",routelen-i,
        inet_ntoa(netaddr),
        (rarray[route[i]])->or_port,
        (rarray[route[i]])->pkey,
        crypto_pk_keysize((rarray[route[i]])->pkey));
  }
472
    
473
  layer = buf + *len - ONION_LAYER_SIZE - ONION_PADDING_SIZE; /* pointer to innermost layer */
474
475
476
  /* create the onion layer by layer, starting with the innermost */
  for (i=0;i<routelen;i++) {
    router = rarray[route[i]];
477
      
478
479
480
481
//      log(LOG_DEBUG,"create_onion() : %u",router);
//      log(LOG_DEBUG,"create_onion() : This router is %s:%u",inet_ntoa(*((struct in_addr *)&router->addr)),router->or_port);
//      log(LOG_DEBUG,"create_onion() : Key pointer = %u.",router->pkey);
//      log(LOG_DEBUG,"create_onion() : Key size = %u.",crypto_pk_keysize(router->pkey)); 
482
      
483
    *layer = OR_VERSION;
484
    /* Back F + Forw F both use DES OFB*/
485
486
487
    *(layer+1) = (ONION_DEFAULT_CIPHER << 4) /* for backf */ +
                 ONION_DEFAULT_CIPHER; /* for forwf */

488
489
    /* Dest Port */
    if (i) /* not last hop */
490
      *(uint16_t *)(layer+2) = htons(rarray[route[i-1]]->or_port);
491
    else
492
493
      *(uint16_t *)(layer+2) = htons(0);

494
495
    /* Dest Addr */
    if (i) /* not last hop */
496
      *(uint32_t *)(layer+4) = htonl(rarray[route[i-1]]->addr);
497
    else
498
499
      *(uint32_t *)(layer+4) = htonl(0);

500
    /* Expiration Time */
501
502
    *(uint32_t *)(layer+8) = htonl((uint32_t)(time(NULL) + 86400)); /* NOW + 1 day */

503
    /* Key Seed Material */
504
    if(crypto_rand(16, layer+12)) { /* error */
505
506
507
508
      log(LOG_ERR,"Error generating random data.");
      goto error;
    }
//      log(LOG_DEBUG,"create_onion() : Onion layer %u built : %u, %u, %u, %s, %u.",i+1,layer->zero,layer->backf,layer->forwf,inet_ntoa(*((struct in_addr *)&layer->addr)),layer->port);
509
      
510
511
512
513
514
515
516
    /* build up the crypt_path */
    if(cpath) {
      cpath[i] = (crypt_path_t *)malloc(sizeof(crypt_path_t));
      if(!cpath[i]) {
        log(LOG_ERR,"Error allocating memory.");
        goto error;
      }
517
      
518
519
520
      log(LOG_DEBUG,"create_onion() : Building hop %u of crypt path.",i+1);
      hop = cpath[i];
      /* set crypto functions */
521
522
      hop->backf = *(layer+1) >> 4;
      hop->forwf = *(layer+1) & 0x0f;
523

524
      /* calculate keys */
525
      crypto_SHA_digest(layer+12,16,hop->digest3);
526
527
528
529
530
531
532
533
      log(LOG_DEBUG,"create_onion() : First SHA pass performed.");
      crypto_SHA_digest(hop->digest3,20,hop->digest2);
      log(LOG_DEBUG,"create_onion() : Second SHA pass performed.");
      crypto_SHA_digest(hop->digest2,20,hop->digest3);
      log(LOG_DEBUG,"create_onion() : Third SHA pass performed.");
      log(LOG_DEBUG,"create_onion() : Keys generated.");
      /* set IV to zero */
      memset((void *)iv,0,16);
534

535
536
537
538
539
540
      /* initialize cipher engines */
      if (! (hop->f_crypto = create_onion_cipher(hop->forwf, hop->digest3, iv, 1))) { 
        /* cipher initialization failed */
        log(LOG_ERR,"Could not create a crypto environment.");
        goto error;
      }
541

542
543
544
545
      if (! (hop->b_crypto = create_onion_cipher(hop->backf, hop->digest2, iv, 0))) { 
        /* cipher initialization failed */
        log(LOG_ERR,"Could not create a crypto environment.");
        goto error;
546
      }
547
548
549
 
      log(LOG_DEBUG,"create_onion() : Built corresponding crypt path hop.");
    }
550
      
551
552
    /* padding if this is the innermost layer */
    if (!i) {
553
      if (crypto_pseudo_rand(ONION_PADDING_SIZE, layer + ONION_LAYER_SIZE)) { /* error */
554
555
        log(LOG_ERR,"Error generating pseudo-random data.");
        goto error;
556
      }
557
558
      log(LOG_DEBUG,"create_onion() : This is the innermost layer. Adding 100 bytes of padding.");
    }
559
      
560
    /* encrypt */
561

562
    if(encrypt_onion(layer,ONION_PADDING_SIZE+(i+1)*ONION_LAYER_SIZE,router->pkey) < 0) {
563
564
      log(LOG_ERR,"Error encrypting onion layer.");
      goto error;
565
    }
566
567
568
    log(LOG_DEBUG,"create_onion() : Encrypted layer.");
      
    /* calculate pointer to next layer */
569
    layer = buf + (routelen-i-2)*ONION_LAYER_SIZE;
570
  }
571

572
  return buf;
573

574
 error:
575
  if (buf)
576
    free(buf);
577
578
579
580
581
582
583
  if (cpath) {
    for (j=0;j<i;j++) {
      if(cpath[i]->f_crypto)
        crypto_free_cipher_env(cpath[i]->f_crypto);
      if(cpath[i]->b_crypto)
        crypto_free_cipher_env(cpath[i]->b_crypto);
      free((void *)cpath[i]);
584
    }
585
586
  }
  return NULL;
587
588
589
590
}

/* encrypts 128 bytes of the onion with the specified public key, the rest with 
 * DES OFB with the key as defined in the outter layer */
591
int encrypt_onion(unsigned char *onion, uint32_t onionlen, crypto_pk_env_t *pkey) {
592
593
594
595
  unsigned char *tmpbuf = NULL; /* temporary buffer for crypto operations */
  unsigned char digest[20]; /* stores SHA1 output - 160 bits */
  unsigned char iv[8];
  
596
  crypto_cipher_env_t *crypt_env = NULL; /* crypto environment */
597
 
598
  assert(onion && pkey);
599
  assert(onionlen >= 128);
600

601
  memset(iv,0,8);
602
    
603
//  log(LOG_DEBUG,"Onion layer : %u, %u, %u, %s, %u.",onion->zero,onion->backf,onion->forwf,inet_ntoa(*((struct in_addr *)&onion->addr)),onion->port);
604
605
  /* allocate space for tmpbuf */
  tmpbuf = (unsigned char *)malloc(onionlen);
606
  if(!tmpbuf) {
607
    log(LOG_ERR,"Could not allocate memory.");
608
    return -1;
609
610
  }
  log(LOG_DEBUG,"encrypt_onion() : allocated %u bytes of memory for the encrypted onion (at %u).",onionlen,tmpbuf);
611
  
612
  /* get key1 = SHA1(KeySeed) */
613
  if (crypto_SHA_digest(onion+12,16,digest)) {
614
615
616
617
    log(LOG_ERR,"Error computing SHA1 digest.");
    goto error;
  }
  log(LOG_DEBUG,"encrypt_onion() : Computed DES key.");
618
    
619
620
  log(LOG_DEBUG,"encrypt_onion() : Trying to RSA encrypt.");
  /* encrypt 128 bytes with RSA *pkey */
621
  if (crypto_pk_public_encrypt(pkey, onion, 128, tmpbuf, RSA_NO_PADDING) == -1) {
622
623
624
625
626
    log(LOG_ERR,"Error RSA-encrypting data :%s",crypto_perror());
    goto error;
  }

  log(LOG_DEBUG,"encrypt_onion() : RSA encrypted first 128 bytes of the onion."); 
627
    
628
629
630
631
632
633
  /* now encrypt the rest with DES OFB */
  crypt_env = crypto_create_init_cipher(CRYPTO_CIPHER_DES, digest, iv, 1);
  if (!crypt_env) {
    log(LOG_ERR,"Error creating the crypto environment.");
    goto error;
  }
634
    
635
  if (crypto_cipher_encrypt(crypt_env,onion+128, onionlen-128, (unsigned char *)tmpbuf+128)) { /* error */
636
637
638
639
    log(LOG_ERR,"Error performing DES encryption:%s",crypto_perror()); 
    goto error;
  }
  log(LOG_DEBUG,"encrypt_onion() : DES OFB encrypted the rest of the onion.");
640
    
641
  /* now copy tmpbuf to onion */
642
  memcpy(onion,tmpbuf,onionlen);
643
  log(LOG_DEBUG,"encrypt_onion() : Copied cipher to original onion buffer.");
644
  free(tmpbuf);
645
  crypto_free_cipher_env(crypt_env);
646
  return 0;
647
648
649

 error:
  if (tmpbuf)
650
    free(tmpbuf);
651
652
  if (crypt_env)
    crypto_free_cipher_env(crypt_env);
653
  return -1;
654
655
656
}

/* decrypts the first 128 bytes using RSA and prkey, decrypts the rest with DES OFB with key1 */
657
int decrypt_onion(unsigned char *onion, uint32_t onionlen, crypto_pk_env_t *prkey) {
658
659
660
661
  void *tmpbuf = NULL; /* temporary buffer for crypto operations */
  unsigned char digest[20]; /* stores SHA1 output - 160 bits */
  unsigned char iv[8];
  
662
  crypto_cipher_env_t *crypt_env =NULL; /* crypto environment */
663
  
664
665
666
  assert(onion && prkey);

  memset(iv,0,8);
667
    
668
669
670
671
672
673
674
  /* allocate space for tmpbuf */
  tmpbuf = malloc(onionlen);
  if (!tmpbuf) {
    log(LOG_ERR,"Could not allocate memory.");
    return -1;
  }
  log(LOG_DEBUG,"decrypt_onion() : Allocated memory for the temporary buffer.");
675

676
677
678
679
680
681
682
  /* decrypt 128 bytes with RSA *prkey */
  if (crypto_pk_private_decrypt(prkey, onion, 128, tmpbuf, RSA_NO_PADDING) == -1)
  {
    log(LOG_ERR,"Error RSA-decrypting data :%s",crypto_perror());
    goto error;
  }
  log(LOG_DEBUG,"decrypt_onion() : RSA decryption complete.");
683
    
684
685
686
687
688
689
  /* get key1 = SHA1(KeySeed) */
  if (crypto_SHA_digest(tmpbuf+12,16,digest)) {
    log(LOG_ERR,"Error computing SHA1 digest.");
    goto error;
  }
  log(LOG_DEBUG,"decrypt_onion() : Computed DES key.");
690
    
691
692
693
694
695
696
  /* now decrypt the rest with DES OFB */
  crypt_env = crypto_create_init_cipher(CRYPTO_CIPHER_DES, digest, iv, 0);
  if (!crypt_env) {
    log(LOG_ERR,"Error creating crypto environment");
    goto error;
  }
697
 
698
699
700
701
  if (crypto_cipher_decrypt(crypt_env,onion+128, onionlen-128,tmpbuf+128)) {
    log(LOG_ERR,"Error performing DES decryption:%s",crypto_perror());
    goto error;
  }
702
    
703
  log(LOG_DEBUG,"decrypt_onion() : DES decryption complete.");
704
    
705
706
707
708
709
  /* now copy tmpbuf to onion */
  memcpy(onion,tmpbuf,onionlen);
  free(tmpbuf);
  crypto_free_cipher_env(crypt_env);
  return 0;
710
711
712

 error:
  if (tmpbuf)
713
    free(tmpbuf);
714
715
  if (crypt_env)
    crypto_free_cipher_env(crypt_env);
716
  return -1;
717
718
719
}

/* delete first n bytes of the onion and pads the end with n bytes of random data */
720
void pad_onion(unsigned char *onion, uint32_t onionlen, int n)
721
{
722
723
724
725
  assert(onion);

  memmove(onion,onion+n,onionlen-n);
  crypto_pseudo_rand(n, onion+onionlen-n);
726
727
}

728
729
730
731



/* red black tree using Niels' tree.h. I used
732
http://www.openbsd.org/cgi-bin/cvsweb/src/regress/sys/sys/tree/rb/
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
as my guide */

#include "tree.h"

struct tracked_onion { 
  RB_ENTRY(tracked_onion) node;
  uint32_t expire;
  char digest[20]; /* SHA digest of the onion */
  struct tracked_onion *next;
};

RB_HEAD(tracked_tree, tracked_onion) tracked_root;

int compare_tracked_onions(struct tracked_onion *a, struct tracked_onion *b) {
  return memcmp(a->digest, b->digest, 20);
748
749
}

750
751
752
753
754
RB_PROTOTYPE(tracked_tree, tracked_onion, node, compare_tracked_onions);
RB_GENERATE(tracked_tree, tracked_onion, node, compare_tracked_onions);

void init_tracked_tree(void) {
  RB_INIT(&tracked_root);
755
756
}

757
758
759
/* see if this onion has been seen before. if so, return 1, else
 * return 0 and add the sha1 of this onion to the tree.
 */
760
static int find_tracked_onion(unsigned char *onion, uint32_t onionlen) {
761
762
763
764
765
766
767
  static struct tracked_onion *head_tracked_onions = NULL; /* linked list of tracked onions */
  static struct tracked_onion *tail_tracked_onions = NULL;

  uint32_t now = time(NULL); 
  struct tracked_onion *to;

  /* first take this opportunity to see if there are any expired
768
   * onions in the tree. we know this is fast because the linked list
769
770
771
772
773
774
775
776
777
778
779
780
781
   * 'tracked_onions' is ordered by when they were seen.
   */
  while(head_tracked_onions && (head_tracked_onions->expire < now)) {
    to = head_tracked_onions;
    log(LOG_DEBUG,"find_tracked_onion(): Forgetting old onion (expires %d)", to->expire);
    head_tracked_onions = to->next;
    if(!head_tracked_onions)          /* if there are no more, */
      tail_tracked_onions = NULL; /* then make sure the list's tail knows that too */
    RB_REMOVE(tracked_tree, &tracked_root, to);
    free(to);
  }

  to = malloc(sizeof(struct tracked_onion));
782
783
  
  /* compute the SHA digest of the onion */
784
785
786
787
788
789
790
  crypto_SHA_digest(onion, onionlen, to->digest);

  /* try adding it to the tree. if it's already there it will return it. */
  if(RB_INSERT(tracked_tree, &tracked_root, to)) {
    /* yes, it's already there: this is a replay. */
    free(to);
    return 1;
791
792
  }
  
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
  /* this is a new onion. add it to the list. */

  to->expire = ntohl(*(uint32_t *)(onion+8)); /* set the expiration date */
  to->next = NULL;

  if (!head_tracked_onions) {
    head_tracked_onions = to;
  } else {
    tail_tracked_onions->next = to;
  }
  tail_tracked_onions = to;

  log(LOG_DEBUG,"find_tracked_onion(): Remembered new onion (expires %d)", to->expire);
 
  return 0;
808
}
809