src/or/onion.c

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