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