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 */
9 * \brief Functions to queue create cells, and handle onionskin
10 * parsing and creation.
14 #include "circuitlist.h"
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
{
25 struct onion_queue_t
*next
;
28 /** 5 seconds on the onion queue til we just send back a destroy */
29 #define ONIONQUEUE_WAIT_CUTOFF 5
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;
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.
42 onion_pending_add(or_circuit_t
*circ
, char *onionskin
)
45 time_t now
= time(NULL
);
47 tmp
= tor_malloc_zero(sizeof(onion_queue_t
));
49 tmp
->onionskin
= onionskin
;
50 tmp
->when_added
= now
;
54 tor_assert(!ol_length
);
62 tor_assert(!ol_tail
->next
);
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
);
69 if ((m
= rate_limit_log(&last_warned
, approx_time()))) {
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
);
84 while ((int)(now
- ol_list
->when_added
) >= ONIONQUEUE_WAIT_CUTOFF
) {
85 /* cull elderly requests. */
87 onion_pending_remove(ol_list
->circ
);
89 "Circuit create request is too old; canceling due to overload.");
90 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_RESOURCELIMIT
);
95 /** Remove the first item from ol_list and return it, or return
96 * NULL if the list is empty.
99 onion_next_task(char **onionskin_out
)
104 return NULL
; /* no onions pending, we're done */
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
);
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.
120 onion_pending_remove(or_circuit_t
*circ
)
122 onion_queue_t
*tmpo
, *victim
;
125 return; /* nothing here. */
127 /* first check to see if it's the first entry */
129 if (tmpo
->circ
== circ
) {
130 /* it's the first one. remove it from the list. */
131 ol_list
= tmpo
->next
;
136 } else { /* we need to hunt through the rest of the list */
137 for ( ;tmpo
->next
&& tmpo
->next
->circ
!= circ
; tmpo
=tmpo
->next
) ;
139 log_debug(LD_GENERAL
,
140 "circ (p_circ_id %d) not in list, probably at cpuworker.",
144 /* now we know tmpo->next->circ == circ */
146 tmpo
->next
= victim
->next
;
147 if (ol_tail
== victim
)
152 /* now victim points to the element that needs to be removed */
154 tor_free(victim
->onionskin
);
158 /*----------------------------------------------------------------------*/
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)
167 * Stores the DH private key into handshake_state_out for later completion
170 * The meeting point/cookies and auth are zeroed out for now.
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 */
177 char challenge
[DH_KEY_LEN
];
178 crypto_dh_env_t
*dh
= NULL
;
179 int dhbytes
, pkbytes
;
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
);
187 if (!(dh
= crypto_dh_new()))
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);
195 if (crypto_dh_get_public(dh
, challenge
, dhbytes
))
198 note_crypto_pk_op(ENC_ONIONSKIN
);
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)
206 memset(challenge
, 0, sizeof(challenge
));
207 *handshake_state_out
= dh
;
211 memset(challenge
, 0, sizeof(challenge
));
212 if (dh
) crypto_dh_free(dh
);
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.
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*/
229 char challenge
[ONIONSKIN_CHALLENGE_LEN
];
230 crypto_dh_env_t
*dh
= NULL
;
232 char *key_material
=NULL
;
233 size_t key_material_len
=0;
239 k
= i
==0?private_key
:prev_private_key
;
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);
250 log_info(LD_PROTOCOL
,
251 "Couldn't decrypt onionskin: client may be using old onion key");
253 } else if (len
!= DH_KEY_LEN
) {
254 log_warn(LD_PROTOCOL
, "Unexpected onionskin length after decryption: %ld",
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.");
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
,
271 log_info(LD_GENERAL
, "crypto_dh_compute_secret failed.");
275 /* send back H(K|0) as proof that we learned K. */
276 memcpy(handshake_reply_out
+DH_KEY_LEN
, key_material
, DIGEST_LEN
);
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
);
281 memset(challenge
, 0, sizeof(challenge
));
282 memset(key_material
, 0, key_material_len
);
283 tor_free(key_material
);
287 memset(challenge
, 0, sizeof(challenge
));
289 memset(key_material
, 0, key_material_len
);
290 tor_free(key_material
);
292 if (dh
) crypto_dh_free(dh
);
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.
304 * After the invocation, call crypto_dh_free on handshake_state.
307 onion_skin_client_handshake(crypto_dh_env_t
*handshake_state
,
308 const char *handshake_reply
, /* ONIONSKIN_REPLY_LEN bytes */
313 char *key_material
=NULL
;
314 size_t key_material_len
;
315 tor_assert(crypto_dh_get_bytes(handshake_state
) == DH_KEY_LEN
);
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
,
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. "
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
);
335 memset(key_material
, 0, key_material_len
);
336 tor_free(key_material
);
339 memset(key_material
, 0, key_material_len
);
340 tor_free(key_material
);
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, <0 on failure.
352 fast_server_handshake(const char *key_in
, /* DIGEST_LEN bytes */
353 char *handshake_reply_out
, /* DIGEST_LEN*2 bytes */
357 char tmp
[DIGEST_LEN
+DIGEST_LEN
];
362 if (crypto_rand(handshake_reply_out
, DIGEST_LEN
)<0)
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
)) {
372 memcpy(handshake_reply_out
+DIGEST_LEN
, out
, DIGEST_LEN
);
373 memcpy(key_out
, out
+DIGEST_LEN
, key_out_len
);
376 memset(tmp
, 0, sizeof(tmp
));
377 memset(out
, 0, out_len
);
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,
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).
395 fast_client_handshake(const char *handshake_state
, /* DIGEST_LEN bytes */
396 const char *handshake_reply_out
, /* DIGEST_LEN*2 bytes */
400 char tmp
[DIGEST_LEN
+DIGEST_LEN
];
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
)) {
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. "
418 memcpy(key_out
, out
+DIGEST_LEN
, key_out_len
);
421 memset(tmp
, 0, sizeof(tmp
));
422 memset(out
, 0, out_len
);
427 /** Remove all circuits from the pending list. Called from tor_free_all. */
429 clear_pending_onions(void)
432 onion_queue_t
*victim
= ol_list
;
433 ol_list
= victim
->next
;
434 tor_free(victim
->onionskin
);
437 ol_list
= ol_tail
= NULL
;