Re: Redirects and Revocation in a Capability Filesystem

On Thu, Nov 6, 2014 at 3:58 PM, Rob Meijer <rmeijer-qWit8jRvyhVmR6Xm/[email protected]> wrote:

>
> cyclic redirects however simply can not exist given that every redirect
> adds a level of leaf node's that guarantee a DAG for the primary file
> system.
>

Redirects are combinatorial, not linear. I.e. consider:

   /bob and /alice are directories in the primary system
   /bob/Alice is a redirect to /alice
   /alice/Bob is a redirect to /bob
   /alice/foo is an object

   Distinct ways to access /alice/foo:

    /alice/foo
    /bob/Alice/foo
    /alice/Bob/Alice/foo
    /bob/Alice/Bob/Alice/foo

Two redirects leads to four relevant permutations. If we can figure out how
optimize it, we might consider the last two equivalent, in the sense that
they have the same revocation behavior: if either redirect is cut, access
to foo is lost. Thus, combinatorial rather than permutative... but still
exponential.

We can't readily eliminate cycles, i.e. because /a/b/c/d/e/f/g/a/foo is
remarkably different from /a/foo with respect to revocation behavior.
Fortunately, we can collapse repetitive cycles that contribute nothing to
revocation behavior. For example, /a/b/c/d/e/f/g/a/b/c/d/e/f/g/a/foo is
effectively equivalent to /a/b/c/d/e/f/g/a/foo.


> Could you sketch how, given a redirect, we can do

decomposition membrane operations without as
> you state it adding breadcrumbs throughout the sub tree?
>
> Lets say we have:
>
> /cap/$alicecap/foo/bar/baz.txt
>
> and a redirect (that alice can revoke)
>
> /cap/$bobcap/alicedata -> /cap/sparsecap($alicecap/foo)
>

I don't know your naming conventions. But if I understand right, I'd tweak
it just a bit.

    Alice holds a master capability to /alice.
    Bob holds a master capability to /bob.
    /alice/foo/bar/baz.txt is a resource.
    Alice wants to share access to this resource to Bob.
    Alice creates a redirect:
        /alice/sharing_baz_with_bob → cap(/alice/foo/bar/baz.txt)
    Alice grants to Bob the capability to her redirect.
    Bob adds this capability to his directory as:
        /bob/alicedata → cap(/alice/sharing_baz_with_bob)

At this point there are two redirects involved.

One redirect is owned by Bob. This redirect exists entirely for Bob's own
convenience. Bob could just as easily stored his capability in a
spreadsheet, or printed it out and stuck it in his wallet. Alice knows
nothing about it.

The other redirect is owned by Alice. Alice gave her redirect a convenient
name so that later, when she's done sharing, she can delete it. This would
be the 'cut point', providing both visibility ("oh! I'm still sharing that
file with bob!") and revocability.

Of course, to make effective use of this does require 'good practices',
e.g. naming conventions, and awareness of this pattern by application
developers.


>
> Now lets say bob wants carol to have:
>
> /cap/$carolcap/bobsalicedata -> /cap/ROSPARSECAP($bobcap/alicedata/bar)
>
> that bob would be able to revoke, and that would also get revoked when
> alice revokes bob his redirect.
>

Bob has a lot of options.

Option A:

     /bob/sharing_alicedata_with_carol →
         attenuate(cap(/alice/sharing_baz_with_bob))
    give carol:  cap(/bob/sharing_alicedata_with_carol)

Option B:

    /bob/sharing_alicedata_with_carol →
          attenuate(cap(/bob/alicedata))
    give carol:  cap(/bob/sharing_alicedata_with_carol)

Option C:

     /bob/sharing_alicedata_with_carol → cap(/bob/alicedata)
     give carol: attenuate(cap(/bob/sharing_alicedata_with_carol))

Option D:

     /bob/sharing_alicedata_with_carol →
           cap(/alice/sharing_baz_with_bob)
     give carol: attenuate(cap(/bob/sharing_alicedata_with_carol))

There are subtle differences between these options. But any of them would
get the job done.

Carol, of course, may do whatever she wishes with her cap.


>
> I would be really interested in using a less costly solution than the
> above one (in fact the costliness is what keeps me from wanting to
> actually implement a revocability membrane filesystem). Could you maybe
> take me through the above scenario using your concepts?
>
>
Let's say Alice deletes /alice/sharing_baz_with_bob.

When Bob tries to use his cap, he'll get a 'object does not exist' error.
Because his cap contains information about the full path from root. The
system will first check that /alice exists, then that
/alice/sharing_baz_with_bob exists.

To make this efficient mostly regards the encoding of capabilities, trading
search (CPU time) for space (compact representation). E.g. if all you have
is 2 bytes of an identifier.

Essentially:
  ALICE/SHARE
is encoded as:

    ALICE
        SHARE    (+)
   --------------
     AL(I+S)(C+H)(E+A)RE

Albeit, using the globally unique locator hashes instead of the English
names, and using xor for (+).

This lets us quickly filter down capabilities: after decoding 'AL', we can
narrow our candidates down to /ALICE and /ALLOY and a few other things.
Then we subtract ALICE and ALLOY, exposing SHARE and some unrecognized
value. Then we know we encoded /ALICE/SHARE because that's the only option
remaining.

I probably have a cleaner description of this at [1].

[1] https://github.com/dmbarbour/wikilon/blob/master/docs/StateModels.md

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