routerparse.c 152 KB
Newer Older
1
/* Copyright (c) 2001 Matej Pfajfar.
Roger Dingledine's avatar
Roger Dingledine committed
2
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Karsten Loesing's avatar
Karsten Loesing committed
4
 * Copyright (c) 2007-2009, The Tor Project, Inc. */
5
6
7
8
9
10
11
12
/* See LICENSE for licensing information */

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

#include "or.h"
13
#include "memarea.h"
14
15
16

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

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

66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
  K_DIRREQ_END,
  K_DIRREQ_V2_IPS,
  K_DIRREQ_V3_IPS,
  K_DIRREQ_V2_REQS,
  K_DIRREQ_V3_REQS,
  K_DIRREQ_V2_SHARE,
  K_DIRREQ_V3_SHARE,
  K_DIRREQ_V2_RESP,
  K_DIRREQ_V3_RESP,
  K_DIRREQ_V2_DIR,
  K_DIRREQ_V3_DIR,
  K_DIRREQ_V2_TUN,
  K_DIRREQ_V3_TUN,
  K_ENTRY_END,
  K_ENTRY_IPS,
  K_CELL_END,
  K_CELL_PROCESSED,
  K_CELL_QUEUED,
  K_CELL_TIME,
  K_CELL_CIRCS,
  K_EXIT_END,
  K_EXIT_WRITTEN,
  K_EXIT_READ,
  K_EXIT_OPENED,

91
92
93
94
95
  K_DIR_KEY_CERTIFICATE_VERSION,
  K_DIR_IDENTITY_KEY,
  K_DIR_KEY_PUBLISHED,
  K_DIR_KEY_EXPIRES,
  K_DIR_KEY_CERTIFICATION,
96
  K_DIR_KEY_CROSSCERT,
97
  K_DIR_ADDRESS,
98
99

  K_VOTE_STATUS,
100
101
  K_VALID_AFTER,
  K_FRESH_UNTIL,
102
  K_VALID_UNTIL,
103
104
  K_VOTING_DELAY,

105
  K_KNOWN_FLAGS,
106
  K_PARAMS,
107
108
  K_VOTE_DIGEST,
  K_CONSENSUS_DIGEST,
109
110
  K_ADDITIONAL_DIGEST,
  K_ADDITIONAL_SIGNATURE,
111
  K_CONSENSUS_METHODS,
112
  K_CONSENSUS_METHOD,
113
  K_LEGACY_DIR_KEY,
114

115
  A_PURPOSE,
116
  A_LAST_LISTED,
117
118
  _A_UNKNOWN,

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
  R_RENDEZVOUS_SERVICE_DESCRIPTOR,
  R_VERSION,
  R_PERMANENT_KEY,
  R_SECRET_ID_PART,
  R_PUBLICATION_TIME,
  R_PROTOCOL_VERSIONS,
  R_INTRODUCTION_POINTS,
  R_SIGNATURE,

  R_IPO_IDENTIFIER,
  R_IPO_IP_ADDRESS,
  R_IPO_ONION_PORT,
  R_IPO_ONION_KEY,
  R_IPO_SERVICE_KEY,

134
135
136
137
  C_CLIENT_NAME,
  C_DESCRIPTOR_COOKIE,
  C_CLIENT_KEY,

138
139
140
141
142
  _ERR,
  _EOF,
  _NIL
} directory_keyword;

143
144
145
#define MIN_ANNOTATION A_PURPOSE
#define MAX_ANNOTATION _A_UNKNOWN

146
147
148
149
150
151
/** 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.
152
153
 *
 * This structure is only allocated in memareas; do not allocate it on
154
 * the heap, or token_clear() won't work.
155
156
157
 */
typedef struct directory_token_t {
  directory_keyword tp;        /**< Type of the token. */
158
  int n_args:30;               /**< Number of elements in args */
159
  char **args;                 /**< Array of arguments from keyword line. */
160

161
  char *object_type;           /**< -----BEGIN [object_type]-----*/
162
  size_t object_size;          /**< Bytes in object_body */
163
  char *object_body;           /**< Contents of object, base64-decoded. */
164
165
166

  crypto_pk_env_t *key;        /**< For public keys only.  Heap-allocated. */

167
  char *error;                 /**< For _ERR tokens only. */
168
169
170
171
172
173
174
175
} 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 {
176
177
  NO_OBJ,        /**< No object, ever. */
  NEED_OBJ,      /**< Object is required. */
178
  NEED_SKEY_1024,/**< Object is required, and must be a 1024 bit private key */
179
180
181
  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. */
182
183
} obj_syntax;

184
#define AT_START 1
185
#define AT_END 2
186
187

/** Determines the parsing rules for a single token type. */
188
typedef struct token_rule_t {
189
190
191
192
193
194
195
196
197
198
199
  /** 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;
Nick Mathewson's avatar
Nick Mathewson committed
200
  /** Requirements on object syntax for this item. */
201
  obj_syntax os;
202
203
204
205
206
207
208
  /** 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;
209
  /** True iff this token is an annotation. */
210
  int is_annotation;
211
212
} token_rule_t;

213
214
215
216
217
218
/*
 * 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.
 *
 */
219

220
/** Appears to indicate the end of a table. */
221
#define END_OF_TABLE { NULL, _NIL, 0,0,0, NO_OBJ, 0, INT_MAX, 0, 0 }
222
/** An item with no restrictions: used for obsolete document types */
223
#define T(s,t,a,o)    { s, t, a, o, 0, INT_MAX, 0, 0 }
224
/** An item with no restrictions on multiplicity or location. */
225
#define T0N(s,t,a,o)  { s, t, a, o, 0, INT_MAX, 0, 0 }
226
/** An item that must appear exactly once */
227
#define T1(s,t,a,o)   { s, t, a, o, 1, 1, 0, 0 }
228
/** An item that must appear exactly once, at the start of the document */
229
#define T1_START(s,t,a,o)   { s, t, a, o, 1, 1, AT_START, 0 }
230
/** An item that must appear exactly once, at the end of the document */
231
#define T1_END(s,t,a,o)   { s, t, a, o, 1, 1, AT_END, 0 }
232
/** An item that must appear one or more times */
233
#define T1N(s,t,a,o)  { s, t, a, o, 1, INT_MAX, 0, 0 }
234
/** An item that must appear no more than once */
235
236
#define T01(s,t,a,o)  { s, t, a, o, 0, 1, 0, 0 }
/** An annotation that must appear no more than once */
237
#define A01(s,t,a,o)  { s, t, a, o, 0, 1, 0, 1 }
238
239

/* Argument multiplicity: any number of arguments. */
240
#define ARGS        0,INT_MAX,0
241
/* Argument multiplicity: no arguments. */
242
#define NO_ARGS     0,0,0
243
/* Argument multiplicity: concatenate all arguments. */
244
#define CONCAT_ARGS 1,1,1
245
/* Argument multiplicity: at least <b>n</b> arguments. */
246
#define GE(n)       n,INT_MAX,0
247
/* Argument multiplicity: exactly <b>n</b> arguments. */
248
249
#define EQ(n)       n,n,0

Nick Mathewson's avatar
Nick Mathewson committed
250
/** List of tokens allowable in router descriptors */
251
252
static token_rule_t routerdesc_token_table[] = {
  T0N("reject",              K_REJECT,              ARGS,    NO_OBJ ),
253
  T0N("accept",              K_ACCEPT,              ARGS,    NO_OBJ ),
254
255
256
  T0N("reject6",             K_REJECT6,             ARGS,    NO_OBJ ),
  T0N("accept6",             K_ACCEPT6,             ARGS,    NO_OBJ ),
  T1_START( "router",        K_ROUTER,              GE(5),   NO_OBJ ),
257
258
  T1( "signing-key",         K_SIGNING_KEY,         NO_ARGS, NEED_KEY_1024 ),
  T1( "onion-key",           K_ONION_KEY,           NO_ARGS, NEED_KEY_1024 ),
259
  T1_END( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
260
  T1( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
261
  T01("uptime",              K_UPTIME,              GE(1),   NO_OBJ ),
262
  T01("fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),
263
  T01("hibernating",         K_HIBERNATING,         GE(1),   NO_OBJ ),
264
265
  T01("platform",            K_PLATFORM,        CONCAT_ARGS, NO_OBJ ),
  T01("contact",             K_CONTACT,         CONCAT_ARGS, NO_OBJ ),
266
267
  T01("read-history",        K_READ_HISTORY,        ARGS,    NO_OBJ ),
  T01("write-history",       K_WRITE_HISTORY,       ARGS,    NO_OBJ ),
268
  T01("extra-info-digest",   K_EXTRA_INFO_DIGEST,   GE(1),   NO_OBJ ),
269
  T01("hidden-service-dir",  K_HIDDEN_SERVICE_DIR,  NO_ARGS, NO_OBJ ),
270
  T01("allow-single-hop-exits",K_ALLOW_SINGLE_HOP_EXITS,    NO_ARGS, NO_OBJ ),
271
272

  T01("family",              K_FAMILY,              ARGS,    NO_OBJ ),
273
  T01("caches-extra-info",   K_CACHES_EXTRA_INFO,   NO_ARGS, NO_OBJ ),
274
275
276
  T01("eventdns",            K_EVENTDNS,            ARGS,    NO_OBJ ),

  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
277
  T1( "bandwidth",           K_BANDWIDTH,           GE(3),   NO_OBJ ),
278
  A01("@purpose",            A_PURPOSE,             GE(1),   NO_OBJ ),
279
280
281
282

  END_OF_TABLE
};

283
/** List of tokens allowable in extra-info documents. */
284
static token_rule_t extrainfo_token_table[] = {
285
  T1_END( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
286
287
288
289
  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 ),
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
  T01("dirreq-stats-end",    K_DIRREQ_END,          ARGS,    NO_OBJ ),
  T01("dirreq-v2-ips",       K_DIRREQ_V2_IPS,       ARGS,    NO_OBJ ),
  T01("dirreq-v3-ips",       K_DIRREQ_V3_IPS,       ARGS,    NO_OBJ ),
  T01("dirreq-v2-reqs",      K_DIRREQ_V2_REQS,      ARGS,    NO_OBJ ),
  T01("dirreq-v3-reqs",      K_DIRREQ_V3_REQS,      ARGS,    NO_OBJ ),
  T01("dirreq-v2-share",     K_DIRREQ_V2_SHARE,     ARGS,    NO_OBJ ),
  T01("dirreq-v3-share",     K_DIRREQ_V3_SHARE,     ARGS,    NO_OBJ ),
  T01("dirreq-v2-resp",      K_DIRREQ_V2_RESP,      ARGS,    NO_OBJ ),
  T01("dirreq-v3-resp",      K_DIRREQ_V3_RESP,      ARGS,    NO_OBJ ),
  T01("dirreq-v2-direct-dl", K_DIRREQ_V2_DIR,       ARGS,    NO_OBJ ),
  T01("dirreq-v3-direct-dl", K_DIRREQ_V3_DIR,       ARGS,    NO_OBJ ),
  T01("dirreq-v2-tunneled-dl", K_DIRREQ_V2_TUN,     ARGS,    NO_OBJ ),
  T01("dirreq-v3-tunneled-dl", K_DIRREQ_V3_TUN,     ARGS,    NO_OBJ ),
  T01("entry-stats-end",     K_ENTRY_END,           ARGS,    NO_OBJ ),
  T01("entry-ips",           K_ENTRY_IPS,           ARGS,    NO_OBJ ),
  T01("cell-stats-end",      K_CELL_END,            ARGS,    NO_OBJ ),
  T01("cell-processed-cells", K_CELL_PROCESSED,     ARGS,    NO_OBJ ),
  T01("cell-queued-cells",   K_CELL_QUEUED,         ARGS,    NO_OBJ ),
  T01("cell-time-in-queue",  K_CELL_TIME,           ARGS,    NO_OBJ ),
  T01("cell-circuits-per-decile", K_CELL_CIRCS,     ARGS,    NO_OBJ ),
  T01("exit-stats-end",      K_EXIT_END,            ARGS,    NO_OBJ ),
  T01("exit-kibibytes-written", K_EXIT_WRITTEN,     ARGS,    NO_OBJ ),
  T01("exit-kibibytes-read", K_EXIT_READ,           ARGS,    NO_OBJ ),
  T01("exit-streams-opened", K_EXIT_OPENED,         ARGS,    NO_OBJ ),

315
  T1_START( "extra-info",          K_EXTRA_INFO,          GE(2),   NO_OBJ ),
316
317
318
319

  END_OF_TABLE
};

320
321
/** List of tokens allowable in the body part of v2 and v3 networkstatus
 * documents. */
322
static token_rule_t rtrstatus_token_table[] = {
323
  T01("p",                   K_P,               CONCAT_ARGS, NO_OBJ ),
324
  T1( "r",                   K_R,                   GE(7),   NO_OBJ ),
325
326
  T1( "s",                   K_S,                   ARGS,    NO_OBJ ),
  T01("v",                   K_V,               CONCAT_ARGS, NO_OBJ ),
327
  T01("w",                   K_W,                   ARGS,    NO_OBJ ),
328
  T0N("m",                   K_M,               CONCAT_ARGS, NO_OBJ ),
329
330
331
332
  T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
  END_OF_TABLE
};

333
334
/** List of tokens allowable in the header part of v2 networkstatus documents.
 */
335
336
337
338
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 ),
339
  T1( "dir-signing-key",     K_DIR_SIGNING_KEY,  NO_ARGS,    NEED_KEY_1024 ),
340
  T1( "fingerprint",         K_FINGERPRINT,     CONCAT_ARGS, NO_OBJ ),
341
  T1_START("network-status-version", K_NETWORK_STATUS_VERSION,
342
343
                                                    GE(1),   NO_OBJ ),
  T1( "dir-source",          K_DIR_SOURCE,          GE(3),   NO_OBJ ),
344
  T01("dir-options",         K_DIR_OPTIONS,         ARGS,    NO_OBJ ),
345
  T01("client-versions",     K_CLIENT_VERSIONS, CONCAT_ARGS, NO_OBJ ),
Roger Dingledine's avatar
Roger Dingledine committed
346
  T01("server-versions",     K_SERVER_VERSIONS, CONCAT_ARGS, NO_OBJ ),
347
348
349
350

  END_OF_TABLE
};

351
352
/** List of tokens allowable in the footer of v1/v2 directory/networkstatus
 * footers. */
353
static token_rule_t dir_footer_token_table[] = {
354
  T1("directory-signature", K_DIRECTORY_SIGNATURE, EQ(1), NEED_OBJ ),
355
356
357
  END_OF_TABLE
};

358
/** List of tokens allowable in v1 directory headers/footers. */
359
360
361
362
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 ),
363
  T( "recommended-software",K_RECOMMENDED_SOFTWARE,CONCAT_ARGS, NO_OBJ ),
364
365
366
367
  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 ),
368
  T( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
369
370
371
372
373
374
  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
375
376
};

377
/** List of tokens common to V3 authority certificates and V3 consensuses. */
378
379
#define CERTIFICATE_MEMBERS                                                  \
  T1("dir-key-certificate-version", K_DIR_KEY_CERTIFICATE_VERSION,           \
Roger Dingledine's avatar
Roger Dingledine committed
380
                                                     GE(1),       NO_OBJ ),  \
381
382
383
384
  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 ),\
385
  T01("dir-key-crosscert", K_DIR_KEY_CROSSCERT,       NO_ARGS,    NEED_OBJ ),\
386
  T1("dir-key-certification", K_DIR_KEY_CERTIFICATION,                       \
387
388
                                                     NO_ARGS,     NEED_OBJ), \
  T01("dir-address",     K_DIR_ADDRESS,              GE(1),       NO_OBJ),
389

390
/** List of tokens allowable in V3 authority certificates. */
391
392
393
394
395
396
static token_rule_t dir_key_certificate_table[] = {
  CERTIFICATE_MEMBERS
  T1("fingerprint",      K_FINGERPRINT,              CONCAT_ARGS, NO_OBJ ),
  END_OF_TABLE
};

397
398
/** List of tokens allowable in rendezvous service descriptors */
static token_rule_t desc_token_table[] = {
399
400
  T1_START("rendezvous-service-descriptor", R_RENDEZVOUS_SERVICE_DESCRIPTOR,
           EQ(1), NO_OBJ),
401
402
403
404
405
  T1("version", R_VERSION, EQ(1), NO_OBJ),
  T1("permanent-key", R_PERMANENT_KEY, NO_ARGS, NEED_KEY_1024),
  T1("secret-id-part", R_SECRET_ID_PART, EQ(1), NO_OBJ),
  T1("publication-time", R_PUBLICATION_TIME, CONCAT_ARGS, NO_OBJ),
  T1("protocol-versions", R_PROTOCOL_VERSIONS, EQ(1), NO_OBJ),
406
  T01("introduction-points", R_INTRODUCTION_POINTS, NO_ARGS, NEED_OBJ),
407
  T1_END("signature", R_SIGNATURE, NO_ARGS, NEED_OBJ),
408
409
410
411
412
413
  END_OF_TABLE
};

/** List of tokens allowed in the (encrypted) list of introduction points of
 * rendezvous service descriptors */
static token_rule_t ipo_token_table[] = {
414
  T1_START("introduction-point", R_IPO_IDENTIFIER, EQ(1), NO_OBJ),
415
416
417
418
419
420
421
  T1("ip-address", R_IPO_IP_ADDRESS, EQ(1), NO_OBJ),
  T1("onion-port", R_IPO_ONION_PORT, EQ(1), NO_OBJ),
  T1("onion-key", R_IPO_ONION_KEY, NO_ARGS, NEED_KEY_1024),
  T1("service-key", R_IPO_SERVICE_KEY, NO_ARGS, NEED_KEY_1024),
  END_OF_TABLE
};

422
423
424
425
426
427
428
429
430
/** List of tokens allowed in the (possibly encrypted) list of introduction
 * points of rendezvous service descriptors */
static token_rule_t client_keys_token_table[] = {
  T1_START("client-name", C_CLIENT_NAME, CONCAT_ARGS, NO_OBJ),
  T1("descriptor-cookie", C_DESCRIPTOR_COOKIE, EQ(1), NO_OBJ),
  T01("client-key", C_CLIENT_KEY, NO_ARGS, NEED_SKEY_1024),
  END_OF_TABLE
};

431
/** List of tokens allowed in V3 networkstatus votes. */
432
static token_rule_t networkstatus_token_table[] = {
433
434
435
436
  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 ),
437
438
  T1("valid-after",            K_VALID_AFTER,      CONCAT_ARGS, NO_OBJ ),
  T1("fresh-until",            K_FRESH_UNTIL,      CONCAT_ARGS, NO_OBJ ),
439
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),
440
  T1("voting-delay",           K_VOTING_DELAY,     GE(2),       NO_OBJ ),
441
  T1("known-flags",            K_KNOWN_FLAGS,      ARGS,        NO_OBJ ),
442
  T01("params",                K_PARAMS,           ARGS,        NO_OBJ ),
443
444
445
446
447
448
  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 ),
449
  T1( "dir-source",          K_DIR_SOURCE,      GE(6),       NO_OBJ ),
450
  T01("legacy-dir-key",      K_LEGACY_DIR_KEY,  GE(1),       NO_OBJ ),
451
452
453
  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 ),
454
  T1( "consensus-methods",   K_CONSENSUS_METHODS, GE(1),     NO_OBJ ),
455
456
457

  END_OF_TABLE
};
458
459

/** List of tokens allowed in V3 networkstatus consensuses. */
460
static token_rule_t networkstatus_consensus_token_table[] = {
461
462
463
  T1("network-status-version", K_NETWORK_STATUS_VERSION,
                                                   GE(1),       NO_OBJ ),
  T1("vote-status",            K_VOTE_STATUS,      GE(1),       NO_OBJ ),
464
465
  T1("valid-after",            K_VALID_AFTER,      CONCAT_ARGS, NO_OBJ ),
  T1("fresh-until",            K_FRESH_UNTIL,      CONCAT_ARGS, NO_OBJ ),
466
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),
467
  T1("voting-delay",           K_VOTING_DELAY,     GE(2),       NO_OBJ ),
468
469
470

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

471
  T1N("dir-source",          K_DIR_SOURCE,          GE(6),   NO_OBJ ),
472
473
474
475
476
477
  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 ),
478
479
  T01("server-versions",     K_SERVER_VERSIONS, CONCAT_ARGS, NO_OBJ ),
  T01("consensus-method",    K_CONSENSUS_METHOD,    EQ(1),   NO_OBJ),
480
  T01("params",                K_PARAMS,           ARGS,        NO_OBJ ),
481
482
483
484

  END_OF_TABLE
};

485
486
/** List of tokens allowable in the footer of v1/v2 directory/networkstatus
 * footers. */
487
static token_rule_t networkstatus_vote_footer_token_table[] = {
488
489
490
  T(  "directory-signature", K_DIRECTORY_SIGNATURE, GE(2),   NEED_OBJ ),
  END_OF_TABLE
};
491

492
/** List of tokens allowable in detached networkstatus signature documents. */
493
494
static token_rule_t networkstatus_detached_signature_token_table[] = {
  T1_START("consensus-digest", K_CONSENSUS_DIGEST, GE(1),       NO_OBJ ),
495
  T("additional-digest",       K_ADDITIONAL_DIGEST,GE(3),       NO_OBJ ),
496
497
498
  T1("valid-after",            K_VALID_AFTER,      CONCAT_ARGS, NO_OBJ ),
  T1("fresh-until",            K_FRESH_UNTIL,      CONCAT_ARGS, NO_OBJ ),
  T1("valid-until",            K_VALID_UNTIL,      CONCAT_ARGS, NO_OBJ ),
499
500
  T("additional-signature",  K_ADDITIONAL_SIGNATURE, GE(4),   NEED_OBJ ),
  T1N("directory-signature", K_DIRECTORY_SIGNATURE,  GE(2),   NEED_OBJ ),
501
502
503
  END_OF_TABLE
};

504
505
506
507
508
509
510
511
static token_rule_t microdesc_token_table[] = {
  T1_START("onion-key",        K_ONION_KEY,        NO_ARGS,     NEED_KEY_1024),
  T01("family",                K_FAMILY,           ARGS,        NO_OBJ ),
  T01("p",                     K_P,                CONCAT_ARGS, NO_OBJ ),
  A01("@last-listed",          A_LAST_LISTED,      CONCAT_ARGS, NO_OBJ ),
  END_OF_TABLE
};

512
513
#undef T

514
515
/* static function prototypes */
static int router_add_exit_policy(routerinfo_t *router,directory_token_t *tok);
516
static addr_policy_t *router_parse_addr_policy(directory_token_t *tok);
517
518
static addr_policy_t *router_parse_addr_policy_private(directory_token_t *tok);

519
static int router_get_hash_impl(const char *s, char *digest,
520
                                const char *start_str, const char *end_str,
521
522
                                char end_char,
                                digest_algorithm_t alg);
523
524
525
static int router_get_hashes_impl(const char *s, digests_t *digests,
                                  const char *start_str, const char *end_str,
                                  char end_char);
526
static void token_clear(directory_token_t *tok);
527
static smartlist_t *find_all_exitpolicy(smartlist_t *s);
528
529
530
531
532
533
534
static directory_token_t *_find_by_keyword(smartlist_t *s,
                                           directory_keyword keyword,
                                           const char *keyword_str);
#define find_by_keyword(s, keyword) _find_by_keyword((s), (keyword), #keyword)
static directory_token_t *find_opt_by_keyword(smartlist_t *s,
                                              directory_keyword keyword);

535
536
537
#define TS_ANNOTATIONS_OK 1
#define TS_NOCHECK 2
#define TS_NO_NEW_ANNOTATIONS 4
538
539
static int tokenize_string(memarea_t *area,
                           const char *start, const char *end,
540
                           smartlist_t *out,
541
                           token_rule_t *table,
542
                           int flags);
543
544
static directory_token_t *get_next_token(memarea_t *area,
                                         const char **s,
545
                                         const char *eos,
546
                                         token_rule_t *table);
547
548
#define CST_CHECK_AUTHORITY   (1<<0)
#define CST_NO_CHECK_OBJTYPE  (1<<1)
549
static int check_signature_token(const char *digest,
550
                                 ssize_t digest_len,
551
552
                                 directory_token_t *tok,
                                 crypto_pk_env_t *pkey,
553
                                 int flags,
554
                                 const char *doctype);
555
static crypto_pk_env_t *find_dir_signing_key(const char *str, const char *eos);
556
static int tor_version_same_series(tor_version_t *a, tor_version_t *b);
557

558
559
560
561
562
563
564
565
566
567
568
569
570
#undef DEBUG_AREA_ALLOC

#ifdef DEBUG_AREA_ALLOC
#define DUMP_AREA(a,name) STMT_BEGIN                              \
  size_t alloc=0, used=0;                                         \
  memarea_get_stats((a),&alloc,&used);                            \
  log_debug(LD_MM, "Area for %s has %lu allocated; using %lu.",   \
            name, (unsigned long)alloc, (unsigned long)used);     \
  STMT_END
#else
#define DUMP_AREA(a,name) STMT_NIL
#endif

571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
/** Last time we dumped a descriptor to disk. */
static time_t last_desc_dumped = 0;

/** For debugging purposes, dump unparseable descriptor *<b>desc</b> of
 * type *<b>type</b> to file $DATADIR/unparseable-desc. Do not write more
 * than one descriptor to disk per minute. If there is already such a
 * file in the data directory, overwrite it. */
static void
dump_desc(const char *desc, const char *type)
{
  time_t now = time(NULL);
  tor_assert(desc);
  tor_assert(type);
  if (!last_desc_dumped || last_desc_dumped + 60 < now) {
    char *debugfile = get_datadir_fname("unparseable-desc");
    size_t filelen = 50 + strlen(type) + strlen(desc);
    char *content = tor_malloc_zero(filelen);
    tor_snprintf(content, filelen, "Unable to parse descriptor of type "
                 "%s:\n%s", type, desc);
    write_str_to_file(debugfile, content, 0);
    log_info(LD_DIR, "Unable to parse descriptor of type %s. See file "
             "unparseable-desc in data directory for details.", type);
    tor_free(content);
    tor_free(debugfile);
    last_desc_dumped = now;
  }
}

599
/** Set <b>digest</b> to the SHA-1 digest of the hash of the directory in
600
 * <b>s</b>.  Return 0 on success, -1 on failure.
601
 */
602
603
int
router_get_dir_hash(const char *s, char *digest)
604
605
{
  return router_get_hash_impl(s,digest,
606
607
                              "signed-directory","\ndirectory-signature",'\n',
                              DIGEST_SHA1);
608
609
610
}

/** Set <b>digest</b> to the SHA-1 digest of the hash of the first router in
611
 * <b>s</b>. Return 0 on success, -1 on failure.
612
 */
613
614
int
router_get_router_hash(const char *s, char *digest)
615
616
{
  return router_get_hash_impl(s,digest,
617
618
                              "router ","\nrouter-signature", '\n',
                              DIGEST_SHA1);
619
620
}

Nick Mathewson's avatar
Nick Mathewson committed
621
/** Set <b>digest</b> to the SHA-1 digest of the hash of the running-routers
622
 * string in <b>s</b>. Return 0 on success, -1 on failure.
Nick Mathewson's avatar
Nick Mathewson committed
623
 */
624
625
int
router_get_runningrouters_hash(const char *s, char *digest)
626
627
{
  return router_get_hash_impl(s,digest,
628
629
                              "network-status","\ndirectory-signature", '\n',
                              DIGEST_SHA1);
630
631
}

632
633
/** 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. */
634
635
636
637
int
router_get_networkstatus_v2_hash(const char *s, char *digest)
{
  return router_get_hash_impl(s,digest,
638
                              "network-status-version","\ndirectory-signature",
639
640
                              '\n',
                              DIGEST_SHA1);
641
642
}

643
644
/** Set <b>digests</b> to all the digests of the consensus document in
 * <b>s</b> */
645
646
647
648
649
650
651
652
653
int
router_get_networkstatus_v3_hashes(const char *s, digests_t *digests)
{
  return router_get_hashes_impl(s,digests,
                                "network-status-version",
                                "\ndirectory-signature",
                                ' ');
}

654
655
656
/** 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
657
658
router_get_networkstatus_v3_hash(const char *s, char *digest,
                                 digest_algorithm_t alg)
659
660
{
  return router_get_hash_impl(s,digest,
661
662
                              "network-status-version",
                              "\ndirectory-signature",
663
                              ' ', alg);
664
665
}

666
667
/** 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. */
668
669
670
int
router_get_extrainfo_hash(const char *s, char *digest)
{
671
672
  return router_get_hash_impl(s,digest,"extra-info","\nrouter-signature",'\n',
                              DIGEST_SHA1);
673
674
}

675
676
677
678
679
680
681
682
683
/** 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,
684
                               size_t digest_len, crypto_pk_env_t *private_key)
685
{
686
  char *signature;
687
  size_t i;
688
  int siglen;
689

690
  signature = tor_malloc(crypto_pk_keysize(private_key));
691
692
  siglen = crypto_pk_private_sign(private_key, signature, digest, digest_len);
  if (siglen < 0) {
693
    log_warn(LD_BUG,"Couldn't sign digest.");
694
    goto err;
695
696
697
698
699
  }
  if (strlcat(buf, "-----BEGIN SIGNATURE-----\n", buf_len) >= buf_len)
    goto truncated;

  i = strlen(buf);
700
  if (base64_encode(buf+i, buf_len-i, signature, siglen) < 0) {
701
    log_warn(LD_BUG,"couldn't base64-encode signature");
702
    goto err;
703
704
705
706
707
  }

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

708
  tor_free(signature);
709
  return 0;
710

711
 truncated:
712
  log_warn(LD_BUG,"tried to exceed string length.");
713
714
 err:
  tor_free(signature);
715
716
717
  return -1;
}

718
/** Return VS_RECOMMENDED if <b>myversion</b> is contained in
719
720
 * <b>versionlist</b>.  Else, return VS_EMPTY if versionlist has no
 * entries. Else, return VS_OLD if every member of
721
722
723
 * <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
Nick Mathewson's avatar
Nick Mathewson committed
724
 * is newer than <b>myversion.</b>.  Else, return VS_NEW if every member of
725
726
 * <b>versionlist</b> is older than <b>myversion</b>.  Else, return
 * VS_UNRECOMMENDED.
727
 *
728
729
 * (versionlist is a comma-separated list of version strings,
 * optionally prefixed with "Tor".  Versions that can't be parsed are
730
 * ignored.)
731
 */
732
733
734
version_status_t
tor_version_is_obsolete(const char *myversion, const char *versionlist)
{
735
  tor_version_t mine, other;
736
737
738
  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;
739
  smartlist_t *version_sl;
740

741
742
  log_debug(LD_CONFIG,"Checking whether version '%s' is in '%s'",
            myversion, versionlist);
743

744
  if (tor_version_parse(myversion, &mine)) {
745
    log_err(LD_BUG,"I couldn't parse my own version (%s)", myversion);
746
747
    tor_assert(0);
  }
748
749
  version_sl = smartlist_create();
  smartlist_split_string(version_sl, versionlist, ",", SPLIT_SKIP_SPACE, 0);
750

751
752
753
754
755
  if (!strlen(versionlist)) { /* no authorities cared or agreed */
    ret = VS_EMPTY;
    goto done;
  }

756
757
  SMARTLIST_FOREACH(version_sl, const char *, cp, {
    if (!strcmpstart(cp, "Tor "))
758
759
760
761
762
      cp += 4;

    if (tor_version_parse(cp, &other)) {
      /* Couldn't parse other; it can't be a match. */
    } else {
763
764
765
      same = tor_version_same_series(&mine, &other);
      if (same)
        found_any_in_series = 1;
766
767
      r = tor_version_compare(&mine, &other);
      if (r==0) {
768
        ret = VS_RECOMMENDED;
769
        goto done;
770
771
      } else if (r<0) {
        found_newer = 1;
772
773
        if (same)
          found_newer_in_series = 1;
774
775
      } else if (r>0) {
        found_older = 1;
776
777
      }
    }
778
779
  });

780
  /* We didn't find the listed version. Is it new or old? */
781
  if (found_any_in_series && !found_newer_in_series && found_newer) {
782
783
784
785
786
    ret = VS_NEW_IN_SERIES;
  } else if (found_newer && !found_older) {
    ret = VS_OLD;
  } else if (found_older && !found_newer) {
    ret = VS_NEW;
787
  } else {
788
    ret = VS_UNRECOMMENDED;
789
  }
790
791
792
793
794

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

797
798
/** 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.
799
 */
800
801
int
router_parse_directory(const char *str)
802
803
{
  directory_token_t *tok;
804
805
  char digest[DIGEST_LEN];
  time_t published_on;
806
  int r;
807
  const char *end, *cp, *str_dup = str;
808
  smartlist_t *tokens = NULL;
809
  crypto_pk_env_t *declared_key = NULL;
810
  memarea_t *area = memarea_new();
811

812
813
  /* 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
814
   * touch it. */
815

816
  if (router_get_dir_hash(str, digest)) {
817
    log_warn(LD_DIR, "Unable to compute digest of directory");
818
819
    goto err;
  }
820
  log_debug(LD_DIR,"Received directory hashes to %s",hex_str(digest,4));
821

822
823
824
825
826
  /* Check signature first, before we try to tokenize. */
  cp = str;
  while (cp && (end = strstr(cp+1, "\ndirectory-signature")))
    cp = end;
  if (cp == str || !cp) {
827
    log_warn(LD_DIR, "No signature found on directory."); goto err;
828
829
830
  }
  ++cp;
  tokens = smartlist_create();
831
  if (tokenize_string(area,cp,strchr(cp,'\0'),tokens,dir_token_table,0)) {
832
    log_warn(LD_DIR, "Error tokenizing directory signature"); goto err;
833
834
  }
  if (smartlist_len(tokens) != 1) {
835
    log_warn(LD_DIR, "Unexpected number of tokens in signature"); goto err;
836
  }
837
  tok=smartlist_get(tokens,0);
838
  if (tok->tp != K_DIRECTORY_SIGNATURE) {
839
    log_warn(LD_DIR,"Expected a single directory signature"); goto err;
840
  }
841
  declared_key = find_dir_signing_key(str, str+strlen(str));
842
  note_crypto_pk_op(VERIFY_DIR);
843
  if (check_signature_token(digest, DIGEST_LEN, tok, declared_key,
844
                            CST_CHECK_AUTHORITY, "directory")<0)
845
    goto err;
846

847
  SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_clear(t));
848
849
  smartlist_clear(tokens);
  memarea_clear(area);
850
851

  /* Now try to parse the first part of the directory. */
852
853
854
855
856
857
858
859
  if ((end = strstr(str,"\nrouter "))) {
    ++end;
  } else if ((end = strstr(str, "\ndirectory-signature"))) {
    ++end;
  } else {
    end = str + strlen(str);
  }

860
  if (tokenize_string(area,str,end,tokens,dir_token_table,0)) {
861
    log_warn(LD_DIR, "Error tokenizing directory"); goto err;
862
863
  }

864
  tok = find_by_keyword(tokens, K_PUBLISHED);
865
866
  tor_assert(tok->n_args == 1);

867
  if (parse_iso_time(tok->args[0], &published_on) < 0) {
868
869
870
     goto err;
  }

871
872
  /* Now that we know the signature is okay, and we have a
   * publication time, cache the directory. */
873
  if (directory_caches_v1_dir_info(get_options()) &&
874
      !authdir_mode_v1(get_options()))
875
    dirserv_set_cached_directory(str, published_on, 0);
876

877
878
879
  r = 0;
  goto done;
 err:
880
  dump_desc(str_dup, "v1 directory");
881
882
  r = -1;
 done:
883
  if (declared_key) crypto_free_pk_env(declared_key);
884
  if (tokens) {
885
    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_clear(t));
886
887
    smartlist_free(tokens);
  }
888
889
  if (area) {
    DUMP_AREA(area, "v1 directory");
890
    memarea_drop_all(area);
891
  }
892
893
894
  return r;
}

895
896
897
/** 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.*/
898
899
int
router_parse_runningrouters(const char *str)
900
901
902
903
{
  char digest[DIGEST_LEN];
  directory_token_t *tok;
  time_t published_on;
904
  int r = -1;
905
  crypto_pk_env_t *declared_key = NULL;
906
  smartlist_t *tokens = NULL;
907
  const char *eos = str + strlen(str), *str_dup = str;
908
  memarea_t *area = NULL;
909
910

  if (router_get_runningrouters_hash(str, digest)) {
911
    log_warn(LD_DIR, "Unable to compute digest of running-routers");
912
913
    goto err;
  }
914
  area = memarea_new();
915
  tokens = smartlist_create();
916
  if (tokenize_string(area,str,eos,tokens,dir_token_table,0)) {
917
    log_warn(LD_DIR, "Error tokenizing running-routers"); goto err;
918
919
920
  }
  tok = smartlist_get(tokens,0);
  if (tok->tp != K_NETWORK_STATUS) {
921
    log_warn(LD_DIR, "Network-status starts with wrong token");
922
923
924
    goto err;
  }

925
  tok = find_by_keyword(tokens, K_PUBLISHED);
926
  tor_assert(tok->n_args == 1);
927
  if (parse_iso_time(tok->args[0], &published_on) < 0) {
928
929
     goto err;
  }
930
  if (!(tok = find_opt_by_keyword(tokens, K_DIRECTORY_SIGNATURE))) {
931
    log_warn(LD_DIR, "Missing signature on running-routers");
932
933
    goto err;
  }
934
  declared_key = find_dir_signing_key(str, eos);
935
  note_crypto_pk_op(VERIFY_DIR);
936
  if (check_signature_token(digest, DIGEST_LEN, tok, declared_key,
937
                            CST_CHECK_AUTHORITY, "running-routers")
938
      < 0)
939
940
    goto err;

941
942
  /* Now that we know the signature is okay, and we have a
   * publication time, cache the list. */
943
  if (get_options()->DirPort && !authdir_mode_v1(get_options()))
<