A (possibly) new aproach to capabilities

Discussions on more advanced topics such as monolithic vs micro-kernels, transactional memory models, and paging vs segmentation should go here. Use this forum to expand and improve the wiki!
Post Reply
User avatar
Schol-R-LEA
Member
Member
Posts: 1925
Joined: Fri Oct 27, 2006 9:42 am
Location: Athens, GA, USA

A (possibly) new aproach to capabilities

Post by Schol-R-LEA »

I am planning on using capabilities in my OS. However, one of the problems with capabilities is that they need to be unforgeable, which can present problems across networks (on a single system, they are usually implemented through what are called c-list indices - handles which index into a list of capabilities stored in kernel space, thus separating the applications from the capabilities themselves).

My thought - and I doubt that no one has come up with this before - is to give each grantor (the kernel would act as grantor for system resources, but any process can act as a grantor to control access to its own resources), each capability, and each process a public/private key pair. The grantor would sign the capability's public key with it's own private key and encrypt it with the public key of process that will hold the capability.

When the capability is to be used, the holder would send the access request to the grantor signed with the holder's private key, encrypted with the capability's public key, and then signed again with the holder's private key. Note that the signature is not an access control, it only is used to reduce the risks of MitM attacks by confirming that the request wasn't tampered with - the signature inside the encrypted request has to match the one on the outside.

Each process would have its own set of capabilities in kernel space, and can set new ones or remove existing ones with a system call (I'm not sure yet how this would work with floated processes). To delegate a capability, the delegating holder would act as a grantor where the capability itself is treated as a protected resource.

The big problems with all this are speed and memory overhead. In a capability system like this, you would need a capability for anything that has access controls, such as files, IPC queues, requests for additional dynamic memory, and a lot more. Having to encrypt and decrypt every single read or write to a file (or dataset in my case) would be a lot of added overhead, especially if a capability has been repeatedly delegated. This last part can be ameliorated somewhat by allowing delegating holders to request that the original grantor issue a new capability to the delegate for long-term delegations, but the basic problem still remains.

However, this does have significant advantages, with the chief among them being that it might be possible (in some cases, maybe, with fingers crossed and some favorable divine intervention) to use such an approach to retro-fit capabilities into systems that lack them; the way this would work is that for any capability-protected data or action, the ownership of the protected element would be re-assigned to the primary grantor, and non-owner rights would be removed (in Unix terms, the protected items' permissions would be "<grantor> 700"). While this would still be vulnerable to attack (especially if the grantor isn't a kernel process) by reassigning the permissions, it would at least give some separation and allow for various checks to be done on a periodic (say, once every second, assuming suitable caching of permissions) basis by the grantor. It would not give anywhere near the protection of a true capability-based security system, but it would allow the system to transition into using capabilities over time, something usually thought to be impossible.
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re: A (possibly) new aproach to capabilities

Post by Brendan »

Hi,

Imagine if processA and processB are on the same computer; and processA tells the kernel; "Give the capability with my_handle=3 to processB", so the kernel creates a new handle for processB and tells processB "You were given the capability with your_handle=9". If a process uses a forged handle then the kernel isn't able to find the capability that corresponds to that handle, so there is no reason to encrypt the handles. The actual data for the capability never leaves the kernel so there's no reason to encrypt that either.

For distributed systems; the only requirement is that your kernel on one machine is able to trust information from your kernel on another machine. This requires both authentication (to ensure that the remote kernel is what it says it is) and encryption (so that after authentication kernels can communicate securely).

Imagine if processA and processB are on different computers; and processA tells kernelA; "Give the capability with my_handle=3 to processB". KernelA uses the handle to find the capability, then uses secure "kernel to kernel" communication to tell KernelB "ProcessB has been given the capability with these details". Then kernelB creates a new handle for processB and tells processB "You were given the capability with your_handle=9". If a process uses a forged handle then the kernel isn't able to find the capability that corresponds to that handle, so there is no reason to encrypt the handles. The actual data for the capability is only ever sent over secure "kernel to kernel" communication; so there's no reason for additional encryption of the capability's data.


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
User avatar
Schol-R-LEA
Member
Member
Posts: 1925
Joined: Fri Oct 27, 2006 9:42 am
Location: Athens, GA, USA

Re: A (possibly) new aproach to capabilities

Post by Schol-R-LEA »

OK, good point; however, I was trying to find a way to eliminate the c-lists and handles, and let the capabilities be represented as the code doing the access itself. It seems that I didn't state that part.

I came up with it indirectly, while considering ways to eliminate the system call in a quaject's callentries.

I am pretty sure Brendan is familiar with this, but I expect there are others reading this who aren't, so let me explain. A quaject can be seen loosely as an object which can have vtable slots (er, not exactly, but close enough for now) for callentries (methods), callbacks, and callouts (continuations, usually to call finalizers or similar things) which are specific to the instance, where the 'default' vtable entries can be replaced with entries pointing to specialized code generated by the system, either when constructed or over the course of their lifetime, and can even have the entries themselves replaced by code for very small snippets. The purpose is to allow general-purpose code to be replaced by code generated at run time for a specific operation, based on one or more templates which are created when the 'class' is defined.

Most quajects are not used for data, per se, but as placeholders for operations such as reading from or writing to disk, where the overhead of the generating the specialized code is less than that of using the general-purpose driver; the 'driver' would be a template which could be used to generate the callentries.

In Synthesis, access to callentries/callbacks/callouts is done using handles that are given to it by the kernel, in a way similar to c-lists (the original dissertation explicitly compares the quaject handles to c-lists, in fact). As I understand it,the synthesized code is stored in memory shared by the kernel and the specific process, which the process has execute permissions for but not read or write permissions (and with most applications also getting their own virtualized 's-machine' for further separation), but in order to access the right code, you need a system call, each and every time. While system calls in Synthesis are usually a good deal faster than in most other OSes (relatively speaking, as the two systems it ran on are rather dated today, being based on the 68000 CPU), it still seemed like a good idea to find a way to eliminate even that overhead. I thought of public-key encryption as a way to do this, but concluded that the overhead would probably be higher than that of the system call would be.

(In any case, a lot of the things which a callentry might need to do would require the CPU to be in system mode anyway. That didn't occur to me until just now, for some reason. I think I need to re-read those papers again.)

That's when I thought about capabilities. They are implemented in similar ways, as already stated, and are invoked much less often than callentries would be. It seemed to me that this approach would be acceptable as a way of implementing capabilities in terms of quajects - each callentry/back/out would in effect also be a capability.

Still, I can't see any way to do this that isn't either slower than c-lists, or less secure, or both. I still want to play around with the idea, both regarding this and for something a little different (I think it might have applications regarding DRM, specifically as 'gatekeeper' which could be done as an a pair of add-ons for HTTP servers and browsers, but I need to think more about it), but at this point I don't know if it will go anywhere.
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.
User avatar
dchapiesky
Member
Member
Posts: 204
Joined: Sun Dec 25, 2016 1:54 am
Libera.chat IRC: dchapiesky

Re: A (possibly) new aproach to capabilities

Post by dchapiesky »

I would recommend a long read of the iAPX-432 architecture documents...

That along with IBM System/38 capability addressing....

both used a single global address for objects whether local or distributed....

That said, by looking at it from a hardware perspective you find that you have a *single* entry point to all capabilities for all objects....

and this single entry point performs a lookup of the object/capability address, which may be local or remote...

There is similar system like this... a web server....

1) single point of entry: http ://www.mycapabilitiesblahblah.com
2) RESTful interface: POST http :www.mycapabilitiesblahblah.com/1000/ to add capability "something"
3) RESTful interface: GET http :www.mycapabilitiesblahblah.com/1000/something returns 200 ok
4) RESTful interface: GET http :www.mycapabilitiesblahblah.com/1000/notthere returns 404 not found

This model allows caching... just like web caching... it allows time-of-life just like web caching... it allows for a single point of synchronization.... it allows for top down flushing of all caches of expired capabilties... and it allows for reporting of *attempts* to access unknown or disallowed capabilities....

I am not saying use web addressing in your code... I am saying looking at it from a RESTful perspective makes it easier to create distributed capability based systems.....

cheers
Last edited by dchapiesky on Sun Feb 26, 2017 8:16 pm, edited 2 times in total.
Plagiarize. Plagiarize. Let not one line escape thine eyes...
User avatar
Schol-R-LEA
Member
Member
Posts: 1925
Joined: Fri Oct 27, 2006 9:42 am
Location: Athens, GA, USA

Re: A (possibly) new aproach to capabilities

Post by Schol-R-LEA »

Thank you. I have read about capabilities (and quajects) before, but I suspect I am still wearing a lemon-juice mask about them at this point. I will study up some more.

(Oh, and I assume that the URI you used was just an example; in case you didn't know, that is in fact a live domain, but it has nothing to do with computing and the '1000' fortunately does not give a page there. For an example, that's perfectly fine, but I might not be the only one who wondered at first if there was some actual significance to it.)
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.
User avatar
dchapiesky
Member
Member
Posts: 204
Joined: Sun Dec 25, 2016 1:54 am
Libera.chat IRC: dchapiesky

Re: A (possibly) new aproach to capabilities

Post by dchapiesky »

they can drive you crazy I know...

My post was primarily in regards to your possible requirements of a distributed system.

The idea of a central server of capabilities lends its self to fault tolerance, triple redundant voting, and caching of long lived static capabilities.... all which are well understood and numerous examples being available.

Synchronization of capabilities between multiple servers for fault tolerance can easily be achieved with something like the Raft protocol.... see logcabin

Forcing objects to communicate via message queues hosted on the central server (or perhaps via lockless rings) again lends its self to fault tolerance and side-by-side testing as well as hiding the network transport from object implementation

Finally... as for speed.... using a RESTful interface to the server for capabilities lets you use random numbers for the capabilities assigned to a specific object.... this is important because it means that if the server has to respond 404 not found for any object's capability then the object is being attacked... only the assigner of the capability and the subject object would know the random number's value... add a little symmetric encryption and a few chained hashes and you have a fairly secure and adaptable system...

just sayin... :wink:

(pulled the name of the uri out of the air... gonna change it...)

cheers
Plagiarize. Plagiarize. Let not one line escape thine eyes...
User avatar
Schol-R-LEA
Member
Member
Posts: 1925
Joined: Fri Oct 27, 2006 9:42 am
Location: Athens, GA, USA

Re: A (possibly) new aproach to capabilities

Post by Schol-R-LEA »

Well... For a website model, yes. Obviously, HTTP is already a (primarily) client-server system, so a central capabilities server would be a natural fit.

...But the same isn't true for my distributed OS plans. The design I have in mind really only works if it is peer-to-peer; a client-server approach just isn't on my radar for that. If I were to compare it to anything already in use, then for the document system at least, the closest would be bittorrent.
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.
User avatar
dozniak
Member
Member
Posts: 723
Joined: Thu Jul 12, 2012 7:29 am
Location: Tallinn, Estonia

Re: A (possibly) new aproach to capabilities

Post by dozniak »

Schol-R-LEA wrote:Well... For a website model, yes. Obviously, HTTP is already a (primarily) client-server system, so a central capabilities server would be a natural fit.

...But the same isn't true for my distributed OS plans. The design I have in mind really only works if it is peer-to-peer; a client-server approach just isn't on my radar for that. If I were to compare it to anything already in use, then for the document system at least, the closest would be bittorrent.
Capability is a token granting access to some operations on some object. In a distributed system, issuing a capability should be working somewhat like DHT hash lookups - "searching" for it should yield a server to run it on, and then, when presented a capability the issuing server may validate the token itself. This way the only source of truth for a capability is the issuing server, the one where the object target of capability invocation lies.
Learn to read.
User avatar
Schol-R-LEA
Member
Member
Posts: 1925
Joined: Fri Oct 27, 2006 9:42 am
Location: Athens, GA, USA

Re: A (possibly) new aproach to capabilities

Post by Schol-R-LEA »

Permit me to post something I had started to write before you replied; I was editing the previous post but had to go AFK before I finished. This is a pretty general and naive outline of the idea I have for the management of data transfers (not searching to find that it exists; this assumes that the data is already known to be out there, but it has not been transferred yet). I have not really put most of this to (virtual) paper before, so just doing this is both giving it more substance, and airing the idea for review by others. It is not directly related to how capabilities will be handled, but it may or may not have some similar qualities - I just haven't thought that out yet, nor have I worked out all the faults and quirks of the data transfers beyond this very brief overview.

The idea is that when a peer wants to access a given item that isn't already in that peer's local storage, it would trace a route to the item's source (or a known permanent mirror of it). Then send a store-and-forward request to the first peer (as opposed to a router with no cache of it's own) in each of the first 5 shortest routes it finds. That peer would check its own storage and cache for a copy of that item, and if it has one, it passes it along, short-circuiting the request and sending a stop request to the other routes. If it doesn't have a copy, it passes the request along. When a copy is found, it is passed back along the same route (if possible), with each peer on the route caching a copy (but not necessarily in the top-generation cache) for future possible use. The requesting peer caches the item, generational by MRU (primarily), unless the user authorizes it (or rather, the view it used in) to be mirrored.

The idea here is to distribute both the data storage (through caching and mirroring) and the data transfer (ditto), both to improve fault tolerance and to speed up access by shortening transfer routes. Note that a requested unit may be a part of a larger unit, or a view spanning several separately stored units, or some combination of those (i.e., a document might be a view consisting of several paragraphs of new text, a set of images - or even sections of images - from various sources, and a table which uses data from two different sets of statistics, with only the particular statistics needed from sets being included). Note also that none of this alters the originating data itself, nor does it create a new document with any sort of 'object linking and embedding' or change of format; it just displays it in different ways.

And yes, this is taken straight from the Xanadu model; what a lot of people never understood about Xanadu was that this separation of storage and presentation, which presents so much trouble in HTML, is at the heart of the Xanadu design. There is no 'browser' in a Xanalogical storage system, because presentation is the job of the applications - the back end, which handles the data, has no inherent presentation. In many ways it is closer in structure and purpose to a database engine than an HTTP server (Nelson even trying to made a 'Xanadu Lite' on top of MySQL once, and it probably would have worked if he hadn't been, I dunno, but knowing him he was probably distracted by something shiny - severe ADHD can't much fun). What matters isn't the way the data went in, it is how you can rearrange it and make connections between arbitrary pieces.
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.
User avatar
dozniak
Member
Member
Posts: 723
Joined: Thu Jul 12, 2012 7:29 am
Location: Tallinn, Estonia

Re: A (possibly) new aproach to capabilities

Post by dozniak »

Not sure why you need capabilities in this model - this is more or less solved by a DHT.
Learn to read.
User avatar
Roman
Member
Member
Posts: 568
Joined: Thu Mar 27, 2014 3:57 am
Location: Moscow, Russia
Contact:

Re: A (possibly) new aproach to capabilities

Post by Roman »

I was once thinking about implementing capabilities as simple arrays of bytes signed with HMAC, but couldn't find any reasonable benefits.
"If you don't fail at least 90 percent of the time, you're not aiming high enough."
- Alan Kay
User avatar
Schol-R-LEA
Member
Member
Posts: 1925
Joined: Fri Oct 27, 2006 9:42 am
Location: Athens, GA, USA

Re: A (possibly) new aproach to capabilities

Post by Schol-R-LEA »

As I said at the start of that post, this was not directly related to the capabilities idea, but something that paralleled some aspects of it.

However, capabilities would indeed be used to manage publication status and the like; it should be possible to circulate a document privately without it even being visible to others, with the visibility managed by issuing capabilities to particular applications or user accounts (though capabilities usually are tied to processes rather than users, so it would not be a 'classic' capability system as it could issue 'user capabilities' that the user account can delegate to processes launched by said user).

But as I said before, I am currently talking quite a bit beyond my competence, so I need to learn more before making solid plans.
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.
User avatar
dozniak
Member
Member
Posts: 723
Joined: Thu Jul 12, 2012 7:29 am
Location: Tallinn, Estonia

Re: A (possibly) new aproach to capabilities

Post by dozniak »

I'm also interested in capabilities systems, i saw several different implementations of those, but so far it's still rather confusing, so more links are appreciated.

So far I went through EROS/KeyKOS, Mungi, www.cap-lore.com, www.capros.org, now reading up on iAPX 432 and System/38 http://homes.cs.washington.edu/~levy/ca ... apter8.pdf
Learn to read.
Post Reply