User Permission Encoding

March 21, 2006 7:03 AM

Managing User Permissions: I'm reworking an existing system that has a fairly granular permission system and am looking to make it easier to use. At the risk of sounding like a complete clown¹, I've recently seen at least one OS permission system where permissions are encoded with ids that are (I think) all powers of 2, which allows the system to discern whether a user has access to a given permission from the sum of the user's permission ids. Can someone explain how this works?

My question is entirely based on how I perceived the system works, so the details may be different (and that would be useful to know). Because I don't even know how to talk about this in simple labels, it's hard to Google.

1. Vs. the sub-100% clown I normally sound like.

posted by yerfatma to technology (16 comments total)

What OS are you talking about?
posted by popechunk at 7:07 AM on March 21, 2006

Oh, sorry, this isn't in an OS at all, I'm working on a web app, but I'd like to steal the idea. I'm guessing what I saw was Windows-related, probably on TheOldNewThing.
posted by yerfatma at 7:14 AM on March 21, 2006

Bit Vectors
posted by falconred at 7:17 AM on March 21, 2006

I have no idea what OS or security model you are talking about. However, maybe the permissions are implemented using bitwise operations. That would be consistent with the whole "powers of 2" thing and is a pretty typical technique in C programming.

You have a set of bits: 10000110. Usually that is stored in an integer but you don't ever really care about the decimal value, just the bits. Using bitwise operations you can pick out individual bits through combinations of ORs, ANDs, and XORs.

The reason this is consistent with your "sums of powers of 2" observation is that the above bit vector would be described as an integer as follows: 2⁷ + 2² + 2¹ = 134. However, that exact decimal value is (usually) of little importance.
posted by mto at 7:21 AM on March 21, 2006

There are two popular permission systems, the flag system and the access control list systems.

Lets restrict the domain of discussion to files so that the language is concrete, since almost anything can be secured with these techniques.

The ACL system is what windows NT and many advanced permission systems on unix use. One can say "user x is a member of group y, and this file can be accessed by everyone in group y." You can apply any set of users and groups to any file. Very flexible. very modern.

The flag system is what unix uses by default. Each file has a small bit field stored in a file's file system entry. This bit-field is what you describe, basically. In the simple version (no sticky bit, etc), there are 9 positions in the bit field, corresponding to granting various read/write/execute permissions. Along with the bit field, there is a user-id and a group-id in the file table. The first three bits control read/write/execute for the user-id in the file. the next three control access for the group-id. The last three are for global access -- everyone.

The execute bit is overloaded, so that when you apply to directories, you allow switching into the directory, whereas when you set it on files, you are indicating the shell should try and execute the file.

Bit-fields are just numbers where the bits are relevant. You need to know how to count in binary. Starting with granting no access to anyone:

000 000 000 : all the bits zero

110 000 000 : grant r/w to the owner of the file. note that if we represent this as three numbers from zero to 7, we get 600. the command `chmod 600 file.txt` would set r/w access to owner of file.

110 000 100 : Now grant read access to everyone in the world (file is on a web server, say) `chmod 604 file.txt`

Pretty basic, and not terribly functional compared to ACLs. Especially ACL's which have an 'obtain from parent'
default mode.
posted by clord at 7:26 AM on March 21, 2006

sorry, missed the description of what each bit position does. Would be relevant to your question.

 u  |  g  |  o
rwx | rwx | rwx

if you want to grant world execute, put a bit in the last position. to grant group write, middle position. owner read, put a bit in first position.

To set the group-id and user-id, use `chown` and `chgrp`

chmod will let you set these bits without counting in binary (or fetching the current value). `chmod g+x file.txt` will set the bit for group execute.
posted by clord at 7:35 AM on March 21, 2006

Unless your web app is very trivial (and will never grow past trivial), start all new projects with something like an ACL.
posted by clord at 7:38 AM on March 21, 2006

The storage of permissions in the system is like an ACL; what I'm really looking to do is query it in an efficient manner without having to invent some involved grammar to sit between the business objects and the database tables that store the permission settings. (I promise I'm not proposing to over-engineer things half as much as the phrase "some involved grammar" might suggest).

The tables in the system look like this:
MODULES: things in the system
RESOURCES: actions that can be performed on the modules (some resources are parents of other resources)
PRIVILEGES: mapping users to resources

That's all there and I don't intend to touch it if I can help it (mainly because it powers other tools outside the scope of this one), but I'd like an easy way to figure out if a given user has access to resource 41, 33 and 66. Are bit vectors not a sensible approach?
posted by yerfatma at 8:00 AM on March 21, 2006

They are an extremely sensible approach. Just use a bitwise AND to figure out if someone has permission to access resources, which is incredibly cheap, computationally.

Pseudocode:
//You have a database table of resources, like this: permission_name, permission_bit
file33, 1
resource41, 2
privilege66, 4

//You have a table with users and the total of their rights, like this: username, permissions

yerfatma, 5
evariste, 0
mathowie, 3

function doSomethingRequiringPrivileges($user, $resource){
if($user & $requestedresource){
allowOperation()
//mathowie is allowed to access file33 and resource41
//yerfatma is allowed to access privilege66 and file33
}else{
throwPermissionsError()
//evariste always gets this
//mathowie gets this if he tries to access privilege66
//yerfatma gets this is he tries to access resource41
}
}
posted by evariste at 10:19 AM on March 21, 2006

So yerfatma & privilege66
=5 & 4
=101 & 100
101
100
=1
=true
yerfatma & resource41
=5 & 2
=101 & 010
101
010
=0
=false
mathowie & resource41
=3 & 2
=011 & 010
011
010
=1
=true
posted by evariste at 10:28 AM on March 21, 2006

clord: you can chown and chgrp in the same command with chown username:groupname file
posted by evariste at 10:35 AM on March 21, 2006

Thanks to everybody in this thread. All the answers were helpful. One last question: do I need to make the permission ids something other than simple increments of 1 for this to work (since 1 + 4 and 2+ 3 both equal 5) or is the only math that matters the bitwise math (I can't count in binary and I'm not willing to take a chance on trying to figure it out)?
posted by yerfatma at 12:52 PM on March 21, 2006

All your permissions are single bits in the bitfield, thus the individual permisisons would be powers of two (1, 2, 4, 8, 16, etc.). You wouldn't use a permission of 3 (since it is not a power of 2) except as a shortcut meaning "both permisison 1 and permisison 2".
posted by kindall at 12:56 PM on March 21, 2006

Sorry to be a doofus, but does "All your permissions are single bits in the bitfield" mean yes or no (to: Do the permission ids need to be powers of 2)?
posted by yerfatma at 1:38 PM on March 21, 2006

yerfatma: yes, they must be powers of 2, by definition.
posted by evariste at 2:25 PM on March 21, 2006

To clarify, probably unnecessarilly:

Powers of 2: Yes. Multiples of 2: No.

1,2,4,8,16,32,64,128 are ok. But not 6,10,12,14,18,30, etc. Why? To avoid collisions. Let's say you used all even numbers as permission id's.

0000001=1 (a)
0000010=2 (b)
0000100=4 (c)
0000110=6 (d)
0001000=8 (e)
0001010=10 (f)
0001100=12 (g)

Let's say you have a user whose permissions add up to 10. What does he have the right to do? Operation f? Operations b and e? Operations c and d?

Now let's use only powers of 2:
0000001=1 (a)
0000010=2 (b)
0000100=4 (c)
0001000=8 (d)
0010000=16 (e)

Absolutely no ambiguity about what a permission total of 10 means: it means permissions b and d.
posted by evariste at 2:37 PM on March 21, 2006