# Macaroon MAC Chaining

There's a cool technique I learned about recently: MAC chaining to allow for
append-only authentication tickets. This technique is central to the "Macaroon"
paper[1] which uses it as the basis of a pretty cool authentication system, but
it's neat enough that I want to write about it on its own.

A very common way to implement authentication tickets is like this: you have a
client C, an authentication server A, and a server S. The client contacts the
authentication server in some pleasing way to log in:

  C -> A: login as me@domain, password foo

and the authentication server makes a login ticket, which probably contains the
user's ID and a timestamp, and maybe some other stuff. It then attaches an
authenticator, computed using some secret key Ka, to the ticket so that it can
be validated later:

  A: t = id + timestamp + other stuff...
  A: t' = t + MAC(Ka, t)
  A -> C: t

Now, C can send the resulting ticket to S, and as long as S has Ka as well, S
can verify that t' is a valid ticket and pull out the user id, timestamp, and
other stuff. So far so normal.

## Scopes

If the client wants to only authenticate for a certain purpose (like "send
email" or whatever), they have to ask A to include that purpose in the ticket:

  C -> A: login as me@domain, password foo, scopes send-email

and then A has to include those scopes in the ticket. Each time C wants a ticket
with different scopes, like to talk to a different server S', C has to first
re-authenticate to A to get a new ticket. If there are a lot of such servers,
that could get pretty burdensome on A.

## Client Scoping

There's a trick we can do though. Normally, the client can't take an existing
ticket with no scopes:

  t = id + timestamp + other stuff...
  t' = t + MAC(Ka, t)

and modify it to add scopes, since it doesn't have Ka, and obviously the client
cannot have Ka, or it'd be able to just forge tickets for any other user. We
also can't just do this:

  t'' = t' + scopes send-email

because then S (or anyone else) can simply strip off the "scopes send-email"
part and have the original, unconstrained ticket. We need to somehow mutate the
original ticket in a way that can't be undone by someone without Ka.

Here's the gimmick: we can treat MAC(Ka, t) as a new key Kt! The client has[1]:

  t = id + timestamp + other stuff...
  t' = t + MAC(Ka, t)

and so it can pretty easily compute:

  Kt = MAC(Ka, t)    # by pulling it out of t'
  t'' = t + scopes send-email + MAC(Kt, scopes send-email)

which produces an object ultimately containing:

  id + timestamp + other stuff... + scopes send-email
  + MAC(Kt, scopes send-email)

The new MAC is derived from both MAC(Ka, t), which is known to the client and
can be computed by anyone with Ka, and from "scopes send-email", which is new
data the client added. Anyone who tampers with t will change the computed value of
MAC(Ka, t), which will in turn make MAC(Kt, scopes send-email) invalid, and a
client C' that has the resulting t'' *can't re-derive the original token*
because it doesn't have the value of MAC(Ka, t) any more! Any server with Ka can
re-compute what that original MAC should have been, but any bearer of the token
doesn't get it.


## Downward Scopes Only

There's one key design constraint here: whatever scopes exist can *only* be
allowed to constrain a ticket, never to add new capabilites to it, since any
bearer of the ticket can append any new data they want to it and produce a valid
new ticket! This requires careful design of the auth system; the initial ticket
has to be "all-powerful" with constraints stapled onto it afterwards.

That means you can repeat the extension process above a bunch of times and end
up with a ticket like this, for a hypothetical translation service:

  user me@domain.com, timestamp whatever, other stuff
  + can only read or write documents
  + can only read this specific document
  + can only write this other specific document

and then servers, which have Ka shared with A, can validate the resulting ticket
by rebuilding what the chain of authenticators should be and verifying that the
final MAC on the ticket is still good. Slick!

If you want to read more, the full Macaroons paper is here:

=> https://research.google/pubs/pub41892/

[1]: In real life you would use AEAD probably because you don't want people
     reading the inside of your tickets, and then the client would strip the
     AEAD tag off and reuse it as a key. Same idea.