[cap-talk] Capabilities and the NCSC Trusted Computer Security Evaluation Criteria (TCSEC)

[Jed at Webstart]

At 02:54 PM 10/30/2006, Bill Tulloh wrote:
>I've been trying to trace the history of capability-based approaches
>in the context of the emergence of the Trusted Computer Systems
>Evaluation Criteria (the Orange Book)...

As Bill mentioned I scanned in the following document:

Traditional Capability-Based Systems:
An Analysis of Their Ability to Meet the
Trusted Computer Security Evaluation Criteria

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

It was large enough that to make the scanning practical
I had to divide it into roughly 10 page sections.  I already
noticed that I put one page in twice (31).  If you take a look
at that document, please let me know if you notice any
other problems with the scanning - especially omissions.
Of course the scan was of an already poor quality
photocopy, but I believe everything significant in the
original paper can be read, though some of the OCR'ed
text is broken, especially in places where the photocopy
wasn't too good.

Here is my overall summary of this document.  These authors
absolutely trash (!) the object/capability approach to computer
systems, believing that it makes difficult or impossible just
about every important aspect of their Trusted Computer Security
Evaluation Criteria.

At a high level (more details below) I would say that their view is
that capabilities are designed to allow easy sharing of permissions
(direct communication of permission tokens) and that this facility
makes difficult to impossible nearly all the security features that
they believe are important for blocking inappropriate sharing of
permissions and auditing appropriate sharing of permissions.

There is one quote it paper that I've sadly lost that says that above
nearly perfectly, but I think the quotes below taken as a whole make
their position quite clear - despite their show of academic non bias
and thorough review of capability systems.

Still staying at a high level I would say their position stems from
two basic factors:

1. They don't appreciate and/or understand the fact that blocking
sharing of permissions between collaborating communicators
(sometimes referred to as "conspiring" communicators) is
simply not possible - with all the blocking and auditing
that goes along with that truth.

2.  They don't appreciate that by facilitating communication
of POLA permissions that systems end up being more secure
rather than less secure - contrary to their TCSEC.

I also don't believe they understand just how easy and convenient
revocation through a membrane can be.  I also believe that the
implementations that they considered (perhaps any implementations)
didn't have effective support for the sorts of revocation that they feel
to be important.  For example, run a program, give it some permissions,
the program ends, revoke all permissions that it was given directly or
that it received indirectly.  Of course in a capability system one can
extend that paradigm to requests on remote services.  I think that a
discussion of what one might call "temporary" capabilities vs.
permanent capabilities might be worthwhile on this list.

However, for now I'll comment in more details on the NCSC TCSEC
document (incidentally, the document referred to as Donnelley80
is an earlier version of :

http://www.webstart.com/jed/papers/Managing-Domains/

).  I believe the concerns of the authors about capability systems
are pretty clear, e.g.:

pp. 3 "merely possessing the capability ... is sufficient proof
that access should be granted.  Note that, if a capability is
ever stolen or given away, this protection mechanism can result
in other subjects accessing the object without incurring a
protection violation.  Thus, special care must be taken to
prevent the use of capabilities that are stolen while migrating
on off-line storage or among different sites of a network
[Nessett82, Donnelley80]"

pp. 13 "Whenever capabilities migrate on removable media, or among 
the network hosts,
their integrity must be maintained. Since capabilities in this 
environment are out of the
control of their creating system, the only possible approach to 
integrity maintenance is the
detection and rejection of capabilities whose integrity has been 
violated. The option of not
allowing capabilities to migrate is somewhat simplistic and, in many 
cases, impractical
[Lampson76]. Administrative controls, while helpful and necessary, 
are based on the
skills, care, and integrity of administrative personnel. Total 
reliance on such controls are
inadequate and impractical wherever capabilities migrate on off-line storage.
In general, to help detect whether any migrated object (e.g., a capability) is
changed, an encryption scheme can be used [Gligor79b]. This method 
encrypts both the
external representation of the object and a signature that may be 
computed from the external
representation when an object is placed on the removable media. When 
the type manager
reads an object from the removable media, it decrypts the external 
representation, computes
a new signature, then decrypts the returned signature and compares 
signatures. If the
signatures are the same, then the data is assumed to be correct. If 
not, the data is assumed
to be modified and the object is not restored. A similar scheme, 
which works for
capabilities but not for other types of objects, has also been 
proposed in [Chaum78].
Encryption-based mechanisms have also been proposed in [Nessett82, Donnelley80]
to prevent the use of stolen capabilities. Capability theft becomes 
important whenever
capabilities are allowed to migrate on off-line storage or among the 
sites of a distributed
system. Their re-introduction and use within the system by an 
unintended user must be
prevented [Nessett82, Donnelley80]."

pp. 14 "It must be noted that, regardless of the type of capability 
system, the access
authorization mechanism relies on (1) the capability integrity 
mechanism, (2) the capability
mapping mechanism, and (3) the ability of the processors and/or the 
operating system
software to protect their internal registers, data structures and 
capabilities from
unauthorized user access. (Such mechanisms must also be extended to 
prevent the theft of
capabilities wherever capabilities migrate across the sites of a 
distributed system).
Otherwise, the access authorization mechanism may be circumvented by users."

Then we start to get to the crux of their argument:
______________________________________________________________
pp. 26 "2.3.1 Security Policies

In traditional capability systems, capabilities are freely copyable 
and can be placed
in any storage object In the tagged memory approach, capabilities can 
be intermixed with
the data of storage object and in the partition approach, 
capabilities can be stored in the C-list
of the storage objects. This flexibility, although advantageous in 
many ways, causes
several important security policy and object management problems. In 
fact, these problems
are so great that traditional capability systems are unable to 
support any mandatory security
policies without extensions or basic modifications. (More information 
is provided in
Section 3.L4 - mandatory access control in the TCSEC.) Therefore, 
without extensions or
basic modifications, traditional capability systems are limited to 
the support of discretionary
security policies.

Discretionary security policies are based on the notion that access 
privileges for an
object may only be changed by the owner (creator) of that object 
[Saltzer75]. The three
important components of such policies are: (1) the distribution, (2) 
the review, and (3) the
revocation of access privileges. Note that the discretionary policies 
may allow an owner to
entrust the authority of further distribution and/or revocation of 
privileges to other parties at
his discretion.

     (1) Distribution of access privileges

In capability systems, if a capability for an object with the 
appropriate privileges can
be presented, no further validation is necessary. In this scenario, 
the identity of the subject
requesting access is not needed for access checking. Since possession 
of a capability is all
that is needed to access an object, subjects and their surrogates 
jealously guard capabilities.
However, there are several ways that capabilities can be leaked to 
outsiders. The first is
through the domain call. Since capabilities for the input parameters 
are copied and passed
from the calling domain to the called domain, the called domain can 
surreptitiously save the
input capabilities in a storage segment that only it can access. At a 
later time, the called
domain is invoked by its owner and passes back the saved capability. 
This Trojan Horse
attack is an example of how easily capabilities can be propagated 
without the knowledge of
the capability owner. [Note that both in the partitioned approach and 
in the tagged
approach, capabilities can be passed from domain to domain as 
parameters using the
parameter passing mechanism. No storage of the passed capabilities in 
shared, long-lived
objects is necessary to distribute the capability.]

Another method for acquiring a capability is to have it stored into a 
segment that is
shared with another user. For example, if one user has read access to 
a segment that
another user has write access to, anything written in that segment, 
including capabilities,
can be read and then used by the first user.

Since capabilities can be leaked to outsiders, owner-controlled 
distribution of access
privileges is not possible in traditional capability systems. 
However, it is possible to
modify such systems so they can support owner-controlled distribution of access
privileges. Such modifications are discussed in Section 3.4.

Instead of owner-controlled distribution, traditional capability 
systems support
"holder"-controlled distribution; that is, they support a policy in 
which any holder of an
access privilege can freely distribute the privilege to anybody else. 
This attribute has been
considered a major advantage of capability systems because the 
contrasting owner controlled
policies must rely on a single distribution authority, potentially 
making a system
somewhat inflexible [SaItzer75]. However, due to access review and revocation
requirements, it is often desirable to constrain the holder - 
controlled distribution policy so
that the owner of an object can delegate the right to distribute 
access privileges to only a
subset of all users that hold the capability. The delegation of 
access privilege distribution
cannot be supported in traditional capability-based systems. However, the same
modifications that are necessary for the support of owner-controlled 
distribution can also
support the delegation of access privilege distribution to other 
entities whom an owner
trusts."
__________________________

Notice that they refer to delegation as "leaking".  You can see from 
the above that
they feel that the "Security Policies" that can be supported by 
capabilities are
completely inadequate.

Then it gets worse:

pp. 27  "(2) Access Review
Access review is the mechanism which allows an owner of an object to 
discover the
identity of all users that have access to that object. The 
holder-controlled distribution policy
supported by traditional capability-based systems makes access review 
in a capability
system a very difficult procedure because all objects that can be 
read by a subject must be
examined for internal capabilities that also have the read privilege 
enabled. Finding all
capabilities that one subject can access requires searching the 
transitive closure of all objects
that can be read by that user. This is illustrated by an example in 
Section 3.1. When a
capability for an extended-type object is encountered, there is some 
uncertainty about which
capabilities the holder of the extended-type capability can actually 
access. This depends on
the function of the domain. Thus, access review in a capability 
system providing type
extension is possibly inaccurate. Note that even the partitioned 
memory approach cannot
avoid an extensive search since a potentially very large number of 
object C-lists may be
stored anywhere on disk space and, thus, all the disk space needs to 
be searched. In
systems with very large address spaces such searches are 
prohibitively expensive
regardless of whether tagging or memory partitioning is used for 
capability implementation.

If a traditional capability-based system is modified to support only 
owner-controlled
distribution of access privileges, then efficient access review by 
object owners becomes
possible. For example,..."

and the related on:

pp. 28 "In [Rede1174a,b, Gligor76,79c], it is shown that traditional 
capability-based
systems cannot support any of the review and revocation policies 
suggested above.
Modifications to capability systems that are necessary to support the 
above policies are
presented in Section 3.4."


By the time they get to reviewing the NCSC Criteria they clearly feel that
the rout is on.  The "Access Review" section is particularly damning, e.g.

pp. 35 "Such a review mechanism for a traditional capability system 
assumes that all
capabilities that allow direct or indirect access to an object can be 
found This assumption
requires a form of "reverse" transitive closure, which starts with an 
object and discovers all
o~ects containing capabilities for that object, repeating the process 
for all newly formed
objects. However, neither the TCB nor any other operating system 
module can rely on
extensive searches of the system storage, particularly in systems 
with virtual memory.
(Experience with traditional garbage collectors, which also require 
extensive memory-
searches, supports this contention [BIShop77].) This procedure is 
further complicated by
sealed capabilities, which must be unsealed during the search to 
determine what capabilities
are sealed inside.

and it goes on:

pp. 37 "3.1.1. 5 Impact of the Controlled Distribution of Access Privileges
Requirement on Traditional Capability-Based Systems

The interpretation of the controlled distribution of access 
privileges requires the
precise definition of the "authorized users" that can distribute 
capabilities. In a traditional
capability-based system, any holder of a capability is an authorized 
distributor of access
privileges.The capability and its access privileges are distributed 
by merely making a copy
of the capability (see Section 2.3.1). Thus, such systems may not 
satisfy the required
policy of user authorization. However, in some other capability-based 
systems, the
distribution of capability (and access privileges) is restricted in 
some ways and, thus, the
authorization policy supported by such systems differ from those 
supported by traditional
systems[Neumann75,77, Wu1f74]. (These modifications are discussed in 
Section 3.4.)
To determine whether a capability system can satisfy a given policy 
of controlled
distribution of access privileges, the authorization policy for 
capability propagation must be
explicitly stated or defined a model."

By the time it gets to "Mandatory Access Control" the situation is 
already hopeless, e.g.:

pp. 39 "3.1.4 Mandatory Access Control

Mandatory access control ensures that the subjects doing data accesses have
sufficient authorization for the data. Any secure system must support 
this concept."

and then without going into the gory details of one Mandatory Access 
Control example here:

"Although this problem also appears in non-capability-based systems, such as
MULTICS, SCOMP and UNIX, when mandatory access controls are implemented, the
problem can be solved in a simple way. By contrast, this problem 
cannot be solved in
traditional capability-based system without elimination of the 
reference count interface -an
unacceptable solution owing to the practical necessity of such a mechanism."

They even get some digs in related to Covert Channels, e.g. the summary:

pp. 57 "The three channel examples given in this section are not by 
any means a complete
list of channels that are unique to capability-based systems. Only by 
exhaustive analysis of
a concrete system implementation can such a listing be attempted."

They even dig in regarding what they refer to as "Trusted Facility 
Management", e.g.:

pp. 58  "The discovery of lost objects is a very complex task in traditional
capability-based systems.

An important difference between capability-based systems and other systems
models is the ability to store and distribute capabilities for the 
long term without any TCB
software intervention. With this ability, applications 
programmers/users may manage their
object storage and access individually without much system 
intervention. An important
consequence of providing this ability is that capability-based system 
functions, such as
storage reclamation and garbage collection, which are traditionally 
performed either
automatically or by operators, become more complex because of the 
need to discover all
outstanding capabilities. Garbage collection in a traditional 
capability system is an
extremely time consuming task [Bishop77]. Unless additional 
mechanisms are provided
for guiding the "directed" search for capabilities on secondary 
storage, exhaustive searches
may render the system useless for long periods of time. Note that 
directed searches of
system storage also require "reverse" transitive closures to be taken 
just as for capability
use recovery.

Similarly, user requests to the system operators or system 
administrators for the
recovery of specific capabilities that are accidentally erased (lost 
objects) may require
extensive memory searches and administrative system interfaces that 
are unnecessary in
other systems."


They give a summary of what they view as the basic problems when they discuss
potential modifications to "traditional" capability systems.  These 
are essentially
efforts to turn them into identity based systems.  Here are the four general
properties that cause problems:

pp. 59  "The following four general properties of traditional 
capability-based systems cause
security problems:

(1) Capabilities can be stored by any domain freely, without TCB software
intervention, in any segment of the storage system (uncontrolled propagation
property);

(2) Access authorization by capabilities does not require the identity of the
accessor, namely that of domains, processes, or users (ticket-based
authorization property);

(3) The access privileges, objects, and address space available to an 
accessor (i.e.,
domain, process, or user) can only be determined by taking the transitive
closure of all capabilities available to that accessor (transitive 
closure property);

(4) The identity of all accessors of any given object can only be determined by
finding all capabilities that allow accesses to that object by direct 
or indirect
addressing (reverse transitive-closure property).

The above properties of traditional capability-based systems cause 
difficulties in the
implementation of discretionary and mandatory access control 
policies, audit, and trusted
facility management (viz., Sections 3.1 - 3.3 above). Also, these 
properties cause
revocation of access to become difficult, or impossible, to perform. 
Revocation has also
been considered an important property of discretionary policy [Redell74b]."

With all this there is no doubt about their conclusions, e.g.:

pp. 71 "...traditional capability-based systems prevent the 
implementation of security
policy and accountability as required by the TCSEC, and make some 
aspects of trusted
facility management and recovery more difficult than those of other systems."

and:

"Descriptor-based systems are superior to
traditional capability-based systems in support of DoD policies and 
accountability."


 From that time forward you can be sure that every effort was made by the
DoD community to quash any development of capability systems, hence the
continued use of the disastrous ambient authority model that we have
in the market leading systems today.


I believe this document and a few others like it during this time
were essential in basically killing the object/capability approach
to computer security.  I also believe that any effort we make to
reverse this trend will have to answer the objections in this
and similar documents.

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