routerparse.c 75.7 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
70
71
72
73
74

  K_DIR_KEY_CERTIFICATE_VERSION,
  K_DIR_IDENTITY_KEY,
  K_DIR_KEY_PUBLISHED,
  K_DIR_KEY_EXPIRES,
  K_DIR_KEY_CERTIFICATION,

  K_VOTE_STATUS,
  K_VALID_UNTIL,
  K_KNOWN_FLAGS,
  K_VOTE_DIGEST,
  K_CONSENSUS_DIGEST,

75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
  _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]-----*/
93
  size_t object_size;          /**< Bytes in object_body */
94
95
  char *object_body;           /**< Contents of object, base64-decoded. */
  crypto_pk_env_t *key;        /**< For public keys only. */
96
  char *error;                 /**< For _ERR tokens only. */
97
98
99
100
101
102
103
104
} 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 {
105
106
107
108
109
  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. */
110
111
} obj_syntax;

112
113
114
115
#define AT_START 1
#define AT_END 1

/** Determines the parsing rules for a single token type. */
116
typedef struct token_rule_t {
117
118
119
120
121
122
123
124
125
126
127
128
  /** 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. */
129
  obj_syntax os;
130
131
132
133
134
135
136
  /** 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;
137
138
} token_rule_t;

139
140
141
142
143
144
/*
 * 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.
 *
 */
145

146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/** 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 */
#define T1_START(s,t,a,o)   { s, t, a, o, 1, 1, 0, AT_START }
/** An item that must appear exactly once, at the end of the document */
#define T1_END(s,t,a,o)   { s, t, a, o, 1, 1, 0, AT_END }
/** 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. */
164
#define ARGS        0,INT_MAX,0
165
/* Argument multiplicity: no arguments. */
166
#define NO_ARGS     0,0,0
167
/* Argument multiplicity: concatenate all arguments. */
168
#define CONCAT_ARGS 1,1,1
169
/* Argument multiplicity: at least <b>n</b> arguments. */
170
#define GE(n)       n,INT_MAX,0
171
/* Argument multiplicity: exactly <b>n</b> arguments. */
172
173
#define EQ(n)       n,n,0

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

  T01("family",              K_FAMILY,              ARGS,    NO_OBJ ),
193
  T01("caches-extra-info",   K_CACHES_EXTRA_INFO,   NO_ARGS, NO_OBJ ),
194
195
196
  T01("eventdns",            K_EVENTDNS,            ARGS,    NO_OBJ ),

  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
197
  T1( "bandwidth",           K_BANDWIDTH,           GE(3),   NO_OBJ ),
198
199
200
201

  END_OF_TABLE
};

202
/** List of tokens allowable in extra-info documents. */
203
204
205
206
207
208
static token_rule_t extrainfo_token_table[] = {
  T1( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
  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 ),
209
  T1( "extra-info",          K_EXTRA_INFO,          GE(2),   NO_OBJ ),
210
211
212
213

  END_OF_TABLE
};

214
215
/** List of tokens allowable in the body part of v2 and v3 networkstatus
 * documents. */
216
static token_rule_t rtrstatus_token_table[] = {
217
  T1( "r",                   K_R,                   GE(8),    NO_OBJ ),
218
219
220
221
222
223
  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
};

224
225
/** List of tokens allowable in the header part of v2 networkstatus documents.
 */
226
227
228
229
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 ),
230
  /* XXXX should dir-signing-key really have ARGS? */
231
  T1( "dir-signing-key",     K_DIR_SIGNING_KEY,     ARGS,    NEED_KEY_1024 ),
232
233
  T1( "fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),
  T1( "network-status-version", K_NETWORK_STATUS_VERSION,
234
235
                                                    GE(1),   NO_OBJ ),
  T1( "dir-source",          K_DIR_SOURCE,          GE(3),   NO_OBJ ),
236
  T01("dir-options",         K_DIR_OPTIONS,         ARGS,    NO_OBJ ),
237
238
  T01("client-versions",     K_CLIENT_VERSIONS, CONCAT_ARGS, NO_OBJ ),
  T01("server-versions",     K_SERVER_VERSIONS, CONCAT_ARGS,    NO_OBJ ),
239
240
241
242

  END_OF_TABLE
};

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

250
/** List of tokens allowable in v1 diectory headers/footers. */
251
252
253
254
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 ),
255
  T( "recommended-software",K_RECOMMENDED_SOFTWARE,CONCAT_ARGS, NO_OBJ ),
256
257
258
259
  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 ),
260
  T( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
261
262
263
264
265
266
  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
267
268
};

269
270
/** List of tokens allowable in the footer of v1/v2 directory/networkstatus
 * footers. */
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
#define CERTIFICATE_MEMBERS                                                  \
  T1("dir-key-certificate-version", K_DIR_KEY_CERTIFICATE_VERSION,           \
                                                 GE(1),       NO_OBJ ),      \
  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
};

#if 0
/* XXXX This stuff is commented out for now so we can avoid warnings about
 * unused variables. */

static token_rule_t status_vote_table[] = {
  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 ),
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),
  T1("known-flags",            K_KNOWN_FLAGS,      CONCAT_ARGS, NO_OBJ ),
  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 ),
  T1( "dir-source",          K_DIR_SOURCE,      GE(3),       NO_OBJ ),
  T1( "dir-options",         K_DIR_OPTIONS,     ARGS,        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
};

static token_rule_t status_consensus_table[] = {
  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 ),
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),

  CERTIFICATE_MEMBERS

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

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

#if 0
  T1( "dir-options",         K_DIR_OPTIONS,     ARGS,        NO_OBJ ),
  T1( "known-flags",         K_KNOWN_FLAGS,     CONCAT_ARGS, NO_OBJ ),
#endif

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

  END_OF_TABLE
};

static token_rule_t vote_footer_token_table[] = {
  T01("consensus-digest",    K_CONSENSUS_DIGEST,    EQ(1),   NO_OBJ ),
  T(  "directory-signature", K_DIRECTORY_SIGNATURE, GE(2),   NEED_OBJ ),
  END_OF_TABLE
};
#endif

347
348
#undef T

349
350
/* static function prototypes */
static int router_add_exit_policy(routerinfo_t *router,directory_token_t *tok);
351
static addr_policy_t *router_parse_addr_policy(directory_token_t *tok);
352
353
static addr_policy_t *router_parse_addr_policy_private(directory_token_t *tok);

354
355
356
357
358
359
360
static int router_get_hash_impl(const char *s, char *digest,
                                const char *start_str, const char *end_str);
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,
361
                           smartlist_t *out,
362
                           token_rule_t *table);
363
static directory_token_t *get_next_token(const char **s,
364
365
366
367
368
369
                                         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);
370
static crypto_pk_env_t *find_dir_signing_key(const char *str);
371
static int tor_version_same_series(tor_version_t *a, tor_version_t *b);
372
373

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

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

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

403
404
/** 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. */
405
406
407
408
int
router_get_networkstatus_v2_hash(const char *s, char *digest)
{
  return router_get_hash_impl(s,digest,
409
                            "network-status-version","\ndirectory-signature");
410
411
}

412
413
/** 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. */
414
415
416
417
418
419
int
router_get_extrainfo_hash(const char *s, char *digest)
{
  return router_get_hash_impl(s,digest,"extra-info","\nrouter-signature");
}

420
421
422
423
424
425
426
427
428
429
430
/** 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)
{
431
  char *signature;
432
433
  int i;

434
  signature = tor_malloc(crypto_pk_keysize(private_key));
435
436
  if (crypto_pk_private_sign(private_key, signature, digest, DIGEST_LEN) < 0) {

437
    log_warn(LD_BUG,"Couldn't sign digest.");
438
    goto err;
439
440
441
442
443
444
  }
  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) {
445
    log_warn(LD_BUG,"couldn't base64-encode signature");
446
    tor_free(buf);
447
    goto err;
448
449
450
451
452
  }

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

453
  tor_free(signature);
454
  return 0;
455

456
 truncated:
457
  log_warn(LD_BUG,"tried to exceed string length.");
458
459
 err:
  tor_free(signature);
460
461
462
  return -1;
}

463
464
465
466
467
468
469
470
/** 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.
471
 *
472
473
 * (versionlist is a comma-separated list of version strings,
 * optionally prefixed with "Tor".  Versions that can't be parsed are
474
 * ignored.)
475
 */
476
477
478
version_status_t
tor_version_is_obsolete(const char *myversion, const char *versionlist)
{
479
  tor_version_t mine, other;
480
481
482
  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;
483
  smartlist_t *version_sl;
484

485
486
  log_debug(LD_CONFIG,"Checking whether version '%s' is in '%s'",
            myversion, versionlist);
487

488
  if (tor_version_parse(myversion, &mine)) {
489
    log_err(LD_BUG,"I couldn't parse my own version (%s)", myversion);
490
491
    tor_assert(0);
  }
492
493
  version_sl = smartlist_create();
  smartlist_split_string(version_sl, versionlist, ",", SPLIT_SKIP_SPACE, 0);
494

495
496
  SMARTLIST_FOREACH(version_sl, const char *, cp, {
    if (!strcmpstart(cp, "Tor "))
497
498
499
500
501
      cp += 4;

    if (tor_version_parse(cp, &other)) {
      /* Couldn't parse other; it can't be a match. */
    } else {
502
503
504
      same = tor_version_same_series(&mine, &other);
      if (same)
        found_any_in_series = 1;
505
506
      r = tor_version_compare(&mine, &other);
      if (r==0) {
507
        ret = VS_RECOMMENDED;
508
        goto done;
509
510
      } else if (r<0) {
        found_newer = 1;
511
512
        if (same)
          found_newer_in_series = 1;
513
514
      } else if (r>0) {
        found_older = 1;
515
516
      }
    }
517
518
  });

519
  /* We didn't find the listed version. Is it new or old? */
520
  if (found_any_in_series && !found_newer_in_series && found_newer) {
521
522
523
524
525
    ret = VS_NEW_IN_SERIES;
  } else if (found_newer && !found_older) {
    ret = VS_OLD;
  } else if (found_older && !found_newer) {
    ret = VS_NEW;
526
  } else {
527
    ret = VS_UNRECOMMENDED;
528
  }
529
530
531
532
533

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

536
537
538
539
540
541
542
543
544
545
546
/** 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).
 */
547
548
version_status_t
version_status_join(version_status_t a, version_status_t b)
549
{
550
551
552
553
554
555
556
557
558
559
560
561
562
563
  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;
564
}
565

566
567
/** 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.
568
 */
569
570
int
router_parse_directory(const char *str)
571
572
{
  directory_token_t *tok;
573
574
  char digest[DIGEST_LEN];
  time_t published_on;
575
  int r;
576
  const char *end, *cp;
577
  smartlist_t *tokens = NULL;
578
  crypto_pk_env_t *declared_key = NULL;
579

580
581
  /* 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
582
   * touch it. */
583

584
  if (router_get_dir_hash(str, digest)) {
585
    log_warn(LD_DIR, "Unable to compute digest of directory");
586
587
    goto err;
  }
588
  log_debug(LD_DIR,"Received directory hashes to %s",hex_str(digest,4));
589

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

614
  SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
615
616
617
618
  smartlist_free(tokens);
  tokens = NULL;

  /* Now try to parse the first part of the directory. */
619
620
621
622
623
624
625
626
627
  if ((end = strstr(str,"\nrouter "))) {
    ++end;
  } else if ((end = strstr(str, "\ndirectory-signature"))) {
    ++end;
  } else {
    end = str + strlen(str);
  }

  tokens = smartlist_create();
628
  if (tokenize_string(str,end,tokens,dir_token_table)) {
629
    log_warn(LD_DIR, "Error tokenizing directory"); goto err;
630
631
  }

632
633
  tok = find_first_by_keyword(tokens, K_PUBLISHED);
  tor_assert(tok);
634
635
  tor_assert(tok->n_args == 1);

636
  if (parse_iso_time(tok->args[0], &published_on) < 0) {
637
638
639
     goto err;
  }

640
641
  /* Now that we know the signature is okay, and we have a
   * publication time, cache the directory. */
642
  if (get_options()->DirPort && !authdir_mode_v1(get_options()))
643
    dirserv_set_cached_directory(str, published_on, 0);
644

645
646
647
648
649
  r = 0;
  goto done;
 err:
  r = -1;
 done:
650
  if (declared_key) crypto_free_pk_env(declared_key);
651
  if (tokens) {
652
    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
653
654
655
656
657
    smartlist_free(tokens);
  }
  return r;
}

658
659
660
/** 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.*/
661
662
int
router_parse_runningrouters(const char *str)
663
664
665
666
{
  char digest[DIGEST_LEN];
  directory_token_t *tok;
  time_t published_on;
667
  int r = -1;
668
  crypto_pk_env_t *declared_key = NULL;
669
670
671
  smartlist_t *tokens = NULL;

  if (router_get_runningrouters_hash(str, digest)) {
672
    log_warn(LD_DIR, "Unable to compute digest of running-routers");
673
674
675
    goto err;
  }
  tokens = smartlist_create();
676
  if (tokenize_string(str,str+strlen(str),tokens,dir_token_table)) {
677
    log_warn(LD_DIR, "Error tokenizing running-routers"); goto err;
678
679
680
  }
  tok = smartlist_get(tokens,0);
  if (tok->tp != K_NETWORK_STATUS) {
681
    log_warn(LD_DIR, "Network-status starts with wrong token");
682
683
684
    goto err;
  }

685
686
  tok = find_first_by_keyword(tokens, K_PUBLISHED);
  tor_assert(tok);
687
  tor_assert(tok->n_args == 1);
688
  if (parse_iso_time(tok->args[0], &published_on) < 0) {
689
690
691
     goto err;
  }
  if (!(tok = find_first_by_keyword(tokens, K_DIRECTORY_SIGNATURE))) {
692
    log_warn(LD_DIR, "Missing signature on running-routers");
693
694
    goto err;
  }
695
  declared_key = find_dir_signing_key(str);
696
  note_crypto_pk_op(VERIFY_DIR);
697
698
  if (check_signature_token(digest, tok, declared_key, 1, "running-routers")
      < 0)
699
700
    goto err;

701
702
  /* Now that we know the signature is okay, and we have a
   * publication time, cache the list. */
703
  if (get_options()->DirPort && !authdir_mode_v1(get_options()))
704
705
706
    dirserv_set_cached_directory(str, published_on, 1);

  r = 0;
707
 err:
708
  if (declared_key) crypto_free_pk_env(declared_key);
709
  if (tokens) {
710
    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
711
712
    smartlist_free(tokens);
  }
713
  return r;
714
715
}

716
717
718
/** 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. */
719
720
static crypto_pk_env_t *
find_dir_signing_key(const char *str)
721
722
723
724
725
726
727
728
729
730
731
732
733
{
  const char *cp;
  directory_token_t *tok;
  crypto_pk_env_t *key = NULL;

  /* Is there a dir-signing-key in the directory? */
  cp = strstr(str, "\nopt dir-signing-key");
  if (!cp)
    cp = strstr(str, "\ndir-signing-key");
  if (!cp)
    return NULL;
  ++cp; /* Now cp points to the start of the token. */

734
  tok = get_next_token(&cp, dir_token_table);
735
  if (!tok) {
736
    log_warn(LD_DIR, "Unparseable dir-signing-key token");
737
738
739
    return NULL;
  }
  if (tok->tp != K_DIR_SIGNING_KEY) {
740
    log_warn(LD_DIR, "Dir-signing-key token did not parse as expected");
741
742
743
744
745
746
747
    return NULL;
  }

  if (tok->key) {
    key = tok->key;
    tok->key = NULL; /* steal reference. */
  } else {
748
    log_warn(LD_DIR, "Dir-signing-key token contained no key");
749
750
751
752
753
754
755
756
757
    return NULL;
  }

  token_free(tok);
  return key;
}

/** Return true iff <b>key</b> is allowed to sign directories.
 */
758
759
static int
dir_signing_key_is_trusted(crypto_pk_env_t *key)
760
761
762
763
{
  char digest[DIGEST_LEN];
  if (!key) return 0;
  if (crypto_pk_get_digest(key, digest) < 0) {
764
    log_warn(LD_DIR, "Error computing dir-signing-key digest");
765
766
    return 0;
  }
767
  if (!router_digest_is_trusted_dir(digest)) {
768
    log_warn(LD_DIR, "Listed dir-signing-key is not trusted");
769
770
771
772
773
    return 0;
  }
  return 1;
}

774
775
776
777
778
/** 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.
779
 */
780
static int
781
782
783
784
785
check_signature_token(const char *digest,
                      directory_token_t *tok,
                      crypto_pk_env_t *pkey,
                      int check_authority,
                      const char *doctype)
786
{
787
  char *signed_digest;
788

789
790
791
792
793
794
795
796
  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);
797
    return -1;
798
  }
799

800
  if (strcmp(tok->object_type, "SIGNATURE")) {
801
    log_warn(LD_DIR, "Bad object type on %s signature", doctype);
802
    return -1;
803
  }
804

805
  signed_digest = tor_malloc(tok->object_size);
806
  if (crypto_pk_public_checksig(pkey, signed_digest, tok->object_body,
807
                                tok->object_size)
808
809
      != DIGEST_LEN) {
    log_warn(LD_DIR, "Error reading %s: invalid signature.", doctype);
810
811
    return -1;
  }
812
  log_debug(LD_DIR,"Signed %s hash starts %s", doctype,
813
            hex_str(signed_digest,4));
814
  if (memcmp(digest, signed_digest, DIGEST_LEN)) {
815
    log_warn(LD_DIR, "Error reading %s: signature does not match.", doctype);
816
    return -1;
817
  }
818
  return 0;
819
820
}

821
/** Given a string *<b>s</b> containing a concatenated sequence of router
822
823
824
825
 * 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.
826
827
828
829
830
831
 *
 * 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.
832
833
 */
int
834
router_parse_list_from_string(const char **s, smartlist_t *dest,
835
                              saved_location_t saved_location,
836
                              int want_extrainfo)
837
838
{
  routerinfo_t *router;
839
840
841
  extrainfo_t *extrainfo;
  signed_descriptor_t *signed_desc;
  void *elt;
842
843
  const char *end, *start;
  int have_extrainfo;
844

845
846
  tor_assert(s);
  tor_assert(*s);
847
  tor_assert(dest);
848

849
  start = *s;
850
851
852
  while (1) {
    *s = eat_whitespace(*s);
    /* Don't start parsing the rest of *s unless it contains a router. */
853
854
855
856
    if (strcmpstart(*s, "extra-info ")==0) {
      have_extrainfo = 1;
    } else  if (strcmpstart(*s, "router ")==0) {
      have_extrainfo = 0;
857
    } else {
858
859
860
861
862
863
864
865
866
867
      /* skip junk. */
      const char *ei = strstr(*s, "\nextra-info ");
      const char *ri = strstr(*s, "\nrouter ");
      if (ri && (!ei || ri < ei)) {
        have_extrainfo = 0;
        *s = ri + 1;
      } else if (ei) {
        have_extrainfo = 1;
        *s = ei + 1;
      } else {
868
        break;
869
      }
870
    }
871
872
873
874
875
    end = strstr(*s, "\nrouter-signature");
    if (end)
      end = strstr(end, "\n-----END SIGNATURE-----\n");
    if (end)
      end += strlen("\n-----END SIGNATURE-----\n");
876

877
878
    if (!end)
      break;
879

880
    if (have_extrainfo && want_extrainfo) {
881
882
883
884
885
886
      routerlist_t *rl = router_get_routerlist();
      extrainfo = extrainfo_parse_entry_from_string(*s, end,
                                       saved_location != SAVED_IN_CACHE,
                                       rl->identity_map);
      signed_desc = &extrainfo->cache_info;
      elt = extrainfo;
887
    } else if (!have_extrainfo && !want_extrainfo) {
888
889
890
891
      router = router_parse_entry_from_string(*s, end,
                                          saved_location != SAVED_IN_CACHE);
      signed_desc = &router->cache_info;
      elt = router;
892
    } else {
893
      *s = end;
894
895
      continue;
    }
896
    if (saved_location != SAVED_NOWHERE) {
897
898
      signed_desc->saved_location = saved_location;
      signed_desc->saved_offset = *s - start;
899
    }
900
    *s = end;
901
    smartlist_add(dest, elt);
902
903
904
905
906
  }

  return 0;
}

907
908
909
910
911
912
913
914
/* 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

915
916
917
918
/** 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. */
919
void
920
dump_distinct_digest_count(int severity)
921
{
922
923
924
#ifdef COUNT_DISTINCT_DIGESTS
  if (!verified_digests)
    verified_digests = digestmap_new();
925
  log(severity, LD_GENERAL, "%d *distinct* router digests verified",
926
927
928
929
      digestmap_size(verified_digests));
#else
  (void)severity; /* suppress "unused parameter" warning */
#endif
930
931
}

932
933
/** 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
934
935
936
 * 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.
937
 */
938
routerinfo_t *
939
940
router_parse_entry_from_string(const char *s, const char *end,
                               int cache_copy)
941
{
942
943
944
945
  routerinfo_t *router = NULL;
  char digest[128];
  smartlist_t *tokens = NULL, *exit_policy_tokens = NULL;
  directory_token_t *tok;
946
  struct in_addr in;
947
948
949
950
951

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

952
953
954
955
  /* point 'end' to a point immediately after the final newline. */
  while (end > s+2 && *(end-1) == '\n' && *(end-2) == '\n')
    --end;

956
  if (router_get_router_hash(s, digest) < 0) {
957
    log_warn(LD_DIR, "Couldn't compute router hash.");
958
959
960
    return NULL;
  }
  tokens = smartlist_create();
961
  if (tokenize_string(s,end,tokens,routerdesc_token_table)) {
962
    log_warn(LD_DIR, "Error tokeninzing router descriptor.");
Roger Dingledine's avatar
Roger Dingledine committed
963
    goto err;
964
965
966
  }

  if (smartlist_len(tokens) < 2) {
967
    log_warn(LD_DIR, "Impossibly short router descriptor.");
968
969
970
971
972
    goto err;
  }

  tok = smartlist_get(tokens,0);
  if (tok->tp != K_ROUTER) {
973
    log_warn(LD_DIR,"Entry does not start with \"router\"");
974
975
    goto err;
  }
976
  tor_assert(tok->n_args >= 5);
977
978

  router = tor_malloc_zero(sizeof(routerinfo_t));
979
  router->routerlist_index = -1;
980
981
  if (cache_copy)
    router->cache_info.signed_descriptor_body = tor_strndup(s, end-s);
982
983
  router->cache_info.signed_descriptor_len = end-s;
  memcpy(router->cache_info.signed_descriptor_digest, digest, DIGEST_LEN);
984

985
986
987
  router->nickname = tor_strdup(tok->args[0]);
  if (!is_legal_nickname(router->nickname)) {
    log_warn(LD_DIR,"Router nickname is invalid");
988
989
    goto err;
  }
990
991
992
  router->address = tor_strdup(tok->args[1]);
  if (!tor_inet_aton(router->address, &in)) {
    log_warn(LD_DIR,"Router address is not an IP.");
993
    goto err;
994
995
  }
  router->addr = ntohl(in.s_addr);
996

997
998
999
1000
  router->or_port =
    (uint16_t) tor_parse_long(tok->args[2],10,0,65535,NULL,NULL);
  router->dir_port =
    (uint16_t) tor_parse_long(tok->args[4],10,0,65535,NULL,NULL);