How to implement disjuction caveats?

[Akram Shehadi]

Hello everyone,

I've been trying to implement an authorization middleware for Express using Macaroons and while my implementation works already, it's pretty much the same as the demo code for the reference implementations, just with different caveats, i.e. I'm using simple first-party caveats to authorize access.

The problem I'm having now is how to implement disjunction caveats.

The paper states on page 10:

F. Disjunctive and Negated Caveats When adding third-party caveats to a macaroon, it may be desirable to add a set of them where only one needs to be discharged. An example use case would be to allow a client to choose which authentication provider to use. One way of achieving this would be to augment macaroons to also include a conjunction or disjunction operator at the beginning of every caveat list. The Verify method would then accordingly conjunct or disjunct the proof obligations specified by the caveats. This leads to a notion of caveats on a macaroon as a logical formula with both disjunction and conjunction. One may ask if it makes sense to add negation as well, where a macaroon can only be invoked if a certain caveat is not discharged. However, the semantics of negation become tricky when the negated caveat discharge macaroon contains further nested third-party caveats. Thus, negation should only be supported at the level of predicate checking, e.g., along the lines of op 6∈ {write, delete}, if needed. 

How is it that I can implement a conjunction operator? 

At a first glance it seems to suggest that I can just add a third-party caveat, and inside that caveat we add a first-party caveat predicate that says for example "caveat-operator=conjunction". But what I don't understand is how to change the verifier's logic since as far as I can see, the verifier just checks whether the context satisfies the caveat, i.e. is the satisfaction condition present in the verifier AND in the user provided macaroon (they are the same)?

For example, after a user logs in, the Mint Service (in this case the same as the Target Service) generates a macaroon with caveats as follows:

serverId=1234
method=GET

Then the user can make a GET request to e.g. targetservice.com/info and provide the previous macaroon.

Before the server gives access to /info to the user, it creates a verifier for the macaroon where we satisfy the context as follows:

verifier.satisfyExact("method="+req.method)
verifier.satisfyExact("serverId=1234")

Thus the request would be authorized, since the verifier is satisfying the caveat for "method=GET" as well as "serverId=1234". On the contrary, if the user were to issue a POST request the verification would fail.

So far so good.

But now I want to restrict the request to one of several authorized routes. For example, the user needs to access targetservice/restricted and /restricted2 but should not be able to access /restrictedX

The macaroon could then look like 

serverId=1234
method=GET
route=/restricted,/restricted2

However that would require the verifier to be able to satisfy EITHER route=/restricted OR route=/restricted2. 

When the user sends a request for GET /restricted, the verifier can try to satisfy the caveat with

verifier.satisfyExact("route="+req.path) // translates to verifier.satisfyExact("route=/restricted")

But as far as I understand that won't be valid because the caveat would need to be satisfied with 

verifier.satisfyExact("route=/restricted,/restricted2")

That's where I would like to be able to add a disjunciton operator such that the verifier can satisfy the route for the request and if that route value is present in the macaroon (along side the other authorized ones) then it would be valid.

Something like:

verifier.satisfyDisjunction("route=", ["/restricted", "/restricted2"])

The problem I find with that line of reasoning is that the chained HMACS would not be correct, because the HMAC for that verifier would not include the rest of the routes, only the current one. 

I.e. in the javascript reference implementation we have:

https://github.com/nitram509/macaroons.js/blob/249ac4b607ab1da2f1c6ac7dfd76c3a1299b0068/lib/MacaroonsVerifier.js#L112

Which would not match the signature if the chained HMAC is going to be constructed differently depending on the requested route.

On the other hand, if we separate put a single route in each "route" caveat, we could get a macaroon like this:

serverId=1234
method=GET
route=/restricted
route=/restricted2

Which then again, would require doing something like:

verifier.satisfyDisjunction("route=", ["/restricted", "/restricted2"])

And it presents the same problems as before, regarding the signature.

Can anyone please help me out understand how exactly can we implement a disjunction with Macaroons?  or what could be an alternative to creating a macaroon that gives authorization to a set of things, where only one of those things needs to be present? As I understand Macaroons that would not be possible, however the authors state that it is, so I'm clearly missing something.

Any help is greatly appreciated!

Akram

[Robert Escriva]

The libmacaroons verifier already supports a form of disjunction. You
can provide two different (third party) macaroons that share the same
identity and secret and have different caveats. You could easily make a
third party caveat on the root macaroon in your proof tree and have one
discharge macaroon for each predicate in the disjunction.

-Robert

> --
> You received this message because you are subscribed to the Google Groups
> "Macaroons" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to macaroons+...@googlegroups.com.
> To post to this group, send email to maca...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/
> macaroons/0ac6f8d2-dada-41e3-b45f-b76e61d788c3%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Akram Shehadi]

Hi Robert,

Just to get this straight, if I understand correctly I can add a third party caveat to the macaroon that I give to the user. 

first-party caveats:
    serverId=1234
    method=GET

third-party caveats:
    <result of disjunction>

This TP caveat can be fulfilled by more than one discharge macaroons, each of which will have a first-party caveat for each predicate in the disjunction, and since these discharge macaroons will be created with the same id and secret, they shouldn't alter the signature correct?

Then whenever the user issues a request, it presents the macaroon which now needs a discharge macaroon for the TP caveat. As I see it, the same step that verifies the macaroon can create the discharge macaroon with the correct predicate (i.e. route=/restricted) if said route is one of the authorized ones, which means that if the disjunction is not valid because the request contains a unauthorized route value, the discharge macaroon is not generated, and thus the TP caveat not fulfilled and in turn the access is not allowed.

Is my understanding correct?

Thanks a lot!

Akram

[Akram Shehadi]

So in essence, whichever service discharges the third-party caveat for the disjunction, is the one responsible for actually calculating the disjunction's result, correct?

Thanks!

Akram

[Robert Escriva]

One of the principles I tried to uphold in libmacaroons is that a
verifier should be as general as possible and have no knowledge of
caveats directly. The verifier knows nothing of which satisfy_*
function will actually satisfy the predicate, but if there is a proof
tree that can satisfy the request, it is approved.

In your example, to generate a macaroon with a disjunction, you would
generate (at least) three macaroons. The first would have a third party
caveat using a temporarily generated id/secret, and the others use that
id and secret to create one macaroon per predicate in the disjunction.

The client can then present the root macaroon and any one of the other
macaroons when proving that a request is authorized, in effect choosing
which path of the disjunction it will use in its authorization.

This keeps logic for authorizing to a minimum at the target service, but
your example highlights a deficiency in libmacaroons that I've thought
about for awhile: The server-side verification routine is made minimal
and robust, but there's no support for clients. I hope to at some point
in the future be given the opportunity to extend this. Imagine an API
that handles a collection of macaroons and helps you to assemble the
proof tree by giving you the locations to contact for the discharge
macaroons. You could then white-list certain end-points and have a very
general way for clients to dynamically assemble their authorization
credentials. The same mechanism could be used to determine the proper
context and sufficiently restrict the request so a MITM attack that
recovers all macaroons has less exposure.

-Robert

> macaroons/c78b7169-3080-4073-8c97-25664e5c163e%40googlegroups.com.

[Akram Shehadi]

I see. I think I got it the other way around then.

So what you are saying is, have a root macaroon and one discharge macaroon for each predicate in the disjunction.

In my case that would translate to having a root macaroon for the "general caveats" (serverId, method, etc) and then one discharge macaroon for each route the user is authorized to use (i.e. for each of the predicates in the disjunction). This means that if I authorize a user to access 20 routes, I'll have the root macaroon plus 20 discharge macaroons, one for each route. When the user tries to access one of the routes, it will bind the discharge macaroon corresponding to that route, to the root macaroon and send that as proof. 

If that's the case then I guess I'll need to stop storing the macaroons serialized in cookies as that would probably exceed the cookie size limit. Is that an expected side-effect of macaroons? i.e. how bad of a trade off do you think it is that I need so many macaroons for an authorization mechanism? 

Those features you describe would be really neat to make it easier to develop an authorization mechanism using macaroons that sounds more robust and secure than regular auth tokens via cookies. It sort of goes in line with what I'm trying to achieve, albeit your design is more complex. 

In my case my current goal is to be able to provide user access policies to the macaroon generator, so that we can translate a human-readable policy into macaroon caveats. Then in the verification middleware we provide the same user policy as before and use that to build the macaroon verifier which would authorize the user with the correct policy to access a restricted resource. Seems like a similar thing, although maybe I haven't though of the more general case.

Akram

[Robert Escriva]

In this case, why not have one secret per route and then issue a
macaroon per route? The idea of an "id" and a "secret" at the root of
every macaroon is that each resource or unit of authorization is bound
to a different secret.

Under my proposed scheme, you have to generate 20 third party caveat
macaroons for 20 routes. Instead, why not generate 20 root macaroons
each with a third party caveat requiring an auth server state the user
is who they say they are. You have the same number of macaroons total,
but it more naturally (qualitative, I know) maps to the proof-carrying
nature of macaroons.

Storing macaroons in cookies loses quite a bit of the contextualization
of macaroons. In a cookie, you are giving the "bound for request"
macaroons in each request (if I'm understanding you correctly). This is
no better than just a session ID or other opaque token. In an idealized
system, you could take your authorization for the request and throw on
top of it caveats like, "Only valid for the next 5 seconds, from my
current IP address, for this particular URL, at this particular end
server." Now those macaroons will *only* authorize the request you are
making (assuming you contextualize sufficiently), and a replay attack is
all that an attacker can do, and they can only do it in the next 5s.

As for your current goal, you write that you're building a verification
middleware to provide the same user policy to. Ideally, if you build
the right caveats as primitives, you only need to train your verifier to
recognize the custom "satisfy exact" and "satisfy general" methods you
are using in your scheme. The verifier, as written, will automatically
enforce *only* policies you enforced when issuing macaroons. In fact,
you if you had a "satisfy general" predicate that enforced expiration on
macaroons, (nearly)* every other "satisfy exact" predicate could be
transformed into a third party predicate with an intermediate RPC where
the third party attests to what the caveat would have required.

I recommend watching this video for more, especially with regard to
thinking about macaroons as proofs:
https://air.mozilla.org/macaroons-cookies-with-contextual-caveats-for-decentralized-authorization-in-the-cloud/

Parting thought to play with: If a business ran an ad in a newspaper
saying, "Anyone in possession of this ad who can prove they are Robert
Escriva is allowed a free milkshake," anyone could see it, but only I
could act upon it. Similarly, if you had a macaroon authorizing only
@rescrv (via third party caveat authenticating via Twitter) to access
http://example.net/resource, it would not matter if someone other than
@rescrv accidentally came into possession of this macaroon as only
someone who can authenticate to Twitter as me can obtain the relevant
discharge macaroon. Once you realize this, you can start to think of
your database as the newspaper, and can store macaroons for a user on
the service, to be provided to the user iff the user can prove they are
authorized to access those macaroons. Those macaroons, in turn, provide
further authorization. You could make traditional user/group structures
by allowing a user to access a group's macaroons if they can prove they
are a member of the group (or, more accurately, were within the last
X00ms). Any macaroons conferred to the group can be collected by a user
to use as they wish. If you do this, just think about proper expiry.

-Robert

* The only predicates that don't fit this statement are ones where only
parties to the request can verify that the caveats hold at the moment
of request, like the src or dst IP, a hash of the request, or the time
of the request.

> macaroons/924a5233-ff89-472a-886e-c6ac51c2909f%40googlegroups.com.

[Akram Shehadi]

You raise very good points so I guess I'll have to rethink my current structure.

I'll watch the video again and see if I can switch my point of view on what kind of proofs are better served with macaroons.

I definitely think there's an opportunity here to develop a robust macaroon-based authorization mechanism that could ideally provide fine-grained access to API resources.

Hopefully I'll be able to come back with another shot at this interesting problem.

Thanks a mil for the explanation and clarifications! 

Akram

[Evan Cordell]

> The problem I find with that line of reasoning is that the chained HMACS would not be correct, because the HMAC for that verifier would not include the rest of the routes, only the current one. 

> I.e. in the javascript reference implementation we have:

> https://github.com/nitram509/macaroons.js/blob/249ac4b607ab1da2f1c6ac7dfd76c3a1299b0068/lib/MacaroonsVerifier.js#L112

> Which would not match the signature if the chained HMAC is going to be constructed differently depending on the requested route.

The HMAC is calculated based on the caveats in the Macaroon and not something you construct at verification time, so the HMAC chain will be fine. This is where the `satisfyGeneral` can come in handy - you can verify that the route you're accessing is in the set of defined routes in the macaroon.

If you're concerned that this isn't an intended use of Macaroons, here's an example from the paper:

M2 := M1.AddFirstPartyCaveat(“op ∈ {read,write}”)

IMO, subset checks should probably be included in standard implementations in much the same way byte equality is.

There are certainly tradeoffs between this approach and the one Robert described! Just wanted to present an alternate view of the problem.

[Akram Shehadi]

Thanks for the clarification Evan.

That was actually my first approach: Getting a macaroon with a caveat with all the allowed routes (for each HTTP method), and then verify that the requested route exists inside the caveat.

The flow was: whenever a user logs in, the auth server would send one macaroon for each HTTP verb that had at least one authorized route for that user, and some expiry time of course. The idea was that the user could have access to e.g. GET method on routes=[/restricted1, /restricted2] and also POST to routes=[/restricted2].

The problem I had was when I tried to implement this with a satisfyGeneral like you suggested, is that the current implementation (at least in macaroons.js) only passes the caveat as a parameter, and there's no way to pass the current request context to the verifier. 

So if I want to pass the current "req.path" value so that I can search for it in the routes=[...] caveat, I would need to define the satisfyGeneral method inside the scope of the verification routine so that the variables are accessible.

i.e. (this is an Express middleware):

function verify_macaroons(req, res, next) {
    verifier.satisfyGeneral(function(caveat){
        // verify that the requested resource
        // (req.path) exists inside the
        // provided macaroon
        var authorizedRoutes = parseRoutes(caveat);
        if (authorizedRoutes.indexOf(req.path) > -1){
            //is authorized
        }
        else{
           //unauthorized
        }
    });
};

I could also modify the source code of the library so that it takes a context variable that I can use to verify the macaroon, but when I started down this path I realized that maybe I was doing something wrong. That's why I thought of asking about the correct way of implementing a disjunction.

I mean in terms of code it would be pretty easy to add a param to the satisfyGeneral method to take the context, i.e.

verifier.satisfyGeneral(caveat, context){
 ...
}

And so far it seems like it would be in line with the rest of the paper, but I am not really sure. What do you think? it could be a pretty useful addition to increase the functionality of satisfyGeneral, right? 

Whatever the answer is on how to actually implement this check, I think it seems definitely doable, but I would prefer to make meaningful changes to the library instead of just to accommodate my use case.

If it indeed is the case that we can use satisfyGeneral, then I can see basically that the two approaches have several differences with interesting tradeoffs.

In the first approach, the process would be something like this:

- The user contacts the auth service, sends username and password, and in turn gets a macaroon for each of the HTTP verbs that can be used to request a resource in the API. So if the user has low-level access, maybe only one macaroon is sent, for the routes that can be requested via GET. An admin user in turn would probably get all four macaroons (GET, POST, PUT, DELETE) with the authorized routes where they can be used. 

- The corresponding "access macaroon" will be sent with each request, the API can then verify said macaroon and grant or deny access.

This would be mostly like using cookies like Robert pointed out, except that the added macaroon functionality could be used for enhanced functionality later on. E.g. adding a third-party caveat that needs to be discharged via a 2FA service.

The other problem is that since we need to provide a user/password to get these macaroons, we would probably need a longer expiry time. I don't think its a very pleasant user experience to ask for the user and password frequently, so the expiry time would need to be maybe 1 or 2 days? maybe longer?. This in turn has certain side-effects like having a longer attack window and policy updates won't be propagated instantly.

On the other hand, if I understand correctly, Robert's suggestion would boil down to something like this.

- Each resource has an access macaroon associated with it, and these macaroons have a third-party caveat that needs to be discharged by the auth service.

- When a user needs to interact with a resource (endpoint, instance, etc) and doesn't have the access macaroon that authorizes said interaction, the server responds with an access macaroon that needs to have the TP-caveat dispatched to grant access.

Then, two things can be done to get the discharge macaroon:

- The user contacts the auth service, and if the correct password is sent, the auth service responds with a discharge macaroon that proves who the user is and what route is he authorized to use. The problem is this would need to be done for every request, which is unfeasible.

The alternative:

- Add *two* third party caveats to the access macaroon. One for the user and one for the authorized method and route (i.e. the access policy).

The user would then need to:

- Contact the auth service to get a dispatch macaroon for the user part (this one can have a long-ish expiry time, say 2 days).

- Then contact the "policy service", and request a discharge macaroon for the needed HTTP method for the specified resource. We use the previous discharge macaroon that proves we are the correct user, which the policy service uses to determine if the user has access to the requested resource and issues a "policy discharge macaroon". This macaroon can have a short expiry of say, 5 seconds, so that every request would require a fresh discharge macaroon, increasing the probability to defend against a MITM, since like Robert said, at most the attack would be able to do a replay attack inside that 5 sec window only.

- With both discharge macaroons in hand, we take the original "access macaroon", bind both DMs to it, and finally send it along with the request to the resource we wanted to interact with.

That way an attacker would need to get a hold of both the user discharge and the policy discharge macaroons if I understand correctly.

This is a bit more complex and would require, depending on the expiry time of the "policy discharge macaroons", several API requests per each effective resource request, which might be a valid trade off if you care about the increased security a short lived macaroon gives you. Otherwise maybe the first approach is simpler and even though it might have a longer attack window, maybe in particular use cases this is not a problem. Then again the first approach is going back to cookies pretty much, so not sure if it's worth it.

Am I missing something? are my assumptions sane or am I just making this more complicated than it needs to be? 

Maybe there's a third way I'm not seeing here?

In any case, I appreciate any feedback! 

Akram

[Robert Escriva]

There are many more things you could do. Imagine deriving the secret for the user discharge macaroon from the user's password. Now the user can "login" locally to create a discharge macaroon with no potential leaks to MITM with the auth server. 

There are many other things to think about. In the end you are trading the amount of code in the verifier with the number of macaroons. And you are trading number of requests against likelihood of macaroons falling into bad hands. Then there is a question of how general a discharge should be. Should you have a discharge for us...@example.com, or should it be coupled with a random nonce used in the third party caveat to prevent leaks. 

There is so much to consider and everyone's still exploring. 

-Robert 

Sent from mobile; please excuse my brevity 

--
You received this message because you are subscribed to the Google Groups "Macaroons" group.
To unsubscribe from this group and stop receiving emails from it, send an email to macaroons+...@googlegroups.com.
To post to this group, send email to maca...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/macaroons/fb68e116-e8f7-4557-b82c-fff4b01e0ed1%40googlegroups.com.

[Akram Shehadi]

Those are some very interesting ideas!

Thanks for all the feedback.

Hopefully we'll see more and more people getting involved in this.

Cheers,

Akram