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

Five-tuple reduction (section 3.3.1) -- necessary fix


The section 3.3.1 (5-tuple reduction) of the proposed SPKI draft needs
to be fixed to accomodate general names as subjects.  This note
describes the problem, and how to fix it.

For the purposes of this note, I'll divide the set S of possible
subjects into three groups:
	S0 -- bare keys or their hashes
	S1 -- basic references having only a single name
		( basic-ref <key-hash> name )
        S2 -- references with two or more names
		( general-ref <key-hash> name1 name2 ... )
For convenience in this note, I'll denote a subject of any of these
types as 
	{k,name1,name2,...}
using braces to surround the initial key and the list of names.  (I'll
always give the key, since it is in any case implied for a floating-ref).

A certificate can be abbreviated as
	{k1,...} ==> {k2,...}      (i.e. issuer ==> subject )
ignoring the tag field, validity etc.  Here the issuer must be in S0 or
S1; we do not allow elements of S2 as the issuer of a certificate, because
it makes it impossible to tell whether the signer is the same as the issuer
without yet other certificates, leading to ambiguity and uncertainties.
However, the subject may be in S0, S1, or S2.

In the original write-up, a certificate chain was OK (suitable for
reduction) if the i-th subject was the same as the i-th issuer, e.g.
	cert 1:	{k1,A} ==> {k2} 
	cert 2:	{k2} ==> {k3,B}
	cert 3:	{k3,B} ==> {k4,C}
	cert 4:	{k4,C} ==> {k5}
is an OK chain.  Each certificate has a issuer the subject of the previous
certificate.  

This requirement is too strict, and doesn't accomodate subject names
in S2 properly.  For example, consider the name {k,alice,mother}.  Here
k might be my own key, and I want to talk about the key for alice's mother,
where "alice" is defined in my own name space (the space of k), and "mother"
is defined in alice's name space (let's call alice's key k').  What is
the appropriate certificate chain.
We start with the name
	{k,alice,mother}
that we wish to resolve.  We can not have a certificate with issuer
{k,alice,mother} as noted above.  But we might have a certificate
	{k,alice} ==> {k'}
which gives my definition of alice as the key k'.  This naturally
reduces our problem to figuring out what is meant by
	{k',mother}
since we have replaced the first part ({k,alice}) of our problem by the
appropriate replacement ({k'}).  Then we can use the certificate
	{k',mother} ==> {k"}
to get the desired result k", the key of alice's mother.

We just need to formalize the above process as follows:

We are given a certificate chain 
	C1,C2,...,Cn
and we want to figure out what it's reduction is.  That is, we want,if
possible, to reduce this to a single "equivalent" certificate C.

The issuer of the new certificate C is just issuer(C1).  To compute
the subject of the new certificate C:
	Let S = subject(C1).
	for j = 2 to n do
		if issuer(Cj) is a prefix of S
			then replace that prefix in S with subject(Cj)
		else error("certificate chain is not well formed")
	return(S)

In this case where issuer(Cj)=subject(C(j-1)), everything works just as
before.  When a subject is in S2, the new algorithm captures what I
believe is the correct semantics.

Note that the length of S is not necessarily decreasing during this process,
as a certificate may have a subject that is longer than its issuer, rather
than shorter.  For example, I might have defined
	{k,alice} ==> {k,susan,sister}				(*)
so that an ACL that had {k,alice,mother} as its subject could be followed
by the appropriate set of certificates, yielding a trace of S:
	S = {k,alice,mother}
	S = {k,susan,sister,mother}   (using the new certificate (*))
	S = {k'''',sister,mother}
	S = {k',mother}
	S = {k''}

The validity and tag fields should be handled as before, yielding a new
tag field that is the "intersection" of the tag fields of the certificates,
and a validity period that is the intersection of the validity periods of
the certificates.  For most of the examples above, one might expect the
tag field to be empty ( tag ), since these are just name/value definitions
(in SDSI terms) with no restriction on authorization.

I note that the ability to handle general names properly is something that
can NOT be accomplished within the existing X.509 framework, even though one
often hears claims of the sort that everything that can be done in SPKI or
SDSI can be done by appropriate coding in X.509-world.  

To summarise: We have proposed a revised certificate chain reduction procedure
              that handles general names properly when they occur as subjects
              in a certificate in a certificate chain.  The new procedure
              generalizes the procedure given in 3.3.1 of the draft, and should
              replace that procedure there.