[cap-talk] A paper on web-keys

[Jed Donnelley]

On 1/17/2008 3:11 PM, Tyler Close wrote:
> One of the WWW 2008 reviewers of this paper wrote:
> 
> "Capabilities are *always* easier to implement, and the tradeoff is
> *always* about giving up control."
> 
> What is the canonical paper to critique in order to rebut the "giving
> up control" argument? Which paper had so much influence that people
> like the reviewer believe this fiction to the point of using star
> quotes?
> 
> --Tyler

Tyler,

I believe the closest thing to a "canonical" reference to
this "loss of control" with capabilities topic is the 'Rainbow' publication:

A Guide to Understanding Discretionary Access Control in Trusted Systems
http://www.fas.org/irp/nsa/rainbow/tg003.htm

which is moderately widely referenced.  There they have a
section on capabilities (7.1) where they say (among other
things) <see the second sentence of the third paragraph for
the most direct reference to loss of control>:
_______________
7.1 CAPABILITIES

In a capability-based system, access to protected objects such as files is
granted if the would- be accessor possesses a capability for the object.  The
capability is a protected identifier that both identifies the object and
specifies the access rights to be allowed to the accessor who possesses the
capability.  Two fundamental properties of capabilities are that they may be
passed from one accessor (subject) to another, and that the accessor who
possesses capabilities may not alter or fabricate capabilities without the
mediation of the operating system TCB.

Capability-based systems [8] provide dynamically changeable domains (name
spaces) for processes to run in.  Ability to access an object is demonstrated
when a process has a capability or ``ticket'' to the object.  The capability
also contains allowable access modes (e.g., read, write, execute).  In some
implementations, programs can contain capabilities or capabilities can be
stored in files.  They are protected by hardware and software mechanisms or by
encryption.  Capabilities can usually be passed along to other processes and
can sometimes be increased or decreased in scope.

A pure capability system includes the ability for users to pass the capability
to other users.  Because this ability is *not controlled* and capabilities can
be stored, determining all the users who have access for a particular object
generally is not possible.  This makes a complete DAC implementation,
including revocation, very difficult.  (Revocation may not be an issue,
however, since a user who has access to an object can make a copy of the
information in another object.  Revoking the user's access on the original
object does not revoke access to the information contained in the user's copy.
After revocation, however, changes can be made to the original object without
the knowledge of revoked users.) For a discussion on revokable capabilities,
see Redell's paper [9].

Since capabilities implement dynamic domains they can ideally limit the
objects accessible to any program.  This would limit a Trojan horse's access
to only the protected objects handed to it.  At this time, few systems have
been implemented with capabilities and very few, if any, have attempted to
implement a complete DAC mechanism.  Some research has been conducted in
restricting capabilities by overlaying a DAC mechanism [10].

Capabilities could be useful in enforcing the least privilege principle and
providing dynamically changeable domains, making discretionary access controls
less vulnerable to Trojan horse attacks.  However, in order to pass the class
C2 and above DAC requirements, the ability for users to pass capabilities to
other users must be sufficiently controlled.  There could be some design
difficulties in building capability-based mechanisms to satisfy the B3 DAC
requirement because of difficulty in implementing precisely defined groups
[11].  Also, at class B3 it is required that users be able to specify a list
of users that have permission (or do not have permission) to access each
object.  Capability-based systems are row-based mechanisms and do not easily
lend themselves to this function.  Deletion of an object from the system and
revocation of access present yet another problem.  The problem is that
row-based systems do not provide an efficient means of determining which users
have access to a given object.
...
In general, with profiles as with capabilities, answering the
question of who has access to a protected object is very difficult.  Since
this is usually an important question in a secure system and more efficient
mechanisms exist, profiles are not a recommended implementation of DAC.
...
7.6 SUMMARY

Access control lists, if implemented properly, can satisfy the DAC requirement
for any class.  Protection bits lack the ability to conveniently control
access to each object to the granularity of a single user.  Row-based
mechanisms, such as capabilities and profiles, may encounter design problems
with revocation of access and group access to objects.
_______________

Of course the above is just with regard to Discretionary Access
Control with capabilities.  The notion of Mandatory Access Control
with capabilities would cause the above authors to laugh.

I would say that regarding their statement:

"A pure capability system includes the ability for users to pass the capability
to other users.  Because this ability is *not controlled* and capabilities can
be stored, determining all the users who have access for a particular object
generally is not possible.  This makes a complete DAC implementation,
including revocation, very difficult."

The ability to communicate access constrained only by
constraints on communication also makes other aspects of
access control difficult such as logging and auditing
(knowing 'who' has access to what).

The reference that they give [11] is our old friend:

GLIGOR V., HUSKAMP J., WELKE S. LINN C. UND MAYFIELD W.:
Traditional Capability-Based Systems: An Analysis of Their
Ability to Meet the Trusted Computer Security Evaluation Criteria.
IDA Paper P1 935, 1986.

http://www.webstart.com/jed/papers/P-1935/

which is of course how I got there as I expect others do.

<I'll see if I can put those PDF files together this evening>

The above paper isn't widely referenced directly, likely because I know
of no on-line copy but the one I recently scanned.  Heh, I wonder
if I should take care not to let people know it is on-line?  I expect
most references to it (all?) come through the above Rainbow publication.
However, I looked into a few references through:

http://www.google.com/search?q=%22traditional+capability-based+systems:%22+gligor

Here are those I found:

http://portal.acm.org/citation.cfm?id=266761&coll=portal&dl=ACM

-> http://www.itl.nist.gov/div897/staff/barkley/rbacweb/dfpaper.pdf

Then there are these:

http://security.isu.edu/pdf/trfacman.pdf
and
http://security.isu.edu/pdf/ncsctg016.pdf

Here is a thesis from 2001 with a reference:

http://www.mnm-team.org/pub/Diplomarbeiten/fack01/HTML-Version/

A Babelfish translation of the relevant section of the thesis is:
____________
Capabilities (subject/rows) each subject possesses Capabilities Capabilities specifies the rights of access their owner 
on objects specified within the Capabilities. Capabilities are valid within a certain Domain. So that it can be excluded 
that Capabilities are illegitimately copied or produced, can produce or change only one control instance Capabilities [ 
GAL 87 ]. Individual programs can possess Capabilities. In addition, Capabilities can be stored e.g. in a file. They are 
protected thereby by hardware or software mechanisms and/or by coding mechanisms. A Capability can be sometimes also 
passed on and be made possible to so different subjects the access to specific objects. The delegation of rights of 
access is thus possible. The lease Privilege principle can be fulfilled by Capabilities, whereby besides a dynamically 
changing environment is supported [ SUM 97 ]. By the possibility of being able to pass Capabilities on it is to be able 
to determine however very heavily and/or not possibly, who has straight access to a specific object. This does not make 
the implementation of completely user-assignable access control politics (DAC implementation) simple. Investigations for 
the implementation of a complete DAC mechanism by means of Capabilities are into `` augmented capability architecture 
ton support lattice security and traceability to OF ACCESS on '' [ HEK 84]. The cancelling of rights of access is a 
further problem when using Capabilities. There are solutions also here nevertheless, then the article of D Redell treats 
`` Revokable Capabilities '' [ TALK 74]. Difficulties exist also with the precise definition and implementation of 
groups [ GHW 86 ]. A pure Capability based method is usually unsuitable due to these disadvantages.
______________

The above reference appears to derive from the Rainbow publication,
though he also references this book:

http://www.amazon.com/Secure-Computing-Safeguards-Rita-Summers/dp/0070694192

Has anybody read that book?

I don't know what this is:

http://www.thei3p.org/library/document_detail.html?document-id=12229

Just thought I'd respond in a bit more detail as I seem to
keep being drawn back to this topic.

--Jed  http://www.webstart.com/jed/