1 /* $OpenBSD: parse_assertion.c,v 1.17 2022/12/27 17:10:06 jmc Exp $ */
2 /*
3 * The author of this code is Angelos D. Keromytis (angelos@dsl.cis.upenn.edu)
4 *
5 * This code was written by Angelos D. Keromytis in Philadelphia, PA, USA,
6 * in April-May 1998
7 *
8 * Copyright (C) 1998, 1999 by Angelos D. Keromytis.
9 *
10 * Permission to use, copy, and modify this software with or without fee
11 * is hereby granted, provided that this entire notice is included in
12 * all copies of any software which is or includes a copy or
13 * modification of this software.
14 *
15 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR
16 * IMPLIED WARRANTY. IN PARTICULAR, THE AUTHORS MAKES NO
17 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE
18 * MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
19 * PURPOSE.
20 */
21
22 #include <sys/types.h>
23
24 #include <ctype.h>
25 #include <limits.h>
26 #include <regex.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30
31 #include "keynote.h"
32 #include "assertion.h"
33 #include "signature.h"
34
35 /*
36 * Recurse on graph discovery.
37 */
38 static int
rec_evaluate_query(struct assertion * as)39 rec_evaluate_query(struct assertion *as)
40 {
41 struct assertion *ast;
42 struct keylist *kl;
43 int i, s;
44
45 as->as_kresult = KRESULT_IN_PROGRESS;
46
47 /*
48 * If we get the minimum result or an error from evaluating this
49 * assertion, we don't need to recurse.
50 */
51 keynote_evaluate_assertion(as);
52 if (keynote_errno != 0)
53 {
54 as->as_kresult = KRESULT_DONE;
55 if (keynote_errno)
56 as->as_error = keynote_errno;
57 if (keynote_errno == ERROR_MEMORY)
58 return -1;
59 else
60 {
61 keynote_errno = 0; /* Ignore syntax errors for now */
62 return 0;
63 }
64 }
65
66 if (as->as_result == 0)
67 {
68 as->as_kresult = KRESULT_DONE;
69 return as->as_result;
70 }
71
72 for (kl = as->as_keylist;
73 kl != NULL;
74 kl = kl->key_next)
75 {
76 switch (keynote_in_action_authorizers(kl->key_key, kl->key_alg))
77 {
78 case -1:
79 as->as_kresult = KRESULT_DONE;
80 if (keynote_errno == ERROR_MEMORY)
81 {
82 as->as_error = ERROR_MEMORY;
83 return -1;
84 }
85 else
86 {
87 keynote_errno = 0; /* Reset */
88 continue;
89 }
90
91 case RESULT_FALSE: /* Not there, check for assertions instead */
92 break;
93
94 case RESULT_TRUE: /* Ok, don't bother with assertions */
95 keynote_current_assertion = NULL;
96 continue;
97 }
98
99 for (i = 0;; i++)
100 {
101 ast = keynote_find_assertion(kl->key_key, i, kl->key_alg);
102 if (ast == NULL)
103 break;
104
105 if (ast->as_kresult == KRESULT_IN_PROGRESS) /* Cycle detected */
106 continue;
107
108 if (ast->as_kresult == KRESULT_UNTOUCHED) /* Recurse if needed */
109 rec_evaluate_query(ast);
110
111 /* Check for errors */
112 if (keynote_errno == ERROR_MEMORY)
113 {
114 as->as_error = ERROR_MEMORY;
115 as->as_kresult = KRESULT_DONE;
116 return -1;
117 }
118 else
119 keynote_errno = 0; /* Reset */
120 }
121 }
122
123 keynote_current_assertion = as;
124 s = keynote_parse_keypred(as, 0);
125 keynote_current_assertion = NULL;
126
127 if (keynote_errno == ERROR_MEMORY)
128 {
129 as->as_error = ERROR_MEMORY;
130 as->as_kresult = KRESULT_DONE;
131 return -1;
132 }
133 else
134 if (keynote_errno)
135 {
136 keynote_errno = 0;
137 s = 0;
138 }
139
140 /* Keep lower of two */
141 as->as_result = (as->as_result < s ? as->as_result : s);
142
143 /* Check the signature now if we haven't done so already */
144 if (as->as_sigresult == SIGRESULT_UNTOUCHED)
145 {
146 if (!(as->as_flags & ASSERT_FLAG_LOCAL))
147 as->as_sigresult = keynote_sigverify_assertion(as);
148 else
149 as->as_sigresult = SIGRESULT_TRUE; /* Trusted assertion */
150 }
151
152 if (as->as_sigresult != SIGRESULT_TRUE)
153 {
154 as->as_result = 0;
155 as->as_sigresult = SIGRESULT_FALSE;
156 if (keynote_errno != ERROR_MEMORY)
157 keynote_errno = 0; /* Reset */
158 else
159 {
160 as->as_error = ERROR_MEMORY;
161 as->as_kresult = KRESULT_DONE;
162 return -1;
163 }
164 }
165
166 as->as_kresult = KRESULT_DONE;
167 return as->as_result;
168 }
169
170 /*
171 * Fix the Authorizer/Licencees/Signature fields. If the first argument is
172 * empty, fix all assertions. The second argument specifies whether the
173 * Signature field should be parsed or not.
174 */
175 static int
keynote_fix_fields(struct assertion * ast,int sigfield)176 keynote_fix_fields(struct assertion *ast, int sigfield)
177 {
178 struct assertion *as;
179 int i;
180
181 /* Signature generation/verification handling, no need to eval Licensees */
182 if (ast != NULL)
183 {
184 /* Authorizer */
185 if (keynote_evaluate_authorizer(ast, 1) != RESULT_TRUE)
186 return -1;
187
188 /* Signature */
189 if ((sigfield) && (ast->as_signature_string_s != NULL))
190 if (keynote_evaluate_authorizer(ast, 0) != RESULT_TRUE)
191 return -1;
192
193 return RESULT_TRUE;
194 }
195
196 for (i = 0; i < HASHTABLESIZE; i++)
197 for (as = keynote_current_session->ks_assertion_table[i];
198 as != NULL;
199 as = as->as_next)
200 {
201 if (!(as->as_internalflags & ASSERT_IFLAG_NEEDPROC) &&
202 !(as->as_internalflags & ASSERT_IFLAG_WEIRDLICS) &&
203 !(as->as_internalflags & ASSERT_IFLAG_WEIRDAUTH) &&
204 !(as->as_internalflags & ASSERT_IFLAG_WEIRDSIG))
205 continue;
206
207 /* Parse the Signature field */
208 if (((as->as_internalflags & ASSERT_IFLAG_WEIRDSIG) ||
209 (as->as_internalflags & ASSERT_IFLAG_NEEDPROC)) &&
210 (as->as_signature_string_s != NULL))
211 if (keynote_evaluate_authorizer(as, 0) == -1)
212 {
213 if (keynote_errno)
214 as->as_error = keynote_errno;
215 if (keynote_errno == ERROR_MEMORY)
216 return -1;
217 else
218 keynote_errno = 0;
219 }
220
221 /* Parse the Licensees field */
222 if ((as->as_internalflags & ASSERT_IFLAG_WEIRDLICS) ||
223 (as->as_internalflags & ASSERT_IFLAG_NEEDPROC))
224 if (keynote_parse_keypred(as, 1) == -1)
225 {
226 if (keynote_errno)
227 as->as_error = keynote_errno;
228 if (keynote_errno == ERROR_MEMORY)
229 return -1;
230 else
231 keynote_errno = 0;
232 }
233
234 /* Parse the Authorizer field */
235 if ((as->as_internalflags & ASSERT_IFLAG_WEIRDAUTH) ||
236 (as->as_internalflags & ASSERT_IFLAG_NEEDPROC))
237 if (keynote_evaluate_authorizer(as, 1) == -1)
238 {
239 if (keynote_errno)
240 as->as_error = keynote_errno;
241 if (keynote_errno == ERROR_MEMORY)
242 return -1;
243 else
244 keynote_errno = 0;
245 }
246 }
247
248 /* Reposition if necessary */
249 for (i = 0; i < HASHTABLESIZE; i++)
250 for (as = keynote_current_session->ks_assertion_table[i];
251 as != NULL;
252 as = as->as_next)
253 if (((as->as_internalflags & ASSERT_IFLAG_WEIRDAUTH) &&
254 !(as->as_internalflags & ASSERT_IFLAG_PROCESSED)) ||
255 (as->as_internalflags & ASSERT_IFLAG_NEEDPROC))
256 {
257 as->as_internalflags &= ~ASSERT_IFLAG_NEEDPROC;
258 as->as_internalflags |= ASSERT_IFLAG_PROCESSED;
259 keynote_sremove_assertion(keynote_current_session->ks_id,
260 as->as_id);
261
262 if (keynote_add_htable(as, 1) != RESULT_TRUE)
263 return -1;
264
265 /* Point to beginning of the previous list. */
266 i--;
267 break;
268 }
269
270 return RESULT_TRUE;
271 }
272
273 /*
274 * Find the trust graph. This is a depth-first search, starting at
275 * POLICY assertions.
276 */
277 int
keynote_evaluate_query(void)278 keynote_evaluate_query(void)
279 {
280 struct assertion *as;
281 int p, prev;
282 int i;
283
284 /* Fix the authorizer/licensees/signature fields */
285 if (keynote_fix_fields(NULL, 0) != RESULT_TRUE)
286 return -1;
287
288 /* Find POLICY assertions and try to evaluate the query. */
289 for (i = 0, prev = 0; i < HASHTABLESIZE; i++)
290 for (as = keynote_current_session->ks_assertion_table[i];
291 as != NULL;
292 as = as->as_next)
293 if ((as->as_authorizer != NULL) && /* Paranoid */
294 (as->as_signeralgorithm == KEYNOTE_ALGORITHM_NONE))
295 if ((!strcmp("POLICY", as->as_authorizer)) &&
296 (as->as_flags & ASSERT_FLAG_LOCAL))
297 {
298 if ((p = rec_evaluate_query(as)) == -1)
299 {
300 if (keynote_errno)
301 as->as_error = keynote_errno;
302 if (keynote_errno == ERROR_MEMORY)
303 return -1;
304 else
305 {
306 keynote_errno = 0;
307 continue;
308 }
309 }
310
311 if (p > prev)
312 prev = p;
313
314 /* If we get the highest possible return value, just return */
315 if (prev == (keynote_current_session->ks_values_num - 1))
316 return prev;
317 }
318
319 return prev;
320 }
321
322 /*
323 * Return keyword type.
324 */
325 static int
whichkeyword(char * start,char * end)326 whichkeyword(char *start, char *end)
327 {
328 int len = (end - start);
329
330 if (len <= 0)
331 {
332 keynote_errno = ERROR_MEMORY;
333 return -1;
334 }
335
336 if (!strncasecmp("keynote-version:", start, len))
337 return KEYWORD_VERSION;
338
339 if (!strncasecmp("local-constants:", start, len))
340 return KEYWORD_LOCALINIT;
341
342 if (!strncasecmp("authorizer:", start, len))
343 return KEYWORD_AUTHORIZER;
344
345 if (!strncasecmp("licensees:", start, len))
346 return KEYWORD_LICENSEES;
347
348 if (!strncasecmp("conditions:", start, len))
349 return KEYWORD_CONDITIONS;
350
351 if (!strncasecmp("signature:", start, len))
352 return KEYWORD_SIGNATURE;
353
354 if (!strncasecmp("comment:", start, len))
355 return KEYWORD_COMMENT;
356
357 keynote_errno = ERROR_SYNTAX;
358 return -1;
359 }
360
361 /*
362 * Parse an assertion. Set keynote_errno to ERROR_SYNTAX if parsing
363 * failed due to certificate badness, and ERROR_MEMORY if memory
364 * problem. If more than one assertions have been passed in the
365 * buffer, they will be linked.
366 */
367 struct assertion *
keynote_parse_assertion(char * buf,int len,int assertion_flags)368 keynote_parse_assertion(char *buf, int len, int assertion_flags)
369 {
370 int k, i, j, seen_field = 0, ver = 0, end_of_assertion = 0;
371 char *ks, *ke, *ts, *te = NULL;
372 struct assertion *as;
373
374 /* Allocate memory for assertion */
375 as = calloc(1, sizeof(struct assertion));
376 if (as == NULL)
377 {
378 keynote_errno = ERROR_MEMORY;
379 return NULL;
380 }
381
382 /* Keep a copy of the assertion around */
383 as->as_buf = strdup(buf);
384 if (as->as_buf == NULL)
385 {
386 keynote_errno = ERROR_MEMORY;
387 keynote_free_assertion(as);
388 return NULL;
389 }
390
391 as->as_flags = assertion_flags & ~(ASSERT_FLAG_SIGGEN |
392 ASSERT_FLAG_SIGVER);
393
394 /* Skip any leading whitespace */
395 for (i = 0, j = len; i < j && isspace((unsigned char)as->as_buf[i]); i++)
396 ;
397
398 /* Keyword must start at beginning of buffer or line */
399 if ((i >= j) || ((i != 0) && (as->as_buf[i - 1] != '\n')))
400 {
401 keynote_free_assertion(as);
402 keynote_errno = ERROR_SYNTAX;
403 return NULL;
404 }
405
406 while (i < j) /* Decomposition loop */
407 {
408 ks = as->as_buf + i;
409
410 /* Mark beginning of assertion for signature purposes */
411 if (as->as_startofsignature == NULL)
412 as->as_startofsignature = ks;
413
414 /* This catches comments at the beginning of an assertion only */
415 if (as->as_buf[i] == '#') /* Comment */
416 {
417 seen_field = 1;
418
419 /* Skip until the end of line */
420 while ((i< j) && as->as_buf[++i] != '\n')
421 ;
422
423 i++;
424 continue; /* Loop */
425 }
426
427 /* Advance until we find a keyword separator */
428 for (; (as->as_buf[i] != ':') && (i < j); i++)
429 ;
430
431 if (i + 1 > j)
432 {
433 keynote_free_assertion(as);
434 keynote_errno = ERROR_SYNTAX;
435 return NULL;
436 }
437
438 /* ks points at beginning of keyword, ke points at end */
439 ke = as->as_buf + i;
440
441 /* ts points at beginning of value field */
442 ts = as->as_buf + i + 1; /* Skip ':' */
443
444 /*
445 * Find the end of the field -- means end of buffer,
446 * a newline followed by a non-whitespace character,
447 * or two newlines.
448 */
449 while (++i <= j)
450 {
451 /* If end of buffer, we're at the end of the field */
452 if (i == j)
453 {
454 end_of_assertion = 1;
455 te = as->as_buf + i;
456 break;
457 }
458
459 /* If two newlines, end of assertion */
460 if ((as->as_buf[i] == '\n') && (i + 1 < j) &&
461 (as->as_buf[i + 1] == '\n'))
462 {
463 end_of_assertion = 1;
464 te = as->as_buf + i;
465 break;
466 }
467
468 /* If newline followed by non-whitespace or comment character */
469 if ((as->as_buf[i] == '\n') &&
470 (!isspace((unsigned char)as->as_buf[i + 1])) &&
471 (as->as_buf[i + 1] != '#'))
472 {
473 te = as->as_buf + i;
474 break;
475 }
476 }
477
478 i++;
479
480 /*
481 * On each of the cases (except the first), we check that:
482 * - we've already seen a keynote-version field (and that
483 * it's the first one that appears in the assertion)
484 * - the signature field, if present, is the last one
485 * - no field appears more than once
486 */
487 switch (whichkeyword(ks, ke))
488 {
489 case -1:
490 keynote_free_assertion(as);
491 return NULL;
492
493 case KEYWORD_VERSION:
494 if ((ver == 1) || (seen_field == 1))
495 {
496 keynote_free_assertion(as);
497 keynote_errno = ERROR_SYNTAX;
498 return NULL;
499 }
500
501 /* Test for version correctness */
502 keynote_get_envlist(ts, te, 1);
503 if (keynote_errno != 0)
504 {
505 keynote_free_assertion(as);
506 return NULL;
507 }
508
509 ver = 1;
510 break;
511
512 case KEYWORD_LOCALINIT:
513 if (as->as_env != NULL)
514 {
515 keynote_free_assertion(as);
516 keynote_errno = ERROR_SYNTAX;
517 return NULL;
518 }
519
520 as->as_env = keynote_get_envlist(ts, te, 0);
521 if (keynote_errno != 0)
522 {
523 keynote_free_assertion(as);
524 return NULL;
525 }
526 break;
527
528 case KEYWORD_AUTHORIZER:
529 if (as->as_authorizer_string_s != NULL)
530 {
531 keynote_free_assertion(as);
532 keynote_errno = ERROR_SYNTAX;
533 return NULL;
534 }
535
536 as->as_authorizer_string_s = ts;
537 as->as_authorizer_string_e = te;
538 break;
539
540 case KEYWORD_LICENSEES:
541 if (as->as_keypred_s != NULL)
542 {
543 keynote_free_assertion(as);
544 keynote_errno = ERROR_SYNTAX;
545 return NULL;
546 }
547
548 as->as_keypred_s = ts;
549 as->as_keypred_e = te;
550 break;
551
552 case KEYWORD_CONDITIONS:
553 if (as->as_conditions_s != NULL)
554 {
555 keynote_free_assertion(as);
556 keynote_errno = ERROR_SYNTAX;
557 return NULL;
558 }
559
560 as->as_conditions_s = ts;
561 as->as_conditions_e = te;
562 break;
563
564 case KEYWORD_SIGNATURE:
565 if (as->as_signature_string_s != NULL)
566 {
567 keynote_free_assertion(as);
568 keynote_errno = ERROR_SYNTAX;
569 return NULL;
570 }
571
572 end_of_assertion = 1;
573 as->as_allbutsignature = ks;
574 as->as_signature_string_s = ts;
575 as->as_signature_string_e = te;
576 break;
577
578 case KEYWORD_COMMENT:
579 if (as->as_comment_s != NULL)
580 {
581 keynote_free_assertion(as);
582 keynote_errno = ERROR_SYNTAX;
583 return NULL;
584 }
585
586 as->as_comment_s = ts;
587 as->as_comment_e = te;
588 break;
589 }
590
591 seen_field = 1;
592 if (end_of_assertion == 1)
593 {
594 /* End of buffer, good termination */
595 if ((te == as->as_buf + len) || (te + 1 == as->as_buf + len) ||
596 (*(te) == '\0') || (*(te + 1) == '\0'))
597 break;
598
599 /* Check whether there's something else following */
600 for (k = 1; te + k < as->as_buf + len && *(te + k) != '\n'; k++)
601 if (!isspace((unsigned char)*(te + k)))
602 {
603 keynote_free_assertion(as);
604 keynote_errno = ERROR_SYNTAX;
605 return NULL;
606 }
607
608 break; /* Assertion is "properly" terminated */
609 }
610 }
611
612 /* Check that the basic fields are there */
613 if (as->as_authorizer_string_s == NULL)
614 {
615 keynote_free_assertion(as);
616 keynote_errno = ERROR_SYNTAX;
617 return NULL;
618 }
619
620 /* Signature generation/verification handling */
621 if (assertion_flags & ASSERT_FLAG_SIGGEN)
622 {
623 if (keynote_fix_fields(as, 0) != RESULT_TRUE)
624 {
625 keynote_free_assertion(as);
626 return NULL;
627 }
628 }
629 else
630 if (assertion_flags & ASSERT_FLAG_SIGVER)
631 if (keynote_fix_fields(as, 1) != RESULT_TRUE)
632 {
633 keynote_free_assertion(as);
634 return NULL;
635 }
636
637 return as;
638 }
639