parsecommon.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458
  1. /* Copyright (c) 2016-2018, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file parsecommon.c
  5. * \brief Common code to parse and validate various type of descriptors.
  6. **/
  7. #include "feature/dirparse/parsecommon.h"
  8. #include "lib/log/log.h"
  9. #include "lib/log/util_bug.h"
  10. #include "lib/encoding/binascii.h"
  11. #include "lib/container/smartlist.h"
  12. #include "lib/string/util_string.h"
  13. #include "lib/string/printf.h"
  14. #include "lib/memarea/memarea.h"
  15. #include "lib/crypt_ops/crypto_rsa.h"
  16. #include <string.h>
  17. #define MIN_ANNOTATION A_PURPOSE
  18. #define MAX_ANNOTATION A_UNKNOWN_
  19. #define ALLOC_ZERO(sz) memarea_alloc_zero(area,sz)
  20. #define ALLOC(sz) memarea_alloc(area,sz)
  21. #define STRDUP(str) memarea_strdup(area,str)
  22. #define STRNDUP(str,n) memarea_strndup(area,(str),(n))
  23. #define RET_ERR(msg) \
  24. STMT_BEGIN \
  25. if (tok) token_clear(tok); \
  26. tok = ALLOC_ZERO(sizeof(directory_token_t)); \
  27. tok->tp = ERR_; \
  28. tok->error = STRDUP(msg); \
  29. goto done_tokenizing; \
  30. STMT_END
  31. /** Free all resources allocated for <b>tok</b> */
  32. void
  33. token_clear(directory_token_t *tok)
  34. {
  35. if (tok->key)
  36. crypto_pk_free(tok->key);
  37. }
  38. /** Read all tokens from a string between <b>start</b> and <b>end</b>, and add
  39. * them to <b>out</b>. Parse according to the token rules in <b>table</b>.
  40. * Caller must free tokens in <b>out</b>. If <b>end</b> is NULL, use the
  41. * entire string.
  42. */
  43. int
  44. tokenize_string(memarea_t *area,
  45. const char *start, const char *end, smartlist_t *out,
  46. const token_rule_t *table, int flags)
  47. {
  48. const char **s;
  49. directory_token_t *tok = NULL;
  50. int counts[NIL_];
  51. int i;
  52. int first_nonannotation;
  53. int prev_len = smartlist_len(out);
  54. tor_assert(area);
  55. s = &start;
  56. if (!end) {
  57. end = start+strlen(start);
  58. } else {
  59. /* it's only meaningful to check for nuls if we got an end-of-string ptr */
  60. if (memchr(start, '\0', end-start)) {
  61. log_warn(LD_DIR, "parse error: internal NUL character.");
  62. return -1;
  63. }
  64. }
  65. for (i = 0; i < NIL_; ++i)
  66. counts[i] = 0;
  67. SMARTLIST_FOREACH(out, const directory_token_t *, t, ++counts[t->tp]);
  68. while (*s < end && (!tok || tok->tp != EOF_)) {
  69. tok = get_next_token(area, s, end, table);
  70. if (tok->tp == ERR_) {
  71. log_warn(LD_DIR, "parse error: %s", tok->error);
  72. token_clear(tok);
  73. return -1;
  74. }
  75. ++counts[tok->tp];
  76. smartlist_add(out, tok);
  77. *s = eat_whitespace_eos(*s, end);
  78. }
  79. if (flags & TS_NOCHECK)
  80. return 0;
  81. if ((flags & TS_ANNOTATIONS_OK)) {
  82. first_nonannotation = -1;
  83. for (i = 0; i < smartlist_len(out); ++i) {
  84. tok = smartlist_get(out, i);
  85. if (tok->tp < MIN_ANNOTATION || tok->tp > MAX_ANNOTATION) {
  86. first_nonannotation = i;
  87. break;
  88. }
  89. }
  90. if (first_nonannotation < 0) {
  91. log_warn(LD_DIR, "parse error: item contains only annotations");
  92. return -1;
  93. }
  94. for (i=first_nonannotation; i < smartlist_len(out); ++i) {
  95. tok = smartlist_get(out, i);
  96. if (tok->tp >= MIN_ANNOTATION && tok->tp <= MAX_ANNOTATION) {
  97. log_warn(LD_DIR, "parse error: Annotations mixed with keywords");
  98. return -1;
  99. }
  100. }
  101. if ((flags & TS_NO_NEW_ANNOTATIONS)) {
  102. if (first_nonannotation != prev_len) {
  103. log_warn(LD_DIR, "parse error: Unexpected annotations.");
  104. return -1;
  105. }
  106. }
  107. } else {
  108. for (i=0; i < smartlist_len(out); ++i) {
  109. tok = smartlist_get(out, i);
  110. if (tok->tp >= MIN_ANNOTATION && tok->tp <= MAX_ANNOTATION) {
  111. log_warn(LD_DIR, "parse error: no annotations allowed.");
  112. return -1;
  113. }
  114. }
  115. first_nonannotation = 0;
  116. }
  117. for (i = 0; table[i].t; ++i) {
  118. if (counts[table[i].v] < table[i].min_cnt) {
  119. log_warn(LD_DIR, "Parse error: missing %s element.", table[i].t);
  120. return -1;
  121. }
  122. if (counts[table[i].v] > table[i].max_cnt) {
  123. log_warn(LD_DIR, "Parse error: too many %s elements.", table[i].t);
  124. return -1;
  125. }
  126. if (table[i].pos & AT_START) {
  127. if (smartlist_len(out) < 1 ||
  128. (tok = smartlist_get(out, first_nonannotation))->tp != table[i].v) {
  129. log_warn(LD_DIR, "Parse error: first item is not %s.", table[i].t);
  130. return -1;
  131. }
  132. }
  133. if (table[i].pos & AT_END) {
  134. if (smartlist_len(out) < 1 ||
  135. (tok = smartlist_get(out, smartlist_len(out)-1))->tp != table[i].v) {
  136. log_warn(LD_DIR, "Parse error: last item is not %s.", table[i].t);
  137. return -1;
  138. }
  139. }
  140. }
  141. return 0;
  142. }
  143. /** Helper: parse space-separated arguments from the string <b>s</b> ending at
  144. * <b>eol</b>, and store them in the args field of <b>tok</b>. Store the
  145. * number of parsed elements into the n_args field of <b>tok</b>. Allocate
  146. * all storage in <b>area</b>. Return the number of arguments parsed, or
  147. * return -1 if there was an insanely high number of arguments. */
  148. static inline int
  149. get_token_arguments(memarea_t *area, directory_token_t *tok,
  150. const char *s, const char *eol)
  151. {
  152. /** Largest number of arguments we'll accept to any token, ever. */
  153. #define MAX_ARGS 512
  154. char *mem = memarea_strndup(area, s, eol-s);
  155. char *cp = mem;
  156. int j = 0;
  157. char *args[MAX_ARGS];
  158. memset(args, 0, sizeof(args));
  159. while (*cp) {
  160. if (j == MAX_ARGS)
  161. return -1;
  162. args[j++] = cp;
  163. cp = (char*)find_whitespace(cp);
  164. if (!cp || !*cp)
  165. break; /* End of the line. */
  166. *cp++ = '\0';
  167. cp = (char*)eat_whitespace(cp);
  168. }
  169. tok->n_args = j;
  170. tok->args = memarea_memdup(area, args, j*sizeof(char*));
  171. return j;
  172. #undef MAX_ARGS
  173. }
  174. /** Helper: make sure that the token <b>tok</b> with keyword <b>kwd</b> obeys
  175. * the object syntax of <b>o_syn</b>. Allocate all storage in <b>area</b>.
  176. * Return <b>tok</b> on success, or a new ERR_ token if the token didn't
  177. * conform to the syntax we wanted.
  178. **/
  179. static inline directory_token_t *
  180. token_check_object(memarea_t *area, const char *kwd,
  181. directory_token_t *tok, obj_syntax o_syn)
  182. {
  183. char ebuf[128];
  184. switch (o_syn) {
  185. case NO_OBJ:
  186. /* No object is allowed for this token. */
  187. if (tok->object_body) {
  188. tor_snprintf(ebuf, sizeof(ebuf), "Unexpected object for %s", kwd);
  189. RET_ERR(ebuf);
  190. }
  191. if (tok->key) {
  192. tor_snprintf(ebuf, sizeof(ebuf), "Unexpected public key for %s", kwd);
  193. RET_ERR(ebuf);
  194. }
  195. break;
  196. case NEED_OBJ:
  197. /* There must be a (non-key) object. */
  198. if (!tok->object_body) {
  199. tor_snprintf(ebuf, sizeof(ebuf), "Missing object for %s", kwd);
  200. RET_ERR(ebuf);
  201. }
  202. break;
  203. case NEED_KEY_1024: /* There must be a 1024-bit public key. */
  204. case NEED_SKEY_1024: /* There must be a 1024-bit private key. */
  205. if (tok->key && crypto_pk_num_bits(tok->key) != PK_BYTES*8) {
  206. tor_snprintf(ebuf, sizeof(ebuf), "Wrong size on key for %s: %d bits",
  207. kwd, crypto_pk_num_bits(tok->key));
  208. RET_ERR(ebuf);
  209. }
  210. /* fall through */
  211. case NEED_KEY: /* There must be some kind of key. */
  212. if (!tok->key) {
  213. tor_snprintf(ebuf, sizeof(ebuf), "Missing public key for %s", kwd);
  214. RET_ERR(ebuf);
  215. }
  216. if (o_syn != NEED_SKEY_1024) {
  217. if (crypto_pk_key_is_private(tok->key)) {
  218. tor_snprintf(ebuf, sizeof(ebuf),
  219. "Private key given for %s, which wants a public key", kwd);
  220. RET_ERR(ebuf);
  221. }
  222. } else { /* o_syn == NEED_SKEY_1024 */
  223. if (!crypto_pk_key_is_private(tok->key)) {
  224. tor_snprintf(ebuf, sizeof(ebuf),
  225. "Public key given for %s, which wants a private key", kwd);
  226. RET_ERR(ebuf);
  227. }
  228. }
  229. break;
  230. case OBJ_OK:
  231. /* Anything goes with this token. */
  232. break;
  233. }
  234. done_tokenizing:
  235. return tok;
  236. }
  237. /** Helper function: read the next token from *s, advance *s to the end of the
  238. * token, and return the parsed token. Parse *<b>s</b> according to the list
  239. * of tokens in <b>table</b>.
  240. */
  241. directory_token_t *
  242. get_next_token(memarea_t *area,
  243. const char **s, const char *eos, const token_rule_t *table)
  244. {
  245. /** Reject any object at least this big; it is probably an overflow, an
  246. * attack, a bug, or some other nonsense. */
  247. #define MAX_UNPARSED_OBJECT_SIZE (128*1024)
  248. /** Reject any line at least this big; it is probably an overflow, an
  249. * attack, a bug, or some other nonsense. */
  250. #define MAX_LINE_LENGTH (128*1024)
  251. const char *next, *eol, *obstart;
  252. size_t obname_len;
  253. int i;
  254. directory_token_t *tok;
  255. obj_syntax o_syn = NO_OBJ;
  256. char ebuf[128];
  257. const char *kwd = "";
  258. tor_assert(area);
  259. tok = ALLOC_ZERO(sizeof(directory_token_t));
  260. tok->tp = ERR_;
  261. /* Set *s to first token, eol to end-of-line, next to after first token */
  262. *s = eat_whitespace_eos(*s, eos); /* eat multi-line whitespace */
  263. tor_assert(eos >= *s);
  264. eol = memchr(*s, '\n', eos-*s);
  265. if (!eol)
  266. eol = eos;
  267. if (eol - *s > MAX_LINE_LENGTH) {
  268. RET_ERR("Line far too long");
  269. }
  270. next = find_whitespace_eos(*s, eol);
  271. if (!strcmp_len(*s, "opt", next-*s)) {
  272. /* Skip past an "opt" at the start of the line. */
  273. *s = eat_whitespace_eos_no_nl(next, eol);
  274. next = find_whitespace_eos(*s, eol);
  275. } else if (*s == eos) { /* If no "opt", and end-of-line, line is invalid */
  276. RET_ERR("Unexpected EOF");
  277. }
  278. /* Search the table for the appropriate entry. (I tried a binary search
  279. * instead, but it wasn't any faster.) */
  280. for (i = 0; table[i].t ; ++i) {
  281. if (!strcmp_len(*s, table[i].t, next-*s)) {
  282. /* We've found the keyword. */
  283. kwd = table[i].t;
  284. tok->tp = table[i].v;
  285. o_syn = table[i].os;
  286. *s = eat_whitespace_eos_no_nl(next, eol);
  287. /* We go ahead whether there are arguments or not, so that tok->args is
  288. * always set if we want arguments. */
  289. if (table[i].concat_args) {
  290. /* The keyword takes the line as a single argument */
  291. tok->args = ALLOC(sizeof(char*));
  292. tok->args[0] = STRNDUP(*s,eol-*s); /* Grab everything on line */
  293. tok->n_args = 1;
  294. } else {
  295. /* This keyword takes multiple arguments. */
  296. if (get_token_arguments(area, tok, *s, eol)<0) {
  297. tor_snprintf(ebuf, sizeof(ebuf),"Far too many arguments to %s", kwd);
  298. RET_ERR(ebuf);
  299. }
  300. *s = eol;
  301. }
  302. if (tok->n_args < table[i].min_args) {
  303. tor_snprintf(ebuf, sizeof(ebuf), "Too few arguments to %s", kwd);
  304. RET_ERR(ebuf);
  305. } else if (tok->n_args > table[i].max_args) {
  306. tor_snprintf(ebuf, sizeof(ebuf), "Too many arguments to %s", kwd);
  307. RET_ERR(ebuf);
  308. }
  309. break;
  310. }
  311. }
  312. if (tok->tp == ERR_) {
  313. /* No keyword matched; call it an "K_opt" or "A_unrecognized" */
  314. if (*s < eol && **s == '@')
  315. tok->tp = A_UNKNOWN_;
  316. else
  317. tok->tp = K_OPT;
  318. tok->args = ALLOC(sizeof(char*));
  319. tok->args[0] = STRNDUP(*s, eol-*s);
  320. tok->n_args = 1;
  321. o_syn = OBJ_OK;
  322. }
  323. /* Check whether there's an object present */
  324. *s = eat_whitespace_eos(eol, eos); /* Scan from end of first line */
  325. tor_assert(eos >= *s);
  326. eol = memchr(*s, '\n', eos-*s);
  327. if (!eol || eol-*s<11 || strcmpstart(*s, "-----BEGIN ")) /* No object. */
  328. goto check_object;
  329. obstart = *s; /* Set obstart to start of object spec */
  330. if (eol - *s <= 16 || memchr(*s+11,'\0',eol-*s-16) || /* no short lines, */
  331. strcmp_len(eol-5, "-----", 5) || /* nuls or invalid endings */
  332. (eol-*s) > MAX_UNPARSED_OBJECT_SIZE) { /* name too long */
  333. RET_ERR("Malformed object: bad begin line");
  334. }
  335. tok->object_type = STRNDUP(*s+11, eol-*s-16);
  336. obname_len = eol-*s-16; /* store objname length here to avoid a strlen() */
  337. *s = eol+1; /* Set *s to possible start of object data (could be eos) */
  338. /* Go to the end of the object */
  339. next = tor_memstr(*s, eos-*s, "-----END ");
  340. if (!next) {
  341. RET_ERR("Malformed object: missing object end line");
  342. }
  343. tor_assert(eos >= next);
  344. eol = memchr(next, '\n', eos-next);
  345. if (!eol) /* end-of-line marker, or eos if there's no '\n' */
  346. eol = eos;
  347. /* Validate the ending tag, which should be 9 + NAME + 5 + eol */
  348. if ((size_t)(eol-next) != 9+obname_len+5 ||
  349. strcmp_len(next+9, tok->object_type, obname_len) ||
  350. strcmp_len(eol-5, "-----", 5)) {
  351. tor_snprintf(ebuf, sizeof(ebuf), "Malformed object: mismatched end tag %s",
  352. tok->object_type);
  353. ebuf[sizeof(ebuf)-1] = '\0';
  354. RET_ERR(ebuf);
  355. }
  356. if (next - *s > MAX_UNPARSED_OBJECT_SIZE)
  357. RET_ERR("Couldn't parse object: missing footer or object much too big.");
  358. if (!strcmp(tok->object_type, "RSA PUBLIC KEY")) { /* If it's a public key */
  359. tok->key = crypto_pk_new();
  360. if (crypto_pk_read_public_key_from_string(tok->key, obstart, eol-obstart))
  361. RET_ERR("Couldn't parse public key.");
  362. } else if (!strcmp(tok->object_type, "RSA PRIVATE KEY")) { /* private key */
  363. tok->key = crypto_pk_new();
  364. if (crypto_pk_read_private_key_from_string(tok->key, obstart, eol-obstart))
  365. RET_ERR("Couldn't parse private key.");
  366. } else { /* If it's something else, try to base64-decode it */
  367. int r;
  368. tok->object_body = ALLOC(next-*s); /* really, this is too much RAM. */
  369. r = base64_decode(tok->object_body, next-*s, *s, next-*s);
  370. if (r<0)
  371. RET_ERR("Malformed object: bad base64-encoded data");
  372. tok->object_size = r;
  373. }
  374. *s = eol;
  375. check_object:
  376. tok = token_check_object(area, kwd, tok, o_syn);
  377. done_tokenizing:
  378. return tok;
  379. #undef RET_ERR
  380. #undef ALLOC
  381. #undef ALLOC_ZERO
  382. #undef STRDUP
  383. #undef STRNDUP
  384. }
  385. /** Find the first token in <b>s</b> whose keyword is <b>keyword</b>; fail
  386. * with an assert if no such keyword is found.
  387. */
  388. directory_token_t *
  389. find_by_keyword_(smartlist_t *s, directory_keyword keyword,
  390. const char *keyword_as_string)
  391. {
  392. directory_token_t *tok = find_opt_by_keyword(s, keyword);
  393. if (PREDICT_UNLIKELY(!tok)) {
  394. log_err(LD_BUG, "Missing %s [%d] in directory object that should have "
  395. "been validated. Internal error.", keyword_as_string, (int)keyword);
  396. tor_assert(tok);
  397. }
  398. return tok;
  399. }
  400. /** Find the first token in <b>s</b> whose keyword is <b>keyword</b>; return
  401. * NULL if no such keyword is found.
  402. */
  403. directory_token_t *
  404. find_opt_by_keyword(const smartlist_t *s, directory_keyword keyword)
  405. {
  406. SMARTLIST_FOREACH(s, directory_token_t *, t, if (t->tp == keyword) return t);
  407. return NULL;
  408. }
  409. /** If there are any directory_token_t entries in <b>s</b> whose keyword is
  410. * <b>k</b>, return a newly allocated smartlist_t containing all such entries,
  411. * in the same order in which they occur in <b>s</b>. Otherwise return
  412. * NULL. */
  413. smartlist_t *
  414. find_all_by_keyword(const smartlist_t *s, directory_keyword k)
  415. {
  416. smartlist_t *out = NULL;
  417. SMARTLIST_FOREACH(s, directory_token_t *, t,
  418. if (t->tp == k) {
  419. if (!out)
  420. out = smartlist_new();
  421. smartlist_add(out, t);
  422. });
  423. return out;
  424. }