Tannenbaum's Amoeba system is one example of a distributed operating system. One of the major ways this system differs from the model of distributed operating systems illustrated by DEMOS, for example, is that the Amoeba system uses cryptographic methods to guard capabilities from tampering by users:
Conventional Model:
Modifiable by User || Hidden inside Kernel
||
Varialbes || Capability List
||
||
Amoeba Model:
Modifiable by User || Hidden inside Kernel
||
Varialbes || (not much!)
Capabilities ||
||
Despite the fact that Amoeba capabilities are just bit patterns, in the same
way as any other variable, and despite the fact that user code may
freely modify bits in these patterns, Amoeba offers a considerable
amount of security!
The reason is that capabilities in Amoeba are protected by cryptographic means. As a result, while a user may easily damage a capability by changing the bit pattern, it is very hard for users to deliberately create a valid capability.
Cryptographic protection of capabilities has several major advantages; first and foremost, it allows users to store capabilities in any data structure; users may directly store capabilities in files, in records, or in arrays. If the capabilities are in a list managed by the kernel, this is much harder to do! (As an example of the difficulty of doing so, imagine the problems that arise if a UNIX user needs to save an open file descriptor, which is effectively a capability for a file, returned by the open() system call. The most the user can do is save the integer which is used as an index into the system-maintained list of open files of that user process, and this integer has no meaning beyond the life of that process.)
The primary disadvantage of cryptographic protection of capabilities (aside from the obvious problem of guaranteeing that the cryptographic method being used is actually secure) is that the system can no-longer find all capabilities. In a conventional capability system, for example, garbage collection can be used to reclaim inaccessable storage, and the kernel can automatically update capabilities to point to the current location of resources that have migrated. Under Amoeba, none of this is possible!
The most obvious way for an operating system to protect capabilities by encryption is for the system to manufacture the capability, then encrypt it before passing it to the user, then reverse the encryption every time the user presents the capability to the system. For example:
User || Kernel
or || or
Client || Server
||
Request new resource --->
|| Create Capability
|| Encrypt
<--- return capability to user
store capability ||
Pass capability to kernel --->
|| Decrypt
|| Use Capability
||
This model uses a secret key, or password, held by the kernel, to encrypt and
decrypt capabilities. If all local kernels in a distributed system have the
same password and they have the same secure encryption algorithm, then
users may freely pass capabilities around, and the kernel need not fear
that users will be able to intentionally forge a particular capability.
Unfortunately, this scheme relies on keeping a secret password, and it also suffers from problems of accidental creation of valid capabilities by users. Consider the following:
User || Kernel
or || or
Client || Server
||
Pass random number --->
|| Decrypt
|| Use as Capability
||
What are the chances that a random bit string passed to the kernel
will be interpreted as a valid capability after decryption? This
depends strongly on the structure of a capability!
The natural form of a capability in a distributed system is a permission
to send a message to a process. Thus, a capability might be as simple
as
The key is to make sure that the encrypted capability is sparse -- that
is, that the vast majority of random bitstrings do not decrypt to make
valid capabilities. One easy way to do this is to use a one-to many
mapping as part of the encryption process; that is, each bit in the original
item is represented by many bits in the encrypted form. Consider the
following:
The trouble with this scheme is that the checksum defeats the encryption.
As a general rule, cryptanalysis -- that is, derivation of the key or password
to a cryptographic algorithm from example encrypted messages, is greatly
simplified by the presence of any kind of redundancy in the messages, and
checksums are almost perfectly suited to the job of aiding the cryptanalytical
process.
If reliability in the face of accidents is the only criterion, this is no
problem, but if malicious users may be trying to crack the encryption scheme,
it is useful to add an extra encryption step:
Most notions of the use of capabilities in distributed operating systems
revolve around the rights to use certain objects implemented by certain
servers. Thus, the basic representation of a capability boils down to:
The second key idea in server-side authentication is that the object-id
field, as assigned by the server, can have considerable internal structure.
For example, one subfield might be used to identify the object being used,
while another subfield might be used to verify that the capability is valid:
One alternative is to have the server assign a random number to each new
object it creates. In effect, these numbers are used as passwords to protect
the resources under that server. If the server remembers these random
numbers in a
table, indexed by object number, it may quickly check capabilities it is
handed in order to see that they are valid references to objects it has
created. Random numbers used for such purposes may be generated by a
pseudorandom number generator, and if high levels of security are needed,
a cryptographically secure pseudorandom number generator will suffice
(standard texts on cryptography discuss these).
The net result of these kinds of extensions is a capability system where
most of the responsibility for security rests on the servers, but this burden
is fairly light. In Amoeba, standard library routines are provided for the
standard capability representation; these make it very easy for users to
write servers that conform to a highly secure model, while eliminating most
of the concern for security from the kernel.
capability
__________
|__________|
\_\_\_\_\__checksum
__________ ________
|__________|________|
| encrypt |
___________________
|___________________|
The checksum in this scheme can be made arbitrarily large in order to make
the entire scheme arbitrarily resistant to accidental creation of valid
capabilties. The more bits assigned to the checksum, the less likely it
will be that a randomly chosen bitstring will be indistinguishable from a
legitimate capability.
capability
__________
|__________|
| encrypt |
__________
|__________|
\_\_\_\_\__checksum
__________ ________
|__________|________|
| encrypt |
___________________
|___________________|
The first encryption step makes the input to the checksum algorithm resemble
a random number, so that, even if the password is found for the second
encryption step, the user can't use this to attack a specific capability.
| server id | resource id |
|___________|_____________|
|___________|_____________|
Tannenbaum's Amoeba system takes advantage of this, recognizing that the
server itself can play a major part in capability authentication. This is
called server side authentication; in such schems, a checksum field
is generally added, as in the previous encrypted schemes:
| server id | resource id | checksum |
|___________|_____________|__________|
|___________|_____________|__________|
This is verified by the kernel when a process tries to use a capability to
send a message to a server, but the checksum algorithm is no secret; any
process can forge a valid checksum. The primary purpose of the checksum
at this level is merely to speed error detection for accidentally created
invalid capabilities.
| server id | resource id | checksum |
| |verify|number| |
|___________|______|______|__________|
|___________|______|______|__________|
Here, the server might assign consecutive numbers to each object it creates;
these are easily forged, but the key to the security -- the redundancy in the
capability representation, rests in what the server stores in the verification
field.
server:
repeat
receive message m from client c
if message requests resource creation
create resource number n
password[n] := random
return
If the verification code plus the object number are smaller than the available
resource ID field, these can be extended by a locally generated checksum
over both the verification and object number fields.
note that checksums that include random numbers tend to look equally random,