Hacker News Reader

Comment by winrid | Hacker News Reader

ISO any articles/documents related to scaling access control, for example if you have 100_000 users and 90k of them have access to some resource, but 10k do not, and you can't use groups that your customer knows about. Obvious solutions are "where allowed_user_ids = ... big list" or "where disallowed_user_ids NE ... small list"; the latter not a solution as you can't optimize this query with a normal tree-like index.

I suppose you could use some sort of bloom filter, or create/maintain groups behind the scenes somehow, but haven't seen many articles cover this.

View on HN

Oso engineer here. It's a good question -- definitely a dearth of content about this topic.

Like pphysch said, using RBAC generally gets you 90% or more of the way there on this, and a good intro to this concept is the Tailscale post: https://tailscale.com/blog/rbac-like-it-was-meant-to-be/

In most cases (even with many 100s of thousands or millions of users), there are far fewer _roles_. So you can generally answer the question of "which users can access this resource" by answering the questions "which roles can access this resource", and "which users have those roles". If you're using SQL to store roles and role assignments, your query for all users becomes:

    select * from users
    join user_roles on user_roles.user_id = users.id
    where user_roles.role_id in [... small list ...]

This can get tricky if you have 100s of thousands or millions of _roles_, and each of those roles can be dynamically assigned access to a significant percentage of your resources. But that might suggest you're structuring roles incorrectly in the first place (and you should be using fewer roles with more users per role).

All that being said, I think there's definitely more to be written here. Keep a lookout -- we might do some more writing about the topic.

> This can get tricky if you have 100s of thousands or millions of _roles_

If you use something like a bitmap index (e.g. Roaring Bitmaps), you can easily manage roles in-line on each user row if the role membership is typically sparse.

You can still maintain a separate Roles table as a canonical reference, but you would no longer need to join on it to determine who has what.

Out of curiosity, is there any kind of support for bitmaps in mainstream databases?

You can just roll it yourself in the application logic and store as a raw binary column.

This all assuming you don't need to make queries along the axis of "give me every user with role X".

Yes and no: there is no bitmap SQL type, but at least MSSQL packs multiple BIT-columns on the same table into the same word/byte and then uses bit tests for filtering. I suspect Oracle and Postgresql can do the same, but I don't know for sure.

I'm a little confused, does Oso employ row level security? If not, why not?

I explicitly said can't use roles (groups). :)

But yeah, that's the cleanest way to go, if you can.

Can you encrypt the role names for when it might be seen by a user?

Disclosure: I'm a cofounder of Authzed, a YC company building a permissions database[0] inspired by Google's Zanzibar paper[1].

This is actually a really hard problem and depends on the systems with which you are integrating. We call this problem "ACL filtering"[2] and there are two general strategies: pre and post filtering.

We have a blog post[3] describing our API for pre-filtering which can stream results that you can then use build a SQL query or data-structures like bloom filters/bitmaps. We currently have a proposal on GitHub[4] for an extension to that strategy adding a denormalization/caching layer (which is applying a similar strategy to the Leopard Indexing system internally at Google).

You might also be surprised at the performance you can achieve with post-filtering by building an iterator in your programming language of choice that will batch together permission checks and amortize the cost of filtering those results from the set of all results that you pull out of your database.

Additionally, if you're interested deeper database specific integrations, there are hooks into various components such as Postgres's Row Level Security, but that typically means eschewing a cloud service to operate your database for you (e.g. RDS) so that you can install your own plugins.

[0]: https://github.com/authzed/spicedb

[1]: https://authzed.com/blog/what-is-zanzibar/

[2]: https://docs.authzed.com/reference/glossary#acl-filtering

[3]: https://authzed.com/blog/acl-filtering-in-authzed/

[4]: https://github.com/authzed/spicedb/issues/207

I haven’t seen any Postgres plugins that extend RLS but very interested. Any links?

"RBAC Like It Was Meant To Be" https://tailscale.com/blog/rbac-like-it-was-meant-to-be/

The key insight is to define policies as purely virtual; a policy never refers to real users or real resources. Instead, it refers to virtual users (via "roles") or virtual resources (via "tags"), which can then be associated with real users/resources without modifying the policy.

Interesting, this neatly divides authorization checks into three-ish questions: 1. What roles are assigned to the user?, 2. What tags are assigned to the resource?, 3. Do the answers to 1 and 2 overlap? Each of which could have a cached denormalized index and should compress well.

Yeah I've built this kind of stuff before, was just hoping for some interesting information on the data access side - when you can't use tags/roles. But I always push for this approach when I can.

I think I'm missing something. Are you reframing your original constraint, that you can't use groups that your customer knows about, as you can't use tags/roles? You can certainly use tags/roles that your customer doesn't know about. This is a common issue in something like healthcare data security.

Sorry, when I said groups I meant can't use tags/roles as well. Conceptually they are the same to me, sorry for the confusion.

It also wouldn't work in the scenarios I've mentioned in other comments.

Why can't you use tags/roles on the data access side?

Could be a lot of reasons, but what if you have millions of tags/roles, and a user has a large subset of those roles? This actually happened at one job...

What if you sell reporting on location based data with access control, and customers want fine grain control on who sees what? Then you also can't always use groups. Example: I'm a Healthcare provider with 15k locations. Manager X is responsible for 5k locations, so when we create reports we filter all the data by those 5k locations first. Same with viewing any data in the product.

Just curious how others approached this. You could obviously do grouping somehow.

I have a similar use case but even worse. Rather than locations users are given access directly to the consumer/patient and the each resource is for some consumer x. So any access not just reporting we have to filter by a huge list of accessible consumers which sometimes can be as small as 50 but large as 100K+ which is massive challenge to scale.

We can obviously manage this still with careful optimization but I'm not sure if this is kind unlimitedly scalable say for 1M+ consumers. I wonder if this can only be handled by reframing business requirements (like location as you are using) or someone has better design/ideas.

Yeah, same problem, but I don't think I ever saw more than 50k resources per user.

I think the best solution potentially is to have the system monitor the "whale" users and have a special case where you turn their list of resources into a single group/tag behind the scenes and add this single identifier to all the relevant objects. It'd be hell to get right and keep consistent but it'd be fast.

It's hard to name things. There's consumers whose data the system records, by resource I meant the data of the consumer (bulk of the system) and obviously users.

The users are authorized on consumer (a set of consumer + a set of roles or action they can do). We have been able to move the role aspect to app layer very cheaply. User A is doing X say running a report, we know role R is needed for it, we then ask the system run the report for the customers user A has access to it with index on consumer for all resources in system allowing fast query. But if your consumer list is too large the efficiency falls.

We can't make auto groups at system level because adding a group column in resource level and updating would be too expensive. There's no just large grouping. Some users say have access to consumer 1..100K where another has random 100K from 1..1M.

Have separate admin-facing and user-facing RBAC. Don't try to force them under one roof. You have an organization, and a product. Both have different authorization needs (many products don't have any), even if they may use the same authentication mechanism.

I tend to keep admin RBAC simple and group-oriented. It's mostly for direct data access permissions (per table, etc), but can add others too. Different groups for different departments. Mainly for internal CRUD apps at first (e.g. Django Admin).

OTOH, User-facing RBAC is project-oriented and uses the virtual policy system described by Tailscale. The users themselves, in a project-manager role, can manage their own policies, memberships, and resources tags. I like to provide sane defaults and support for modifying policies should they even need it. Importantly, one user can have membership in different projects with different roles.

You'd create a project with the 15K resources, add the customer to it in a manager role, and then they choose the policies, tags, and roles to make it work for their organization.

Ofc, admins can also be users. Simply create one or more projects for internal use.

Seconded! I can get to a million authentication-related articles and services, but "authorization theory" seems to be very hard to find. (It doesn't help that the big text box in the sky treats the two words as somewhat interchangeable.)

There's the paper on Google's Zanzibar:

https://research.google/pubs/pub48190/

"This paper presents the design, implementation, and deployment of Zanzibar, a global system for storing and evaluating access control lists. Zanzibar provides a uniform data model and configuration language for expressing a wide range of access control policies from hundreds of client services at Google, including Calendar, Cloud, Drive, Maps, Photos, and YouTube. Its authorization decisions respect causal ordering of user actions and thus provide external consistency amid changes to access control lists and object contents. Zanzibar scales to trillions of access control lists and millions of authorization requests per second to support services used by billions of people. It has maintained 95th-percentile latency of less than 10 milliseconds and availability of greater than 99.999% over 3 years of production use."

You could use hashed token claims to encode a role or other identifying info.

If you use a webhook you don't have to worry about this, since the user doesn't get to see what you forward as the authorization claims payload. But if you're using a JWT to hold state, since JWT's are publicly viewable it has to be non-obvious and non-deterministic.

IE, something like:

  { "user_id": 5316, "$2a$09$ckHFIEsR8Sjveh1ynOLKguynRDGjEfMCZz0vsUk/Jtm/cW1SxibaK": "$2a$09$pCyjFN6perhHNspS1NFj0eScZ4.ZlOzzPMXhoMrYVmNLMx3MvXdYK" }

Where in the example above, the key is "X-User-Role" and the value is "moderator" that have been bcrypt hashed.

Probably you would want to choose more obscure/uncommon words. I'm not familiar with the details of hashing but it seems like a good idea.

Then you can attach the role (or other identifying) metadata to each request in a way that isn't immediately obvious what it's for.

Disclaimer: I'm not a security expert, possible (probable?) there is a gaping hole in this and it's an awful idea.

Maybe I'm not understanding. But in a JWT you can verify the signature from when you originally signed that user's JWT. So even if I change some data in my JWT, on the backend it will not match the signature. So just reject if it doesn't match, say someone change permission:read to permission:admin

https://jwt.io/

It's not about verification of the jwt, it's about hiding the roles from the user.

The question isn't about encoding role information. It's about query / data retrieval optimization.

Roles are an approach towards query optimization, but the question placed a constraint on the user not knowing about them. Encoding the role information so it is not visible to the user is a potential solution.

By not knowing about them I mean that the customer/company never defines the roles as part of onboarding, etc. In this case they define the restrictions per-user.

> Obvious solutions are "where allowed_user_ids = ... big list" or "where disallowed_user_ids NE ... small list"; the latter not a solution as you can't optimize this query with a normal tree-like index.

This is not exactly an answer but it's worth remembering that the lower the selectivity of a condition is the more likely it'll turn out that brute force and ignorance will actually work out better - loading data in batches and filtering out the ones that are disallowed by a secondary positive index lookup (assuming you've pre-materialised your 'is disallowed' list) could easily turn out to be a better option for a lot of cases than trying to be more clever than that.

The more general question is of course rather more complicated and interesting, but other people already had better answers than I do there in other replies.

Sounds to me like you can have a huge table of authorizations and compile it silently into a list of roles whenever the contents of that table are modified. This recompilation step may be comparatively slow, but it needs to be executed quite seldom and the roles/groups you end up with should small in number and be quite easy to index.

> you can't use groups that your customer knows about

I don't understand why you can't use groups to organize access control. Is this a customer-enforced restriction? Or a technical one?

Sometimes it's customer enforced. Just based on various places I've worked.

One place for example sold location-based software, so users could have access to say 10k out of 100k locations, but those locations might not always be next to each other. Data would be stored with a location id, and to do things like "show the average star rating for the locations this user has access to", we'd do "aggregate star rating where location id IN [....]"

Oh okay, so you can store authorization data in a table mapping user_ids to location_ids right? Then instead of using `IN (big_list)` (which can't use indexes) you join on the mapping table (which can use indexes). Something like

    CREATE TABLE locations (
        location_id INT PRIMARY KEY,
        rating INT
    );

    CREATE TABLE authorized_locations (
        user_id INT REFERENCES users (user_id),
        location_id INT REFERENCES locations (location_id)
    );
    CREATE INDEX authorized_locations_user_id_idx ON authorized_locations (user_id);
    CREATE INDEX authorized_locations_location_id_idx ON authorized_locations (location_id);

    SELECT AVG(rating) FROM locations JOIN authorized_locations USING (location_id) WHERE user_id = $1;

In (list) can use an index just fine in most databases. It's "not equal" that has trouble.

A better example would be:

Product {LocationID, Rating} User{id} UserLocations{UserID, locationID)

However, let's say you have an architecture where you have 100s of these "product" tables, since every piece of the app restricts access by location. So not only do you have Product but maybe you have FormResult{LocationID}, Feedback{LocationID} etc.

So for a service to find out what a user has access to, first they call the User service to get a list of locations, and then they pass the big list of ids to their own DB, whatever that DB is.

I guess this is one case where a monolith and good ol SQL would win. :)

Wasn't LDAP developed exactly for that?

Yeah but the question is scaling queries against large data sets with access control, LDAP would only provide the meta data.

Reply on news.ycombinator.com