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

[Jonathan S. Shapiro]

Okay. Now that I finally think I understand #s13, let me respond on the
points of protection and confinement.

First, a concise description of the essential points of #s13.

For every domain K, there are two cryptographic keys, K+ (encrypt) and
K- (decrypt). K- is held on behalf of K by the kernel. An in-memory bit
string s is a valid capability in domain K exactly if the bit string
K-(s) is a well-formed raw capability. That is, if s = K+(c) where c is
a valid capability.

No mechanism for checking validity is identified by the capsule
description of #s13, but there are several straightforward options for
that.

#s13 assumes an encryption method in which K-(K+(s)) == K+(K-(s)) == s.

Qualitatively, the system is very similar to the Pose password
capability design. The primary difference is that the encryption key K+
is held private in the Pose design, while it is promiscuously known in
the #s13 design.

In #s13, a layering of encryption is used, but this appears to me to be
superfluous if we exclude the problem of memory dump analysis. The
source of this requirement is the need to ensure that a server S holding
the clear text of a capability c that designates S does not reveal the
clear-text of c when dumped. This is primarily a problem because the
various keys K+ are promiscuously available. In the absence of this
consideration, layered encrypt does not appear necessary.

I frankly suspect that this doesn't help matters. The window of
vulnerability during initial capability fabrication seems difficult to
beat in abstract but very narrow. It may be a sufficient defense for S
to immediately encrypt c using S+. Or at least, it is not immediately
obvious that any better solution is practical.

I concur that the system enforces both capability protection and
confinement, but this relies on the fact that intermediate computations
in the application of encryption/decryption are never revealed (a
requirement that David Hopwood has noted). In particular, if domain K
holding s = K+(c) is at any point able to apply K- to s, it is then able
to fabricate X+(c) for an arbitrary domain X. If X+(c) can be conveyed
to X in a fashion that bypassed the send operation (e.g. by shared
memory), then confinement is lost. Confinement also relies on the fact
that the key K+ is not known prior to fabrication of K. This is required
in order to prevent pre-caching of unauthenticatable capabilities.

I concur that this system works and confines. I see three pragmatic
deficiencies:

1. It would be better achieved by a symmetric key system with both
halves held by the kernel. The result would be significantly faster and
simpler, and could use cheaper cryptographic operations.
2. Sharing of segments containing capabilities appears to be impossible,
or at least requires mechanisms beyond those described.
3. It appears to be operationally expensive. While the supervisor is
argued to be smaller, the cryptographic operations are significantly
more expensive than the corresponding lookup operations in an
index-based partitioned capability scheme.

Concerning the claim of supervisor simplification, I am skeptical,
because of the high degree of reuse between the mapping support for data
and the mapping support for capabilities. If I recall earlier
conversations, the system at LLNL did not support virtual memory, so
this consideration may not have applied at the time.

Concerning the challenges of sharing, I am not sure how serious they are
in practice, and I would be very interested to hear how Jed anticipated
handling this.

shap
-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100