Redirects and Revocation in a Capability Filesystem

--===============5348074773167198448==
Content-Type: multipart/alternative; boundary=047d7bdc853443b4d10507253ce4

--047d7bdc853443b4d10507253ce4
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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:

    =C2=B5Object.{query : Value =E2=86=92 Value, update : Value =E2=86=92 O=
bject}

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 =3D 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

--047d7bdc853443b4d10507253ce4
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I&#39;m currently developing a filesystem-like abstraction=
 for a wiki-based software platform (Wikilon) for a concatenative capabilit=
y-based bytecode and language (Awelon Bytecode (ABC), Awelon Object (AO)). =
If you&#39;re interested, I expect you can find my github pages. In this me=
ssage, =C2=A0I describe the design that&#39;s been evolving for the capabil=
ity secure filesystem, in particular my effort surrounding redirects and re=
vocable attenuation. Some of you may find it interesting.<div><br></div><di=
v>I&#39;ll call this WFS (Wikilon&#39;s FileSystem) for this article.<br></=
div><div><br></div><div>BACKGROUND</div><div><br></div><div><div>Unlike con=
ventional filesystems, where files are strings or streams of bytes, most ob=
jects in WFS are made of bytecode. State is modeled by pure functions repre=
senting objects of roughly the form:</div><div><br></div><div>=C2=A0 =C2=A0=
 =C2=B5Object.{query : Value =E2=86=92 Value, update : Value =E2=86=92 Obje=
ct}</div><div><br></div><div>Update messages can thus change the object sta=
te, and query messages will return a value. There is a strong separation be=
tween queries and updates for reasons that would take a lot of text to expl=
ain. While we could represent objects that are simple stacks or queues or w=
hatever, one of my goals is that many objects eventually support human inte=
raction and direct manipulation - e.g. via queries like &quot;how would you=
 render in SVG?&quot; or &quot;what is a menu of options for a human?&quot;=
. I haven&#39;t worked out the details there.</div><div><br></div><div>A cr=
itical feature is that &#39;update&#39; 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. Sharin=
g update access to an object thus allows much easier collaboration between =
mutually distrustful agents.=C2=A0</div><div><br></div><div>Utility of &quo=
t;query-only&quot; or &quot;update-only&quot; attenuation should be obvious=
. In addition to query and update, I have &quot;read&quot; and &quot;write&=
quot; authorities that operate at the bytecode level. I.e. if you &#39;writ=
e&#39; an object, that means you&#39;re directly replacing the object. Obje=
cts cannot protect themselves from writes. Similarly, objects cannot hide i=
nformation from those with &#39;read&#39; authority.</div><div><br></div><d=
iv>Besides stateful but purely functional objects, I have stateless scripts=
 that may query or update dozens of objects in response to a message. Scrip=
ts thus support filtering or transforming specific queries or updates, prov=
iding type type adapters and lenses on other objects in the system, modelin=
g &#39;smart&#39; constructors, extending WFS in ad-hoc ways. Scripts are c=
apability-secure. They are granted exactly no authority based on location w=
ithin the file system.</div><div><br></div><div>The separation of scripts f=
rom purely functional stateful objects isn&#39;t strictly necessary.=C2=A0<=
/div><div><br></div><div>But it&#39;s a good idea. Separation simplifies ex=
tensibility, i.e. if we add new scripts they can potentially access the sam=
e state resources as accessed by existing scripts, so there is no privilege=
d state in that respect. Separation reduces entanglement, i.e. because obje=
cts can perform meaningful computations even if separated from their enviro=
nment. Separation offers more opportunities for parallelism, i.e. because i=
t&#39;s easy to compute queries and updates on many different objects at th=
e same time. Separation enables more optimizations, i.e. because we can eas=
ily integrate code and optimize when one script invokes a known other scrip=
t.=C2=A0</div><div><br></div><div>Besides scripts and stateful objects, we =
have directories, and redirects.</div><div><br></div><div>Like conventional=
 file systems, WFS organizes data into a tree structure. This is useful fro=
m an administrative point of view. Each user would be granted a space in th=
e WFS tree, and each application might be granted a space in a user&#39;s t=
ree. Agents and users may share mutual spaces for shared-state communicatio=
ns. It is possible to track quotas, or reset whole subdirectories. Director=
ies also provide stable names by default, which have many advantages over v=
olatile names typically produced by `new Object()`. (We may, of course, sim=
ulate `new` with a script that has authority over a directory and a counter=
.)</div><div><br></div><div>Attenuation of a directory provides the same at=
tenuation to all the children of that directory. A write authority on a sub=
directory is necessary to create or delete children. A query authority is n=
ecessary to enumerate children.=C2=A0</div><div><br></div><div>Redirects ar=
e the last big idea of WFS.=C2=A0</div><div><br></div><div>Redirects serve =
a similar role to symbolic links or mounts in conventional systems. I envis=
ion that each user in the Wikilon filesystem would be granted their own lit=
tle space (with read-write authority), and a &quot;/public&quot; space migh=
t then be mounted into it via redirect. Redirects are transparent with resp=
ect to all messages received by them directly, but may be distinguished or =
manipulated by reads and writes on the parent directory.</div><div><br></di=
v><div>Redirects serve a critical role in supporting...</div><div><br></div=
><div>TRANSITIVE REVOCABILITY</div><div><br></div><div>Directly granting ca=
pabilities to a directory has a major weakness that you can&#39;t effective=
ly take it back. Best you could do is up and move your entire directory, wh=
ich might break other things. There are many use cases for granting capabil=
ities 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 y=
our home shouldn&#39;t confer a standing invitation. Revocability is among =
Ka-Ping Yee&#39;s ten principles for secure interaction design [1].</div><d=
iv><br></div><div>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 princip=
le should apply to redirects. A redirect provides indirect access to a reso=
urce. If that resource is a directory, then that means we should have indir=
ect access to all the children of that directory. As far as the user is con=
cerned, deleting the redirect should be equivalent to deleting the director=
y.</div><div><br></div><div>Thus, redirects become clear &quot;cut points&q=
uot; for revocation.</div><div><br></div><div>Usefully, these redirects - c=
ut points - remain visible in our directory structure, clearly indicating w=
hich authorities have been granted (albeit, only those we can revoke). Visi=
bility is another principle for secure interaction design. Further, revocat=
ion composes in an interesting way: a redirect is constructed with another =
capability, which itself may independently be revoked, thus enabling &#39;c=
hains&#39; where every agent on the redirect path has some authority to rev=
oke access (or transparently replace the redirect with something else).</di=
v><div><br></div><div>It would be up to best practices, capability patterns=
, to make effective use of redirects.</div><div><br></div><div>REPRESENTATI=
ON OF CAPABILITIES</div><div><br></div><div>My design goals include keeping=
 capabilities opaque, stable, reasonably short, and suitable for use in a U=
RL, without sacrificing security properties. I don&#39;t plan to support en=
cryption or distribution at the WFS layer.=C2=A0</div><div><br></div><div>T=
o support opacity and stability, objects have textual pet names within a di=
rectory such as &quot;foo&quot; or &quot;user2625&quot;, 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 commo=
n naming convention, you cannot determine the child&#39;s pet name. The det=
erministic nature of this function ensures stability. If users want to mode=
l unstable names, as generated by allocation and `new Object()`, they must =
do so explicitly.</div><div><br></div><div>The object name doesn&#39;t conf=
er any authority. It&#39;s just used to search for objects in a global inde=
x. Instead, authority comes from coupling this object name with some author=
ity codes and another HMAC.=C2=A0</div><div><br></div><div>To help keep obj=
ect names short, I came up with the idea of partially overlapping these IDs=
 with an XOR function.=C2=A0</div><div><br></div><div>For example, let&#39;=
s say we have a 224-bit hash, and we don&#39;t want to truncate either the =
object name or the HMAC. One option is to lay them out side by side, result=
ing 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 =3D 256 bits, or 43 characte=
rs 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&#39;ll occasionally=
 encounter collisions. Fortunately, we can resolve this collision by applyi=
ng the HMAC to each candidate and finding which (if any) are a match.</div>=
<div><br></div><div>I doubt I&#39;m the first to have this idea. But it&#39=
;s new to me, and I&#39;m feeling pretty clever about it. :)</div><div><br>=
</div><div>In the absence of redirects, use of object name, authority, and =
HMAC would be sufficient. Redirects and transitive revocation require a lot=
 more information.=C2=A0</div><div><br></div><div>I&#39;ve spent a fair amo=
unt of time thinking about this. I rejected Hansel and Gretel bread crumbs =
both because worst-case state burden is exponential with the number of redi=
rects, and because any attempts to the alleviate state burden (e.g. by eati=
ng the bread crumbs when deleting a redirect) will result in unstable names=
 and hinder interesting patterns like temporarily disabling a directory. Th=
e best approach I&#39;ve so far been able to think of is to simply include =
full path information in each capability. Then, before accepting a capabili=
ty as valid, Wikilon will verify the path.=C2=A0</div><div><br></div><div>T=
he capability would bulk up far too much if we simply laid out this path in=
formation end-to-end. But, fortunately, we can use a similar technique to w=
hat was proposed earlier, but tighter. We only need to expose the first 8 b=
its 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 p=
ath, thus, we&#39;ll need about 8N+248 bits (for a 224-bit hash, again). Th=
is is much more compact than URLs! A 25-step path wouldn&#39;t be an issue.=
</div><div><br></div><div>I was originally hoping to have fixed-size capabi=
lity strings, but keeping path information in the capability seems cleaner,=
 and I&#39;m pretty satisfied with this compact result.</div><div><br></div=
><div>Your thoughts are welcome!</div><div><br></div><div>Best,</div><div><=
br></div><div>Dave</div><div><br></div><div>[1]=C2=A0<a href=3D"http://zest=
y.ca/pubs/csd-02-1184.pdf">http://zesty.ca/pubs/csd-02-1184.pdf</a></div><d=
iv><br></div><div><br></div></div></div>

--047d7bdc853443b4d10507253ce4--

--===============5348074773167198448==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

--===============5348074773167198448==--