Re: Redirects and Revocation in a Capability Filesystem

On Fri, Nov 7, 2014 at 8:39 AM, Rob Meijer <rmeijer-qWit8jRvyhVmR6Xm/[email protected]> wrote:

> /fs2/$r1/Bob ->  dead link to /fs1/bob:r2 (r2 not available in r1 view)
>

> The base idea is that the '..' implied by the extended attribute usage can
> only ever be used in an amplify+filter-view operation by the second
> file-system.


I see. You're sacrificing expressiveness in order to avoid DAGs. I'd rather
avoid this second-class treatment of redirects. I imagine it would create
complexity for applications, dealing with special corner cases and
workarounds.

So, how do you ensure that /alice/Bob uses a different attribute than
/bob/Alice?


> /cap/ would be the mountpoint of your file-system
>

Why wouldn't /cap/ just itself be a capability? Seems to me we don't need
to pretend our ideal-world filesystems are mounted in ext-3 or whatever. :)


> for a moment skip the delegation process itself. At one point we end
> up with a revokable link in the carol directory

$link2=revokableref(


I feel that skipping the delegation process has hindered your
comprehension. Consider: If you did have a "revocableref" function, you'd
need to return TWO capabilities.

    $revoker,$ref = revokableref(destination)

At which point you'd need to somehow save the revoker for future use.
Atlernatively, you could create a revoker ahead of time, and associate it
with the revocable on construction:

   $ref = revocableref(revoker, destination)

Use of a redirect to model revocables avoids this conundrum simplify this
by reifying the (revoker,destination) pair as an object in the filesystem.
A redirect, of course, also permits other forms of useful intercession,
such as transparently changing the destination.



>
> A think I see a glimmer of the source of my disconnect. In the design I've
> been using, there is no such thing as a top node in the graph


This isn't an impediment. The technique works just as well for a forest, or
even for a fully cyclic graph, as it does for a tree. At essence, all we're
doing is keeping information about *a path*, and validating that this *path
still exists* before granting access to a resource.

For efficient performance, you would need an index that tells you for each
location to which other locations they are connected. I.e. you can't be
decrypting directory files or hashing pet names on every step. This index,
if exposed to users, would give them some information about connectivity
that you do not wish them to have.

And, of course, you'd also need a larger filtering factor at the start -
e.g. a filtering factor of about four billion for the first step, since you
don't have a common root. Instead of an initial branch filter factor of 256
(monospaced):

M             auth code
 AAAAAAAA     path elem
  BBBBBBBB    path elem
   CCCCCCCC   path elem
    DDDDDDDD  path elem
        HHHH  hmac

You might tweak it as follows:

M                auth code
 AAAAAAAA        path elem
     BBBBBBBB    path elem
      CCCCCCCC   path elem
       DDDDDDDD  path elem
           HHHH  hmac

In general, this method is highly tunable. I'm thinking I might support
tunable branch-filtering factors on a per-directory basis.


>
> As a result for me operations such as path resolution and (single)
> attenuation are CPU bound and relatively cheap


Well, sure. If I didn't want to bother with revocability, which is perhaps
THE most important attenuation pattern for secure interaction design, then
I also would have very cheap resolutions - just a simple auth code, a GUID,
and an HMAC. Or I could use Rumpelstiltskin hash trees by squeezing the
lattice of auth codes into one linear chain of secure hash operations.

But I think revocability - more generally, giving temporal attenuation the
same first-class treatment as spatial attenuation - is important enough
that I'm willing to take a performance hit in terms of inspecting an index.



Am I correct to believe that your approach requires:
>
> 1) A generic single root.
> 2) The file-system keeping a reference to this root at all times.
> 3) Tree traversal for finding candidates.
>

1) No.
2) No.
3) Yes. Sorta.

More generally, it's a graph traversal. Redirects allow us to overlay a
graph onto a tree. And we don't need to traverse the actual data structure;
we could traverse an indexed representation.


>
> it would be incompatible with my
> Rumpelstiltskin tree approach


This is quite possible. I certainly haven't been able to reconcile it with
your Rumpelstiltskin hash trees. I did spend some time trying, since your
Rumpelstiltskin tree approach does have some advantages, e.g. fixed-size
capability strings, and off-server attenuation. It seems the cost of your
approach is that you can only support very simplistic attenuation.


> I was kind of hoping that you had found a way that would allow me to limit
> the number of check-if-exists + decrypt + de-serializations to some single
> digit number.


Well, you don't need to decrypt anything with this technique, not with a
separate index. And depending on how you represent a connectivity index or
make use of memoization, you might need only a few lookups even for very
long paths.

But, fundamentally, you'll be validating existence for every object on a
path of effectively unbounded size. The idea of reducing to a single "check
if this object exists" doesn't seem very compatible with the idea of
avoiding exponential state explosions, at least without crippling the
redirect model into something Alice and Bob will both hate.

_______________________________________________
cap-talk mailing list
[email protected]
http://www.eros-os.org/mailman/listinfo/cap-talk