Re: Redirects and Revocation in a Capability Filesystem

I've been working on tackling the symlink as revocation point myself. For
me it has led to the conclusion that you basically have two choices:

* A redirect is a simple overlay point that excludes any possibilities for
further decomposition or attenuation.
* A redirect starts of as a single node, but grows in a membrane like way
to a tree in itself.

I have been thinking about how I could use the 'cutting point' as you
describe it in a multi-filesystem setup, and I've come basically to a two
file-system design that could choose to pick one of the above (both with
their own drawbacks):

1) Create an 'extended attribute' node in the main tree for each redirect
with as content the capability for the parent node.
2) Don't allow users access to extended attributes without supplying the
capability to the node it belongs to.
3) Allow a second file-system access to extended attributes using the
attribute capability directly.
4A) Decomposition, attenuation and recursive revocation become possible by
the fact that the second file-system can traverse the first (one up and
down from there) and can create or delete extended attributes in a
membrane like way. This comes at a price wrt performance and storage needs
though.
4B) Alternatively the redirect can provide just a base overlay providing
proper access to all sub node's and full subtree revocation but no
decomposition or attenuation. While there are no performance and storage
issues, the result is a rather inflexible cut-of point.

Do these choices match your findings?

Am I correct you believe to have found to allow for 4A like scenario's
without paying the performance or storage price for dynamically creating
and deleting the extended attributes throughout the tree?


On Thu, November 6, 2014 00:49, David Barbour wrote:
> I'm currently developing a filesystem-like abstraction for a wiki-based
> software platform (Wikilon) for a concatenative capability-based bytecode
> and language (Awelon Bytecode (ABC), Awelon Object (AO)). If you're
> interested, I expect you can find my github pages. In this message,  I
> describe the design that's been evolving for the capability secure
> filesystem, in particular my effort surrounding redirects and revocable
> attenuation. Some of you may find it interesting.
>
> I'll call this WFS (Wikilon's FileSystem) for this article.
>
> BACKGROUND
>
> Unlike conventional filesystems, where files are strings or streams of
> bytes, most objects in WFS are made of bytecode. State is modeled by pure
> functions representing objects of roughly the form:
>
>     µObject.{query : Value → Value, update : Value → Object}
>
> Update messages can thus change the object state, and query messages will
> return a value. There is a strong separation between queries and updates
> for reasons that would take a lot of text to explain. While we could
> represent objects that are simple stacks or queues or whatever, one of my
> goals is that many objects eventually support human interaction and direct
> manipulation - e.g. via queries like "how would you render in SVG?" or
> "what is a menu of options for a human?". I haven't worked out the details
> there.
>
> A critical feature is that 'update' allows an object to protect its own
> invariants, which is thus very different from conventional files where any
> agent with write access is free to damage its structural integrity.
> Sharing
> update access to an object thus allows much easier collaboration between
> mutually distrustful agents.
>
> Utility of "query-only" or "update-only" attenuation should be obvious. In
> addition to query and update, I have "read" and "write" authorities that
> operate at the bytecode level. I.e. if you 'write' an object, that means
> you're directly replacing the object. Objects cannot protect themselves
> from writes. Similarly, objects cannot hide information from those with
> 'read' authority.
>
> Besides stateful but purely functional objects, I have stateless scripts
> that may query or update dozens of objects in response to a message.
> Scripts thus support filtering or transforming specific queries or
> updates,
> providing type type adapters and lenses on other objects in the system,
> modeling 'smart' constructors, extending WFS in ad-hoc ways. Scripts are
> capability-secure. They are granted exactly no authority based on location
> within the file system.
>
> The separation of scripts from purely functional stateful objects isn't
> strictly necessary.
>
> But it's a good idea. Separation simplifies extensibility, i.e. if we add
> new scripts they can potentially access the same state resources as
> accessed by existing scripts, so there is no privileged state in that
> respect. Separation reduces entanglement, i.e. because objects can perform
> meaningful computations even if separated from their environment.
> Separation offers more opportunities for parallelism, i.e. because it's
> easy to compute queries and updates on many different objects at the same
> time. Separation enables more optimizations, i.e. because we can easily
> integrate code and optimize when one script invokes a known other script.
>
> Besides scripts and stateful objects, we have directories, and redirects.
>
> Like conventional file systems, WFS organizes data into a tree structure.
> This is useful from an administrative point of view. Each user would be
> granted a space in the WFS tree, and each application might be granted a
> space in a user's tree. Agents and users may share mutual spaces for
> shared-state communications. It is possible to track quotas, or reset
> whole
> subdirectories. Directories also provide stable names by default, which
> have many advantages over volatile names typically produced by `new
> Object()`. (We may, of course, simulate `new` with a script that has
> authority over a directory and a counter.)
>
> Attenuation of a directory provides the same attenuation to all the
> children of that directory. A write authority on a subdirectory is
> necessary to create or delete children. A query authority is necessary to
> enumerate children.
>
> Redirects are the last big idea of WFS.
>
> Redirects serve a similar role to symbolic links or mounts in conventional
> systems. I envision that each user in the Wikilon filesystem would be
> granted their own little space (with read-write authority), and a
> "/public"
> space might then be mounted into it via redirect. Redirects are
> transparent
> with respect to all messages received by them directly, but may be
> distinguished or manipulated by reads and writes on the parent directory.
>
> Redirects serve a critical role in supporting...
>
> TRANSITIVE REVOCABILITY
>
> Directly granting capabilities to a directory has a major weakness that
> you
> can't effectively take it back. Best you could do is up and move your
> entire directory, which might break other things. There are many use cases
> for granting capabilities limited not just spatially, but also temporally.
> We want the helpful expert to dive in and make a few repairs. But inviting
> the cable guy into your home shouldn't confer a standing invitation.
> Revocability is among Ka-Ping Yee's ten principles for secure interaction
> design [1].
>
> Earlier, I mentioned that attenuation of a directory, e.g. reducing
> read-write authority to a read authority, will provide similarly
> attenuated
> access to all the children of that directory. A similar principle should
> apply to redirects. A redirect provides indirect access to a resource. If
> that resource is a directory, then that means we should have indirect
> access to all the children of that directory. As far as the user is
> concerned, deleting the redirect should be equivalent to deleting the
> directory.
>
> Thus, redirects become clear "cut points" for revocation.
>
> Usefully, these redirects - cut points - remain visible in our directory
> structure, clearly indicating which authorities have been granted (albeit,
> only those we can revoke). Visibility is another principle for secure
> interaction design. Further, revocation composes in an interesting way: a
> redirect is constructed with another capability, which itself may
> independently be revoked, thus enabling 'chains' where every agent on the
> redirect path has some authority to revoke access (or transparently
> replace
> the redirect with something else).
>
> It would be up to best practices, capability patterns, to make effective
> use of redirects.
>
> REPRESENTATION OF CAPABILITIES
>
> My design goals include keeping capabilities opaque, stable, reasonably
> short, and suitable for use in a URL, without sacrificing security
> properties. I don't plan to support encryption or distribution at the WFS
> layer.
>
> To support opacity and stability, objects have textual pet names within a
> directory such as "foo" or "user2625", and external names are constructed
> as HMAC(serverSecret, parentName|utf8(petName)). The HMAC ensures opacity,
> i.e. even given a parent and a external names, and a common naming
> convention, you cannot determine the child's pet name. The deterministic
> nature of this function ensures stability. If users want to model unstable
> names, as generated by allocation and `new Object()`, they must do so
> explicitly.
>
> The object name doesn't confer any authority. It's just used to search for
> objects in a global index. Instead, authority comes from coupling this
> object name with some authority codes and another HMAC.
>
> To help keep object names short, I came up with the idea of partially
> overlapping these IDs with an XOR function.
>
> For example, let's say we have a 224-bit hash, and we don't want to
> truncate either the object name or the HMAC. One option is to lay them out
> side by side, resulting in 448 bits, or 75 characters in base64. We can
> cut
> this down with the following layout: overlap the last 192 bits of object
> ID
> with the first 192 bits of the HMAC, resulting in 32+192+32 bits = 256
> bits, or 43 characters in base64. The cost of this compaction is that our
> search is a bit more involved: only 32 bits are exposed for indexing, and
> we'll occasionally encounter collisions. Fortunately, we can resolve this
> collision by applying the HMAC to each candidate and finding which (if
> any)
> are a match.
>
> I doubt I'm the first to have this idea. But it's new to me, and I'm
> feeling pretty clever about it. :)
>
> In the absence of redirects, use of object name, authority, and HMAC would
> be sufficient. Redirects and transitive revocation require a lot more
> information.
>
> I've spent a fair amount of time thinking about this. I rejected Hansel
> and
> Gretel bread crumbs both because worst-case state burden is exponential
> with the number of redirects, and because any attempts to the alleviate
> state burden (e.g. by eating the bread crumbs when deleting a redirect)
> will result in unstable names and hinder interesting patterns like
> temporarily disabling a directory. The best approach I've so far been able
> to think of is to simply include full path information in each capability.
> Then, before accepting a capability as valid, Wikilon will verify the
> path.
>
> The capability would bulk up far too much if we simply laid out this path
> information end-to-end. But, fortunately, we can use a similar technique
> to
> what was proposed earlier, but tighter. We only need to expose the first 8
> bits of each element in the path, and the last element - our object -
> should still expose 32 bits to reduce the number of HMAC efforts. For an
> N-step path, thus, we'll need about 8N+248 bits (for a 224-bit hash,
> again). This is much more compact than URLs! A 25-step path wouldn't be an
> issue.
>
> I was originally hoping to have fixed-size capability strings, but keeping
> path information in the capability seems cleaner, and I'm pretty satisfied
> with this compact result.
>
> Your thoughts are welcome!
>
> Best,
>
> Dave
>
> [1] http://zesty.ca/pubs/csd-02-1184.pdf
> _______________________________________________
> cap-talk mailing list
> [email protected]
> http://www.eros-os.org/mailman/listinfo/cap-talk
>