Re: Redirects and Revocation in a Capability Filesystem

On Fri, November 7, 2014 01:11, David Barbour wrote:
> 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.

Using the extended-attribute approach the initial picture would look
different:

/fs1/bob and /fs1/alice are directories in the primary system
/fs1/bob/Alice is a redirect to /fs1/alice:r1 (the r1 attribute of /alice)
/fs1/alice/Bob is a redirect to /fs1/bob:r2 (the r2 attribute of /fs1/bob)
/fs1/alice/foo is an object

So from this 'view' we would have a DAG.

If r1 is reachable (by a second file-statem) using the capability $r1,
etc, than:

/fs2/$r1 is a view on /fs1/allice that filters out any non-r1 extended
attributes.

/fs2/$r1 -> /fs1/allice
/fs2/$r1:r1 -> /fs1/allice:r1
/fs2/$r1/Bob ->  dead link to /fs1/bob:r2 (r2 not available in r1 view)
/fs2/$r1/Bob:r1 -> membrane r1 attribure for /fs1/alice/Bob
/fs2/$r1/foo -> /fs1/allice/foo
/fs2/$r1/foo:r1 -> membrane r1 attribure for /fs1/alice/foo

So while there is a hidden cycle between /alice and /alice:r1, non of the
two file-systems, nor any of the operations on the filesystems are exposed
to being able to do any non DAG compliant graph operations.

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.

Result: Any operation is performed on one of two pure DAG views, so no
operation can ever suffer from any cyclic reference issues.

Want to delete /fs1/bob/Alice? The result is the following need to get
deleted:

/fs1/bob/Alice
/fs1/alice:r1
/fs1/alice/Bob:r1
/fs1/alice/foo:r1

There would neither be a need nor a possibility to perform any cyclic
reference related operations on revocation.

Yes, there are issues with membrane approach, but the extended-attribute /
dual-file-system hack makes clear that cyclic references should not be
part of the stack of problems AFAICS.

That is unless we count some specific TOCTOU implementation issues. I
won't go into these now, but they are trivially solvable.


>
>> 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.

Let me try to elaborate:

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

$somecap would be a sparse capability for a specific node that in reality
could look like for example pv89acggp1289cklatsbcxqp517cnns1

SPARSECAP(somepath) would be the specific sparse capability representation
of the node between the braces.

ROSPARSECAP(somepath) would be the specific sparse capability
representation of the read-only attenuated version of the node between the
braces.

>     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.
>

Lets for a moment skip the delegation process itself. At one point we end
up with a revokable link in the carol directory to an attenuated version
of a decomposition of the revokable link in the bob directory that points
at one of allice her sub trees.

basically :

$link2=revokableref(
  attenuation(
    decomposition(
      revokableref(
        decomposition(alicedir,"foo")
      ),
      "bar"
    ),
    READ_ONLY_ATTENUATION
  )
)


I can understand how the xor stuff could work for just:

$link1=revokableref(
   decomposition(alicedir,"foo")
)

What I would like to understand is how it could still work for finally
accessing /$link1/baz.txt without the same storage and performance issues
that come with the extended-attribute dual-file-system membrane approach I
tried to explain I found to be lacking in both performance and storage
usage.

>>
>> 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.

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, just
combinations of sparse capability entry nodes and relative paths from
there. So instead of having a single '/' anchor point that holds both
/alice and /bob, I could have two root sparse capabilities, $alice for
allica and $bob for bob. Not even the file-system would be able to
distinguish if pv89acggp1289cklatsbcxqp517cnns1 equates /$alice or /$bob
or /$alice/foo/bar . The file-system would just take
pv89acggp1289cklatsbcxqp517cnns1, do some operations on it to conclude
that the underlying data (file, dir, symlink or extended attribute) had to
be serialized (and encrypted) in some file for example
//var/rumpelstiltskin/6e2/55f/2c5e00c40ff85b98874924c214831ace87.aes . No
such file means no access. File exists: use
pv89acggp1289cklatsbcxqp517cnns1 as key to decrypt the data.


As a result for me operations such as path resolution and (single)
attenuation are CPU bound and relatively cheap compared to the disk+aes
operations needed for de-serializing the actual nodes. If something wants
to access /capfs/rw-pv89acggp1289cklatsbcxqp517cnns1/foo/bar/baz.txt, I
have no need to check if any intermediate level node exist. Just some
chain oof hmac sha256 operations on the different path tokens to calculate
some path under /var/rumpelstiltsken/. The file-sytem has no clue about
any root and even if it had, looking for candidates would significantly
increase the number of IO+decryption operations needed, possibly even more
than the extended-attribute approach.

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.

If so, that basically means it would be incompatible with my
Rumpelstiltskin tree approach, and even if it wasn't still would require
substantial expensive de-serialization operations for traversing
redirects.

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. Am I correct in concluding that your technique is
fundamentally incompatible with my approach?



> 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
>