Split Capabilities: Making Capabilities Scale

[Bill Frantz]

Alan Karp wrote:
> If capabilities are cryptographically secure, they're bigger than 
> encrypted inodes.  For example, SPKI capabilities are of the order 
> of 1 KB at a minimum.

An SPKI capability is a 5-tuple (and I know I am going to screw up the
names of the fields): Owner, User, Delegate, Permission, and Signature.

Using 1024 bit DSS/SHA1 as an example:

The Owner and User are public keys at 128 bytes each, or hashes of keys at
20 bytes each.  The Delegate is a single bit at 1 byte.  The Permission is
variable and application specific, and the Signature is 40 bytes.  A
reasonable SPKI style capability could be represented in 128 bytes by this
analysis using key hashes.  It could be represented in 324 bytes using the
keys themselves.

Elliptic curve cryptography provides a similar level of security with 200
bit public keys.  It should allow SPKI-like capabilities of a size between
256 and 512 bytes.  (It also offers somewhat faster (a factor of 2 more or
less) signature checking.)

RSA signatures are attractive in any system where the signatures are
checked more often than they are generated, but I'm not thinking about RSA
until September 20.  :-)


At 09:29 PM 7/8/00 -0400, Jonathan S. Shapiro wrote:
>There is a level at which names must be reused, which is the level at which
>the system names physical resources. In EROS/KeyKOS, name reuse is prevented
>by ensuring that every system object (page or node) carries a version
>number, and that every capability also carries a version number. We call
>this number an allocation count. If the count in the capability and the
>count in the object do not match, the capability is void. Modulo the possibi
>lity of GC to address rollover, this satisfies your "never reuse names"
>suggestion. In fact, we've yet to see a rollover happen.

In KeyKOS we limited the maximum update rate for the version number to the
rate of disk I/O.  We used a 32 bit counter.  Because relevant disk writes
only occurred at the checkpoint rate (about once every 5 minutes), that is
some 40,000+ years.  (I think there was one kernel capability which would
allow the rate to be at CPU speeds rather than checkpoint speeds.  But as I
remember, that capability was not widely distributed.)