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