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

For SPKI



Carl,

In reply to:
>Tony,
>
>I'm obviously confused.  I think it would make the most sense if we were to
>try a concrete example, one under the last BNF I sent out and one with your
>tag-ids, and compare them.  Care to suggest one?
>
> - Carl

I am happy to oblige.  It may even be of benefit to someone besides myself.

It is not easy to craft a "simplest" example that will exercize the range
of constructs that SPKI users may encounter.  Rather than begin with a full
and gloriously complex real-world example, I would like to start with some
underlying assumptions, and some abstracted examples.  This way, if any of
my assumptions are ill-informed, I can retreat gracefully;)

1.  Assumptions and Terminology

1.1 Tag Collection is allowed.

    If two principals P1 and P2 certify my key (separate certs) with tags
    X and Y, respectively, and with delegation, then I may certify my agent
    with a cert that says (taglist X Y).  Where appropriate, I may have
    restricted tags X and Y in some way to X' and Y' where, foreinstance,
    X' = intersect(X',X).  (ie, X' = subset(X)).

1.2 Tag Propagation is allowed.

    Given that I am certified with tag (and delegation)

      T1:  (spend (* range (amount (<1000))) (* set (for X Y)))

    I can create two tags, each a proper subset of T1, that are not subsets
    of each other, nor necessarily disjoint, as in

      T2:  (spend (* range (amount (<800))) (for X))
      T3:  (spend (* range (amount (<700))) (for Y))

    (here it looks like I can spend 1500, but these are limits on single
     purchases.  Or a different example, like awarding {Mon, Tue, Wed}
     vacation days to employees in departments X and Y would be more to
     the point.  I could restrict to {Mon, Tue} for X, {Tue, Wed} for Y.)

    And I can place these together in a taglist on a certificate for my
    agent.  Or I can issue tag T2 to one agent and tag T3 to another.

    (I sometimes refer to tags T2 and T3 as "subs", subordinate to T1.
     I call T1 a "sup", a superior to T2 and T3.  I introduce the term
     "sibs", siblings, to describe the relation between T2 and T3, and note
     that in general, neither tag-intersection nor tag-union is appropriate
     between siblings!)

2.  Abstracted Examples

2.1 "Well, That's another fine mesh you've gotten me into!"

    Here, I rapidly depict 9 principles in 4 tiers.  The two principals in
    the top tier are the "root" authorities, and likewise represent the two
    points of which actual end-services are requested.  Lines leading down
    from a principal lead to a cert [] they have issued on the key of a
    principal below, with tags indicated inside.  Assume all tags are of
    type "spend", intentionally depicted opaquely here by the letter S.
    The example is not meant to be exhaustive, but simply exhausting;)

    Tier 1.               P1                P2
                        /    \            /    \
                       /      \          /      \
                      /        \        /        \
                 [S S S]     [S S S][S S S]     [S S S]
    Tier 2.      -------      ------------       -----
                    P3             P4              P5
                      \          /    \          /    \
                       \        /      \        /      \
                        \      /        \      /        \
                       [S S][S S]    [S S S][S S]      [S S]
    Tier 3.            ---------      ----------       ------
                          P6             P7             P8
                               \          |         /
                                \         |        /
                                 \        |       /
                                [S S S][S S S][S S]
    Tier 4.                     -------------------
                                          Q

    At the bottom, agent Q has a key authorized with 8 tags distributed
    across 3 separate certificates.  Q submits a purchase request to P2.
    We assume that P2 obtains the 3 certs on Q's key KQ.  None of these
    certs were issued by P2 directly.  What to do first?

    P2 may first authenticate the sig on each of the bottom three certs.
    It may be more efficient to test if the request (call it R) is itself
    covered by any of the tags in these certs (has a non-empty intersect.)
    But we will be perverse and suppose that each of the three certs has
    at least one tag that seems to work.  So we must attempt to validate
    all three certs.

    A glance at tier 3 shows that this may involve 5 more certificates,
    and again, none of these were signed by P2.  As we move further up
    the mesh, a total of 31 tags in 12 certificates need to be examined.
    That is 31 tag-intersects, and 12 signatures.

    Rather than continue with this marginal example as it is, I redraw it
    by relabeling the tags to indicate the original issuing authority.

2.2 Another fine mesh.

                         [C1]              [C2]
    Tier 1.               P1                P2
                        /    \            /    \
                       /      \          /      \
                      /        \        /        \
                 [1 1 1]     [1 1 1][2 2 2]     [2 2 2]
    Tier 2.      -------      ------------       -----
                    P3             P4              P5
                      \          /    \          /    \
                       \        /      \        /      \
                        \      /        \      /        \
                       [1 1][1 2]    [1 2 2][2 2]      [2 2]
    Tier 3.            ---------      ----------       ------
                          P6             P7             P8
                               \          |         /
                                \         |        /
                                 \        |       /
                                [1 1 1][2 2 2][2 2]
    Tier 4.                     -------------------
                                          Q


    Here, the introduction of tag-ids, with tag-id-major-number equal to
    the original issuer's autocert-id, make the necessary validation easier
    to digest.  Consider that the first tier-4 cert "[1 1 1]" has no tags
    that derive their authority from P2.  This not only suggests that they
    will likely not intersect with a valid request (to P2), but even if by
    chance they did, the cert-chain leading upwards from it cannot possibly
    validate, so why bother?  One omniscient glance shows that this serves
    to eliminate 5 certs from the mesh, plus the autocert C1 at the point
    where these chains would terminate.

    Total workout: 24 tags examined for tag-id, 17 tag-intersects, 7 certs.

2.3 Another possible improvement.  To motivate this, we assume that the
    principals P1 and P2 have crafted the "high-level" spending tags they
    created for a purpose.  They may wish to limit spending on certain items
    or from certain accounts, to certain sellers, etc.  Purely as a form of
    "bookkeeping", they issue these tags to themselves in an autocert, with
    a tag-id-minor-number that serves simply to distinguish them from one
    another.  Now when they issue (possibly restricted versions of) these
    tags to tier-2 keys, they let the authority flow from these autocerts.

    This leads to the last diagram (that I will draw tonight!)
    To make it easier for me to draw, I will use A B C D for P1 tags, and
    x y z w for P2 tags, rather than 1.1, 1.2, ... 2.1, ... etc.


                      [A B C D]         [x y z w]
    Tier 1.               P1                P2
                        /    \            /    \
                       /      \          /      \
                      /        \        /        \
                 [A B D]     [B C D][x y z]     [y z w]
    Tier 2.      -------      ------------       -----
                    P3             P4              P5
                      \          /    \          /    \
                       \        /      \        /      \
                        \      /        \      /        \
                       [A D][C y]    [B x y][y z]      [y w]
    Tier 3.            ---------      ----------       ------
                          P6             P7             P8
                               \          |         /
                                \         |        /
                                 \        |       /
                                [A C D][x y z][y w]
    Tier 4.                     -------------------
                                          Q

    (Why am I reminded of wrinkled yellow peas?)

    Now P2 begins as in the previous diagram, eliminating cert [A C D]
    first on the grounds that is has no lowercase tag-ids.  P2 must
    (blindly) check the intersection of request R with 5 tags x y y z w].
    Note that the "y y" siblings may not be identical internally.

    (For efficiency, if there had been a great many tier-4 certs, P2
    could begin by intersecting R with the tags in its own autocert.)

    Suppose P2 finds that the only valid intersection of R is with z.
    This eliminates the need to validate [y w] and its immediate parent.
    Upon examining P7's certs, it can now eliminate [B x y] without ever
    performing a tag-intersection, based on non-matching tag-ids.

    This leaves only P7's [y z] and P5's [y z w] (and P2's autocert) to
    validate, and even here the choice of tags to test is limited.

    Final tally:  20 tag-ids examined (including 4 in autocert)
                   4 tag-intersects conducted
                   4 certs validated (including autocert)

Conclusion:  This was a contrived example.  But the main point is that
these "structured tag-ids" serve only for efficiency, and should not have
any effect upon the result of validation.  No tag or cert is discarded
that would have been needed, and in the event that, by mislabeling or by
mal-intent, some inappropriate tag or cert were included, either the tag
would be eliminated by intersection, or its cert by validation.

Indeed, there is no hard requirement that the autocert-ids be absolutely
distinct in a global, or even a local sense.  Its just that more collisions
will mean more work.

I believe that tag-ids sully somewhat the "cleanliness" of the certs, but
would like to see them made optional somehow.

___TONY___ (way past bedtime.)