plus/minus epsilon

Macaroons are a proposed method of distributed (NOT decentralized) authorization. Their main distinction from a bearer token is that, if I'm given a Macaroon that authorizes me to perform some action(s) under certain restrictions, I can non-interactively build a second Macaroon with stricter restrictions that I can then give to you. For example, if I have a Macaroon that allows me to view and delete an image on Imgur, I can construct a second Macaroon that only allows the holder to view the image as long as time ≤ "5/1/13, 1am GMT" and give that to all of my friends.

Construction

Macaroons are a Merkle-Damgård construction, with the exception that the IV is a secret known only to the server. The server builds a new Macaroon by choosing a nonce as the head and compressing it with the IV, h(IV, nonce), called the tail. Caveats, or predicates in some domain-specific language, are then added as successive message blocks, each time calculating the new tail as h(lastTail, caveat). The server outputs the head, the list of caveats, and the tail.

A user can continue to add caveats in the exact same fashion as the server--i.e., by appending the new caveat to the list and then compressing it with the last tail to get the new tail:   h(lastTail, caveat).

A Macaroon authorizes an action if all of the predicates/caveats are satisfied when it's presented back to the server. This means that if there are multiple predicates on a single variable, only their intersection is authorized--if a Macaroon has disjoint predicates, then it authorizes nothing. The server should also verify the integrity of the presented Macaroon by checking that its tail equals the tail calculated by pushing the head and list of caveats through the Merkle-Damgård construction with its secret key as the IV.

Macaroons are secure because the compression function is hard-to-invert, meaning that an adversary can't remove caveats they wouldn't already be allowed to bypass by having a less-restrictive Macaroon. Because the IV is secret, an adversary also can't generate fresh Macaroons with whatever caveats suit them.

(In the original paper, HMAC was specified as the compression function, but any hard-to-invert compression function can be used.)

Third-Party Caveats

A third-party caveat is a predicate that can only be verified by a third party, like an authentication service. If the third-party believes the predicate is satisfied, they give the user a proof saying so, which then allows the user to make requests to the first party (who issued the Macaroon) without any interaction (or even affiliation) between the first and third party. Taking the example from the introduction again, this would be useful for making sure that all of my friends are logged into their Twitter accounts, so I know only they can see whatever I've posted on Imgur and that they can't share the link with people I don't like.

To create a third-party caveat, a random key r is first generated, and then a caveat is added to the Macaroon containing the following information:

1. The service's name: Tells the Macaroon's holder where they need to go to satisfy the third-party caveat.
2. Enc(K, r || predicate): Where Enc is the encrypt function for an authenticated encryption mode, K is a secret key shared by the third-party and the party adding the caveat, and predicate is the conditions on which the third-party should authorize the holder. This value in its entirety functions as the head of the new Macaroon.
3. Enc(lastTail, r): Allows the server (first party) to learn r.

When the holder presents this caveat to the third party, it decrypts section #2 to obtain r and the predicate. If the predicate is satisfied by the holder, the third party creates a new Macaroon by compressing the head (section #2, still encrypted) with the key r:   h(r, Enc(K, r || predicate)). It can then go through and add any caveats restricting the validity of its proof with the same Merkle-Damgård construction as above, and once it's finished, it hashes/finalizes the tail once more to prevent any more caveats from being added and outputs the new Macaroon.

The server can verify third-party Macaroons in the same way that it verifies first-party Macaroons because it can reconstruct lastTail and retrieve r from section #3.

Third-party caveats are secure for the same reason as above--they can't be removed unless the holder already knows a less-restrictive Macaroon. In addition, only the first and third parties, as well as the person who created the caveat, can produce a valid second Macaroon because they're the only ones who know r.

Conclusion

Macaroons. Super simple stuff.

Addendum

Publicly-verifiable Macaroons can be constructed naturally with Append-Only Signatures (AOS), or equivalently, Hierarchical Identity-Based Signatures (HIBS).

References

1. "Macaroons: Cookies with Contextual Caveats for Decentralized Authorization in the Cloud"
2. "Append-Only Signatures"