5 ms·

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

• deepsun 5y ago
  Wasn't LDAP developed exactly for that?
  • winrid 5y ago
    Yeah but the question is scaling queries against large data sets with access control, LDAP would only provide the meta data.
• rzzzt 5y ago
  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.)
• tmoertel 5y ago
  There's the paper on Google's Zanzibar: https://research.google/pubs/pub48190/ 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."
• jzelinskie 5y ago
  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 https://github.com/authzed/spicedb [1]: https://authzed.com/blog/what-is-zanzibar/ https://authzed.com/blog/what-is-zanzibar/ [2]: https://docs.authzed.com/reference/glossary#acl-filtering https://docs.authzed.com/reference/glossary#acl-filtering [3]: https://authzed.com/blog/acl-filtering-in-authzed/ https://authzed.com/blog/acl-filtering-in-authzed/ [4]: https://github.com/authzed/spicedb/issues/207 https://github.com/authzed/spicedb/issues/207
  • sa46 5y ago
    I haven’t seen any Postgres plugins that extend RLS but very interested. Any links?
• deleted 5y ago
  [deleted]
• pphysch 5y ago
  "RBAC Like It Was Meant To Be" https://tailscale.com/blog/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.
  • infogulch 5y ago
    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.
  • winrid 5y ago
    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.
    • dragonwriter 5y ago
      Why can't you use tags/roles on the data access side?
      • winrid 5y ago
        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.
• gavinray 5y ago
  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.
  • winrid 5y ago
    The question isn't about encoding role information. It's about query / data retrieval optimization.
    • janto 5y ago
      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.
      • winrid 5y ago
        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.
  • dillondoyle 5y ago
    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/ https://jwt.io/
• gkaemmer 5y ago
  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/ 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.
  • bob1029 5y ago
    > 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.
    • Yoric 5y ago
      Out of curiosity, is there any kind of support for bitmaps in mainstream databases?
      • bob1029 5y ago
        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".
• SPBS 5y ago
  > 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?
  • winrid 5y ago
    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 [....]"
    • SPBS 5y ago
      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;
      • winrid 5y ago
        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. :)
• Yoric 5y ago
  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.
• mst 5y ago
  > 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.