Macaroons - A Better Kind of Cookie

From Papers We Love (Too) #21

Video: https://www.youtube.com/watch?v=bFn-wjQtxZ0

Transcript

1. Macaroons A better kind of cookie Tony Arcieri Papers We Love November 19th, 2015
4. Macaroons: Cookies with Contextual Caveats for Decentralized Authorization in the Cloud Arnar Birgisson Chalmers University of Technology arnarbi@gmail.com Joe Gibbs Politz Brown University joe@cs.brown.edu ´ Ulfar Erlingsson, Ankur Taly, Michael Vrable, and Mark Lentczner Google Inc {ulfar,ataly,mvrable,mzero}@google.com Abstract —Controlled sharing is fundamental to distributed systems; yet, on the Web, and in the Cloud, sharing is still based on rudimentary mechanisms. More flexible, decentralized cryptographic authorization credentials have not been adopted, largely because their mechanisms have not been incrementally deployable, simple enough, or efficient enough to implement across the relevant systems and devices. This paper introduces macaroons : flexible authorization cre- dentials for Cloud services that support decentralized delegation between principals. Macaroons are based on a construction that uses nested, chained MACs (e.g., HMACs [43]) in a manner that is highly efficient, easy to deploy, and widely applicable. Although macaroons are bearer credentials, like Web cookies, macaroons embed caveats that attenuate and contextually confine when, where, by who, and for what purpose a target service should authorize requests. This paper describes macaroons and motivates their design, compares them to other credential systems, such as cookies and SPKI/SDSI [14], evaluates and measures a prototype implementation, and discusses practical security and application considerations. In particular, it is considered how macaroons can enable more fine-grained authorization in the Cloud, e.g., by strengthening mechanisms like OAuth2 [17], and a formalization of macaroons is given in authorization logic. I. INTRODUCTION Macaroons are authorization credentials that provide flexible support for controlled sharing in decentralized, distributed systems. Macaroons are widely applicable since they are a form of bearer credentials—much like commonly-used cookies on the Web—and have an efficient construction based on keyed cryptographic message digests [43]. Macaroons are designed for the Web, mobile devices, and the related distributed systems collectively known as the Cloud. Such modern software is often constructed as a decentralized graph of collaborative, loosely-coupled services. Those ser- vices comprise different protection domains, communication channels, execution environments, and implementations—with each service reflecting the characteristics and interests of the different underlying stakeholders. Thus, security and access control are of critical concern, especially as the Cloud is commonly used for sharing private, sensitive end-user data, e.g., through email or social networking applications. Unfortunately, controlled sharing in the Cloud is founded on basic, rudimentary authorization mechanisms, such HTTP cookies that carry pure bearer tokens [21, 54]. Thus, today, it is practically impossible for the owner of a private, sensitive image stored at one Cloud service to email a URL link to that image, safely—given the many opportunities for impersonation and eavesdropping—such that the image can be seen only by logged-in members of a group of users that the owner maintains at another, unrelated Cloud service. Currently, this use case is possible only if the image, access group, and users are all at a single service, or if two Cloud services keep special, pairwise ties using custom, proprietary mechanisms (e.g., as done by Dropbox and Facebook [55]). Of course, the ubiquitous use of bearer tokens is due to advantages—such as simplicity and ease of adoption—that cannot be overlooked. For example, bearer tokens can easily authorize access for unregistered users (e.g., to the shopping cart of a first-time visitor to a Cloud service) or from unnamed, transient contexts (e.g., from a pop-up window shown during private, incognito Web browsing). Such dynamic and short- lived principals arise naturally in distributed systems, like the Cloud and the “Grid” [47]. In comparison, most authorization mechanisms based on public-key certificates are not directly suited to the Cloud, since they are based on more expensive primitives that can be difficult to deploy, and define long-lived, linkable identities, which may impact end-user privacy [21]. Even so, the inflexibility of current Cloud authorization is quite unsatisfactory. Most users will have first-hand experience of the resulting frustrations—for example, because they have clicked on a shared URL, only to be redirected to a page requesting account creation or sharing of their existing online identity. Similarly, many users will have uncomfortably surren- dered their passwords to use some Cloud service functionality, such as to populate an address book (e.g., on LinkedIn.com) or to aggregate their financial data (e.g., on mint.com). Macaroons aim to combine the best aspects of using bearer tokens and using flexible, public-key certificates for authorization, by providing (i) the wide applicability, ease- of-use, and privacy benefits of bearer credentials based on fast cryptographic primitives, (ii) the expressiveness of truly decentralized credentials based on authorization logic, like SPKI/SDSI [14], and (iii) general, precise restrictions on how, where, and when credentials may be used. Permission to freely reproduce all or part of this paper for noncommercial purposes is granted provided that copies bear this notice and the full citation on the first page. Reproduction for commercial purposes is strictly prohibited without the prior written consent of the Internet Society, the first-named author (for reproduction of an entire paper only), and the author’s employer if the paper was prepared within the scope of employment. NDSS ’14, 23-26 February 2014, San Diego, CA, USA Copyright 2014 Internet Society, ISBN 1-891562-35-5 http://dx.doi.org/doi-info-to-be-provided-later
5. What are Macaroons? Layers
6. Why should you care?
8. Why should you care? username + password/2FA
9. Why should you care?
10. Why should you care?
11. Why should you care?
12. Why should you care?
13. “Internet of Things”
14. “Internet of ”
15. Internet of Things
16. Existing solutions are rather complex…
17. Distributed Authorization
18. Single Sign-On
19. Single Sign-On
20. Federated Access
21. Why should you care?
22. Principal
23. A very brief and biased history of access control and identity systems…
24. 1970s
26. Identity-centric Access Control Lists Authorization-centric Capabilities
27. Maybe they’re right?
28. Ambient Authority
29. 1980s
30. The Confused Deputy (or why capabilities might have been invented) Norm Hardy Senior Architect Key Logic 5200 Great America Parkway Santa Clara, CA 95054-1108 This is a nearly true story (inessential details have been changed). The events happened about eleven years ago at Tymshare, a company which provided commercial timesharing services. Be- fore this happened I had heard of capabilities and thought that they Were neat and tidy, but was not yet convinced that they were necessary. This occasion convinced me that they were necessary. Our operating system was much like Unix (aM of AT&T) in its protection structures. A compiler was installed in a directory called SYSX. A user would use the compiler by saying "RUN (SYSX)FORT", and could provide the name of a file to receive some optional debugging output. We had instrumented the compiler to collect statistics about language feature usage. The statistics file was called (SYSX)STAT, a name which was assembled into the compiler. To enable the compiler to write the (SYSX)STAT file, we marked the file holding the compiler { (9YSX)FORT} with homefiles license. The operating system allowed a program with such license to write files in its home directory, SYSX in our case. The billing information file (SYSX)BILL was also stored in SYSX. Some user came to know the name (9YSX)BILL and supplied it to the compiler as the name of the file to receive the debugging information. The compiler passed the name to the operating system in a request to open that file for output. The operating system, observing that the compiler had home files license, let the compiler write debugging information over (SYSX)BILL. The billing information was lost. Who is to blame? What can we change to rectify the problem? Will that cause other problems? How can we foresee such problems? The code to deposit the debugging output in the file named by the user cannot be blamed. Must the compiler check to see if the output file name is in another directory by scanning the file name? No--it is useful to specify the name of a file in another directory to receive output. Should the compiler check for directory name SYSX? No---the name "SYSX" had not been invented when this code was written. Indeed there might be a legitimate request for the compiler to deposit its out- put in some file in SYSX made by someone with legitimate access to that directory. Should the compiler check for the name (SYSX)BILL? That is not the only sensitive file in SYSX. Must the compiler be modified whenever new files are added to SYSX? When the code was written to produce the output it was correct! What happened to make it wrong? The precise answer is that it became wrong when we added home files license to (SYSX)FORT. To determine this, however, would have required examination of every situation in which the compiler wrote a file. Even when we identify those situations it is not clear what to do. 36
31. A somewhat inaccurate retelling…
32. Confused Deputy Arrest Santa! Why?
33. Confused Deputy I’m Andy Griffith Ok then! X
34. Confused Deputy X little authority OMG
35. Respect Authority little authority
36. Confused Deputy X little authority OMG
37. Respect Authority little authority
38. Meanwhile in Bureaucracy Land
39. A.K.A. Papers We Don’t Love
40. X.509
43. 1990s
45. X.509 PKI
46. X.509 Certificates
48. Can we do better?
49. 1996 Concern is already spreading!
50. SPKI/SDSI Simple Public Key Infrastructure Simple Distributed Security Infrastructure
52. 2000s
53. ACLs don’t Tyler Close Hewlett-Packard Labs Palo Alto, CA Email: tyler.close@hp.com Abstract The ACL model is unable to make correct access decisions for interactions involving more than two principals, since required information is not retained across message sends. Though this deficiency has long been documented in the published literature, it is not widely understood. This logic error in the ACL model is exploited by both the clickjacking and Cross- Site Request Forgery attacks that affect many Web applications. 1. Introduction In the last few years, increasing attention has been devoted to attacks which are distinctly different in nature from the major vulnerabilities discussed in the past. Previously, buffer overflow, SQL injection and Cross-Site Scripting (XSS) garnered the most attention. These attacks all share a common modus operandi in that they inject code into a victim program and thus make it behave according to the attacker’s wishes. For example, in a buffer overflow attack, data provided by the attacker is written to a buffer of dimensions declared by the victim. The attacker provides more data than fits in the buffer, causing data to be written into another region of memory, changing the logic of the victim program. In an SQL injection attack, a literal value provided by the attacker is included verbatim in an SQL expression constructed by the victim program. The literal value contains text that matches the SQL syntax for closing a literal expression, followed by more SQL expressions. When the constructed SQL query is executed, the attacker gains unexpected access to the victim’s database. Similarly, an XSS attack involves attacker input that breaks out of the intended quoting context in HTML, CSS, JavaScript or URL syntax. Recent attacks such as Cross-Site Request Forgery (CSRF) and clickjacking don’t fit this familiar mold. Neither attack requires injecting code chosen by the attacker into the victim program. Instead, both attacks use the victim’s existing program logic to unexpected ends. Using messages that follow the syntactic con- ventions expected for legitimate requests, the attacker makes use of resources that should be inaccessible ac- cording to the application’s access policy. For example, in a CSRF attack, an attacker may successfully send a buy request to a victim’s stock trading application, though no one but the account’s owner is supposed to be allowed to do that. In a clickjacking attack, an attacker may start a web-cam recording, though no one but the computer’s user is supposed to be allowed to do that. Though these victim applications may correctly implement traditional access control lists (ACLs), somehow the attacker still gains access to resources that are supposed to be inaccessible, and does so without modifying any of the application’s program logic. Stranger still, the popular counter-measures for these attacks do not involve fixing incorrect ACL config- urations, nor adding ACLs to unprotected parts of the application. Though these attacks circumvent the application’s access policy, ACLs seem to play no part in fixing the problems. Why do ACLs seem to be so ineffective at fulfilling their basic purpose of controlling access? This paper provides an explanation of the com- mon modus operandi of the new wave of attacks that includes CSRF and clickjacking. This explanation clarifies how these attacks exploit flaws in the ACL model. These flaws render the ACL model ineffective for access control in scenarios involving more than two principals, such as are common on the Web. The first part of this paper starts with the fundamen- tals of the access matrix, explaining how it operates in multi-party scenarios. This explanation points out exactly where the logic errors occur in the ACL model and what their effects are. Enhancements of the ACL model and alternate models are discussed in terms of
54. Tyler Close Hewlett-Packard Labs Palo Alto, CA Email: tyler.close@hp.com Abstract The ACL model is unable to make correct access decisions for interactions involving more than two principals, since required information is not retained across message sends. Though this deficiency has long been documented in the published literature, it is not widely understood. This logic error in the ACL model is exploited by both the clickjacking and Cross- Site Request Forgery attacks that affect many Web applications. 1. Introduction In the last few years, increasing attention has been devoted to attacks which are distinctly different in nature from the major vulnerabilities discussed in the past. Previously, buffer overflow, SQL injection and Cross-Site Scripting (XSS) garnered the most attention. Neither attack requ attacker into the vic use the victim’s exi ends. Using messag ventions expected f makes use of resour cording to the applic in a CSRF attack, a buy request to a though no one but to be allowed to d an attacker may st no one but the co allowed to do that. may correctly imple (ACLs), somehow resources that are does so without m program logic.
55. Macaroons
56. Macaroons: Cookies with Contextual Caveats for Decentralized Authorization in the Cloud Arnar Birgisson Chalmers University of Technology arnarbi@gmail.com Joe Gibbs Politz Brown University joe@cs.brown.edu ´ Ulfar Erlingsson, Ankur Taly, Michael Vrable, and Mark Lentczner Google Inc {ulfar,ataly,mvrable,mzero}@google.com Abstract —Controlled sharing is fundamental to distributed systems; yet, on the Web, and in the Cloud, sharing is still based on rudimentary mechanisms. More flexible, decentralized cryptographic authorization credentials have not been adopted, largely because their mechanisms have not been incrementally deployable, simple enough, or efficient enough to implement across the relevant systems and devices. This paper introduces macaroons : flexible authorization cre- dentials for Cloud services that support decentralized delegation between principals. Macaroons are based on a construction that uses nested, chained MACs (e.g., HMACs [43]) in a manner that is highly efficient, easy to deploy, and widely applicable. Although macaroons are bearer credentials, like Web cookies, macaroons embed caveats that attenuate and contextually confine when, where, by who, and for what purpose a target service should authorize requests. This paper describes macaroons and motivates their design, compares them to other credential systems, such as cookies and SPKI/SDSI [14], evaluates and measures a prototype implementation, and discusses practical security and application considerations. In particular, it is considered how macaroons can enable more fine-grained authorization in the Cloud, e.g., by strengthening mechanisms like OAuth2 [17], and a formalization of macaroons is given in authorization logic. I. INTRODUCTION Macaroons are authorization credentials that provide flexible support for controlled sharing in decentralized, distributed systems. Macaroons are widely applicable since they are a form of bearer credentials—much like commonly-used cookies on the Web—and have an efficient construction based on keyed cryptographic message digests [43]. Macaroons are designed for the Web, mobile devices, and the related distributed systems collectively known as the Cloud. Such modern software is often constructed as a decentralized graph of collaborative, loosely-coupled services. Those ser- vices comprise different protection domains, communication channels, execution environments, and implementations—with each service reflecting the characteristics and interests of the different underlying stakeholders. Thus, security and access control are of critical concern, especially as the Cloud is commonly used for sharing private, sensitive end-user data, e.g., through email or social networking applications. Unfortunately, controlled sharing in the Cloud is founded on basic, rudimentary authorization mechanisms, such HTTP cookies that carry pure bearer tokens [21, 54]. Thus, today, it is practically impossible for the owner of a private, sensitive image stored at one Cloud service to email a URL link to that image, safely—given the many opportunities for impersonation and eavesdropping—such that the image can be seen only by logged-in members of a group of users that the owner maintains at another, unrelated Cloud service. Currently, this use case is possible only if the image, access group, and users are all at a single service, or if two Cloud services keep special, pairwise ties using custom, proprietary mechanisms (e.g., as done by Dropbox and Facebook [55]). Of course, the ubiquitous use of bearer tokens is due to advantages—such as simplicity and ease of adoption—that cannot be overlooked. For example, bearer tokens can easily authorize access for unregistered users (e.g., to the shopping cart of a first-time visitor to a Cloud service) or from unnamed, transient contexts (e.g., from a pop-up window shown during private, incognito Web browsing). Such dynamic and short- lived principals arise naturally in distributed systems, like the Cloud and the “Grid” [47]. In comparison, most authorization mechanisms based on public-key certificates are not directly suited to the Cloud, since they are based on more expensive primitives that can be difficult to deploy, and define long-lived, linkable identities, which may impact end-user privacy [21]. Even so, the inflexibility of current Cloud authorization is quite unsatisfactory. Most users will have first-hand experience of the resulting frustrations—for example, because they have clicked on a shared URL, only to be redirected to a page requesting account creation or sharing of their existing online identity. Similarly, many users will have uncomfortably surren- dered their passwords to use some Cloud service functionality, such as to populate an address book (e.g., on LinkedIn.com) or to aggregate their financial data (e.g., on mint.com). Macaroons aim to combine the best aspects of using bearer tokens and using flexible, public-key certificates for authorization, by providing (i) the wide applicability, ease- of-use, and privacy benefits of bearer credentials based on fast cryptographic primitives, (ii) the expressiveness of truly decentralized credentials based on authorization logic, like SPKI/SDSI [14], and (iii) general, precise restrictions on how, where, and when credentials may be used. Permission to freely reproduce all or part of this paper for noncommercial purposes is granted provided that copies bear this notice and the full citation on the first page. Reproduction for commercial purposes is strictly prohibited without the prior written consent of the Internet Society, the first-named author (for reproduction of an entire paper only), and the author’s employer if the paper was prepared within the scope of employment. NDSS ’14, 23-26 February 2014, San Diego, CA, USA Copyright 2014 Internet Society, ISBN 1-891562-35-5 http://dx.doi.org/doi-info-to-be-provided-later
57. Bearer Credentials
58. Caveats
59. Can Be Redundant
60. Can Be Overlapping
61. Contextual Caveats
62. Construction
64. tag = HMAC(key, message)
65. Cookie Structure user_id=42;expires_at=1447978216 HMAC
66. Cookie Structure user_id=42;expires_at=1447978216 10110…
67. Cookie Structure user_id=42;expires_at=1447978216
68. Macaroon Structure identifier 0df660d08982db8766d6490402376105 Nonce
69. Adding Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216
70. Adding Caveats HMAC identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216
71. Adding Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216
72. Adding Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 HMAC
73. Adding Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085
74. http://crypto-class.org
76. How does this help?
77. Authorization Not Identity user_id=42;… identifier 0df660d08982db8766d6490402376105 Authorization Caveats Macaroon Cookie cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid widget-id 327,484,589,701,1032 cid widget-op read,write Users Policy Domain Objects
78. “What you can do” not “Who you are”
79. Authorization Not Identity user_id=42;… identifier 0df660d08982db8766d6490402376105 Macaroon Cookie cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid widget-id 327,484,589,701,1032 cid widget-op read,write cid expires-at 144605501 cid widget-id 701 cid widget-op read A t t e n u a t i o n
80. Delegation TS IS C TS IS C TS IS C Proxy Re-minted Macaroon restrictions restrictions restrictions Fig. 2. Three ways for an intermediary service IS to give a client C limited access to a target service TS: by proxying requests, by having TS mint new, restricted credentials for C, or by IS deriving new macaroons for C. Arrows show credential passing and doubled arrows indicate access. In their expressiveness, and in aspects of their construction, macaroons are related to cascaded proxy certificates [44], re- stricted delegation [33], active certificates [12], proof-carrying authentication [6], and Grid computing [22], as well as systems for limiting resource consumption [23] and access to net- predicate that must hold that the derived macaroon with that predicate evaluat of each particular request adding caveats, new, mor can be directly derived requests to the target ser from it. Thus, macaroon overhead, loss of transpar by the proxying and cred used in the today’s Cloud For example, every m more validity-period cave (at the target service) duri requests; similarly, each m restrict the arguments per have multiple caveats on which case all the cavea context of requests.
81. Contextual Caveats cid public-key 55b84d02e6b94f6125a87a4a47f085 http://www.browserauth.net/channel-bound-cookies
82. Contextual Caveats cid subject-rdn cn=beautiful-snowflake
83. Contextual Caveats
84. Macaroon Service Service Service Service
85. What makes Macaroons truly unique?
86. Third-Party Caveats
87. Unconfused Deputy Arrest Santa! You’ll have to ask the Sheriff first!
88. Unconfused Deputy Tell Barney to arrest Santa! No.
89. Unconfused Deputy
90. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org
91. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org
92. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org
93. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org 3rd Party Key
94. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org
95. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org
96. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org @authentication.org
97. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org @authentication.org cid expires-at 1445863121
98. Third-Party Caveats identifier 0df660d08982db8766d6490402376105 cid expires-at 1447978216 cid public-key 55b84d02e6b94f6125a87a4a47f085 cid identity@authentication.org @authentication.org cid expires-at 1445863121 Discharge Macaroon
99. “Holder-of-Key Proof”
101. Nested Third-Party Caveats
102. Syntax: Compound principals A, B ::= P | k | A ^ B | b Formulas , ::= valid | true | p | X | 8X. | ^ | _ | | A says | A ) B Axioms: All the axioms of propositional constructive logic [PROP] ` (A says ( )) (A says A says ) [DISTRIBUTION] ` (A says B ) A) B ) A [HANDOFF] ` A ^ A ⌘ A [CONJ1] ` A ^ B ⌘ B ^ A [CONJ2] ` (A ^ B) ^ C ⌘ A ^ (B ^ C) [CONJ3] ` (A ^ B says ) ⌘ (A says ) ^ (B says ) [CONJ4] ` A ) B ⌘ (A ^ B = A) [SPEAKS-FOR] ` (TR says ) (b says valid) [PPRIN] Rules: ` ` ` [MODUS-PONENS] ` ` A says [NECESSITATION] Fig. 11. The syntax, axioms and rules for an authorization logic suitable for macaroons. Here, TR and b are request and predicate principals, respectively, P 2 Prncs , k 2 Keys , and X is a variable in a proposition p 2 PropCavs . Request principals and predicate principals: A request principal TR is a special principal that makes the strongest possible assertion—using propositions from PropCavs —that a target service can see to be true for the context of a request. Such principals are completely controlled by the target service. For example, TR says “chunk is 250” ^ “operation is read” ^ “IP is 172 . 12 . 34 . 4” indicates that the target service is seeing a request to read chunk 250 being made from the IP address 172.12.3.44. A predicate principal b is a special principal introduced to model the effect of a first-party caveat with predicate . Informally, the principal b says that a request is valid, and the caveat is satisfied, if the request principal TR asserts . This characteristic is formalized by the axiom [PPRIN]. By combining the axiom [PPRIN], the [DISTRIBUTION] axiom and the [NECESSITATION] rule, the following rule can be derived: ` ` TR says ` b says valid [FCAVDISCHARGE] . This rule means that if TR asserts a predicate for a request, and this predicate logically implies a weaker predicate in a first-party caveat, then that caveat is satisfied for this request. Macaroon formulas: In this logic, macaroons are defined by formulas that describe restricted speaks-for delegations from the target service to certain caveat principals (corresponding to embedded first-party caveats), and certain keys (correspond- ing to the root keys of embedded third-party caveats). A request made using macaroon credentials is authorized if it can be proven—from the macaroon’s formulas, and the request principal TR ’s assertion about the request context—that the root key of the macaroon says valid, which implies that the macaroon signatures verify using this root key, and that all embedded caveat predicates are satisfied. Before formally defining macaroon formulas, it’s worth giving some examples. Consider a macaroon M1 := macaroon@L h kId, [ ] , k1 i that is minted from root key k0 without any caveats. This macaroon M1 represents a complete delegation from the key k0 to the empty caveat principal d true, which considers all requests valid. Thus, M1 is modeled by the formula k0 says d true ) k0 . A macaroon M2 := macaroon@L h kId, [cav@> h , 0i] , k2 i can be obtained by extending M1 with a first-party caveat whose predicate is , to represent a delegation from the root key k0 to the caveat principal b. This macaroon M2 is modeled by the formula k0 says b ) k0 . Finally, the macaroon M2 can be extended with a third- party caveat whose root key is cK , to obtain the macaroon M3 := macaroon@L h kId, [cav@> h , 0i , cav@l h cId, vId i] , k3 i . This macaroon M3 represents a delegation from the root key k0 to the conjunction of the cK and b principals—i.e., that k0 says that a request is valid only if both cK and b say so. Thus, M3 is modeled by the formula k0 says cK ^ b ) k0 . The formula for an arbitrary macaroon M can now be defined. Definition 1 (Macaroon formulas): A macaroon M whose root key is k0 , embedding first-party caveats whose predicates are 1, . . . , m , and embedding third-party caveats whose root keys are cK1, . . . , cKn , is modeled using the formula ↵ ( M ) := k0 says (c 1 ^ . . . ^ c m ^ cK1 ^ . . . ^ cKn ) ) k0. For a set M, the formulas are ↵ (M) := { ↵ ( M ) | M 2 M}. Macaroon verification: To verify that a request is authorized by a macaroon M , the target service must verify—using a root key k0 for M , known only to the target service—the set M of macaroons presented with the request, including M and all third-party discharges, and establish that all their embedded first-party caveats are satisfied. The verification of a first-party caveat with a predicate is modeled by having the request principal TR assert the strongest possible formula req about the request context, and, if req , apply the derived rule [FCAVDISCHARGE] to show that the principal b considers the request to be valid. In general, a request accompanied by such a macaroon set M is authorized if the formulas ↵ (M) together with the formula TR says req imply that k0 says valid for the root key k0 . Recursively, this requires that M contain discharge macaroons for any third-party caveats involved, and that TR says req allows cK says valid to be established for the root key cK of each of those discharge macaroons. Definition 2 (Macaroon verification): A set of macaroons M, whose distinguished authorizing macaroon M has the root key k0 , authorizes a request whose target-service context is described by the propositional assertion req , if, and only if ` ( TR says req ^ ^ M2M ↵ ( M )) ( k0 says valid) . In addition to being a basis for the formal analysis of macaroon-based protocols, the above definition makes it clear how macaroons only grant authority for a target-service re- quest, as long as all caveats have been discharged in its context. 16
103. Open Source Libraries • libmacaroons (C): https://github.com/rescrv/libmacaroons • go-macaroon (Go): https://github.com/go-macaroon/macaroon • jmacaroons (Java): https://github.com/nitram509/jmacaroons • macaroons.js (JavaScript): https://github.com/nitram509/macaroons.js • pymacaroons (Python): https://github.com/ecordell/pymacaroons • ruby-macaroons (Ruby): https://github.com/localmed/ruby-macaroons • Macaroons.NET (C#): https://github.com/JornWildt/Macaroons.Net • php-macaroons (PHP): https://github.com/immense/php-macaroons • rust-macaroons (Rust): https://github.com/cryptosphere/rust-macaroons
104. Thank You! • Paper: http://research.google.com/pubs/pub41892.html • Unofficial Macaroons web site: http://macaroons.io/ • Google Group: https://groups.google.com/d/forum/macaroons • We have Slack! • My Twitter: https://twitter.com/bascule