src/or/onion.c

   1 /* Copyright 2001 Matej Pfajfar.
   2  * Copyright 2001-2004 Roger Dingledine.
   3  * Copyright 2004-2005 Roger Dingledine, Nick Mathewson. */
   4 /* See LICENSE for licensing information */
   5 /* $Id$ */
   6 const char onion_c_id[] = "$Id$";
   7
   8 /**
   9  * \file onion.c
  10  * \brief Functions to queue create cells, and handle onionskin
  11  * parsing and creation.
  12  **/
  13
  14 #define NEW_LOG_INTERFACE
  15 #include "or.h"
  16
  17 /** Type for a linked list of circuits that are waiting for a free CPU worker
  18  * to process a waiting onion handshake. */
  19 typedef struct onion_queue_t {
  20   circuit_t *circ;
  21   time_t when_added;
  22   struct onion_queue_t *next;
  23 } onion_queue_t;
  24
  25 /** 5 seconds on the onion queue til we just send back a destroy */
  26 #define ONIONQUEUE_WAIT_CUTOFF 5
  27
  28 /** Global (within this file) variables used by the next few functions */
  29 static onion_queue_t *ol_list=NULL;
  30 static onion_queue_t *ol_tail=NULL;
  31 /** Length of ol_list */
  32 static int ol_length=0;
  33
  34 /** Add <b>circ</b> to the end of ol_list and return 0, except
  35  * if ol_list is too long, in which case do nothing and return -1.
  36  */
  37 int
  38 onion_pending_add(circuit_t *circ)
  39 {
  40   onion_queue_t *tmp;
  41   time_t now = time(NULL);
  42
  43   tmp = tor_malloc_zero(sizeof(onion_queue_t));
  44   tmp->circ = circ;
  45   tmp->when_added = now;
  46
  47   if (!ol_tail) {
  48     tor_assert(!ol_list);
  49     tor_assert(!ol_length);
  50     ol_list = tmp;
  51     ol_tail = tmp;
  52     ol_length++;
  53     return 0;
  54   }
  55
  56   tor_assert(ol_list);
  57   tor_assert(!ol_tail->next);
  58
  59   if (ol_length >= get_options()->MaxOnionsPending) {
  60     notice(LD_GENERAL,"Already have %d onions queued. Closing.", ol_length);
  61     tor_free(tmp);
  62     return -1;
  63   }
  64
  65   ol_length++;
  66   ol_tail->next = tmp;
  67   ol_tail = tmp;
  68   while ((int)(now - ol_list->when_added) >= ONIONQUEUE_WAIT_CUTOFF) {
  69     /* cull elderly requests. */
  70     circ = ol_list->circ;
  71     onion_pending_remove(ol_list->circ);
  72     info(LD_CIRC,"Circuit create request is too old; cancelling due to overload.");
  73     circuit_mark_for_close(circ);
  74   }
  75   return 0;
  76 }
  77
  78 /** Remove the first item from ol_list and return it, or return
  79  * NULL if the list is empty.
  80  */
  81 circuit_t *
  82 onion_next_task(void)
  83 {
  84   circuit_t *circ;
  85
  86   if (!ol_list)
  87     return NULL; /* no onions pending, we're done */
  88
  89   tor_assert(ol_list->circ);
  90   tor_assert(ol_list->circ->p_conn); /* make sure it's still valid */
  91   tor_assert(ol_length > 0);
  92   circ = ol_list->circ;
  93   onion_pending_remove(ol_list->circ);
  94   return circ;
  95 }
  96
  97 /** Go through ol_list, find the onion_queue_t element which points to
  98  * circ, remove and free that element. Leave circ itself alone.
  99  */
 100 void
 101 onion_pending_remove(circuit_t *circ)
 102 {
 103   onion_queue_t *tmpo, *victim;
 104
 105   if (!ol_list)
 106     return; /* nothing here. */
 107
 108   /* first check to see if it's the first entry */
 109   tmpo = ol_list;
 110   if (tmpo->circ == circ) {
 111     /* it's the first one. remove it from the list. */
 112     ol_list = tmpo->next;
 113     if (!ol_list)
 114       ol_tail = NULL;
 115     ol_length--;
 116     victim = tmpo;
 117   } else { /* we need to hunt through the rest of the list */
 118     for ( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ;
 119     if (!tmpo->next) {
 120       debug(LD_GENERAL,"circ (p_circ_id %d) not in list, probably at cpuworker.",circ->p_circ_id);
 121       return;
 122     }
 123     /* now we know tmpo->next->circ == circ */
 124     victim = tmpo->next;
 125     tmpo->next = victim->next;
 126     if (ol_tail == victim)
 127       ol_tail = tmpo;
 128     ol_length--;
 129   }
 130
 131   /* now victim points to the element that needs to be removed */
 132
 133   tor_free(victim);
 134 }
 135
 136 /*----------------------------------------------------------------------*/
 137
 138 /** Given a router's 128 byte public key,
 139  * stores the following in onion_skin_out:
 140  *   - [42 bytes] OAEP padding
 141  *   - [16 bytes] Symmetric key for encrypting blob past RSA
 142  *   - [70 bytes] g^x part 1 (inside the RSA)
 143  *   - [58 bytes] g^x part 2 (symmetrically encrypted)
 144  *
 145  * Stores the DH private key into handshake_state_out for later completion
 146  * of the handshake.
 147  *
 148  * The meeting point/cookies and auth are zeroed out for now.
 149  */
 150 int
 151 onion_skin_create(crypto_pk_env_t *dest_router_key,
 152                   crypto_dh_env_t **handshake_state_out,
 153                   char *onion_skin_out) /* Must be ONIONSKIN_CHALLENGE_LEN bytes */
 154 {
 155   char *challenge = NULL;
 156   crypto_dh_env_t *dh = NULL;
 157   int dhbytes, pkbytes;
 158
 159   tor_assert(dest_router_key);
 160   tor_assert(handshake_state_out);
 161   tor_assert(onion_skin_out);
 162   *handshake_state_out = NULL;
 163   memset(onion_skin_out, 0, ONIONSKIN_CHALLENGE_LEN);
 164
 165   if (!(dh = crypto_dh_new()))
 166     goto err;
 167
 168   dhbytes = crypto_dh_get_bytes(dh);
 169   pkbytes = crypto_pk_keysize(dest_router_key);
 170   tor_assert(dhbytes == 128);
 171   tor_assert(pkbytes == 128);
 172   challenge = tor_malloc_zero(DH_KEY_LEN);
 173
 174   if (crypto_dh_get_public(dh, challenge, dhbytes))
 175     goto err;
 176
 177 #ifdef DEBUG_ONION_SKINS
 178 #define PA(a,n) \
 179   { int _i; for (_i = 0; _i<n; ++_i) printf("%02x ",((int)(a)[_i])&0xFF); }
 180
 181   printf("Client: client g^x:");
 182   PA(challenge+16,3);
 183   printf("...");
 184   PA(challenge+141,3);
 185   puts("");
 186
 187   printf("Client: client symkey:");
 188   PA(challenge+0,16);
 189   puts("");
 190 #endif
 191
 192   /* set meeting point, meeting cookie, etc here. Leave zero for now. */
 193   if (crypto_pk_public_hybrid_encrypt(dest_router_key, onion_skin_out,
 194                                       challenge, DH_KEY_LEN,
 195                                       PK_PKCS1_OAEP_PADDING, 1)<0)
 196     goto err;
 197
 198   tor_free(challenge);
 199   *handshake_state_out = dh;
 200
 201   return 0;
 202  err:
 203   tor_free(challenge);
 204   if (dh) crypto_dh_free(dh);
 205   return -1;
 206 }
 207
 208 /** Given an encrypted DH public key as generated by onion_skin_create,
 209  * and the private key for this onion router, generate the reply (128-byte
 210  * DH plus the first 20 bytes of shared key material), and store the
 211  * next key_out_len bytes of key material in key_out.
 212  */
 213 int
 214 onion_skin_server_handshake(const char *onion_skin, /* ONIONSKIN_CHALLENGE_LEN bytes */
 215                             crypto_pk_env_t *private_key,
 216                             crypto_pk_env_t *prev_private_key,
 217                             char *handshake_reply_out, /* ONIONSKIN_REPLY_LEN bytes */
 218                             char *key_out,
 219                             size_t key_out_len)
 220 {
 221   char challenge[ONIONSKIN_CHALLENGE_LEN];
 222   crypto_dh_env_t *dh = NULL;
 223   int len;
 224   char *key_material=NULL;
 225   int i;
 226   crypto_pk_env_t *k;
 227
 228   len = -1;
 229   for (i=0;i<2;++i) {
 230     k = i==0?private_key:prev_private_key;
 231     if (!k)
 232       break;
 233     len = crypto_pk_private_hybrid_decrypt(k, challenge,
 234                                            onion_skin, ONIONSKIN_CHALLENGE_LEN,
 235                                            PK_PKCS1_OAEP_PADDING,0);
 236     if (len>0)
 237       break;
 238   }
 239   if (len<0) {
 240     info(LD_PROTOCOL, "Couldn't decrypt onionskin: client may be using old onion key");
 241     goto err;
 242   } else if (len != DH_KEY_LEN) {
 243     warn(LD_PROTOCOL, "Unexpected onionskin length after decryption: %d",
 244            len);
 245     goto err;
 246   }
 247
 248   dh = crypto_dh_new();
 249   if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN)) {
 250     info(LD_GENERAL, "crypto_dh_get_public failed.");
 251     goto err;
 252   }
 253
 254 #ifdef DEBUG_ONION_SKINS
 255   printf("Server: server g^y:");
 256   PA(handshake_reply_out+0,3);
 257   printf("...");
 258   PA(handshake_reply_out+125,3);
 259   puts("");
 260 #endif
 261
 262   key_material = tor_malloc(DIGEST_LEN+key_out_len);
 263   len = crypto_dh_compute_secret(dh, challenge, DH_KEY_LEN,
 264                                  key_material, DIGEST_LEN+key_out_len);
 265   if (len < 0) {
 266     info(LD_GENERAL, "crypto_dh_compute_secret failed.");
 267     goto err;
 268   }
 269
 270   /* send back H(K|0) as proof that we learned K. */
 271   memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
 272
 273   /* use the rest of the key material for our shared keys, digests, etc */
 274   memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
 275
 276 #ifdef DEBUG_ONION_SKINS
 277   printf("Server: key material:");
 278   PA(key_material, DH_KEY_LEN);
 279   puts("");
 280   printf("Server: keys out:");
 281   PA(key_out, key_out_len);
 282   puts("");
 283 #endif
 284
 285   tor_free(key_material);
 286   crypto_dh_free(dh);
 287   return 0;
 288  err:
 289   tor_free(key_material);
 290   if (dh) crypto_dh_free(dh);
 291
 292   return -1;
 293 }
 294
 295 /** Finish the client side of the DH handshake.
 296  * Given the 128 byte DH reply + 20 byte hash as generated by
 297  * onion_skin_server_handshake and the handshake state generated by
 298  * onion_skin_create, verify H(K) with the first 20 bytes of shared
 299  * key material, then generate key_out_len more bytes of shared key
 300  * material and store them in key_out.
 301  *
 302  * After the invocation, call crypto_dh_free on handshake_state.
 303  */
 304 int
 305 onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
 306             const char *handshake_reply, /* Must be ONIONSKIN_REPLY_LEN bytes */
 307             char *key_out,
 308             size_t key_out_len)
 309 {
 310   int len;
 311   char *key_material=NULL;
 312   tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
 313
 314 #ifdef DEBUG_ONION_SKINS
 315   printf("Client: server g^y:");
 316   PA(handshake_reply+0,3);
 317   printf("...");
 318   PA(handshake_reply+125,3);
 319   puts("");
 320 #endif
 321
 322   key_material = tor_malloc(20+key_out_len);
 323   len = crypto_dh_compute_secret(handshake_state, handshake_reply, DH_KEY_LEN,
 324                                  key_material, 20+key_out_len);
 325   if (len < 0)
 326     return -1;
 327
 328   if (memcmp(key_material, handshake_reply+DH_KEY_LEN, 20)) {
 329     /* H(K) does *not* match. Something fishy. */
 330     tor_free(key_material);
 331     warn(LD_PROTOCOL,"Digest DOES NOT MATCH on onion handshake. Bug or attack.");
 332     return -1;
 333   }
 334
 335   /* use the rest of the key material for our shared keys, digests, etc */
 336   memcpy(key_out, key_material+20, key_out_len);
 337
 338 #ifdef DEBUG_ONION_SKINS
 339   printf("Client: keys out:");
 340   PA(key_out, key_out_len);
 341   puts("");
 342 #endif
 343
 344   tor_free(key_material);
 345   return 0;
 346 }
 347
 348 /** DOCDOC */
 349 int
 350 fast_server_handshake(const char *key_in, /* DIGEST_LEN bytes */
 351                       char *handshake_reply_out, /* DIGEST_LEN*2 bytes */
 352                       char *key_out,
 353                       size_t key_out_len)
 354 {
 355   char tmp[DIGEST_LEN+DIGEST_LEN+1];
 356   char digest[DIGEST_LEN];
 357   int i;
 358
 359   if (crypto_rand(handshake_reply_out, DIGEST_LEN)<0)
 360     return -1;
 361
 362   memcpy(tmp, key_in, DIGEST_LEN);
 363   memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
 364   tmp[DIGEST_LEN+DIGEST_LEN] = 0;
 365   crypto_digest(handshake_reply_out+DIGEST_LEN, tmp, sizeof(tmp));
 366
 367   for (i = 0; i*DIGEST_LEN < (int)key_out_len; ++i) {
 368     size_t len;
 369     tmp[DIGEST_LEN+DIGEST_LEN] = i+1;
 370     crypto_digest(digest, tmp, sizeof(tmp));
 371     len = key_out_len - i*DIGEST_LEN;
 372     if (len > DIGEST_LEN) len = DIGEST_LEN;
 373     memcpy(key_out+i*DIGEST_LEN, digest, len);
 374   }
 375
 376   return 0;
 377 }
 378
 379 /** DOCDOC */
 380 int
 381 fast_client_handshake(const char *handshake_state, /* DIGEST_LEN bytes */
 382                       const char *handshake_reply_out, /* DIGEST_LEN*2 bytes */
 383                       char *key_out,
 384                       size_t key_out_len)
 385 {
 386   char tmp[DIGEST_LEN+DIGEST_LEN+1];
 387   char digest[DIGEST_LEN];
 388   int i;
 389
 390   memcpy(tmp, handshake_state, DIGEST_LEN);
 391   memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
 392   tmp[DIGEST_LEN+DIGEST_LEN] = 0;
 393   crypto_digest(digest, tmp, sizeof(tmp));
 394
 395   if (memcmp(digest, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
 396     /* H(K) does *not* match. Something fishy. */
 397     warn(LD_PROTOCOL,"Digest DOES NOT MATCH on fast handshake. Bug or attack.");
 398     return -1;
 399   }
 400
 401   for (i = 0; i*DIGEST_LEN < (int)key_out_len; ++i) {
 402     size_t len;
 403     tmp[DIGEST_LEN+DIGEST_LEN] = i+1;
 404     crypto_digest(digest, tmp, sizeof(tmp));
 405     len = key_out_len - i*DIGEST_LEN;
 406     if (len > DIGEST_LEN) len = DIGEST_LEN;
 407     memcpy(key_out+i*DIGEST_LEN, digest, len);
 408   }
 409
 410   return 0;
 411 }
 412
 413 /** Remove all circuits from the pending list.  Called from tor_free_all. */
 414 void
 415 clear_pending_onions(void)
 416 {
 417   while (ol_list) {
 418     onion_queue_t *victim = ol_list;
 419     ol_list = victim->next;
 420     tor_free(victim);
 421   }
 422   ol_list = ol_tail = NULL;
 423   ol_length = 0;
 424 }
 425