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