routerparse.c 89.1 KB
Newer Older
1
/* oCpyright (c) 2001 Matej Pfajfar.
Roger Dingledine's avatar
Roger Dingledine committed
2
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2007, Roger Dingledine, Nick Mathewson. */
4
5
/* See LICENSE for licensing information */
/* $Id$ */
6
7
const char routerparse_c_id[] =
  "$Id$";
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * \file routerparse.c
 * \brief Code to parse and validate router descriptors and directories.
 **/

#include "or.h"

/****************************************************************************/

/** Enumeration of possible token types.  The ones starting with K_
 * correspond to directory 'keywords'.  _UNRECOGNIZED is for an
 * unrecognized keyword; _ERR is an error in the tokenizing process,
 * _EOF is an end-of-file marker, and _NIL is used to encode
 * not-a-token.
 */
typedef enum {
25
  K_ACCEPT = 0,
26
27
28
29
30
31
32
33
34
35
  K_DIRECTORY_SIGNATURE,
  K_RECOMMENDED_SOFTWARE,
  K_REJECT,
  K_ROUTER,
  K_SIGNED_DIRECTORY,
  K_SIGNING_KEY,
  K_ONION_KEY,
  K_ROUTER_SIGNATURE,
  K_PUBLISHED,
  K_RUNNING_ROUTERS,
36
  K_ROUTER_STATUS,
37
38
39
40
  K_PLATFORM,
  K_OPT,
  K_BANDWIDTH,
  K_PORTS,
41
  K_CONTACT,
42
  K_NETWORK_STATUS,
Nick Mathewson's avatar
Nick Mathewson committed
43
  K_UPTIME,
44
  K_DIR_SIGNING_KEY,
45
  K_FAMILY,
46
47
48
49
  K_FINGERPRINT,
  K_HIBERNATING,
  K_READ_HISTORY,
  K_WRITE_HISTORY,
50
51
52
53
54
55
56
  K_NETWORK_STATUS_VERSION,
  K_DIR_SOURCE,
  K_DIR_OPTIONS,
  K_CLIENT_VERSIONS,
  K_SERVER_VERSIONS,
  K_R,
  K_S,
57
  K_V,
58
  K_EVENTDNS,
59
60
61
  K_EXTRA_INFO,
  K_EXTRA_INFO_DIGEST,
  K_CACHES_EXTRA_INFO,
62
63
64
65
66
67
68
69

  K_DIR_KEY_CERTIFICATE_VERSION,
  K_DIR_IDENTITY_KEY,
  K_DIR_KEY_PUBLISHED,
  K_DIR_KEY_EXPIRES,
  K_DIR_KEY_CERTIFICATION,

  K_VOTE_STATUS,
70
71
  K_VALID_AFTER,
  K_FRESH_UNTIL,
72
  K_VALID_UNTIL,
73
74
  K_VOTING_DELAY,

75
76
77
78
  K_KNOWN_FLAGS,
  K_VOTE_DIGEST,
  K_CONSENSUS_DIGEST,

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
  _UNRECOGNIZED,
  _ERR,
  _EOF,
  _NIL
} directory_keyword;

/** Structure to hold a single directory token.
 *
 * We parse a directory by breaking it into "tokens", each consisting
 * of a keyword, a line full of arguments, and a binary object.  The
 * arguments and object are both optional, depending on the keyword
 * type.
 */
typedef struct directory_token_t {
  directory_keyword tp;        /**< Type of the token. */
  int n_args;                  /**< Number of elements in args */
  char **args;                 /**< Array of arguments from keyword line. */
  char *object_type;           /**< -----BEGIN [object_type]-----*/
97
  size_t object_size;          /**< Bytes in object_body */
98
99
  char *object_body;           /**< Contents of object, base64-decoded. */
  crypto_pk_env_t *key;        /**< For public keys only. */
100
  char *error;                 /**< For _ERR tokens only. */
101
102
103
104
105
106
107
108
} directory_token_t;

/* ********************************************************************** */

/** We use a table of rules to decide how to parse each token type. */

/** Rules for whether the keyword needs an object. */
typedef enum {
109
110
111
112
113
  NO_OBJ,        /**< No object, ever. */
  NEED_OBJ,      /**< Object is required. */
  NEED_KEY_1024, /**< Object is required, and must be a 1024 bit public key */
  NEED_KEY,      /**< Object is required, and must be a public key. */
  OBJ_OK,        /**< Object is optional. */
114
115
} obj_syntax;

116
#define AT_START 1
117
#define AT_END 2
118
119

/** Determines the parsing rules for a single token type. */
120
typedef struct token_rule_t {
121
122
123
124
125
126
127
128
129
130
131
132
  /** The string value of the keyword identifying the type of item. */
  const char *t;
  /** The corresponding directory_keyword enum. */
  directory_keyword v;
  /** Minimum number of arguments for this item */
  int min_args;
  /** Maximum number of arguments for this item */
  int max_args;
  /** If true, we concatenate all arguments for this item into a single
   * string. */
  int concat_args;
  /** Requirments on object syntax for this item. */
133
  obj_syntax os;
134
135
136
137
138
139
140
  /** Lowest number of times this item may appear in a document. */
  int min_cnt;
  /** Highest number of times this item may appear in a document. */
  int max_cnt;
  /** One or more of AT_START/AT_END to limit where the item may appear in a
   * document. */
  int pos;
141
142
} token_rule_t;

143
144
145
146
147
148
/*
 * Helper macros to define token tables.  's' is a string, 't' is a
 * directory_keyword, 'a' is a trio of argument multiplicities, and 'o' is an
 * object syntax.
 *
 */
149

150
151
152
153
154
155
156
157
158
/** Appears to indicate the end of a table. */
#define END_OF_TABLE { NULL, _NIL, 0,0,0, NO_OBJ, 0, INT_MAX, 0 }
/** An item with no restrictions: used for obsolete document types */
#define T(s,t,a,o)    { s, t, a, o, 0, INT_MAX, 0 }
/** An item with no restrictions on multiplicity or location. */
#define T0N(s,t,a,o)  { s, t, a, o, 0, INT_MAX, 0 }
/** An item that must appear exactly once */
#define T1(s,t,a,o)   { s, t, a, o, 1, 1, 0 }
/** An item that must appear exactly once, at the start of the document */
159
#define T1_START(s,t,a,o)   { s, t, a, o, 1, 1, AT_START }
160
/** An item that must appear exactly once, at the end of the document */
161
#define T1_END(s,t,a,o)   { s, t, a, o, 1, 1, AT_END }
162
163
164
165
166
167
/** An item that must appear one or more times */
#define T1N(s,t,a,o)  { s, t, a, o, 1, INT_MAX, 0 }
/** An item that must appear no more than once */
#define T01(s,t,a,o)  { s, t, a, o, 0, 1, 0 }

/* Argument multiplicity: any number of arguments. */
168
#define ARGS        0,INT_MAX,0
169
/* Argument multiplicity: no arguments. */
170
#define NO_ARGS     0,0,0
171
/* Argument multiplicity: concatenate all arguments. */
172
#define CONCAT_ARGS 1,1,1
173
/* Argument multiplicity: at least <b>n</b> arguments. */
174
#define GE(n)       n,INT_MAX,0
175
/* Argument multiplicity: exactly <b>n</b> arguments. */
176
177
#define EQ(n)       n,n,0

178
/** List of tokens allowable in router derscriptors */
179
180
static token_rule_t routerdesc_token_table[] = {
  T0N("reject",              K_REJECT,              ARGS,    NO_OBJ ),
181
  T0N("accept",              K_ACCEPT,              ARGS,    NO_OBJ ),
182
  T1_START( "router",              K_ROUTER,              GE(5),   NO_OBJ ),
183
184
  T1( "signing-key",         K_SIGNING_KEY,         NO_ARGS, NEED_KEY_1024 ),
  T1( "onion-key",           K_ONION_KEY,           NO_ARGS, NEED_KEY_1024 ),
185
  T1_END( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
186
  T1( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
187
  T01("uptime",              K_UPTIME,              GE(1),   NO_OBJ ),
188
  T01("fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),
189
  T01("hibernating",         K_HIBERNATING,         GE(1),   NO_OBJ ),
190
191
  T01("platform",            K_PLATFORM,        CONCAT_ARGS, NO_OBJ ),
  T01("contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
192
193
  T01("read-history",        K_READ_HISTORY,        ARGS,    NO_OBJ ),
  T01("write-history",       K_WRITE_HISTORY,       ARGS,    NO_OBJ ),
194
  T01("extra-info-digest",   K_EXTRA_INFO_DIGEST,   GE(1),   NO_OBJ ),
195
196

  T01("family",              K_FAMILY,              ARGS,    NO_OBJ ),
197
  T01("caches-extra-info",   K_CACHES_EXTRA_INFO,   NO_ARGS, NO_OBJ ),
198
199
200
  T01("eventdns",            K_EVENTDNS,            ARGS,    NO_OBJ ),

  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
201
  T1( "bandwidth",           K_BANDWIDTH,           GE(3),   NO_OBJ ),
202
203
204
205

  END_OF_TABLE
};

206
/** List of tokens allowable in extra-info documents. */
207
static token_rule_t extrainfo_token_table[] = {
208
  T1_END( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
209
210
211
212
  T1( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
  T01("read-history",        K_READ_HISTORY,        ARGS,    NO_OBJ ),
  T01("write-history",       K_WRITE_HISTORY,       ARGS,    NO_OBJ ),
213
  T1_START( "extra-info",          K_EXTRA_INFO,          GE(2),   NO_OBJ ),
214
215
216
217

  END_OF_TABLE
};

218
219
/** List of tokens allowable in the body part of v2 and v3 networkstatus
 * documents. */
220
static token_rule_t rtrstatus_token_table[] = {
Roger Dingledine's avatar
Roger Dingledine committed
221
  T1( "r",                   K_R,                   GE(8),   NO_OBJ ),
222
223
224
225
226
227
  T1( "s",                   K_S,                   ARGS,    NO_OBJ ),
  T01("v",                   K_V,               CONCAT_ARGS, NO_OBJ ),
  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
  END_OF_TABLE
};

228
229
/** List of tokens allowable in the header part of v2 networkstatus documents.
 */
230
231
232
233
static token_rule_t netstatus_token_table[] = {
  T1( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
  T1( "contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
234
  T1( "dir-signing-key",     K_DIR_SIGNING_KEY,  NO_ARGS,    NEED_KEY_1024 ),
235
  T1( "fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),
236
  T1_START("network-status-version", K_NETWORK_STATUS_VERSION,
237
238
                                                    GE(1),   NO_OBJ ),
  T1( "dir-source",          K_DIR_SOURCE,          GE(3),   NO_OBJ ),
239
  T01("dir-options",         K_DIR_OPTIONS,         ARGS,    NO_OBJ ),
240
  T01("client-versions",     K_CLIENT_VERSIONS, CONCAT_ARGS, NO_OBJ ),
Roger Dingledine's avatar
Roger Dingledine committed
241
  T01("server-versions",     K_SERVER_VERSIONS, CONCAT_ARGS, NO_OBJ ),
242
243
244
245

  END_OF_TABLE
};

246
247
/** List of tokens allowable in the footer of v1/v2 directory/networkstatus
 * footers. */
248
static token_rule_t dir_footer_token_table[] = {
249
  T1("directory-signature", K_DIRECTORY_SIGNATURE, EQ(1), NEED_OBJ ),
250
251
252
  END_OF_TABLE
};

253
/** List of tokens allowable in v1 diectory headers/footers. */
254
255
256
257
static token_rule_t dir_token_table[] = {
  /* don't enforce counts; this is obsolete. */
  T( "network-status",      K_NETWORK_STATUS,      NO_ARGS, NO_OBJ ),
  T( "directory-signature", K_DIRECTORY_SIGNATURE, ARGS,    NEED_OBJ ),
258
  T( "recommended-software",K_RECOMMENDED_SOFTWARE,CONCAT_ARGS, NO_OBJ ),
259
260
261
262
  T( "signed-directory",    K_SIGNED_DIRECTORY,    NO_ARGS, NO_OBJ ),

  T( "running-routers",     K_RUNNING_ROUTERS,     ARGS,    NO_OBJ ),
  T( "router-status",       K_ROUTER_STATUS,       ARGS,    NO_OBJ ),
263
  T( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
264
265
266
267
268
269
  T( "opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
  T( "contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
  T( "dir-signing-key",     K_DIR_SIGNING_KEY,     ARGS,    OBJ_OK ),
  T( "fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),

  END_OF_TABLE
270
271
};

272
273
/** List of tokens allowable in the footer of v1/v2 directory/networkstatus
 * footers. */
274
275
#define CERTIFICATE_MEMBERS                                                  \
  T1("dir-key-certificate-version", K_DIR_KEY_CERTIFICATE_VERSION,           \
Roger Dingledine's avatar
Roger Dingledine committed
276
                                                     GE(1),       NO_OBJ ),  \
277
278
279
280
281
282
283
284
285
286
287
288
289
  T1("dir-identity-key", K_DIR_IDENTITY_KEY,         NO_ARGS,     NEED_KEY ),\
  T1("dir-key-published",K_DIR_KEY_PUBLISHED,        CONCAT_ARGS, NO_OBJ),   \
  T1("dir-key-expires",  K_DIR_KEY_EXPIRES,          CONCAT_ARGS, NO_OBJ),   \
  T1("dir-signing-key",  K_DIR_SIGNING_KEY,          NO_ARGS,     NEED_KEY ),\
  T1("dir-key-certification", K_DIR_KEY_CERTIFICATION,                       \
                                                     NO_ARGS,     NEED_OBJ),

static token_rule_t dir_key_certificate_table[] = {
  CERTIFICATE_MEMBERS
  T1("fingerprint",      K_FINGERPRINT,              CONCAT_ARGS, NO_OBJ ),
  END_OF_TABLE
};

290
static token_rule_t networkstatus_vote_token_table[] = {
291
292
293
294
  T1("network-status-version", K_NETWORK_STATUS_VERSION,
                                                   GE(1),       NO_OBJ ),
  T1("vote-status",            K_VOTE_STATUS,      GE(1),       NO_OBJ ),
  T1("published",              K_PUBLISHED,        CONCAT_ARGS, NO_OBJ ),
295
296
  T1("valid-after",            K_VALID_AFTER,      CONCAT_ARGS, NO_OBJ ),
  T1("fresh-until",            K_FRESH_UNTIL,      CONCAT_ARGS, NO_OBJ ),
297
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),
298
  T1("voting-delay",           K_VOTING_DELAY,     GE(2),       NO_OBJ ),
299
  T1("known-flags",            K_KNOWN_FLAGS,      ARGS,        NO_OBJ ),
300
301
302
303
304
305
  T( "fingerprint",            K_FINGERPRINT,      CONCAT_ARGS, NO_OBJ ),

  CERTIFICATE_MEMBERS

  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
  T1( "contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
306
  T1( "dir-source",          K_DIR_SOURCE,      GE(6),       NO_OBJ ),
307
308
309
310
311
312
  T1( "known-flags",         K_KNOWN_FLAGS,     CONCAT_ARGS, NO_OBJ ),
  T01("client-versions",     K_CLIENT_VERSIONS, CONCAT_ARGS, NO_OBJ ),
  T01("server-versions",     K_SERVER_VERSIONS, CONCAT_ARGS, NO_OBJ ),

  END_OF_TABLE
};
313
static token_rule_t networkstatus_consensus_token_table[] = {
314
315
316
  T1("network-status-version", K_NETWORK_STATUS_VERSION,
                                                   GE(1),       NO_OBJ ),
  T1("vote-status",            K_VOTE_STATUS,      GE(1),       NO_OBJ ),
317
318
  T1("valid-after",            K_VALID_AFTER,      CONCAT_ARGS, NO_OBJ ),
  T1("fresh-until",            K_FRESH_UNTIL,      CONCAT_ARGS, NO_OBJ ),
319
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),
320
  T1("voting-delay",           K_VOTING_DELAY,     GE(2),       NO_OBJ ),
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335

  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),

  T1N("dir-source",          K_DIR_SOURCE,          GE(3),   NO_OBJ ),
  T1N("contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
  T1N("vote-digest",         K_VOTE_DIGEST,         GE(1),   NO_OBJ ),

  T1( "known-flags",         K_KNOWN_FLAGS,     CONCAT_ARGS, NO_OBJ ),

  T01("client-versions",     K_CLIENT_VERSIONS, CONCAT_ARGS, NO_OBJ ),
  T01("server-versions",     K_SERVER_VERSIONS, CONCAT_ARGS,    NO_OBJ ),

  END_OF_TABLE
};

336
static token_rule_t networkstatus_vote_footer_token_table[] = {
337
338
339
  T(  "directory-signature", K_DIRECTORY_SIGNATURE, GE(2),   NEED_OBJ ),
  END_OF_TABLE
};
340

341
342
#undef T

343
344
/* static function prototypes */
static int router_add_exit_policy(routerinfo_t *router,directory_token_t *tok);
345
static addr_policy_t *router_parse_addr_policy(directory_token_t *tok);
346
347
static addr_policy_t *router_parse_addr_policy_private(directory_token_t *tok);

348
static int router_get_hash_impl(const char *s, char *digest,
349
350
                                const char *start_str, const char *end_str,
                                char end_char);
351
352
353
354
355
static void token_free(directory_token_t *tok);
static smartlist_t *find_all_exitpolicy(smartlist_t *s);
static directory_token_t *find_first_by_keyword(smartlist_t *s,
                                                directory_keyword keyword);
static int tokenize_string(const char *start, const char *end,
356
                           smartlist_t *out,
357
                           token_rule_t *table);
358
static directory_token_t *get_next_token(const char **s,
359
                                         const char *eos,
360
361
362
363
364
365
                                         token_rule_t *table);
static int check_signature_token(const char *digest,
                                 directory_token_t *tok,
                                 crypto_pk_env_t *pkey,
                                 int check_authority,
                                 const char *doctype);
366
static crypto_pk_env_t *find_dir_signing_key(const char *str, const char *eos);
367
static int tor_version_same_series(tor_version_t *a, tor_version_t *b);
368
369

/** Set <b>digest</b> to the SHA-1 digest of the hash of the directory in
370
 * <b>s</b>.  Return 0 on success, -1 on failure.
371
 */
372
373
int
router_get_dir_hash(const char *s, char *digest)
374
375
{
  return router_get_hash_impl(s,digest,
376
                              "signed-directory","\ndirectory-signature",'\n');
377
378
379
}

/** Set <b>digest</b> to the SHA-1 digest of the hash of the first router in
380
 * <b>s</b>. Return 0 on success, -1 on failure.
381
 */
382
383
int
router_get_router_hash(const char *s, char *digest)
384
385
{
  return router_get_hash_impl(s,digest,
386
                              "router ","\nrouter-signature", '\n');
387
388
}

Nick Mathewson's avatar
Nick Mathewson committed
389
/** Set <b>digest</b> to the SHA-1 digest of the hash of the running-routers
390
 * string in <b>s</b>. Return 0 on success, -1 on failure.
Nick Mathewson's avatar
Nick Mathewson committed
391
 */
392
393
int
router_get_runningrouters_hash(const char *s, char *digest)
394
395
{
  return router_get_hash_impl(s,digest,
396
                              "network-status","\ndirectory-signature", '\n');
397
398
}

399
400
/** Set <b>digest</b> to the SHA-1 digest of the hash of the network-status
 * string in <b>s</b>.  Return 0 on success, -1 on failure. */
401
402
403
404
int
router_get_networkstatus_v2_hash(const char *s, char *digest)
{
  return router_get_hash_impl(s,digest,
405
406
407
408
409
410
411
412
413
414
415
416
                              "network-status-version","\ndirectory-signature",
                              '\n');
}

/** Set <b>digest</b> to the SHA-1 digest of the hash of the network-status
 * string in <b>s</b>.  Return 0 on success, -1 on failure. */
int
router_get_networkstatus_v3_hash(const char *s, char *digest)
{
  return router_get_hash_impl(s,digest,
                              "network-status-version","\ndirectory-signature",
                              ' ');
417
418
}

419
420
/** Set <b>digest</b> to the SHA-1 digest of the hash of the extrainfo
 * string in <b>s</b>.  Return 0 on success, -1 on failure. */
421
422
423
int
router_get_extrainfo_hash(const char *s, char *digest)
{
424
  return router_get_hash_impl(s,digest,"extra-info","\nrouter-signature",'\n');
425
426
}

427
428
429
430
431
432
433
434
435
436
437
/** Helper: used to generate signatures for routers, directories and
 * network-status objects.  Given a digest in <b>digest</b> and a secret
 * <b>private_key</b>, generate an PKCS1-padded signature, BASE64-encode it,
 * surround it with -----BEGIN/END----- pairs, and write it to the
 * <b>buf_len</b>-byte buffer at <b>buf</b>.  Return 0 on success, -1 on
 * failure.
 */
int
router_append_dirobj_signature(char *buf, size_t buf_len, const char *digest,
                               crypto_pk_env_t *private_key)
{
438
  char *signature;
439
440
  int i;

441
  signature = tor_malloc(crypto_pk_keysize(private_key));
442
443
  if (crypto_pk_private_sign(private_key, signature, digest, DIGEST_LEN) < 0) {

444
    log_warn(LD_BUG,"Couldn't sign digest.");
445
    goto err;
446
447
448
449
450
451
  }
  if (strlcat(buf, "-----BEGIN SIGNATURE-----\n", buf_len) >= buf_len)
    goto truncated;

  i = strlen(buf);
  if (base64_encode(buf+i, buf_len-i, signature, 128) < 0) {
452
    log_warn(LD_BUG,"couldn't base64-encode signature");
453
    tor_free(buf);
454
    goto err;
455
456
457
458
459
  }

  if (strlcat(buf, "-----END SIGNATURE-----\n", buf_len) >= buf_len)
    goto truncated;

460
  tor_free(signature);
461
  return 0;
462

463
 truncated:
464
  log_warn(LD_BUG,"tried to exceed string length.");
465
466
 err:
  tor_free(signature);
467
468
469
  return -1;
}

470
471
472
473
474
475
476
477
/** Return VS_RECOMMENDED if <b>myversion</b> is contained in
 * <b>versionlist</b>.  Else, return VS_OLD if every member of
 * <b>versionlist</b> is newer than <b>myversion</b>.  Else, return
 * VS_NEW_IN_SERIES if there is at least one member of <b>versionlist</b> in
 * the same series (major.minor.micro) as <b>myversion</b>, but no such member
 * is newer than <b>myversion.</b>.  Else, return VS_NEW if every memeber of
 * <b>versionlist</b> is older than <b>myversion</b>.  Else, return
 * VS_UNRECOMMENDED.
478
 *
479
480
 * (versionlist is a comma-separated list of version strings,
 * optionally prefixed with "Tor".  Versions that can't be parsed are
481
 * ignored.)
482
 */
483
484
485
version_status_t
tor_version_is_obsolete(const char *myversion, const char *versionlist)
{
486
  tor_version_t mine, other;
487
488
489
  int found_newer = 0, found_older = 0, found_newer_in_series = 0,
    found_any_in_series = 0, r, same;
  version_status_t ret = VS_UNRECOMMENDED;
490
  smartlist_t *version_sl;
491

492
493
  log_debug(LD_CONFIG,"Checking whether version '%s' is in '%s'",
            myversion, versionlist);
494

495
  if (tor_version_parse(myversion, &mine)) {
496
    log_err(LD_BUG,"I couldn't parse my own version (%s)", myversion);
497
498
    tor_assert(0);
  }
499
500
  version_sl = smartlist_create();
  smartlist_split_string(version_sl, versionlist, ",", SPLIT_SKIP_SPACE, 0);
501

502
503
  SMARTLIST_FOREACH(version_sl, const char *, cp, {
    if (!strcmpstart(cp, "Tor "))
504
505
506
507
508
      cp += 4;

    if (tor_version_parse(cp, &other)) {
      /* Couldn't parse other; it can't be a match. */
    } else {
509
510
511
      same = tor_version_same_series(&mine, &other);
      if (same)
        found_any_in_series = 1;
512
513
      r = tor_version_compare(&mine, &other);
      if (r==0) {
514
        ret = VS_RECOMMENDED;
515
        goto done;
516
517
      } else if (r<0) {
        found_newer = 1;
518
519
        if (same)
          found_newer_in_series = 1;
520
521
      } else if (r>0) {
        found_older = 1;
522
523
      }
    }
524
525
  });

526
  /* We didn't find the listed version. Is it new or old? */
527
  if (found_any_in_series && !found_newer_in_series && found_newer) {
528
529
530
531
532
    ret = VS_NEW_IN_SERIES;
  } else if (found_newer && !found_older) {
    ret = VS_OLD;
  } else if (found_older && !found_newer) {
    ret = VS_NEW;
533
  } else {
534
    ret = VS_UNRECOMMENDED;
535
  }
536
537
538
539
540

 done:
  SMARTLIST_FOREACH(version_sl, char *, version, tor_free(version));
  smartlist_free(version_sl);
  return ret;
541
542
}

543
544
545
546
547
548
549
550
551
552
553
/** Return the combined status of the current version, given that we know of
 * one set of networkstatuses that give us status <b>a</b>, and another that
 * gives us status <b>b</b>.
 *
 * For example, if one authority thinks that we're NEW, and another thinks
 * we're OLD, we're simply UNRECOMMENDED.
 *
 * This function does not handle calculating whether we're RECOMMENDED; that
 * follows a simple majority rule.  This function simply calculates *why*
 * we're not recommended (if we're not).
 */
554
555
version_status_t
version_status_join(version_status_t a, version_status_t b)
556
{
557
558
559
560
561
562
563
564
565
566
567
568
569
570
  if (a == b)
    return a;
  else if (a == VS_UNRECOMMENDED || b == VS_UNRECOMMENDED)
    return VS_UNRECOMMENDED;
  else if (a == VS_RECOMMENDED)
    return b;
  else if (b == VS_RECOMMENDED)
    return a;
  /* Okay.  Neither is 'recommended' or 'unrecommended', and they differ. */
  else if (a == VS_OLD || b == VS_OLD)
    return VS_UNRECOMMENDED;
  /* One is VS_NEW, the other is VS_NEW_IN_SERIES */
  else
    return VS_NEW_IN_SERIES;
571
}
572

573
574
/** Read a signed directory from <b>str</b>.  If it's well-formed, return 0.
 * Otherwise, return -1.  If we're a directory cache, cache it.
575
 */
576
577
int
router_parse_directory(const char *str)
578
579
{
  directory_token_t *tok;
580
581
  char digest[DIGEST_LEN];
  time_t published_on;
582
  int r;
583
  const char *end, *cp;
584
  smartlist_t *tokens = NULL;
585
  crypto_pk_env_t *declared_key = NULL;
586

587
588
  /* XXXX This could be simplified a lot, but it will all go away
   * once pre-0.1.1.8 is obsolete, and for now it's better not to
Roger Dingledine's avatar
Roger Dingledine committed
589
   * touch it. */
590

591
  if (router_get_dir_hash(str, digest)) {
592
    log_warn(LD_DIR, "Unable to compute digest of directory");
593
594
    goto err;
  }
595
  log_debug(LD_DIR,"Received directory hashes to %s",hex_str(digest,4));
596

597
598
599
600
601
  /* Check signature first, before we try to tokenize. */
  cp = str;
  while (cp && (end = strstr(cp+1, "\ndirectory-signature")))
    cp = end;
  if (cp == str || !cp) {
602
    log_warn(LD_DIR, "No signature found on directory."); goto err;
603
604
605
  }
  ++cp;
  tokens = smartlist_create();
606
  if (tokenize_string(cp,strchr(cp,'\0'),tokens,dir_token_table)) {
607
    log_warn(LD_DIR, "Error tokenizing directory signature"); goto err;
608
609
  }
  if (smartlist_len(tokens) != 1) {
610
    log_warn(LD_DIR, "Unexpected number of tokens in signature"); goto err;
611
  }
612
  tok=smartlist_get(tokens,0);
613
  if (tok->tp != K_DIRECTORY_SIGNATURE) {
614
    log_warn(LD_DIR,"Expected a single directory signature"); goto err;
615
  }
616
  declared_key = find_dir_signing_key(str, str+strlen(str));
617
  note_crypto_pk_op(VERIFY_DIR);
618
  if (check_signature_token(digest, tok, declared_key, 1, "directory")<0)
619
    goto err;
620

621
  SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
622
623
624
625
  smartlist_free(tokens);
  tokens = NULL;

  /* Now try to parse the first part of the directory. */
626
627
628
629
630
631
632
633
634
  if ((end = strstr(str,"\nrouter "))) {
    ++end;
  } else if ((end = strstr(str, "\ndirectory-signature"))) {
    ++end;
  } else {
    end = str + strlen(str);
  }

  tokens = smartlist_create();
635
  if (tokenize_string(str,end,tokens,dir_token_table)) {
636
    log_warn(LD_DIR, "Error tokenizing directory"); goto err;
637
638
  }

639
640
  tok = find_first_by_keyword(tokens, K_PUBLISHED);
  tor_assert(tok);
641
642
  tor_assert(tok->n_args == 1);

643
  if (parse_iso_time(tok->args[0], &published_on) < 0) {
644
645
646
     goto err;
  }

647
648
  /* Now that we know the signature is okay, and we have a
   * publication time, cache the directory. */
649
  if (get_options()->DirPort && !authdir_mode_v1(get_options()))
650
    dirserv_set_cached_directory(str, published_on, 0);
651

652
653
654
655
656
  r = 0;
  goto done;
 err:
  r = -1;
 done:
657
  if (declared_key) crypto_free_pk_env(declared_key);
658
  if (tokens) {
659
    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
660
661
662
663
664
    smartlist_free(tokens);
  }
  return r;
}

665
666
667
/** Read a signed router status statement from <b>str</b>.  If it's
 * well-formed, return 0.  Otherwise, return -1.  If we're a directory cache,
 * cache it.*/
668
669
int
router_parse_runningrouters(const char *str)
670
671
672
673
{
  char digest[DIGEST_LEN];
  directory_token_t *tok;
  time_t published_on;
674
  int r = -1;
675
  crypto_pk_env_t *declared_key = NULL;
676
  smartlist_t *tokens = NULL;
677
  const char *eos = str + strlen(str);
678
679

  if (router_get_runningrouters_hash(str, digest)) {
680
    log_warn(LD_DIR, "Unable to compute digest of running-routers");
681
682
683
    goto err;
  }
  tokens = smartlist_create();
684
  if (tokenize_string(str,eos,tokens,dir_token_table)) {
685
    log_warn(LD_DIR, "Error tokenizing running-routers"); goto err;
686
687
688
  }
  tok = smartlist_get(tokens,0);
  if (tok->tp != K_NETWORK_STATUS) {
689
    log_warn(LD_DIR, "Network-status starts with wrong token");
690
691
692
    goto err;
  }

693
694
  tok = find_first_by_keyword(tokens, K_PUBLISHED);
  tor_assert(tok);
695
  tor_assert(tok->n_args == 1);
696
  if (parse_iso_time(tok->args[0], &published_on) < 0) {
697
698
699
     goto err;
  }
  if (!(tok = find_first_by_keyword(tokens, K_DIRECTORY_SIGNATURE))) {
700
    log_warn(LD_DIR, "Missing signature on running-routers");
701
702
    goto err;
  }
703
  declared_key = find_dir_signing_key(str, eos);
704
  note_crypto_pk_op(VERIFY_DIR);
705
706
  if (check_signature_token(digest, tok, declared_key, 1, "running-routers")
      < 0)
707
708
    goto err;

709
710
  /* Now that we know the signature is okay, and we have a
   * publication time, cache the list. */
711
  if (get_options()->DirPort && !authdir_mode_v1(get_options()))
712
713
714
    dirserv_set_cached_directory(str, published_on, 1);

  r = 0;
715
 err:
716
  if (declared_key) crypto_free_pk_env(declared_key);
717
  if (tokens) {
718
    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
719
720
    smartlist_free(tokens);
  }
721
  return r;
722
723
}

724
725
726
/** Given a directory or running-routers string in <b>str</b>, try to
 * find the its dir-signing-key token (if any).  If this token is
 * present, extract and return the key.  Return NULL on failure. */
727
static crypto_pk_env_t *
728
find_dir_signing_key(const char *str, const char *eos)
729
730
731
732
{
  const char *cp;
  directory_token_t *tok;
  crypto_pk_env_t *key = NULL;
733
734
  tor_assert(str);
  tor_assert(eos);
735
736

  /* Is there a dir-signing-key in the directory? */
737
  cp = tor_memstr(str, eos-str, "\nopt dir-signing-key");
738
  if (!cp)
739
    cp = tor_memstr(str, eos-str, "\ndir-signing-key");
740
741
742
743
  if (!cp)
    return NULL;
  ++cp; /* Now cp points to the start of the token. */

744
  tok = get_next_token(&cp, eos, dir_token_table);
745
  if (!tok) {
746
    log_warn(LD_DIR, "Unparseable dir-signing-key token");
747
748
749
    return NULL;
  }
  if (tok->tp != K_DIR_SIGNING_KEY) {
750
    log_warn(LD_DIR, "Dir-signing-key token did not parse as expected");
751
752
753
754
755
756
757
    return NULL;
  }

  if (tok->key) {
    key = tok->key;
    tok->key = NULL; /* steal reference. */
  } else {
758
    log_warn(LD_DIR, "Dir-signing-key token contained no key");
759
760
761
762
763
764
765
766
767
    return NULL;
  }

  token_free(tok);
  return key;
}

/** Return true iff <b>key</b> is allowed to sign directories.
 */
768
769
static int
dir_signing_key_is_trusted(crypto_pk_env_t *key)
770
771
772
773
{
  char digest[DIGEST_LEN];
  if (!key) return 0;
  if (crypto_pk_get_digest(key, digest) < 0) {
774
    log_warn(LD_DIR, "Error computing dir-signing-key digest");
775
776
    return 0;
  }
777
  if (!router_digest_is_trusted_dir(digest)) {
778
    log_warn(LD_DIR, "Listed dir-signing-key is not trusted");
779
780
781
782
783
    return 0;
  }
  return 1;
}

784
785
786
787
788
/** Check whether the object body of the token in <b>tok</b> has a good
 * signature for <b>digest</b> using key <b>pkey</b>.  If
 * <b>check_authority</b> is set, make sure that <b>pkey</b> is the key of a
 * directory authority.  Use <b>doctype</b> as the type of the document when
 * generating log messages.  Return 0 on success, negative on failure.
789
 */
790
static int
791
792
793
794
795
check_signature_token(const char *digest,
                      directory_token_t *tok,
                      crypto_pk_env_t *pkey,
                      int check_authority,
                      const char *doctype)
796
{
797
  char *signed_digest;
798

799
800
801
802
803
804
805
806
  tor_assert(pkey);
  tor_assert(tok);
  tor_assert(digest);
  tor_assert(doctype);

  if (check_authority && !dir_signing_key_is_trusted(pkey)) {
    log_warn(LD_DIR, "Key on %s did not come from an authority; rejecting",
             doctype);
807
    return -1;
808
  }
809

810
  if (strcmp(tok->object_type, "SIGNATURE")) {
811
    log_warn(LD_DIR, "Bad object type on %s signature", doctype);
812
    return -1;
813
  }
814

815
  signed_digest = tor_malloc(tok->object_size);
816
  if (crypto_pk_public_checksig(pkey, signed_digest, tok->object_body,
817
                                tok->object_size)
818
819
      != DIGEST_LEN) {
    log_warn(LD_DIR, "Error reading %s: invalid signature.", doctype);
820
    tor_free(signed_digest);
821
822
    return -1;
  }
823
  log_debug(LD_DIR,"Signed %s hash starts %s", doctype,
824
            hex_str(signed_digest,4));
825
  if (memcmp(digest, signed_digest, DIGEST_LEN)) {
826
    log_warn(LD_DIR, "Error reading %s: signature does not match.", doctype);
827
    tor_free(signed_digest);
828
    return -1;
829
  }
830
  tor_free(signed_digest);
831
  return 0;
832
833
}

834
/** Given a string *<b>s</b> containing a concatenated sequence of router
835
836
837
838
 * descriptors (or extra-info documents if <b>is_extrainfo</b> is set), parses
 * them and stores the result in <b>dest</b>.  All routers are marked running
 * and valid.  Advances *s to a point immediately following the last router
 * entry.  Ignore any trailing router entries that are not complete.
839
840
841
842
843
844
 *
 * If <b>saved_location</b> isn't SAVED_IN_CACHE, make a local copy of each
 * descriptor in the signed_descriptor_body field of each routerinfo_t.  If it
 * isn't SAVED_NOWHERE, remember the offset of each descriptor.
 *
 * Returns 0 on success and -1 on failure.
845
846
 */
int
847
848
router_parse_list_from_string(const char **s, const char *eos,
                              smartlist_t *dest,
849
                              saved_location_t saved_location,
850
                              int want_extrainfo)
851
852
{
  routerinfo_t *router;
853
854
855
  extrainfo_t *extrainfo;
  signed_descriptor_t *signed_desc;
  void *elt;
856
857
  const char *end, *start;
  int have_extrainfo;
858

859
860
  tor_assert(s);
  tor_assert(*s);
861
  tor_assert(dest);
862

863
  start = *s;
864
865
866
867
868
  if (!eos)
    eos = *s + strlen(*s);

  tor_assert(eos >= *s);

869
  while (1) {
870
871
872
873
    *s = eat_whitespace_eos(*s, eos);
    if ((eos - *s) < 32) /* make sure it's long enough. */
      break;

874
    /* Don't start parsing the rest of *s unless it contains a router. */
875
876
877
878
    if (strcmpstart(*s, "extra-info ")==0) {
      have_extrainfo = 1;
    } else  if (strcmpstart(*s, "router ")==0) {
      have_extrainfo = 0;
879
    } else {
880
      /* skip junk. */
881
882
      const char *ei = tor_memstr(*s, eos-*s, "\nextra-info ");
      const char *ri = tor_memstr(*s, eos-*s, "\nrouter ");
883
884
885
886
887
888
889
      if (ri && (!ei || ri < ei)) {
        have_extrainfo = 0;
        *s = ri + 1;
      } else if (ei) {
        have_extrainfo = 1;
        *s = ei + 1;
      } else {
890
        break;
891
      }
892
    }
893
    end = tor_memstr(*s, eos-*s, "\nrouter-signature");
894
    if (end)
895
      end = tor_memstr(end, eos-end, "\n-----END SIGNATURE-----\n");
896
897
    if (end)
      end += strlen("\n-----END SIGNATURE-----\n");
898

899
900
    if (!end)
      break;
901

902
903
    elt = NULL;

904
    if (have_extrainfo && want_extrainfo) {
905
      routerlist_t *rl = router_get_routerlist();
906
      /* XXXX020 fix this cast to digestmap_t* */
907
908
      extrainfo = extrainfo_parse_entry_from_string(*s, end,
                                       saved_location != SAVED_IN_CACHE,
909
                                       (digestmap_t*)rl->identity_map);
910
911
912
913
      if (extrainfo) {
        signed_desc = &extrainfo->cache_info;
        elt = extrainfo;
      }
914
    } else if (!have_extrainfo && !want_extrainfo) {
915
916
      router = router_parse_entry_from_string(*s, end,
                                          saved_location != SAVED_IN_CACHE);
917
918
919
920
921
922
      if (router) {
        signed_desc = &router->cache_info;
        elt = router;
      }
    }
    if (!elt) {
923
      *s = end;
924
925
      continue;
    }
926
    if (saved_location != SAVED_NOWHERE) {
927
928
      signed_desc->saved_location = saved_location;
      signed_desc->saved_offset = *s - start;
929
    }
930
    *s = end;
931
    smartlist_add(dest, elt);
932
933
934
935
936
  }

  return 0;
}

937
938
939
940
941
942
943
944
/* For debugging: define to count every descriptor digest we've seen so we
 * know if we need to try harder to avoid duplicate verifies. */
#undef COUNT_DISTINCT_DIGESTS

#ifdef COUNT_DISTINCT_DIGESTS
static digestmap_t *verified_digests = NULL;
#endif

945
946
947
948
/** Log the total count of the number of distinct router digests we've ever
 * verified.  When compared to the number of times we've verified routerdesc
 * signatures <i>in toto</i>, this will tell us if we're doing too much
 * multiple-verification. */
949
void
950
dump_distinct_digest_count(int severity)
951
{
952
953
954
#ifdef COUNT_DISTINCT_DIGESTS
  if (!verified_digests)
    verified_digests = digestmap_new();
955
  log(severity, LD_GENERAL, "%d *distinct* router digests verified",
956
957
958
959
      digestmap_size(verified_digests));
#else
  (void)severity; /* suppress "unused parameter" warning */
#endif
960
961
}

962
963
/** Helper function: reads a single router entry from *<b>s</b> ...
 * *<b>end</b>.  Mallocs a new router and returns it if all goes well, else
964
965
966
 * returns NULL.  If <b>cache_copy</b> is true, duplicate the contents of
 * s through end into the signed_descriptor_body of the resulting
 * routerinfo_t.
967
 */
968
routerinfo_t *
969
970
router_parse_entry_from_string(const char *s, const char *end,
                               int cache_copy)
971
{
972
973
974
975
  routerinfo_t *router = NULL;
  char digest[128];
  smartlist_t *tokens = NULL, *exit_policy_tokens = NULL;
  directory_token_t *tok;
976
  struct in_addr in;
977
978
979
980
981

  if (!end) {
    end = s + strlen(s);
  }

982
983
984
985
  /* point 'end' to a point immediately after the final newline. */
  while (end > s+2 && *(end-1) == '\n' && *(end-2) == '\n')
    --end;

986
  if (router_get_router_hash(s, digest) < 0) {
987
    log_warn(LD_DIR, "Couldn't compute router hash.");
988
989
990
    return NULL;
  }
  tokens = smartlist_create();