Split Capabilities: Making Capabilities Scale

[Karp, Alan]

> -----Original Message-----
> From: Bill Frantz [mailto:frantz@communities.com]
> Sent: Tuesday, July 18, 2000 6:21 PM
> To: Jonathan S. Shapiro; Karp, Alan; e-lang@eros-os.org
> Subject: Re: Split Capabilities: Making Capabilities Scale
> 
> 
> 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.

I'm trained in astrophysics.  To me, 324 bytes is of the order of 1 KB.
Besides, I believe that delegated certificates encode the chain of
delegation and are therefore larger.

> 
> 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.)
> 
> 

64-bit ints should solve the problem, even at CPU speeds.  Even so, I like
to have a rollover strategy in my hip pocket if I can.  Remember, Microsoft
put the display buffers at 640 KB because no one would ever need that much
memory.  Less facetiously, given that much room to maneuver, it's tempting
to encode information in the int, reducing the available number of states.

_________________________
Alan Karp
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278