[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
*-forms in tags
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