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()))
 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                                       challenge, DH_KEY_LEN,
 203                                       PK_PKCS1_OAEP_PADDING, 1)<0)
 204     goto err;
 205
 206   memset(challenge, 0, sizeof(challenge));
 207   *handshake_state_out = dh;
 208
 209   return 0;
 210  err:
 211   memset(challenge, 0, sizeof(challenge));
 212   if (dh) crypto_dh_free(dh);
 213   return -1;
 214 }
 215
 216 /** Given an encrypted DH public key as generated by onion_skin_create,
 217  * and the private key for this onion router, generate the reply (128-byte
 218  * DH plus the first 20 bytes of shared key material), and store the
 219  * next key_out_len bytes of key material in key_out.
 220  */
 221 int
 222 onion_skin_server_handshake(const char *onion_skin, /*ONIONSKIN_CHALLENGE_LEN*/
 223                             crypto_pk_env_t *private_key,
 224                             crypto_pk_env_t *prev_private_key,
 225                             char *handshake_reply_out, /*ONIONSKIN_REPLY_LEN*/
 226                             char *key_out,
 227                             size_t key_out_len)
 228 {
 229   char challenge[ONIONSKIN_CHALLENGE_LEN];
 230   crypto_dh_env_t *dh = NULL;
 231   ssize_t len;
 232   char *key_material=NULL;
 233   size_t key_material_len=0;
 234   int i;
 235   crypto_pk_env_t *k;
 236
 237   len = -1;
 238   for (i=0;i<2;++i) {
 239     k = i==0?private_key:prev_private_key;
 240     if (!k)
 241       break;
 242     note_crypto_pk_op(DEC_ONIONSKIN);
 243     len = crypto_pk_private_hybrid_decrypt(k, challenge,
 244                                            onion_skin, ONIONSKIN_CHALLENGE_LEN,
 245                                            PK_PKCS1_OAEP_PADDING,0);
 246     if (len>0)
 247       break;
 248   }
 249   if (len<0) {
 250     log_info(LD_PROTOCOL,
 251              "Couldn't decrypt onionskin: client may be using old onion key");
 252     goto err;
 253   } else if (len != DH_KEY_LEN) {
 254     log_warn(LD_PROTOCOL, "Unexpected onionskin length after decryption: %ld",
 255              (long)len);
 256     goto err;
 257   }
 258
 259   dh = crypto_dh_new();
 260   if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN)) {
 261     log_info(LD_GENERAL, "crypto_dh_get_public failed.");
 262     goto err;
 263   }
 264
 265   key_material_len = DIGEST_LEN+key_out_len;
 266   key_material = tor_malloc(key_material_len);
 267   len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh, challenge,
 268                                  DH_KEY_LEN, key_material,
 269                                  key_material_len);
 270   if (len < 0) {
 271     log_info(LD_GENERAL, "crypto_dh_compute_secret failed.");
 272     goto err;
 273   }
 274
 275   /* send back H(K|0) as proof that we learned K. */
 276   memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
 277
 278   /* use the rest of the key material for our shared keys, digests, etc */
 279   memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
 280
 281   memset(challenge, 0, sizeof(challenge));
 282   memset(key_material, 0, key_material_len);
 283   tor_free(key_material);
 284   crypto_dh_free(dh);
 285   return 0;
 286  err:
 287   memset(challenge, 0, sizeof(challenge));
 288   if (key_material) {
 289     memset(key_material, 0, key_material_len);
 290     tor_free(key_material);
 291   }
 292   if (dh) crypto_dh_free(dh);
 293
 294   return -1;
 295 }
 296
 297 /** Finish the client side of the DH handshake.
 298  * Given the 128 byte DH reply + 20 byte hash as generated by
 299  * onion_skin_server_handshake and the handshake state generated by
 300  * onion_skin_create, verify H(K) with the first 20 bytes of shared
 301  * key material, then generate key_out_len more bytes of shared key
 302  * material and store them in key_out.
 303  *
 304  * After the invocation, call crypto_dh_free on handshake_state.
 305  */
 306 int
 307 onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
 308             const char *handshake_reply, /* ONIONSKIN_REPLY_LEN bytes */
 309             char *key_out,
 310             size_t key_out_len)
 311 {
 312   ssize_t len;
 313   char *key_material=NULL;
 314   size_t key_material_len;
 315   tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
 316
 317   key_material_len = DIGEST_LEN + key_out_len;
 318   key_material = tor_malloc(key_material_len);
 319   len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, handshake_state,
 320                                  handshake_reply, DH_KEY_LEN, key_material,
 321                                  key_material_len);
 322   if (len < 0)
 323     goto err;
 324
 325   if (memcmp(key_material, handshake_reply+DH_KEY_LEN, DIGEST_LEN)) {
 326     /* H(K) does *not* match. Something fishy. */
 327     log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on onion handshake. "
 328              "Bug or attack.");
 329     goto err;
 330   }
 331
 332   /* use the rest of the key material for our shared keys, digests, etc */
 333   memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
 334
 335   memset(key_material, 0, key_material_len);
 336   tor_free(key_material);
 337   return 0;
 338  err:
 339   memset(key_material, 0, key_material_len);
 340   tor_free(key_material);
 341   return -1;
 342 }
 343
 344 /** Implement the server side of the CREATE_FAST abbreviated handshake.  The
 345  * client has provided DIGEST_LEN key bytes in <b>key_in</b> ("x").  We
 346  * generate a reply of DIGEST_LEN*2 bytes in <b>key_out</b>, consisting of a
 347  * new random "y", followed by H(x|y) to check for correctness.  We set
 348  * <b>key_out_len</b> bytes of key material in <b>key_out</b>.
 349  * Return 0 on success, &lt;0 on failure.
 350  **/
 351 int
 352 fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
 353                       uint8_t *handshake_reply_out, /* DIGEST_LEN*2 bytes */
 354                       uint8_t *key_out,
 355                       size_t key_out_len)
 356 {
 357   char tmp[DIGEST_LEN+DIGEST_LEN];
 358   char *out = NULL;
 359   size_t out_len;
 360   int r = -1;
 361
 362   if (crypto_rand((char*)handshake_reply_out, DIGEST_LEN)<0)
 363     return -1;
 364
 365   memcpy(tmp, key_in, DIGEST_LEN);
 366   memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
 367   out_len = key_out_len+DIGEST_LEN;
 368   out = tor_malloc(out_len);
 369   if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
 370     goto done;
 371   }
 372   memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
 373   memcpy(key_out, out+DIGEST_LEN, key_out_len);
 374   r = 0;
 375  done:
 376   memset(tmp, 0, sizeof(tmp));
 377   memset(out, 0, out_len);
 378   tor_free(out);
 379   return r;
 380 }
 381
 382 /** Implement the second half of the client side of the CREATE_FAST handshake.
 383  * We sent the server <b>handshake_state</b> ("x") already, and the server
 384  * told us <b>handshake_reply_out</b> (y|H(x|y)).  Make sure that the hash is
 385  * correct, and generate key material in <b>key_out</b>.  Return 0 on success,
 386  * true on failure.
 387  *
 388  * NOTE: The "CREATE_FAST" handshake path is distinguishable from regular
 389  * "onionskin" handshakes, and is not secure if an adversary can see or modify
 390  * the messages.  Therefore, it should only be used by clients, and only as
 391  * the first hop of a circuit (since the first hop is already authenticated
 392  * and protected by TLS).
 393  */
 394 int
 395 fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/
 396                       const uint8_t *handshake_reply_out,/*DIGEST_LEN*2 bytes*/
 397                       uint8_t *key_out,
 398                       size_t key_out_len)
 399 {
 400   char tmp[DIGEST_LEN+DIGEST_LEN];
 401   char *out;
 402   size_t out_len;
 403   int r = -1;
 404
 405   memcpy(tmp, handshake_state, DIGEST_LEN);
 406   memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
 407   out_len = key_out_len+DIGEST_LEN;
 408   out = tor_malloc(out_len);
 409   if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
 410     goto done;
 411   }
 412   if (memcmp(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
 413     /* H(K) does *not* match. Something fishy. */
 414     log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on fast handshake. "
 415              "Bug or attack.");
 416     goto done;
 417   }
 418   memcpy(key_out, out+DIGEST_LEN, key_out_len);
 419   r = 0;
 420  done:
 421   memset(tmp, 0, sizeof(tmp));
 422   memset(out, 0, out_len);
 423   tor_free(out);
 424   return r;
 425 }
 426
 427 /** Remove all circuits from the pending list.  Called from tor_free_all. */
 428 void
 429 clear_pending_onions(void)
 430 {
 431   while (ol_list) {
 432     onion_queue_t *victim = ol_list;
 433     ol_list = victim->next;
 434     tor_free(victim->onionskin);
 435     tor_free(victim);
 436   }
 437   ol_list = ol_tail = NULL;
 438   ol_length = 0;
 439 }
 440