7 ms·

Capability Myths Demolished (2003)

80 points by gullyfur 7y ago

zemnmez 7y ago
Anyone know when this was released? > largely dismissed by computer security reseachers and practitioners due to a history of misunderstandings seems incorrect now as virtually all web auth systems are capability based
- david_draco 7y ago
  HTML code says: Saturday, October 03, 1998
  - ChrisSD 7y ago
    Presumably that's for the HTML template. The article has a citation from November 2002.
- justincormack 7y ago
  Which ones are?
  - warkdarrior 7y ago
    Anything that uses OAuth2 is capability based.
- ChrisSD 7y ago
  ~2003, assuming its related to the paper[0] of the same name (and sharing an author/diagrams). The paper was very influential and helped change minds on the subject. [0]: http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf
  - erights 7y ago
    Yes, that's the paper, from 2003. Please everyone read this paper http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf rather than the web page. And thanks! There's a story behind why this paper became so influential. The paper was submitted to Usenix security and famously rejected https://web.archive.org/web/20160730083134/http://www.eros-os.org/pipermail/cap-talk/2003-March/001133.html https://web.archive.org/web/20160730083134/http://www.eros-o... Although we don't know who the specific reviewers were, they were from the Usenix Security program committee, and so from the elite of the field. This rejection captures perfectly the tone of dismissal common in academia at the time. The common wisdom was that capabilities were a failed and unworkable idea that we need not bother further discussing. As you can see from the date on that email, when we got this rejection, we immediately posted it publicly. My sense is that the paper together with this referee rejection, posted and discussed publicly, caused the initial influence. The embarrassment from that rejection was not on the authors. Within two years, many still thought capabilities were wrong. But the sneer was gone. Arguments could be heard. I dare say it marks the beginning of the capability revival in academia.
    - erights 7y ago
      Much of my work on capabilities, from 1988 till now, can be found at https://research.google/people/author35958/ https://research.google/people/author35958/ and at Agoric https://agoric.com/papers/ https://agoric.com/papers/ Agoric is bringing distributed object-capabilities to the modern world of decentralized crypto-commerce, including blockchains. Starting from object-capabilities, we're building a framework for highly composable smart contracts. Hack it at hackathon https://medium.com/agoric/spend-the-pandemic-inside-join-our-gitcoin-cross-chain-hackathon-and-win-prizes-d58e0437a874 https://medium.com/agoric/spend-the-pandemic-inside-join-our...
      - magicalhippo 7y ago
        > https://agoric.com/papers/ https://agoric.com/papers/ For someone who hadn't really read about this before, I found this[1] article, linked above, to be a really nice introduction. [1]: http://habitatchronicles.com/2017/05/what-are-capabilities/ http://habitatchronicles.com/2017/05/what-are-capabilities/
- lidHanteyk 7y ago
  Kind of. There's still a lot of work to do. OAuth and SAML are quite common, but they cannot federate capabilities; it is not trivial to issue somebody a capability to act on your behalf without an entire infrastructure of assistant services and trusted providers. That said, each decade looks better than the last, but I still encounter the myths covered in the paper, especially incorrect beliefs about revokation, on a regular basis.
- say_it_as_it_is 7y ago
  The opposite is true. Virtually no web auth systems are capability based. Maybe security SaaS providers are using it, but relatively spreading, they're not representative of the web proper.
carapace 7y ago
There's something called "Macaroons" that can be used for this. "Macaroons: Cookies with Contextual Caveats for Decentralized Authorization in the Cloud" Arnar Birgisson, Joe Gibbs Politz, Úlfar Erlingsson, Ankur Taly, Michael Vrable, Mark Lentczner ; Network and Distributed System Security Symposium, Internet Society (2014) https://research.google/pubs/pub41892/ https://research.google/pubs/pub41892/ "Google's Macaroons in Five Minutes or Less" https://blog.bren2010.io/2014/12/04/macaroons.html https://blog.bren2010.io/2014/12/04/macaroons.html A Javascript implementation: https://github.com/nitram509/macaroons.js https://github.com/nitram509/macaroons.js
ggm 7y ago
The main myth we discussed over coffee and biscuits back in the compsci staffroom was .. expensive as all hell on the computers we have now. (a good handwaving often used to say "one day, in the future, somebody will make it work")
- brandmeyer 7y ago
  Looking at it strictly from the outside, it looks like there's a ton of indirection to make it work. People usually do want revocable capabilities, which implies that every capability grant has one or more levels of indirection that go with it. Indirection's costs haven't gotten cheaper in well over a decade.
  - bhk 7y ago
    An ACL implies a level of indirection, and typically a look-up as well.
  - squiggleblaz 7y ago
    Considering now every time you want to do anything on a computer you're getting interpreted code in a memory heavy gui environment to send a HTTP request over a TLS connection to a remote computer via a flaky wifi connection, the cost of doing an indirection might be relatively much less than it was a decade ago. In those days, you might recall, most of the time you clicked in your software it would be doing direct lookups in the machine's comparatively fast spinning disk using native compiled code in a gui api designed with a considered tradeoff between developer's convenience and memory usage - designed in the days when there were fewer developers and much less memory. Of course, half the time those indirections will probably be remote to the server you're already waiting on...
magicalhippo 7y ago
So I haven't been exposed to capability systems before so this might be a dumb question. In an OS like KeyKOS, how does the OS protect against privilege escalation using side-channel attacks similar to how encryption keys are extracted via hardware side-channels?
- throwaway_pdp09 7y ago
  I'm not the person to answer but let me try. Anyone correct me please. Side channel attacks are AIUI about information leakage. They extract info on the state, not modify state[0]. I don't think privilege escalation is really related because that needs to modify state you should not have access to[1]. Capabilities at the OS and software level are software enforced, which is built on assumptions about the security (correctness guarantees) of the hardware. If the hardware leaks, the software is vulnerable unless/until patched to try to paper over the leaky cracks in the hardware. Again, AIUI. [0] Though such extracted data might be a security token that can subsequently be used to actively attack, such as logging in via someone's newly pwned admin password. [1] I suppose rowhammer is exactly that, though, an attack that intentionally leads to a handy state change for the attacker.
  - magicalhippo 7y ago
    > I don't think privilege escalation is really related because that needs to modify state you should not have access to. But in a capability-based OS, privilege is all about the keys you hold, no? So assuming a malicious process can copy keys from other processes, can the OS detect and prevent the malicious process from using the key? I tried reading up on KeyKOS[1] and there was very little info on what exactly a key is and how it is verified by the OS, at least that I could see. [1]: http://cap-lore.com/CapTheory/KK/Arch/ http://cap-lore.com/CapTheory/KK/Arch/
    - throwaway_pdp09 7y ago
      You are right - see my note [0] but I missed the bleedin obvious. Thanks for pointing it out. In that case the hardware is effectively broken and all that's left is attempted software mitigation. Which may/may not work, but surely will cost performance. And extra complexity. And consequential possible bugs. From memory a key can be represented as a random 64-bit integer taken from a sparse set. IOW you'd have bugger all chance of guessing another currently used 64-bit int, and if you tried and guessed wrong the OS, which would keep a list of caps allocated to each process) would say when you tried to use it "and where exactly did this come from, eh?" and kill you. But that's from memory and guesswork. HTH and don't trust what I say too much!
amelius 7y ago
Shouldn't permissions ultimately be Turing-complete functions? E.g. you could do fancy things like grant someone access to a folder, and also to all subdirectories whose name starts with "collaboration_". And you can build any kind of permission system with it, if you don't like the power or complexity.
- fnord123 7y ago
  Absolutely not. Turing-complete functions are subject to Rice's Theorem - meaning that they are undecidable in the general case. Also, if it's Turing-complete then anyone can make a ridiculous mess of an area with little or no tooling. Configuration should be Turing-incomplete unless you have a very good reason to do otherwise. Being Turing-incomplete is a valuable feature.
  - amelius 7y ago
    You haven't given an argument for why "undecidability" would be a problem in this case. Please give a compelling example. We're not banning regular applications either because they are undecidable. Also, we could change Turing completeness into something less powerful, for instance programs without loops.
    - fnord123 7y ago
      Undecidability means loading your configuration could never complete or could consume an indeterminate amount of resources. Which means it's a security concern as a bad config can DOS your system. This type of attack exists even without Turing-complete config but just with references: https://en.wikipedia.org/wiki/Billion_laughs_attack https://en.wikipedia.org/wiki/Billion_laughs_attack > Also, we could change Turing completeness into something less powerful, for instance programs without loops. Yes, this is a strategy. For example BPF does not support loops.

80 points by gullyfur 7y ago

Anyone know when this was released? > largely dismissed by computer security reseachers and practitioners due to a history of misunderstandings seems incorrect now as virtually all web auth systems are capability based

david_draco 7y ago
HTML code says: Saturday, October 03, 1998
- ChrisSD 7y ago
  Presumably that's for the HTML template. The article has a citation from November 2002.
justincormack 7y ago
Which ones are?
- warkdarrior 7y ago
  Anything that uses OAuth2 is capability based.
ChrisSD 7y ago
~2003, assuming its related to the paper[0] of the same name (and sharing an author/diagrams). The paper was very influential and helped change minds on the subject. [0]: http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf
- erights 7y ago
  Yes, that's the paper, from 2003. Please everyone read this paper http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf http://srl.cs.jhu.edu/pubs/SRL2003-02.pdf rather than the web page. And thanks! There's a story behind why this paper became so influential. The paper was submitted to Usenix security and famously rejected https://web.archive.org/web/20160730083134/http://www.eros-os.org/pipermail/cap-talk/2003-March/001133.html https://web.archive.org/web/20160730083134/http://www.eros-o... Although we don't know who the specific reviewers were, they were from the Usenix Security program committee, and so from the elite of the field. This rejection captures perfectly the tone of dismissal common in academia at the time. The common wisdom was that capabilities were a failed and unworkable idea that we need not bother further discussing. As you can see from the date on that email, when we got this rejection, we immediately posted it publicly. My sense is that the paper together with this referee rejection, posted and discussed publicly, caused the initial influence. The embarrassment from that rejection was not on the authors. Within two years, many still thought capabilities were wrong. But the sneer was gone. Arguments could be heard. I dare say it marks the beginning of the capability revival in academia.
  - erights 7y ago
    Much of my work on capabilities, from 1988 till now, can be found at https://research.google/people/author35958/ https://research.google/people/author35958/ and at Agoric https://agoric.com/papers/ https://agoric.com/papers/ Agoric is bringing distributed object-capabilities to the modern world of decentralized crypto-commerce, including blockchains. Starting from object-capabilities, we're building a framework for highly composable smart contracts. Hack it at hackathon https://medium.com/agoric/spend-the-pandemic-inside-join-our-gitcoin-cross-chain-hackathon-and-win-prizes-d58e0437a874 https://medium.com/agoric/spend-the-pandemic-inside-join-our...
    - magicalhippo 7y ago
      > https://agoric.com/papers/ https://agoric.com/papers/ For someone who hadn't really read about this before, I found this[1] article, linked above, to be a really nice introduction. [1]: http://habitatchronicles.com/2017/05/what-are-capabilities/ http://habitatchronicles.com/2017/05/what-are-capabilities/
lidHanteyk 7y ago
Kind of. There's still a lot of work to do. OAuth and SAML are quite common, but they cannot federate capabilities; it is not trivial to issue somebody a capability to act on your behalf without an entire infrastructure of assistant services and trusted providers. That said, each decade looks better than the last, but I still encounter the myths covered in the paper, especially incorrect beliefs about revokation, on a regular basis.
say_it_as_it_is 7y ago
The opposite is true. Virtually no web auth systems are capability based. Maybe security SaaS providers are using it, but relatively spreading, they're not representative of the web proper.

carapace 7y ago

There's something called "Macaroons" that can be used for this. "Macaroons: Cookies with Contextual Caveats for Decentralized Authorization in the Cloud" Arnar Birgisson, Joe Gibbs Politz, Úlfar Erlingsson, Ankur Taly, Michael Vrable, Mark Lentczner ; Network and Distributed System Security Symposium, Internet Society (2014) https://research.google/pubs/pub41892/ https://research.google/pubs/pub41892/ "Google's Macaroons in Five Minutes or Less" https://blog.bren2010.io/2014/12/04/macaroons.html https://blog.bren2010.io/2014/12/04/macaroons.html A Javascript implementation: https://github.com/nitram509/macaroons.js https://github.com/nitram509/macaroons.js

ggm 7y ago

The main myth we discussed over coffee and biscuits back in the compsci staffroom was .. expensive as all hell on the computers we have now. (a good handwaving often used to say "one day, in the future, somebody will make it work")

brandmeyer 7y ago
Looking at it strictly from the outside, it looks like there's a ton of indirection to make it work. People usually do want revocable capabilities, which implies that every capability grant has one or more levels of indirection that go with it. Indirection's costs haven't gotten cheaper in well over a decade.
- bhk 7y ago
  An ACL implies a level of indirection, and typically a look-up as well.
- squiggleblaz 7y ago
  Considering now every time you want to do anything on a computer you're getting interpreted code in a memory heavy gui environment to send a HTTP request over a TLS connection to a remote computer via a flaky wifi connection, the cost of doing an indirection might be relatively much less than it was a decade ago. In those days, you might recall, most of the time you clicked in your software it would be doing direct lookups in the machine's comparatively fast spinning disk using native compiled code in a gui api designed with a considered tradeoff between developer's convenience and memory usage - designed in the days when there were fewer developers and much less memory. Of course, half the time those indirections will probably be remote to the server you're already waiting on...

magicalhippo 7y ago

So I haven't been exposed to capability systems before so this might be a dumb question. In an OS like KeyKOS, how does the OS protect against privilege escalation using side-channel attacks similar to how encryption keys are extracted via hardware side-channels?

throwaway_pdp09 7y ago
I'm not the person to answer but let me try. Anyone correct me please. Side channel attacks are AIUI about information leakage. They extract info on the state, not modify state[0]. I don't think privilege escalation is really related because that needs to modify state you should not have access to[1]. Capabilities at the OS and software level are software enforced, which is built on assumptions about the security (correctness guarantees) of the hardware. If the hardware leaks, the software is vulnerable unless/until patched to try to paper over the leaky cracks in the hardware. Again, AIUI. [0] Though such extracted data might be a security token that can subsequently be used to actively attack, such as logging in via someone's newly pwned admin password. [1] I suppose rowhammer is exactly that, though, an attack that intentionally leads to a handy state change for the attacker.
- magicalhippo 7y ago
  > I don't think privilege escalation is really related because that needs to modify state you should not have access to. But in a capability-based OS, privilege is all about the keys you hold, no? So assuming a malicious process can copy keys from other processes, can the OS detect and prevent the malicious process from using the key? I tried reading up on KeyKOS[1] and there was very little info on what exactly a key is and how it is verified by the OS, at least that I could see. [1]: http://cap-lore.com/CapTheory/KK/Arch/ http://cap-lore.com/CapTheory/KK/Arch/
  - throwaway_pdp09 7y ago
    You are right - see my note [0] but I missed the bleedin obvious. Thanks for pointing it out. In that case the hardware is effectively broken and all that's left is attempted software mitigation. Which may/may not work, but surely will cost performance. And extra complexity. And consequential possible bugs. From memory a key can be represented as a random 64-bit integer taken from a sparse set. IOW you'd have bugger all chance of guessing another currently used 64-bit int, and if you tried and guessed wrong the OS, which would keep a list of caps allocated to each process) would say when you tried to use it "and where exactly did this come from, eh?" and kill you. But that's from memory and guesswork. HTH and don't trust what I say too much!

amelius 7y ago

Shouldn't permissions ultimately be Turing-complete functions? E.g. you could do fancy things like grant someone access to a folder, and also to all subdirectories whose name starts with "collaboration_". And you can build any kind of permission system with it, if you don't like the power or complexity.

fnord123 7y ago
Absolutely not. Turing-complete functions are subject to Rice's Theorem - meaning that they are undecidable in the general case. Also, if it's Turing-complete then anyone can make a ridiculous mess of an area with little or no tooling. Configuration should be Turing-incomplete unless you have a very good reason to do otherwise. Being Turing-incomplete is a valuable feature.
- amelius 7y ago
  You haven't given an argument for why "undecidability" would be a problem in this case. Please give a compelling example. We're not banning regular applications either because they are undecidable. Also, we could change Turing completeness into something less powerful, for instance programs without loops.
  - fnord123 7y ago
    Undecidability means loading your configuration could never complete or could consume an indeterminate amount of resources. Which means it's a security concern as a bad config can DOS your system. This type of attack exists even without Turing-complete config but just with references: https://en.wikipedia.org/wiki/Billion_laughs_attack https://en.wikipedia.org/wiki/Billion_laughs_attack > Also, we could change Turing completeness into something less powerful, for instance programs without loops. Yes, this is a strategy. For example BPF does not support loops.