[cap-talk] Use-case: hybrid capability systems

[Jonathan S. Shapiro]

I have a use case that I do not know how to adequately solve in
real-world terms in a pure capability system. Perhaps someone else will
be able to propose one.

I want to preface this by saying that I do not have the statement of
requirements adequately refined. In particular, I suspect that one
result of the discussion will be significant revision to the threat
model.


Use-Case:

We have a group of people who are working collaboratively on a
graph-structured data set. Ground rules for normal use are:

  1. All parties have co-equal access.
  2. The legitimate activities of the parties involve frequent
     transfer of capabilities within the group.
  3. All parties are permitted to update the graph, by which I
     mean that they are expected, in the normal course of their
     efforts, to insert capabilities into the structure.
  4. The collaborative nature of the effort makes it likely that
     party A, who has legitimate access in their own right to some
     capability C, will interact during decision making with party
     B (also a member of the group), and in the course of that 
     interaction the capability C will be duplicated back and forth
     during the discussion. One result of this is that the capability
     that ultimately gets inserted into the data structure is likely
     to be C', where C' is the result of some number of exchanges
     of the original capability C.

We assume that the parties A, B are not hostile (if they are, that is an
auditing problem). Party B now leaves the project. We now wish to ensure
that:

  R1. B's authority to mutate the data set is eliminated in the absence
      of conspiracy with a continuing group member.
  R2. B's authority to *access* the data set is similarly eliminated in
      the absence of conspiracy with a continuing group member.
  R3. No portion of the graph structure is damaged as a consequence of
      the enforcement of R1, R2.
  R4. The implementation mechanism used to enforce R1, R2 is scalable
      and efficient under conditions of normal use (i.e. when group
      membership is stable, under normal operating conditions).
  R5. The elimination of a member of the group, and the subsequent
      permission modifications necessary to enforce R1, R2 have an
      efficient implementation.

Some constraints must be satisfied in any practical solution:

  C1. No solution requiring new storage to be allocated during every
      communication between the authorized parties is practical.

  C2. No solution requiring a mediator is admissible. Rationale:
      we cannot afford to more than double the cost of every object
      invocation. Solutions that are able to perform a mediation check
      and somehow cache the result in order to achieve reasonable
      efficiency are acceptable.

  C3. While we assume that parties A and B are not hostile, we assume
      pragmatically that they are unable to successfully remember all
      of the places that they may have stored capabilities into the
      data set.

  C4. We are not concerned with *copies* made by the parties -- only
      with capabilities to the definitive data set.


Anybody see a way to do this with a pure capability design? It's
completely straightforward in a hybrid design.


shap