Change the format of access tokens away from macaroons

[richvdh]

Some history might be helpful here:

Access tokens were originally turned into macaroons back in 2015 (in #229 and #256); however, it has always been the case that as well as satisfying the caveats on the macaroons, the macaroon has to be stored in the database.

The fact that the access token has to be in the database meant that much of the power of macaroons was unusable (in particular, the ability to add third-party caveats), and much of the security they offer was redundant.

The spec, as far as I can recall, never required that access tokens be macaroons; matrix-org/matrix-spec-proposals#1204 discussed changing this but concluded that they should be left specified as opaque strings.

#4374 changed the behaviour of synapse again so that the macaroons were never validated (though the token still had to be in the database). The logic behind that change was somewhat tied up in CVE-2019-5885 (#4664).

Once #4374 landed, the macaroonness of the access tokens was completely redundant, and they could equally well be any cryptographically-secure random string. This PR therefore brings us back full circle.

The reasons for switching away from macaroons include:

• they are over 300 bytes long, which is a significant overhead when they have
  to be attached to every single request.
• generating macaroons (in particular, signing them) costs valuable CPU cycles.
• it's generally confusing.

---

The format used in this PR changed a bit as we worked on it. We ended up with:

syt_<base64_localpart>_<20 random characters>_<base62 crc>

... mostly inspired by https://github.blog/2021-04-05-behind-githubs-new-authentication-token-formats.

Whereas access tokens were around 260 bytes before (depending on the length of your localpart and domain), they will now be around 45 bytes (depending on the length of your localpart).

[richvdh]

I'm going to shelve this for now. It turns out we have some lua in our haproxy config which relies on access tokens looking like macaroons. I'm not sure the advantages of this change are worth the work.

[richvdh]

It turns out we have some lua in our haproxy config which relies on access tokens looking like macaroons.

this is no longer true, so we could revisit this I think.

[erikjohnston]

It turns out we have some lua in our haproxy config which relies on access tokens looking like macaroons.

this is no longer true, so we could revisit this I think.

I wonder if we should still encode the user ID in the tokens somehow, in a way that haproxy can efficiently read? A couple of options here are:

• Base64 encode the user ID (or localpart) then prepend the random string (after a deliminator). Then in haproxy we can use the field extractor to get something we can load balance on, and b64dec to get the actual user ID.
• Hash the user ID, base64, truncate to ten bytes, then add the random string after. In haproxy we can then simply load balance on the first ten bytes (though we wouldn't be able to get the user ID).

[richvdh]

yeah, that would probably make some sense.

Another thought is that we should probably take the opportunity to do something like https://github.blog/2021-04-05-behind-githubs-new-authentication-token-formats/.

[erikjohnston]

(I've taken this out of the review queue as Rich is planning on changing the format to incorporate some of the ideas above).

For a concrete suggestion: I think something like: syt_<base64 local part>_<random string> would work, it a) has a prefix to make it easily detectable and b) encodes the user local part in a way that can be extracted by haproxy (and anything else that can split by fields).

[callahad]

has a prefix to make it easily detectable

There's an RFC for this... let me dig it up

[erikjohnston]

I think this LGTM, modulo anything that Dan's RFC throws up.

Do we want to run this past the ops team to make sure we're not missing anything they'd like? (While we're here)

[erikjohnston]

Why are we using base62 for the crc? Is that just how its typically done?

[richvdh]

cargo-culted from https://github.blog/2021-04-05-behind-githubs-new-authentication-token-formats/#checksum

[erikjohnston]

wfm

[richvdh]

a thought occurs. The use of base64 here means that access tokens will have to be correctly url-encoded when used in a query param.

maybe we should use a url-safe base64 encoding.

[erikjohnston]

Oh, hmm. Good point.

I had a quick look at haproxy support and it looks like b64dec only handles standard padded base64 (2.4 will have support for padded url safe base64 decoding). Don't that is a huge concern though, since I think conversion is relatively easy with simple string replacement?

[richvdh]

of course, we could just say that only people with spec-compliant mxids are allowed to use matrix, so it doesn't need encoding at all 😈

[erikjohnston]

I love it :D

[michaelkaye]

I don't think this needs to particularly influence us; we should be deprecating and removing GET based access token use, as it's just a bad idea for http access logs outside of synapse, perhaps the effort of ensuring your access tokens are urlencoded correctly will push developers towards doing the right thing.

[richvdh]

I think that's fair. it's really not that hard to do it right, even from a shell command.

[callahad]

Okay, I was thinking of RFC8959 which defines secret-token:... where the path is alphanumeric plus -._~!$&'()*+,;=:@, and arbitrary percent-encoded bytes.

I thought GH / Stripe / Slack were switching to that, but they're not. They're just doing their own thing.

[callahad]

The GitHub / Slack / Stripe consensus seems to be:

• Prefixes which encode company + token type (e.g., ghp vs gho for GitHub Personal access tokens vs GitHub OAuth access token)
• Separating the prefix with a _ to avoid accidental collisions with randomly generated strings (SHAs, etc.)

GitHub also uses the last 6 characters of their tokens to embed a base62-encoded CRC32 checksum of the token

Their tokens are 40 characters long: prefix (3) + _ + token (30) + checksum (6). The token itself is case-sensitive alphanumeric. 30 characters of that yields 178 bits of entropy.

[richvdh]

30 characters of that yields 178 bits of entropy.

for comparison: our 20 characters from a 52-character range gives 6.5*20 = 130 bits of entropy, though the attacker also has to match it up with the right localpart.

[callahad]

I didn't actually see an approving review happen here? Did I miss it?

[babolivier]

@erikjohnston said:

I think this LGTM, modulo anything that Dan's RFC throws up.

Though he didn't actually tick "approve".

[richvdh]

what @babolivier said. I didn't consider it worth disturbing people again since everyone seemed to be in agreement. Sorry if that was presumptuous.

[callahad]

Had this gone back into the review queue, I think I would've raised the following queries:

• The inclusion of b64local makes our tokens variable length, are we OK with that?
• The base62 vocabulary we're using is in a different order than just base64 without the final two characters, are we OK with that? (b64 uses A-Za-z0-9+/, our b62 uses 0-9A-Za-z)
• We're using unpadded base64, but haproxy's b64dec expects proper padding, are we OK with that?
• Are we sure we're comfortable baking user identifiers into the token itself?
  • Is that a privacy risk? (e.g., inadvertently logging identifiable information)
  • Is that a DoS risk? (since similar local parts will encode similarly, and we'd presumably use these to direct traffic to workers per Erik's comment?)

Also, isn't the entropy 114 bits, not 130? math.log2(52**20)

[callahad]

If I'm reading the code correctly, the regex to match a Synapse Access Token is:

syt_[a-zA-Z0-9+/]+_[a-zA-Z]{20}_[a-zA-Z0-9]{6}

The regex to match a GitHub Personal Access Token is

ghp_[a-zA-Z0-9]{36,}

...is the complexity in our format warranted?

[richvdh]

Had this gone back into the review queue, I think I would've raised the following queries:

Most of these came up in online discussion as well. Thanks for raising them again, not least as a reminder to me to record the conclusions.

• The inclusion of b64local makes our tokens variable length, are we OK with that?

They were variable length before and it was never a problem...

• The base62 vocabulary we're using is in a different order than just base64 without the final two characters, are we OK with that? (b64 uses A-Za-z0-9+/, our b62 uses 0-9A-Za-z)

I couldn't find any sort of convention for b62 alphabets, but most implementations I found with googling used that alphabet. I don't think it matters too much.

• We're using unpadded base64, but haproxy's b64dec expects proper padding, are we OK with that?

hrrrm, good question. I'd forgotten to address that. I think you can go from unpadded to padded base64 with a couple of string manipulations. Erik said "Don't that is a huge concern though, since I think conversion is relatively easy with simple string replacement?", though I'm not sure how you would actually do so,

• Are we sure we're comfortable baking user identifiers into the token itself?
  • Is that a privacy risk? (e.g., inadvertently logging identifiable information)

Again, we've always done it before. I think if you're logging access tokens, you have bigger problems than the identifiable information.

• Is that a DoS risk? (since similar local parts will encode similarly, and we'd presumably use these to direct traffic to workers per Erik's comment?)

I'm not quite sure what sort of attack you're envisaging here. Similar local parts will encode similarly, but likely we would use that as a hash key for a sticky routing table, rather than forcing particular local parts to route to particular backends.

Also, isn't the entropy 114 bits, not 130? math.log2(52**20)

errrr yes. log2(52**20) = 20 * log2(52) =~ 20 * 5.7 = 114. I don't know where I got 6.5 from before.

If I'm reading the code correctly, the regex to match a Synapse Access Token is:

syt_[a-zA-Z0-9+/]+_[a-zA-Z]{20}_[a-zA-Z0-9]{6}

Or possibly syt_[a-zA-Z0-9+/_]+. What's your objective here?

[callahad]

• We're using unpadded base64, but haproxy's b64dec expects proper padding, are we OK with that?

hrrrm, good question. I'd forgotten to address that. I think you can go from unpadded to padded base64 with a couple of string manipulations. Erik said "Don't that is a huge concern though, since I think conversion is relatively easy with simple string replacement?", though I'm not sure how you would actually do so,

I understood Erik's comment to mean translating between urlsafe and normal base64 "with a couple of string manipulations", in the context of haproxy <2.4 not supporting the urlsafe variant

If I'm reading the code correctly, the regex to match a Synapse Access Token is:

syt_[a-zA-Z0-9+/]+_[a-zA-Z]{20}_[a-zA-Z0-9]{6}

Or possibly syt_[a-zA-Z0-9+/_]+. What's your objective here?

To unambiguously identify access tokens, e.g., to participate in programs like GitHub's Secret Scanning or to implement our own audits

[erikjohnston]

• We're using unpadded base64, but haproxy's b64dec expects proper padding, are we OK with that?

hrrrm, good question. I'd forgotten to address that. I think you can go from unpadded to padded base64 with a couple of string manipulations. Erik said "Don't that is a huge concern though, since I think conversion is relatively easy with simple string replacement?", though I'm not sure how you would actually do so,

I understood Erik's comment to mean translating between urlsafe and normal base64 "with a couple of string manipulations", in the context of haproxy <2.4 not supporting the urlsafe variant

FWIW the main use case is to route requests, where you don't need to decode the user ID and can just route based on the second field of the access token.

If I'm reading the code correctly, the regex to match a Synapse Access Token is:

syt_[a-zA-Z0-9+/]+_[a-zA-Z]{20}_[a-zA-Z0-9]{6}

Or possibly syt_[a-zA-Z0-9+/_]+. What's your objective here?

To unambiguously identify access tokens, e.g., to participate in programs like GitHub's Secret Scanning or to implement our own audits

If the goal is to provide a regex that is going to have the least false positives then having a more complicated regex will help that? It's going to be very rare for anyone to want to parse one of these tokens, so I don't think the complexity of the regex (in terms of number of characters) is a huge concern here.

[callahad]

Works for me 👍

[erikjohnston]

(Those were all good Qs though)

[richvdh]

FWIW the main use case is to route requests, where you don't need to decode the user ID and can just route based on the second field of the access token.

in which case maybe we should just have used a hash and saved ourselves the bother of worrying about whether it is ok to encode the localpart in the access token 😇

However, I'm very much inclined to stick with what we have rather than agonise about it too much. (Though yes, all good questions worth discussing)