Redirects and Revocation in a Capability Filesystem

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