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