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