onion.c 8.95 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
3
/* Copyright 2001 Matej Pfajfar.
 * Copyright 2001-2004 Roger Dingledine.
 * Copyright 2004 Roger Dingledine, Nick Mathewson. */
4
5
/* See LICENSE for licensing information */
/* $Id$ */
6
const char onion_c_id[] = "$Id$";
Roger Dingledine's avatar
Roger Dingledine committed
7

8
9
/**
 * \file onion.c
10
11
 * \brief Functions to queue create cells, and handle onionskin
 * parsing and creation.
12
13
 **/

Roger Dingledine's avatar
Roger Dingledine committed
14
15
#include "or.h"

Roger Dingledine's avatar
Roger Dingledine committed
16
17
18
19
20
struct onion_queue_t {
  circuit_t *circ;
  struct onion_queue_t *next;
};

21
/** global (within this file) variables used by the next few functions */
22
23
static struct onion_queue_t *ol_list=NULL;
static struct onion_queue_t *ol_tail=NULL;
24
/** length of ol_list */
25
26
static int ol_length=0;

27
28
29
/** Add <b>circ</b> to the end of ol_list and return 0, except
 * if ol_list is too long, in which case do nothing and return -1.
 */
30
31
32
int onion_pending_add(circuit_t *circ) {
  struct onion_queue_t *tmp;

33
  tmp = tor_malloc_zero(sizeof(struct onion_queue_t));
34
35
  tmp->circ = circ;

36
  if (!ol_tail) {
Roger Dingledine's avatar
Roger Dingledine committed
37
38
    tor_assert(!ol_list);
    tor_assert(!ol_length);
39
40
41
42
43
44
    ol_list = tmp;
    ol_tail = tmp;
    ol_length++;
    return 0;
  }

Roger Dingledine's avatar
Roger Dingledine committed
45
46
  tor_assert(ol_list);
  tor_assert(!ol_tail->next);
47

48
  if (ol_length >= get_options()->MaxOnionsPending) {
Roger Dingledine's avatar
Roger Dingledine committed
49
    log_fn(LOG_NOTICE,"Already have %d onions queued. Closing.", ol_length);
Roger Dingledine's avatar
Roger Dingledine committed
50
    tor_free(tmp);
51
52
53
54
55
56
57
58
59
    return -1;
  }

  ol_length++;
  ol_tail->next = tmp;
  ol_tail = tmp;
  return 0;
}

60
61
62
/** Remove the first item from ol_list and return it, or return
 * NULL if the list is empty.
 */
Roger Dingledine's avatar
Roger Dingledine committed
63
circuit_t *onion_next_task(void) {
64
  circuit_t *circ;
65

66
  if (!ol_list)
Roger Dingledine's avatar
Roger Dingledine committed
67
    return NULL; /* no onions pending, we're done */
68

Roger Dingledine's avatar
Roger Dingledine committed
69
70
71
  tor_assert(ol_list->circ);
  tor_assert(ol_list->circ->p_conn); /* make sure it's still valid */
  tor_assert(ol_length > 0);
72
73
74
  circ = ol_list->circ;
  onion_pending_remove(ol_list->circ);
  return circ;
75
76
}

77
78
/** Go through ol_list, find the onion_queue_t element which points to
 * circ, remove and free that element. Leave circ itself alone.
79
80
81
82
 */
void onion_pending_remove(circuit_t *circ) {
  struct onion_queue_t *tmpo, *victim;

83
  if (!ol_list)
84
85
86
87
    return; /* nothing here. */

  /* first check to see if it's the first entry */
  tmpo = ol_list;
88
  if (tmpo->circ == circ) {
89
90
    /* it's the first one. remove it from the list. */
    ol_list = tmpo->next;
91
    if (!ol_list)
92
93
94
95
      ol_tail = NULL;
    ol_length--;
    victim = tmpo;
  } else { /* we need to hunt through the rest of the list */
96
97
    for ( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ;
    if (!tmpo->next) {
98
      log_fn(LOG_DEBUG,"circ (p_circ_id %d) not in list, probably at cpuworker.",circ->p_circ_id);
99
100
101
102
103
      return;
    }
    /* now we know tmpo->next->circ == circ */
    victim = tmpo->next;
    tmpo->next = victim->next;
104
    if (ol_tail == victim)
105
106
107
108
109
110
      ol_tail = tmpo;
    ol_length--;
  }

  /* now victim points to the element that needs to be removed */

Roger Dingledine's avatar
Roger Dingledine committed
111
  tor_free(victim);
112
113
}

114
115
/*----------------------------------------------------------------------*/

116
117
118
119
120
121
122
/** Given a router's 128 byte public key,
 * stores the following in onion_skin_out:
 *   - [42 bytes] OAEP padding
 *   - [16 bytes] Symmetric key for encrypting blob past RSA
 *   - [70 bytes] g^x part 1 (inside the RSA)
 *   - [58 bytes] g^x part 2 (symmetrically encrypted)
 *
123
124
 * Stores the DH private key into handshake_state_out for later completion
 * of the handshake.
125
 *
126
 * The meeting point/cookies and auth are zeroed out for now.
127
128
 */
int
129
onion_skin_create(crypto_pk_env_t *dest_router_key,
130
                  crypto_dh_env_t **handshake_state_out,
131
                  char *onion_skin_out) /* Must be ONIONSKIN_CHALLENGE_LEN bytes */
132
{
133
  char *challenge = NULL;
134
135
136
137
  crypto_dh_env_t *dh = NULL;
  int dhbytes, pkbytes;

  *handshake_state_out = NULL;
138
  memset(onion_skin_out, 0, ONIONSKIN_CHALLENGE_LEN);
139
140
141

  if (!(dh = crypto_dh_new()))
    goto err;
142

143
  dhbytes = crypto_dh_get_bytes(dh);
144
  pkbytes = crypto_pk_keysize(dest_router_key);
Roger Dingledine's avatar
Roger Dingledine committed
145
146
  tor_assert(dhbytes == 128);
  tor_assert(pkbytes == 128);
147
  challenge = tor_malloc_zero(DH_KEY_LEN);
148

149
  if (crypto_dh_get_public(dh, challenge, dhbytes))
150
151
    goto err;

152
153
154
155
156
#ifdef DEBUG_ONION_SKINS
#define PA(a,n) \
  { int _i; for (_i = 0; _i<n; ++_i) printf("%02x ",((int)(a)[_i])&0xFF); }

  printf("Client: client g^x:");
157
  PA(challenge+16,3);
158
  printf("...");
159
  PA(challenge+141,3);
160
161
162
  puts("");

  printf("Client: client symkey:");
163
  PA(challenge+0,16);
164
  puts("");
165
166
#endif

167
  /* set meeting point, meeting cookie, etc here. Leave zero for now. */
168
169
170
  if (crypto_pk_public_hybrid_encrypt(dest_router_key, onion_skin_out,
                                      challenge, DH_KEY_LEN,
                                      PK_PKCS1_OAEP_PADDING, 1)<0)
171
    goto err;
Roger Dingledine's avatar
Roger Dingledine committed
172

173
  tor_free(challenge);
174
  *handshake_state_out = dh;
175

176
177
  return 0;
 err:
178
  tor_free(challenge);
179
180
181
182
  if (dh) crypto_dh_free(dh);
  return -1;
}

183
/** Given an encrypted DH public key as generated by onion_skin_create,
184
185
186
 * and the private key for this onion router, generate the reply (128-byte
 * DH plus the first 20 bytes of shared key material), and store the
 * next key_out_len bytes of key material in key_out.
187
188
 */
int
189
onion_skin_server_handshake(char *onion_skin, /* ONIONSKIN_CHALLENGE_LEN bytes */
190
                            crypto_pk_env_t *private_key,
191
                            crypto_pk_env_t *prev_private_key,
192
                            char *handshake_reply_out, /* ONIONSKIN_REPLY_LEN bytes */
193
                            char *key_out,
194
                            size_t key_out_len)
195
{
196
  char challenge[ONIONSKIN_CHALLENGE_LEN];
197
  crypto_dh_env_t *dh = NULL;
198
  int len;
199
  char *key_material=NULL;
200
201
  int i;
  crypto_pk_env_t *k;
Roger Dingledine's avatar
Roger Dingledine committed
202

203
204
205
206
207
  len = -1;
  for (i=0;i<2;++i) {
    k = i==0?private_key:prev_private_key;
    if (!k)
      break;
208
    len = crypto_pk_private_hybrid_decrypt(k, challenge,
209
                                           onion_skin, ONIONSKIN_CHALLENGE_LEN,
210
                                           PK_PKCS1_OAEP_PADDING,0);
211
212
213
214
    if (len>0)
      break;
  }
  if (len<0) {
215
    log_fn(LOG_INFO, "Couldn't decrypt onionskin: client may be using old onion key");
216
217
218
219
    goto err;
  } else if (len != DH_KEY_LEN) {
    log_fn(LOG_WARN, "Unexpected onionskin length after decryption: %d",
           len);
220
    goto err;
221
  }
Roger Dingledine's avatar
Roger Dingledine committed
222

223
  dh = crypto_dh_new();
224
  if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN))
225
226
    goto err;

227
228
229
230
231
232
233
234
#ifdef DEBUG_ONION_SKINS
  printf("Server: server g^y:");
  PA(handshake_reply_out+0,3);
  printf("...");
  PA(handshake_reply_out+125,3);
  puts("");
#endif

235
236
237
  key_material = tor_malloc(DIGEST_LEN+key_out_len);
  len = crypto_dh_compute_secret(dh, challenge, DH_KEY_LEN,
                                 key_material, DIGEST_LEN+key_out_len);
238
  if (len < 0)
239
240
    goto err;

241
  /* send back H(K|0) as proof that we learned K. */
242
  memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
243
244

  /* use the rest of the key material for our shared keys, digests, etc */
245
  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
246

247
#ifdef DEBUG_ONION_SKINS
248
249
250
  printf("Server: key material:");
  PA(buf, DH_KEY_LEN);
  puts("");
251
252
253
254
255
  printf("Server: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

256
  tor_free(key_material);
257
258
259
  crypto_dh_free(dh);
  return 0;
 err:
260
  tor_free(key_material);
261
262
263
264
265
  if (dh) crypto_dh_free(dh);

  return -1;
}

266
/** Finish the client side of the DH handshake.
267
268
269
270
271
 * Given the 128 byte DH reply + 20 byte hash as generated by
 * onion_skin_server_handshake and the handshake state generated by
 * onion_skin_create, verify H(K) with the first 20 bytes of shared
 * key material, then generate key_out_len more bytes of shared key
 * material and store them in key_out.
272
273
274
275
276
 *
 * After the invocation, call crypto_dh_free on handshake_state.
 */
int
onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
277
                            char *handshake_reply, /* Must be ONIONSKIN_REPLY_LEN bytes */
278
                            char *key_out,
279
                            size_t key_out_len)
280
{
281
  int len;
282
  char *key_material=NULL;
Roger Dingledine's avatar
Roger Dingledine committed
283
  tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
Roger Dingledine's avatar
Roger Dingledine committed
284

285
286
287
288
289
290
291
292
#ifdef DEBUG_ONION_SKINS
  printf("Client: server g^y:");
  PA(handshake_reply+0,3);
  printf("...");
  PA(handshake_reply+125,3);
  puts("");
#endif

293
  key_material = tor_malloc(20+key_out_len);
294
  len = crypto_dh_compute_secret(handshake_state, handshake_reply, DH_KEY_LEN,
295
                                 key_material, 20+key_out_len);
296
  if (len < 0)
297
    return -1;
Roger Dingledine's avatar
Roger Dingledine committed
298

299
  if (memcmp(key_material, handshake_reply+DH_KEY_LEN, 20)) {
300
301
302
303
304
305
306
307
308
    /* H(K) does *not* match. Something fishy. */
    tor_free(key_material);
    log_fn(LOG_WARN,"Digest DOES NOT MATCH on onion handshake. Bug or attack.");
    return -1;
  }

  /* use the rest of the key material for our shared keys, digests, etc */
  memcpy(key_out, key_material+20, key_out_len);

309
310
311
312
313
314
#ifdef DEBUG_ONION_SKINS
  printf("Client: keys out:");
  PA(key_out, key_out_len);
  puts("");
#endif

315
  tor_free(key_material);
316
317
318
  return 0;
}

319
320
321
322
323
324
325
326
327
328
329
330
/** Remove all circuits from the pending list.  Called from tor_free_all. */
void
clear_pending_onions(void)
{
  while (ol_list) {
    struct onion_queue_t *victim = ol_list;
    ol_list = victim->next;
    tor_free(victim);
  }
  ol_list = ol_tail = NULL;
  ol_length = 0;
}