[cap-talk] Description of s13 - in context, confinement addendum

[Jed Donnelley]

At 07:52 PM 7/17/2007, Jonathan S. Shapiro wrote:
>Jed:
>
>I would like to "go meta" on this conversation.
>
>The reason we are having so much trouble in our discussion of S13

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

>is that the description given in that section of Managing Domains leaves
>too many things unstated. Perhaps it relies on statements elsewhere in
>the document that I had no time to find.

Perfect.  I was going to "go meta" on this topic anyway.  I was really
only using the #s13 reference as an example of technology to pull
into other discussions, but since it has gotten so much attention
now I feel I should explain it more thoroughly.

Firstly I think you need to understand the environment at LLNL in
1980/1981:

A.  Most importantly that we had written essentially all our own
software at that time.  That included network drivers and protocols,
operating systems, compilers, libraries, and applications (mostly
scientific simulations).  There may have been a little sharing
with Los Alamos or Scandia at the time at the application or
library level, but not very much.  It was essentially a closed
community.  We had even designed and implemented much of our
own hardware until shortly before that time, including all the
network hardware, specialty hardware like a display crossbar,
etc.  In 1979 we started using the first piece of networking
hardware that wasn't made in house (the Hyperchannel 50Mb/sec
Ethernet-like hardware that I did the definitive simulations
studies of, e.g.:

J. E. Donnelley and J. W. Yeh, Simulation Studies of Round Robin 
Contention in a Prioritized CSMA Broadcast Network, Third University 
of Minnesota Conference on Local Area Networks, October 1978.

J. E. Donnelley and J. W. Yeh, Interaction Between Protocol Levels in 
a Prioritized CSMA Broadcast Network, Proceedings of the Third 
Berkeley Workshop on Distributed Data Management and Computer 
Networks, August 1978, pp. 123-143. Also in Computer Networks 3 (1979) 9-23.
)

B.  By 1981 the NLTSS implementation was well underway.  It
was essentially complete except for the LTSS emulation.  It
was a password-capability, network operating system:

http://en.wikipedia.org/wiki/NLTSS

with just the one "communicate" system call.  At that
time the kernel knew nothing about capabilities which
occurred strictly at the presentation and application
levels.

C.  Our systems were separated by an air gap from any
other hardware or software that anybody else might have
had a hand in (e.g. the ARPANet or the nascent Internet
of the time).

D.  Quite a common practice at LLNL during that period was to
print out various computer output on very high speed line
printers (30k lines/minute), and this output often included
program dumps.  These dumps were often left in "boxes"
that were little shelves labeled by user ID for pickup
in an open common area.

So ... When you suggested that we should have done end-to-end
encryption, you didn't understand the environment of the time.
At the time there was no value to us in end-to-end encryption.
It wouldn't have protected us from any legitimate threat and
of course it would have come at a significant cost.

What did concern us was that with the password capabilities
that we were using, every time one of those dumps was sitting
in one of those boxes, anybody could pick up the dump and
with a little work extract the password capability for the
"home" directory for the user.

I remember having an interesting debate with Andy Tannenbaum
(Amoeba, Minix:  http://en.wikipedia.org/wiki/Andrew_S._Tanenbaum )
when I was in London to give the Managing Domains paper.
Andy argued strongly that there was no need to protect
capabilities specially in the memory of processes because
the processes memory space already needed to be protected.
If some of the memory of processes was being exposed
improperly, then that was the problem that should be
addressed, not giving extra protection to the more sensitive
capabilities.

While I appreciate the above argument, it was simply wrong
for our environment.  Passwords for users were especially
sensitive (and treated so at LLNL - we had a special
computer to compare password hashes called the
"combination checker").  The fact that what amounted
to a user password (in the form of a password capability
to a user home directory) could show up in a dump which
could in turn show up in a box in a shared common area, I
considered unacceptable.

Somewhat ironically Tannenbaum's argument partly
smoothed the waters and we never did end up doing
anything to protect capabilities in the memory
of processes (except for a brief, abortive bit of work
on access list capabilities - a concept that I'd like
others on this list to understand as it seem to
mix ACLs and capabilities in an interesting way,
and it was essentially what was used in the DCCS) -
right through to 1995 when the last NLTSS system
was shut down.

Of course in later years there weren't nearly so many
dumps printed out.  Even then though there were still
no computers (e.g. personal workstations) on a TCP
network connected to those production systems.  Such
workstations were treated essentially like smart
terminals - only to process keyboard input and
output, so the basic environmental issues above continued
to hold throughout the life of the NLTSS system.

So, with that let me answer your questions:

>Here are some things one needs
>to know that are not clearly stated stated in that section:
>
>1. When are keys generated? I have asked this several times, and I don't
>recall that you have answered this yet.

I believe I answered it in:

http://www.eros-os.org/pipermail/cap-talk/2007-July/008288.html

You said, "Do you assume that the encryption key(s) used by
the supervisor are generated by some strongly random mechanism
at process startup, or is it possible in your system to
generate a static binary image that contains pre-validated
capabilities within its program image?"

and I replied, "The former."

We assumed that the private encryption key (one) was generated
and held by the supervisor on behalf of each process when
the process was created.  We of course understood the
issues of random generation as they were known at that time.
We had a similar issue with the encryption mechanisms for
the password capabilities themselves, though I don't recall
how effectively the randomness was gathered at the time.
Probably not adequately by today's standards.

The assumptions as stated in the paper are:
__________________
We assume that every process A has a secret decryption algorithm, 
which we will denote by Au, (u = up into the bright light of day). We 
also assume that any process can encrypt data to be sent to A with a 
public encryption algorithm, which we will denote by Ad (d = down 
into the dark world of encryption). Therefore, for any process A and 
data c, we have AuAdc = c. Finally, we assume that Au and Ad commute, 
AuAdc = AdAuc = c. The reader is referred to [Lem79-19] for further 
discussion of such algorithms.
__________________

and we say later in that section:
__________________
The private encryption key and the intermediate results can be 
protected in several ways. For example, in a multiprogrammed OS 
component the transformations can be performed by the OS kernel in 
response to a virtual user instruction (only the kernel knows the 
process's private decryption key). In a smaller single-domain system 
(e.g., a microprocessor system), it might prove effective to have the 
transformations performed in a hardware device that alone knows the 
system's private decryption key.
__________________

The above seems to me to make the questions you ask fairly
clearly answered, including:

>2. Which parts of which keys are held by whom? Which parts by the
>respective domains and which parts by their supervisors? Without this,
>it is not possible to assess what protection is actually achieved.

The private key is only available to the supervisor.  It is used
in what appear to the processes to be indivisible virtual
instructions that perform the transformation in table 1:

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

namely:

i.  The virtual instruction to transform a capability from
it's internal form into the form suitable for a sending buffer,
in the case of the public key protection for A sending to
B this was BdAuAu (the public key for B was supplied to
the instruction by the application and was assumed to be
a clear text part of the capability.

ii.  The virtual instruction to check and transform a
capability into it's internal form, e.g. as received
by B from A, BdAuBu to check c, then BdAdBu to store.

>3. The description does not describe who is responsible for which parts
>of which transforms. The domains? The supervisor? The transport?

The supervisor alone has access to the private key, so
the supervisor is responsible for the virtual instructions,
including insuring that no intermediate forms show up
in the memory space of the process.

>4. The notation of the diagram is confusing. I understand the
>annotations on the arcs and the "in memory" notations (though the "in
>memory" notations appear poorly chosen to me).

In what sense?  I don't see how there could be any other notation
used.  Perhaps you are referring to the label "In memory"?  I can
see how that might be confusing, because to be sure those forms
in the sending and receiving buffers are also "in memory".  What
that label refers to is the generic form that is stored in memory
for general manipulation.  The forms in the sending and receiving
buffers are only suitable for their communication roles.

>  I do not understand the
>annotations *inside* the domains that seem to appear at the head/tail of
>the arcs, and these are not explained. Hmm. On reflection, the head/tail
>annotations appear to describe the cryptographic transform applied at
>the sender/receiver sides.

Exactly.

>I still need to know who does the transform (app or supervisor
>or transport).

The transport protocol (incidentally our own invention:

Watson, R. W.,
"Delta-t Protocol Specifications,"
Lawrence Livermore National Laboratory, Report UCRL-52881 (November 1979).

a protocol that I still believe has it's own value that was
missed in the TCP inflation.  Delta-t was used for a time by Mach)

just dealt with transport issues - along the lines of TCP.
It of course knows nothing about the content.  As I noted
above, there was no need in our environment for end-to-end
encryption.

The data shows up in buffers in the applications directly as
sent from one process to another.  Because of this of course
it is important that the forms of the capabilities in the
buffers are safe (protected) as well.  Consequently what shows
up on the arcs also shows up in the respective sending and
receiving buffers.

Of course we imagined caching transformed capabilities for
repeat use.  For example, there is no need to keep re encrypting
a file capability every time it was sent to the file server).
Similarly the file server need not repeatedly do the receiving
transformation on capabilities that it receives.  It can
just keep a cached copy of the untransformed capabilities from
active sources.  We had a library, "cachlib" that was suitable
for such caching.  Doing such caching would substantially cut
down on the costs of the cryptographic operations.

>5. Issues of transmission are being horribly conflated with issues of
>in-memory capability protection.

I'm not sure how you got that conflation out of the paper.  Some
of that may be the different perspective of today.  The reviewers
(this mechanism was published twice, in:

J. E. Donnelley and J. G. Fletcher, Resource Access Control in a 
Network Operating System, Proceedings of the ACM Pacific '80 
Conference, San Francisco, November 1980, pp. 115-125.

and again in:

J. E. Donnelley, Managing Domains in a Network Operating System, 
Proceedings of Local Networks and Distributed Office Systems 
Conference, London, May 1981, pp. 345-361.

) didn't seem to have the difficulties you are having.
Of course they read the papers from start to finish.
It was probably unreasonable of me to point you at the
one mechanism and hope that you could understand it
fully from just reading that section.  I was hoping to
be able to just use some of the concepts presented
there, but I can see how that would be confusing.

>This makes the entire picture
>unnecessarily complicated. Combined with my issues [1,2] I find the
>whole thing fairly incomprehensible.

I hope the above helps to clarify what was going on.

>In the absence of clear statements on points [1,2], it is not possible
>to say whether this scheme is protected.
>
>Here are my *conjectures* on the answers:
>
>[1] I still don't know.

Answered again above.  There is one public/private key pair
generated per process when the process is created.  The
private key is kept by the supervisor for the virtual
instructions.  The public keys are conceptually part of
the network address and appear as part of the capabilities.

>[2] Every domain X holds Xu (it's own decryption key).

No, the private key for a process is kept by the
supervisor for the process - only to be used during
the protected virtual instructions (and if we add
confinement as part of the sending and receiving
operations when checking a network address for
a capability - not proposed in #s13).

>Any domain A may
>promiscuously obtain the encryption key Bd for a second domain B.

Right, it comes clear text with the capability, conceptually
part of the network address.

>[3] All encryption is performed by the respective applications. There is
>no encryption assumed by supervisor or transport.

No.  As you note, that would make the whole mechanism useless.

>[4] Notations at tail/head of arc describe transform applied by the
>respective domain prior to send and after receipt, respectively.

Right, except the transformations are performed by virtual
instructions (system calls) by the supervisor on behalf of
the process.

>If these assumptions are correct,

They aren't.  I hope you'll take the time to reconsider the
mechanism with the correct assumptions.  I'm sorry about
the rather confusing and piecemeal way it ended up being
introduced.  I still believe the #s13 mechanism to be a
rather elegant solution to the problem we were facing,
even if the cryptographic operations available for use
would make it impractical.

Note that the #s13 mechanism doesn't have the confinement
property that I was trying to describe when we started
this thread.

To add confinement (which as I note above wasn't a relevant
issue at LLNL at the time) I believe it suffices to require
valid decryption of a network address (with redundancy for
the check) from a capability when sending a message.  The
way NLTSS was set up, communication could be done directly
with network addresses.  With that approach of course there
was no confinement.  To add confinement one would have to
require a suitably encrypted capability to send or receive
a message.  Still, the TCB would need to know only a bare
minimum about the format of capabilities - enough to
extract and check for validity a network address.

What interested me about this whole discussion is that
one could even get the effective value of a descriptor
based capability system (both capability protection
as I believe you've described and confinement, along
the lines of DVH, RATS, etc.) with capabilities pretty
much as data (not stored separately in a c-list).  It
is true that to do so with this scheme the TCB must
know enough about a capability to safely pull a network
address out of it (to authorize communication), but to
me that is a rather minor addition.

Of course the protection in such a scheme depends on the
safety of the cryptographic operations - which a classic
c-list system does not.  I make no claims about the
practicality of such an approach (e.g. the costs of the
cryptographic operations, etc.).  I expect it would be
entirely impractical - hence a gedanken system.

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