first party caveats are not always checked by verifier

[rogpeppe]

As far as I can tell, the following script should print:

 checked conditions: ['splendid', 'wonderful', 'top of the world']

but it actually prints:

checked conditions: ['top of the world', 'wonderful']

One first party caveat does not appear to be checked.

import macaroons
m1 = macaroons.create("", "root-key", "root-id")
m1 = m1.add_first_party_caveat("wonderful")
m1 = m1.add_third_party_caveat("bob", "bob-caveat-root-key", "bob-is-great")

m2 = macaroons.create("bob", "bob-caveat-root-key", "bob-is-great")
m2 = m2.add_first_party_caveat("splendid")

m3 = macaroons.create("bob", "bob-caveat-root-key", "bob-is-great")
m3 = m3.add_first_party_caveat("top of the world")

m2 = m1.prepare_for_request(m2)
m3 = m1.prepare_for_request(m3)
checked = []
def check(cond):
	checked.append(cond)
	return True
v = macaroons.Verifier()
v.satisfy_general(check)
v.verify(m1, "root-key", [m2, m3])
checked.sort()
print('checked conditions: {}'.format(checked))

[rescrv]

Absent a sort issue ('w' after 't'), you're right. Good catch!

I pushed a potential fix, and I'd appreciate your comments on whether I got the extent of the problem accurately characterized in the commit message. I see potential false negative and timing channels. Is there anything else I missed?

[rogpeppe]

Oops, I hadn't caught the fact that there were two discharge macaroons with the same id (really, my test name ("single third party caveat with two discharges") should've tipped me off, but it was late in the day...)

On further reflection, I'm not sure that my expectations in the test were correct, although I'm not sure either that the verification should have succeeded.

My current thinking is before any caveat checking takes place, the macaroon signature should be verified and also that the verifier should check that each discharge macaroon is used exactly once.

Checking that each discharge is used exactly once serves two purposes: it makes it trivial to check for recursive discharge use (a use count array could replace the tree array used by macaroon_verify_inner, I think, which would make the code a little simpler, I think) and it means that the caller can be sure that all the first party caveats present in the macaroons have been checked (not true currently, even with that latest fix for this issue), which is useful intuitively when inspecting macaroons (it caught me out) and potentially for inferring information from caveat checks too.

I'm that first party caveat checking needs to be done when the signature is invalid, because first party caveat checking is potentially expensive (think online revocation checks), and we probably don't want attackers to be able to invoke arbitrary first party caveat checks with no valid macaroon at all. I guess the question there is: is there some way that an attacker could make use of the information that a macaroon is potentially valid even when its caveats fail?

So I'd suggest doing all the signature and use-count checking and then checking all the first party caveats.

So with respect to this test, I'm not sure that the fix is quite right - your code was actually correct according to the specification in the paper (which only requires that there exists at least one discharge macaroon that can be used for discharge).

What do you think?

[rescrv]

I think the code change I made is for the better, even if it's not the issue you were pointing out. It allows one to do more complex proof trees without having to do client-side interpretation of which macaroons to pass along. It's totally valid for a discharge macaroon to be used multiple times, and we shouldn't exclude this behavior.

As for invoking caveat checks, an attacker who intercepts a macaroon can always add a caveat that passes the signature check. So it's only totally bogus macaroons that would be at risk for servers to invoke caveat verifiers without a valid signature.

Can you elaborate on the inspection point?

[rogpeppe]

BTW I'd misread your code - I'd skim read it and assumed it was checking that all discharges were valid, but it's actually checking that at least one discharge is valid.

It's totally valid for a discharge macaroon to be used multiple times, and we shouldn't exclude this behavior.

Can you elaborate on a situation where this might be appropriate?

As for invoking caveat checks, an attacker who intercepts a macaroon can always add a caveat that passes the signature check.

That depends on when they intercept it. If they intercept it as part of the request, that's not the case (all discharge macaroons are bound to the primary's signature at that point, so no new caveats can be added). If an attacker has stolen an undischarged macaroon along with its discharges, you've got a serious security problem - I don't think we can guard against that in the macaroon library.

So it's only totally bogus macaroons that would be at risk for servers to invoke caveat verifiers without a valid signature.

Everyone in the world can make a bogus macaroon. Only attackers that have stolen your bearer credentials can obtain a valid unbound macaroon with its discharges. There's a big difference in potential attacker count there.

Can you elaborate on the inspection point?

It's not uncommon to inspect first party caveats to infer some information about the security properties of the macaroon. A common one, for example, is to infer the expiration date of the macaroon from the first party caveat that specifies the earliest expiration time (we use that for macaroon garbage collection). It's nice if this inferred information is accurate.

Manual inspection is also not uncommon - it's a nice property to be able to see a set of macaroons that have been used to authorize a request (for example in a server log) and be sure that all the listed caveats have succeeded.