7 ms·

The big problem is that you'd need to be able to change permissions over time. With ACLs that is simple and direct: if you have the access right, you just chang

The big problem is that you'd need to be able to change permissions over time. With ACLs that is simple and direct: if you have the access right, you just change the ACL. Traditional capabilities last forever, unless there is some sort of support for revoking already issued capabilities, and those mechanisms tend are far from straightforward. Some systems have revocation as a core feature, but a cascading revocation (every delegation as a branch in a tree, and revoke a whole subtree of delegated capabilities) is often complex and takes time, especially if they are on disk. There have also been protocols (for EROS-like OS:es) for setting up systems with additional capabilities to revoke individual capabilities but they are even more complex IMHO. So, in most capability systems the only way to revoke capabilities to a resource is to remove the resource itself. In CHERI, where every pointer is a capability, revocation of capabilities into a memory object relies on what is effectively a parallel garbage collector process that finds all pointers to revoked objects and overwrites them with an invalid pointer that traps on use. [0] In the fantasy OS of my mind, ACLs have instead been promoted to "access-control trees" that include a "grant option", allowing a user to grant the permission she has to someone else. But once the first user's permissions are revoked, the sub-tree of re-granted permissions get revoked as well. I think that could be achieved with existing file systems ACLs, with added topology info and enforcement by the OS. Then actual capabilities would be created first when a file is opened, as file handles, but unlike Unix file handles they could be revoked, be revoked in a cascading manner, and revoked automatically if the underlying ACT gets changed. Authorization Certificates (as in X.509) are a type of distributed cryptographic capabilities, but require complex distribution of "revocation lists". In recent years, there new types of distributed "authorization tokens" have been introduced such as e.g. "Biscuits" [1]. [0] https://www.semanticscholar.org/paper/Cornucopia-Reloaded%3A-Load-Barriers-for-CHERI-Heap-Filardo-Gutstein/80a3799d6b56fa25ea495129ee8b212ca6933500 https://www.semanticscholar.org/paper/Cornucopia-Reloaded%3A... [1] https://www.biscuitsec.org https://www.biscuitsec.org

LoganDark 10mo ago
> Traditional capabilities last forever, unless there is some sort of support for revoking already issued capabilities, and those mechanisms tend are far from straightforward. Capabilities don't have to hold the actual permission to access the object. Capabilities can simply hold a provenance that can be used to verify the source of the access. If that access is then revoked from that source, the capability doesn't need to change at all. This is similar to how generational arenas work in some game engines, IMO. AFAIK Android performs something similar to this with the storage URLs that are provided to apps, which will be different depending on which picker provided the file/media, etc. Apple probably also does something similar, but I'd imagine with objects rather than strings.
- bheadmaster 10mo ago
  > Capabilities don't have to hold the actual permission to access the object. Capabilities can simply hold a provenance that can be used to verify the source of the access. If that access is then revoked from that source, the capability doesn't need to change at all. Which complicates the initial premise that > capabilities are the simplest model in the world. You hand out objects. You can call methods on the object. What that method call has access to depends on the permissions on the object, not your permissions. Which is exactly what the parent said. Capabilities sound simple at first, but require complex machinery to work.
- naasking 10mo ago
  > Capabilities can simply hold a provenance that can be used to verify the source of the access. If that access is then revoked from that source, the capability doesn't need to change at all This is basically using access control lists to mimic a capability system [1]. The capability folks did something similar in "Polaris", their layer atop Windows XP that enforced principle of least authority by default. If only MS had taken that and run with it. [1] A Distributed Capability Computing System (DCCS), http://www.webstart.com/jed/papers/DCCS/ http://www.webstart.com/jed/papers/DCCS/ [2] Polaris: Virus-Safe Computing For Windows XP, https://cacm.acm.org/research/polaris-2/ https://cacm.acm.org/research/polaris-2/
  - btilly 10mo ago
    How equivalent this is to ACLs depends on what "provenance" means here. One of the strategies with capabilities is that I do not hand you the capability that I own to X. Instead, I create a proxy Y that can make requests of X, and then hand you the capability to make requests of Y. If I later stop Y, you lose access. This can be viewed as a kind of provenance. The history of how the access came to be is reflected in the actual capability. The downside, obviously, is that we've added overhead. But this strategy can allow us to do a number of interesting things. Like split an existing capability into multiple finer grained ones.
    - naasking 10mo ago
naasking 10mo ago
> Traditional capabilities last forever, unless there is some sort of support for revoking already issued capabilities, and those mechanisms tend are far from straightforward. Revocation is very straightforward in EROS/CapROS and previous systems: it's just incrementing a version number on the capability target. Since the new version number doesn't match any existing capabilities, all of those capabilities are effectively revoked. Revocation is really a non-issue, it's been solved since the 1970s.
- Findecanor 10mo ago
  You're missing the problem. With OS/object capabilities, you'd want to revoke only some (and those derived from them), and keep the rest in place. Otherwise they would not be a viable alternative to ACLs. For pointers-as-capabilities, and version counter as protection against use-after-free, you can't assign it or the object ID too many bits because you don't want to make the size of pointers unwieldy. I've read articles of such systems that use random numbers or encrypted counters to get more randomness but at the end of the day, the safety is still only probabilistic.
  - naasking 10mo ago
    > Otherwise it would not be a viable alternative to ACLs. I just want to point out that this is vastly overblown IMO. Typical ACL systems are just organized differently than capability systems that follow POLA. In the former, permissions to a number of objects are widely shared across many different subjects, and so fine-grained grant and revocation for subjects seem natural. It thus also seems natural to think that you will need fine-grained revocation in a capability system, but that's typically not true, because there is virtually no system-wide sharing of any objects in comparable fashion to ACL systems. In POLA and capability systems, any given object is almost always only reachable by one or two other objects, and of course this must be the case because otherwise it wouldn't be POLA! The need for fine-grained revocation is thus practically nil, and for those rare occasions that you do want some kind of fine-grained revocation, proxy and membrane patterns enable this. > It is also not "solved" problem for capabilities-as-pointers. I'm not clear on what you think isn't solved exactly. KeyKOS solved this issue in the 1970s. > I've read articles of systems using random numbers or an encrypted counter to get more randomness but at the end of the day, the safety is still only probabilistic. To be clear, cryptographic capabilities are not the same as object capabilities.
vacuity 10mo ago
I like to be flexible with policies, so while I think "capabilities" should be the core model, using ACL mechanisms under the hood is valid. If the capability mechanism is very minimal, people can build mechanisms and policies on top that are specialized for different use cases. It's not about "capabilities vs. ACLs"; it's "use the right tool for the job". So while resource revocation in general is a hard problem, anyone can come up and implement their clever scheme in my imagined world.

LoganDark 10mo ago

> Traditional capabilities last forever, unless there is some sort of support for revoking already issued capabilities, and those mechanisms tend are far from straightforward. Capabilities don't have to hold the actual permission to access the object. Capabilities can simply hold a provenance that can be used to verify the source of the access. If that access is then revoked from that source, the capability doesn't need to change at all. This is similar to how generational arenas work in some game engines, IMO. AFAIK Android performs something similar to this with the storage URLs that are provided to apps, which will be different depending on which picker provided the file/media, etc. Apple probably also does something similar, but I'd imagine with objects rather than strings.

bheadmaster 10mo ago
> Capabilities don't have to hold the actual permission to access the object. Capabilities can simply hold a provenance that can be used to verify the source of the access. If that access is then revoked from that source, the capability doesn't need to change at all. Which complicates the initial premise that > capabilities are the simplest model in the world. You hand out objects. You can call methods on the object. What that method call has access to depends on the permissions on the object, not your permissions. Which is exactly what the parent said. Capabilities sound simple at first, but require complex machinery to work.
naasking 10mo ago
> Capabilities can simply hold a provenance that can be used to verify the source of the access. If that access is then revoked from that source, the capability doesn't need to change at all This is basically using access control lists to mimic a capability system [1]. The capability folks did something similar in "Polaris", their layer atop Windows XP that enforced principle of least authority by default. If only MS had taken that and run with it. [1] A Distributed Capability Computing System (DCCS), http://www.webstart.com/jed/papers/DCCS/ http://www.webstart.com/jed/papers/DCCS/ [2] Polaris: Virus-Safe Computing For Windows XP, https://cacm.acm.org/research/polaris-2/ https://cacm.acm.org/research/polaris-2/
- btilly 10mo ago
  How equivalent this is to ACLs depends on what "provenance" means here. One of the strategies with capabilities is that I do not hand you the capability that I own to X. Instead, I create a proxy Y that can make requests of X, and then hand you the capability to make requests of Y. If I later stop Y, you lose access. This can be viewed as a kind of provenance. The history of how the access came to be is reflected in the actual capability. The downside, obviously, is that we've added overhead. But this strategy can allow us to do a number of interesting things. Like split an existing capability into multiple finer grained ones.
  - naasking 10mo ago

naasking 10mo ago

> Traditional capabilities last forever, unless there is some sort of support for revoking already issued capabilities, and those mechanisms tend are far from straightforward. Revocation is very straightforward in EROS/CapROS and previous systems: it's just incrementing a version number on the capability target. Since the new version number doesn't match any existing capabilities, all of those capabilities are effectively revoked. Revocation is really a non-issue, it's been solved since the 1970s.

Findecanor 10mo ago
You're missing the problem. With OS/object capabilities, you'd want to revoke only some (and those derived from them), and keep the rest in place. Otherwise they would not be a viable alternative to ACLs. For pointers-as-capabilities, and version counter as protection against use-after-free, you can't assign it or the object ID too many bits because you don't want to make the size of pointers unwieldy. I've read articles of such systems that use random numbers or encrypted counters to get more randomness but at the end of the day, the safety is still only probabilistic.
- naasking 10mo ago
  > Otherwise it would not be a viable alternative to ACLs. I just want to point out that this is vastly overblown IMO. Typical ACL systems are just organized differently than capability systems that follow POLA. In the former, permissions to a number of objects are widely shared across many different subjects, and so fine-grained grant and revocation for subjects seem natural. It thus also seems natural to think that you will need fine-grained revocation in a capability system, but that's typically not true, because there is virtually no system-wide sharing of any objects in comparable fashion to ACL systems. In POLA and capability systems, any given object is almost always only reachable by one or two other objects, and of course this must be the case because otherwise it wouldn't be POLA! The need for fine-grained revocation is thus practically nil, and for those rare occasions that you do want some kind of fine-grained revocation, proxy and membrane patterns enable this. > It is also not "solved" problem for capabilities-as-pointers. I'm not clear on what you think isn't solved exactly. KeyKOS solved this issue in the 1970s. > I've read articles of systems using random numbers or an encrypted counter to get more randomness but at the end of the day, the safety is still only probabilistic. To be clear, cryptographic capabilities are not the same as object capabilities.

vacuity 10mo ago

I like to be flexible with policies, so while I think "capabilities" should be the core model, using ACL mechanisms under the hood is valid. If the capability mechanism is very minimal, people can build mechanisms and policies on top that are specialized for different use cases. It's not about "capabilities vs. ACLs"; it's "use the right tool for the job". So while resource revocation in general is a hard problem, anyone can come up and implement their clever scheme in my imagined world.