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