[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: spki@c2.net*Subject*: *-forms in tags*From*: rivest@theory.lcs.mit.edu (Ron Rivest)*Date*: Wed, 02 Apr 97 14:30:05 EST*Cc*: blampson@microsoft.com*Sender*: owner-spki@c2.net

After some discussion with Carl Ellison, we have converged on a model for *-forms in tags that seems to capture the variability one wants for intersection of tags. Jump to the end of this note to see an example. Here is the development: (1) When composing certificate chains, the tag fields will be automatically intersected by a standard intersection algorithm. The user will not have to specify a new intersection algorithm, but he will have to write his tags in such a way that the standard algorithm will give the desired behavior. (2) The tags may contain *-forms: lists of type * , as in (* ... ) An S-expression that does not contain any *-forms (at any level) will be called a "constant" S-expression. S-expressions that contain (or are) *-forms (at any level) are called "variable" S-expressions. (3) The standard intersection algorithm matches constant S-expressions with an equality test. That is, if T1 and T2 are two constant S-exressions, then their intersection is T1 if T1 = T2. If T1 is not equal to T2, then the intersection is not defined. (4) A variable S-expression is understood to represent a SET of constant S-expressions. If s is an S-expression, we might denote the set of constant S-expressions it denotes as val(s). If s is a constant S-expression, than val(s) = { s }. Just the singleton set containing s. (5) The standard intersection algorithm takes two S-expressions s1 and s2, and produces, if possible, an S-expression s3 such that val(s3) = set-intersection(val(s1),val(s2)) Note that this is consistent with our definition for constant S-expressions. If it is impossible to compute a suitable variable S-expression s3, then the intersection fails and is undefined. This may happen because the *-forms aren't expressive enough to represent the resulting set of S-expressions, even though that result is (always) well-defined. (6) If s is a list (s1 s2 s3 ... sk) that is not a *-form, then val(s) = cross-product(val(s1),val(s2),...,val(sk)) That is, the set of lists obtained by taking a constant S-expression from val(s1), followed by a constant S-expression from val(s2), and so on. This means that the standard intersection operator can work recursively. (7) (Elaboration) Let A(s,s') denote the S-expression (if any) resulting from taking the intersection of S-expressions s and s' by the standard algorithm. If s = (s1, s2, ...,sk ) and s'= (s1',s2',...,sk') are two S-expressions that are not *-forms, then A(s,s') = (A(s1,s1'),A(s2,s2'),...,A(sk,sk')) (8) [* set form] Here is the first (of several) *-forms Suppose s = (* set s1 s2 ... sk ) We now define val(s) = set-union(val(s1),val(s2),...,val(sk)) Also a singleton set has the same val as the string itself: val( (* set 45) ) = val( 45 ) = { 45 } (9) [example] We might have a tag of the form T1 = (tag (spend-from 45123)) Here 45123 is intended to denote an account number at the bank. As written, this can only be matched with an exact copy. Consider now the variable S-exression of the form T2 = (tag (spend-from (* set 45123 11112))) This is intended to denote an authorization to spend from either account 45123 or account 11112. Note that Alice can delegate to Bob the authority to spend from either account using tag T2, and Bob can delegate to Charles the ability to spend from account 45123 only using tag T1, and this will work properly automatically, since A(T1,T2) = T1 because A(tag,tag) = tag A(spend-from,spend-from) = spend-from A(45123,(* set 45123 11112)) = 45123 (10) [Matching two *-forms] If Alice delegates to Bob with T2 = (tag (spend-from (* set 45123 11112))) and Bob delegates to Charles with T2 = (tag (spend-from (* set 11112 66632))) then Charles may spend from 11112, since A(T1,T2) = (tag (spend-from 11112)) (11) Basically, you can use the (* set ...) form to represent some variability in the authorization that can be refined by other issuers in the certificate chain. (12) There are other *-forms for representing other kinds of variability. Each such *-form always represents a set of S-expressions, and there a special rule for determining what that set is. The format of a *-form is always ( * <star-type> <arguments>) The rule for specifying what set of S-expressions this represents implies how to intersect the *-form with another S-expression (including another *-form). (13) Here are two simple *-forms representing sets of byte strings: (* prefix "string") -- represents the set of byte strings having "string" as its prefix. Example of use: T1 = (tag (http (* prefix "http://abc.com/"))) This can be automatically intersected with T2 = (tag (http (* prefix "http://abc.com/accounting"))) to yield T2 = (tag (http (* prefix "http://abc.com/accounting"))) (* range <order> <lower-limit>? <upper-limit>? ) where <order> is one of "alpha" or "numeric" and <lower-limit> ::= (<ge-or-geq> <byte-string>) <ge-or-geq> ::= ">" | ">=" <upper-limit> ::= (<le-or-leq> <byte-string>) <le-or-leq> ::= "<" | "<=" Example of use: T1 = (tag (spend-amount (* range numeric (< 5000)))) to authorize someone to spend up to 5000 dollars. T2 = (tag (login-permission (date (* range alpha (<= 1996-01-01)(<= 1997-12-31))))) (using the fact that dates compare nicely as alpha strings). (14) Here are four forms for representing sets of lists: ( * append s ) -- represents all S-expressions that can be obtained by appending additional elements to the end of list s. This is like "prefix", except for lists. Example: T1 = ( tag ( * append ( ftp "abc.com" ))) allows there to be additional elements in the ftp list. ( * reorder s ) ( * reorder-insert s ) ( * reorder-delete s ) These represent the set of S-expressions you can get from s by re-ordering the elements of s (other than the first) and possibily inserting new elements, or deleting some elements (other than the first). For example, (* reorder (rsa (n &44)(e &33))) allows the n and e fields to be given in either order. Or, (* reorder-insert (a (b 4)(c 5))) will match with (a d (c 5) e f (g 23) (b 4)) The reorder capability is good when the elements of the list are indexed by keywords or list type, rather than by position. For these two options, the list s must have no *-forms at its top level, and any top-level sublists of s must have a byte-string as its first element. Also, there must be no repeated byte-strings at the top level, and no repeated top-level sublists having the same name (first element). This must also be true of anything matching these *-forms. These restrictions allow the intersection algorithm to easily figure out which elements of s match up with which elements of s' when computing A(s,s'). (15) It is possible to recursively work out the intersections then for tags in an automatic manner. For example, the intersection of (tag (spend (amount (* range numeric (< 5000))) (account (* set 12345 67890)) (* reorder-insert (for socks shirt pants)) (date (* range alpha (>= 1997-01-01))))) intersects with (tag (spend (amount (* range numeric (< 1000))) (account (* set 87654 12345)) (for tie pants socks belt shirt) (date (* range alpha (< 1998-01-01))))) to produce (tag (spend (amount (* range numeric (< 1000))) (account 12345) (for tie pants socks belt shirt) (date (* range alpha (< 1997-01-01)(>= 1998-01-01))))) Ron Rivest

- Prev by Date:
**Re: Intersection of tag fields** - Next by Date:
**Multiple tags per cert** - Prev by thread:
**Re: Auth** - Next by thread:
**Re: *-forms in tags** - Index(es):