[cap-talk] KeyKOS and the Orange Book

[Bill Tulloh]

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). Whether or not
capability-approaches in general and GNOSIS/KeyKOS in particular fit
with the approach of TCSEC was a question that was asked repeatedly
during the 1980s. Although not necessarily classified, a lot of the
documents from this period are not easily accessible, so what I've
been able to piece together so far is rather spotty. I was hoping that
people on this list (especially the KeyKOS folk) might be able to fill
in some of the detail.

Here is a summary of what I've found so far:

Background.

The military security problem (the need for multi-level security)
seems to have been first recognized in the late 1960s as time-sharing
systems were first appearing. The story that is told is that a
contractor for the air force, McDonald Douglass I believe, asked the
air force if they could share a computer that had classified military
data with their non-military clients. At this stage the Air Force
realized they had no policy in place to deal with this.

This set in motion a couple of different activities: one was the work
on ADEPT-50 at System Development Corporation, a first attempt to
build a multi-level secure time-sharing system; the other was a
task-force to study the issue which resulted in the Ware report in
1970.

During the early 1970s, the Air Force' s Electronic Systems Division
established a group under the direction of Roger Schell that continued
to investigate this issue. They were responsible for much of the
foundational work in this area including, the Anderson report that
outlined the reference monitor/security kernel approach, as well as
sponsoring the Bell and La Padula modelling work. This work was
heavily Multics-centric: Schell did his PhD at MIT under Saltzer and
he and Paul Karger were the Tiger team that successfully attacked
Multics security. ESD sponsored two efforts to add multi-level
security to Multics: the Access Isolation Mechanism, and the Multics
Secure Kernel project. This continued until 1976 when the Air Force
decided to no longer fund this work.

Notably, two other projects from this period that (I believe) weren't
funded out of Schell's group, were the PSOS project at SRI led by
Peter Neumann, and the UCLA Secure Unix which was led by Gerald Popek.
PSOS was capability based, and I've seen the UCLA work  referred to as
capability-based as well, but I don't know enough about it yet to know
what that means.

During the latter half of the 70s, the activity in this area shifted
to the DOD Computer Security Initiative led by Stephen Walker,
eventually resulting in the creation of the National Computer Security
Center at the NSA, which focused their efforts around the Trusted
Computer Security Evaluation Criteria, aka the Orange Book. The first
appearance of the criteria was the Nibaldi report in 1979 that was
eventually refined into the final draft of the TCSEC in 1983, and made
a DoD standard in 1985.

Capabilities and the Orange Book

It is pretty clear from looking at the criteria that it was heavily
influenced by the Multics-centric work done by Schell's ESD group, and
very early on in the process the question of how do capability-based
systems fit with this model came up.

Even before the final draft of the Orange Book, there was interest in
GNOSIS and how it fit with the criteria. This seems to have been the
work of Susan Rajunas (at Mitre?). She produced a report in 1980 on
GNOSIS and organized a Workshop in 1982 on "Implementing DoD
Multilevel Security Policy on Capability-Based Operating Systems".

After the workshop, however, there seems to have been something of a
backlash against capability-based approaches. The view that
capability-based systems can't do military security date from this
time; e.g. Karger & Herbert, Boebert & Kain. Marv Schaefer, Chief
Scientist at NCSC, states that he "requested that Earl Boebert ...
write a paper for an NCSC Conference showing that multilevel security
confinement could not be assured in a pure capability based operating
system."

Recently, with the much appreciated help of Jed Donnelley, I was able
to track down a copy of report by Gligor, Huskamp, Welke, Linn and
Mayfield of the Institute for Defense Analyses titled: "Traditional
Capability-Based Systems: An Analysis of their Ability to Meet the
Trusted Computer Security Evaluation Criteria" The conclusion is that
they lack the ability, although the arguments aren't very persuasive.

At some point, around the time Key Logic was spun off, Susan Rajunas
joined them, and they began the KeySAFE effort to get KeyKOS certified
at the B-level. The evaluation process started in 1988 but I'm not
sure how far through the process they got before Key Logic folded in
1990.

Here is a timeline of the interactions between capabilities and TCSEC
that I have found.

1979: The Nibaldi Report -draft evaluation criteria
1980: Rajunas et al "Preliminary Security Review of GNOSIS: A
Capability-Based Operating System" Mitre Report, Aug.
1981: DoD Computer Security Center formed at NSA
1982 May: First Draft of Orange Book
1982: Workshop on Implementing DoD Multilevel Security Policy on
Capability-Based Operating Systems (presenters include Boebert, Cox,
Dahlby, Hardy, Nesset, Rajunas)
1983: Final Draft of Orange book
1984 Boebert publishes "On the Inability of an Unmodified Capability
Machine to Enforce the *-Property"
1987:Institute for Defence Analysis report released: Traditional
Capability-Based Systems An Analysis of their Ability to Meet the
Trusted Computer Security Evaluation Criteria
1987: TSCEC people visit Key Logic and determine that KeyKOS would be
a good candidate for B-level certification
1988: Evalution of KeyKOS for B-level security begins
1990: Key Logic goes out of business.

Beyond KeyKOS, I'm not aware of any other efforts in the US to have a
capability-based system achieve TCSEC certification. The SMITE project
in the UK was apparently another attempt to build a capability-based
multi-level secure operating system that began around 1987, but I
don't know much about this effort yet.

My reading of this episode shows a real clash of paradigms.
Capability-based systems didn't fit the trusted security model very
well. One possible way to deal with this is to reevaluate the model;
another is to declare the model sound and capabilities unfit. This
latter seems to be the dominant approach. A third way to deal with
this is to build the necessary abstractions on top of a capability
foundations that attempt to meet the model on its own terms; this
seems to be the approach that KeyKOS (and perhaps SMITE) took.

One can question the wisdom of the whole TCSEC approach, but it
certainly had a major influence on computer security thinking during
the 1980s, a period when capability-based approaches were in decline.

A lot of this material I have not been able to track down yet, like
the Rajunas report on GNOSIS, and the papers from the 1982 workshop
she organized. If anybody knows how to get hold of these I would love
to know. Any help would be greatly appreciated.  Likewise, I would
appreciate any clarifications and corrections on the above sketch of
events, no doubt it contains omissions and inaccuracies.

Thanks.

Bill