5 ms·

As it was explained to me, the main problem with capabilities is working out how to revoke them. You either have expiring capabilities, which is a hassle but p

As it was explained to me, the main problem with capabilities is working out how to revoke them. You either have expiring capabilities, which is a hassle but probably inevitable. Or you have revoked capability lists, imposing an additional cost on every single invocation. The latter was a bit of a killer once people had figured out clever, fast bit-operation ways to check a capability, because the cost of looking up the list swamped the gains from bit-twiddling optimisations. Mind you, we sorta wound up with it anyhow, in the form of OAuth tokens. And here the algo-economics changes again to favour it: the cost of a network roundtrip is gigantic compared to any comparison operation, so it doesn't seem quite so bad after all.

willvarfar 11y ago
It's hard to generalise like that. There are lots of flavors of cap system. On many hardware capability-based addressing systems it is easy to zap them by clearing the corresponding bit in the capability mask. However, the problem then becomes how to revoke a cap from some holders and not others etc (which can be done with chains and ... turns into an interesting permission-like system ;) ...) Permission-list systems have exactly the same problem too. IIRC munmap ends up walking linked lists on Linux rather like ancient heaps. It might have changed.
evancordell 11y ago
There's a paper called "Capability Myths Demolished" that addresses this. There's an online version here[0], see "revoking access". Personally I'm fascinated by ocap systems and am always looking for ways to employ them. There are some interesting "modern" applications (aside from a couple of research kernels) like CapnProto and Pony language. Macaroons come close but are more of a hybrid approach to authorization. (They don't out of the box prevent confused deputy or anything) [0]: http://www.erights.org/elib/capability/duals/myths.html http://www.erights.org/elib/capability/duals/myths.html
- bascule 11y ago
  Yes, Capability Myths Demolished describes the "revocable forwarder" pattern, which uses a proxy to delegate access in a revokable manner. Macaroons on the other hand are nice because they don't need a proxy to solve this problem: the authorizer can issue a short-lived "discharge Macaroon" to authorize access, then the client can get to the target resource directly without the need to use a proxy. To revoke access: just refuse to issue subsequent discharge Macaroons when the current discharge expires.
  - kentonv 11y ago
    A common optimization in a capability system is to allow a remote client to create a new revokable membrane living on the same machine as the target object, thus avoiding introducing a new network hop due to the proxy. Said client receives a separate capability to revoke the new wrapper, which it can exercise later. Or, the client might supply the object host with some other instructions on when revocation should occur. Macaroons can probably be seen as an implementation of this.
abecedarius 11y ago
To revoke them, the usual pattern is to never hand out the original capability, you hand out a wrapper that you can disable. E.g. in Javascript: let [revoke, revocable] = makeRevocable(cap); share(revocable); // share can call revocable(), which forwards to cap() unless revoked setTimeout(1000, revoke); // for auto-expiring, just for example See section 4.3 in http://www.erights.org/talks/asian03/index.html http://www.erights.org/talks/asian03/index.html A capability system can help you batch up those round trips you mention, btw: https://capnproto.org/rpc.html https://capnproto.org/rpc.html
- ChuckMcM 11y ago
  This is exactly right. Back before Java 1.0 was released I was working on a capability based security model for it. The class loader would hand out what was essentially a virtual method of the instantiated class based on the capability's allowed. Revoking capability consisted of updating the template which would fail to resolve the revoked methods on the next call but leave the ones which were still on the stack.
  - EGreg 11y ago
    So there is still the indirection of the function call, but it's probably the right approach.

willvarfar 11y ago

It's hard to generalise like that. There are lots of flavors of cap system. On many hardware capability-based addressing systems it is easy to zap them by clearing the corresponding bit in the capability mask. However, the problem then becomes how to revoke a cap from some holders and not others etc (which can be done with chains and ... turns into an interesting permission-like system ;) ...) Permission-list systems have exactly the same problem too. IIRC munmap ends up walking linked lists on Linux rather like ancient heaps. It might have changed.

evancordell 11y ago

There's a paper called "Capability Myths Demolished" that addresses this. There's an online version here[0], see "revoking access". Personally I'm fascinated by ocap systems and am always looking for ways to employ them. There are some interesting "modern" applications (aside from a couple of research kernels) like CapnProto and Pony language. Macaroons come close but are more of a hybrid approach to authorization. (They don't out of the box prevent confused deputy or anything) [0]: http://www.erights.org/elib/capability/duals/myths.html http://www.erights.org/elib/capability/duals/myths.html

bascule 11y ago
Yes, Capability Myths Demolished describes the "revocable forwarder" pattern, which uses a proxy to delegate access in a revokable manner. Macaroons on the other hand are nice because they don't need a proxy to solve this problem: the authorizer can issue a short-lived "discharge Macaroon" to authorize access, then the client can get to the target resource directly without the need to use a proxy. To revoke access: just refuse to issue subsequent discharge Macaroons when the current discharge expires.
- kentonv 11y ago
  A common optimization in a capability system is to allow a remote client to create a new revokable membrane living on the same machine as the target object, thus avoiding introducing a new network hop due to the proxy. Said client receives a separate capability to revoke the new wrapper, which it can exercise later. Or, the client might supply the object host with some other instructions on when revocation should occur. Macaroons can probably be seen as an implementation of this.

abecedarius 11y ago

To revoke them, the usual pattern is to never hand out the original capability, you hand out a wrapper that you can disable. E.g. in Javascript: let [revoke, revocable] = makeRevocable(cap); share(revocable); // share can call revocable(), which forwards to cap() unless revoked setTimeout(1000, revoke); // for auto-expiring, just for example See section 4.3 in http://www.erights.org/talks/asian03/index.html http://www.erights.org/talks/asian03/index.html A capability system can help you batch up those round trips you mention, btw: https://capnproto.org/rpc.html https://capnproto.org/rpc.html

ChuckMcM 11y ago
This is exactly right. Back before Java 1.0 was released I was working on a capability based security model for it. The class loader would hand out what was essentially a virtual method of the instantiated class based on the capability's allowed. Revoking capability consisted of updating the template which would fail to resolve the revoked methods on the next call but leave the ones which were still on the stack.
- EGreg 11y ago
  So there is still the indirection of the function call, but it's probably the right approach.