The O(N^3) Authz Problem
A mental model for building authz systems
Every time you sign-in to a website, that website must (1) authenticate that you are who you claim to be and based on that, (2) authorize your interactions.
There are plenty of ways for websites to support authentication (or authn for short). When you login with a password, that password is used to authenticate you as the user associated with that email.
However, if you’re an engineer like me, then you probably spend more time with authorization (authz) systems. Once authn systems are built, they don’t need to change much, but authz systems must be integrated into every new feature. Given that, it’s important to have a good mental model for how authz works.
A good authz system has a surprisingly minimal interface:
In other words, can <Subject> perform <Action> on <Resource>? Let’s break that down:
Subject: who the authenticated end-user or machine (“service account”) is
Resource: what the subject wants to access (e.g. an S3 bucket)
Action: how the subject wants to interact with that resource (e.g. view a bucket)
Together, we refer to this (subject, action, resource) tuple as a permission grant.
This API can then be slotted into a codebase like so:
To motivate our discussion, let’s consider a hypothetical email campaign product. You are testing it out for the bike shop you work at and have drafted a campaign that you want your co-worker, Kyle, to review. To do that, you grant Kyle access to view the campaign:
Subject: email@example.com Action: campaigns.view Resource: campaign_1
After he reviews the campaign, you send it out, and decide to expand this product to the rest of the marketing team! Unfortunately, that’s going to be a daunting task… 💀
The O(N^3) Problem
To invite the entire marketing team, you’ll need to create permission grants for every combination of X subjects (one per member of the marketing team), Y actions (view, comment, edit, etc.), and Z campaigns (all existing campaigns, along with every new one you launch). All together, you’ll have to manage up to O(N^3) permission grants.
Of course, no product actually makes you do all of that. Instead, they extend their authorization model with a couple new concepts.
Instead of managing permissions on individual subjects, it’s easier to manage in bulk with a set of subjects. This is accomplished with a new kind of subject — a Group. Since groups are subjects, you can create permission grants directly on groups:
Subject: firstname.lastname@example.org Action: campaigns.view Resource: campaign_1 --- Subject: email@example.com Action: campaigns.comment Resource: campaign_1 --- Subject: firstname.lastname@example.org Action: campaigns.edit Resource: campaign_1
The set of permissions granted to a user is now the union of permissions granted directly to that user plus the permissions granted to each group the user is a member of. That alone has simplified our management issue from O(N^3) → O(N^2)!
Now logically, you wouldn’t grant edit access without also granting view access. Most services will provide bundles of actions that are commonly used together, called Roles:
CampaignViewer: campaigns.view CampaignReviewer: campaigns.view, campaigns.comment CampaignEditor: campaigns.view, campaigns.comment, campaigns.edit
We can now assign the CampaignEditor role to the marketing team instead of individual actions:
Subject: email@example.com Role: CampaignEditor Resource: campaign_1
We’re now down to an O(N) problem. Unfortunately, we still cannot grant access to all campaigns and instead must create a new grant every time we create a new campaign.
One way to resolve this issue is to expand permission grants to classes of resources. Doing so would allow us to attach the CampaignEditor role to the Campaign resource class, thereby applying to all campaigns.
This works well, but isn’t sufficient for handling parent-child relationships. Consider how our bike shop’s organization will have multiple email campaigns, each with its own list of sent emails:
Let’s say we hire a marketing consultant who helps us write a new campaign. We only want to grant this consultant access to the single campaign they worked on. How do we grant them access to just the emails sent from their campaign?
We could manually grant the consultant the EmailViewer role on each sent email, but this could be thousands of emails.
We can’t use the email resource class, otherwise they would get access to all emails not just those from their campaign.
Instead, the authz system will need to understand the parent-child relationship between campaigns and emails.
To do this, our authz system could be modified to traverse the hierarchy of resources, starting with the queried resource and moving upwards. In other words, the check will succeed if there exists a (subject, action) tuple on the queried resource or any of its parents. To give the consultant access to their campaign and its emails, all we need are these two grants:
Subject: firstname.lastname@example.org Role: CampaignEditor Resource: campaign_1 --- Subject: email@example.com Role: EmailViewer Resource: campaign_1
Going one step further, we can recreate class-based permission grants by inserting a grant on a higher-level resource. For example, we can accomplish our original goal — giving the marketing team access to all campaigns — by granting the corresponding role on the org resource:
Subject: firstname.lastname@example.org Role: CampaignEditor Resource: org_bikes
Anyway, enough with the theory. How would you go about implementing this?
If you are using a SQL database, you could store the permission tuples explicitly granted by users and then join them with other metadata — groups, roles, and the resource hierarchy — at query time:
Case Study: GCP
I switched jobs about a year ago and with that, switched from AWS to GCP. I was pleasantly surprised by how straightforward GCP’s IAM model is — or at least, it is once you grok the model of hierarchal resources that we just discussed. It’s a great example, so let’s walk through it.
Note: GCP uses different terminology than us. For simplicity, I’ll stick with our terms.
Actions (GCP calls them “permissions”) take the form of “service.resource.verb” (e.g. “storage.objects.get”). Each service has a handful of actions which are packaged into pre-defined roles (e.g. “roles/storage.objectViewer“).
Subjects (called "principals", sometimes "members") come in a few kinds including Google accounts, service accounts, and Google Groups.
Resources are modeled in a hierarchy starting from a GCP organization and expanding downwards to the individual resources within each service, such as a GCS bucket.
Now, how do you grant permissions? That is done through IAM Policies which are a list of (role, subject) tuples called Role Bindings. This policy is then attached to a resource. Authz checks will then traverse up this hierarchy to the root — a GCP org — checking for a role binding that offers the queried action.
Putting this all together, you could give an engineering team full access to GCS buckets with the following IAM policy:
Subject: email@example.com RoleBindings: - Role: roles/storage.admin Resource: project|bikes
By granting this IAM policy on a GCP project, engineers will receive admin access to all buckets in the project. With just a single IAM policy, we’ve granted O(N^3) individual permissions. Cool stuff.