Access Control Lists by Nicolai Haehnle -------------------- GiX will of course have to have a proper authorization scheme for users. There are different systems out there, and I don't think the Unix one with users & groups is the best. A system using Access Control Lists together with User IDs allows for much more fine grained permission sets, and should prove to be a lot more flexible. What is an Access Control List (ACL)? ------------------------------------- An ACL consists of a header and an array of ACL entries. Its purpose is to determine whether a calling user has a certain set of rights. Sets of rights are stored in a 32bit (*) bitfield, where a bit 1 means that a certain right is granted, while a bit set to 0 means that this right is not granted. The meaning of the bits themselves depends on the domain of the ACL, though there are many common bits, such as Read and Write permission. One bit is the same for every ACL: bit 0 is the ACL Modify permission. If a user has this bit set in an ACL, he will be allowed to give/withdraw any of the rights he has to/from any of the ACL entries that are listed after the entry which gives him the Access Right permission. This will be covered in detail later. An ACL also has one owning user. This user does not get any of the access rights that are controlled by the ACL, but he can manipulate and even delete the ACL at will, so in effect he can get all the access rights that are controlled by the ACL. (*) maybe one could save memory by reducing this to 16bit. However, as most processors are faster in their native integer size, it's probably more effective to use 32bit here What's in an ACL header? ------------------------ The ACL header contains several pieces of global information about the ACL: - the owner of the ACL (see the section above) - the number of entries in the ACL The following are just ideas; I'm not sure in how far they're important/ whatever... - the domain of the ACL - this would ensure that the meanings of the permission bits are understood correctly (for example, a filesystem ACL might have different meanings for the bits than an ACL controlling GUI resources). However, cases in which this is necessary should be avoided - a describing string for the ACL; while this is IMHO a must at a user level, I doubt that we should burden the kernel with stuff like this... What's in an ACL entry? ----------------------- An ACL entry usually consists of two pieces of information: - WHEN should the entry be applied to the caller - i.e., which user does this entry apply to - WHAT permissions are given. This part contains two bitmasks: o) the masking bitmask - it determines which bits of the permission mask are controlled by this ACL entry o) the permission bitmask - this contains the actual permission information, but it needs to be masked with the masking bitmask. (perm_bitmask & ~mask_bitmask) should be 0, but implementations shouldn't rely on this either Another important type of ACL entry is the "linking" entry which "calls" a sub-ACL. This type of ACL entry contains the following data: - a pointer to the ACL which should be executed - a masking bitmask which is ANDed with the result of the called bitmask, for example to avoid the maintainers of the sub-ACL to subvert security by adding permission bits which were never meant to be there How an ACL is interpreted ------------------------- When reading in an ACL, it is looked at entry by entry in the given order. Any parser needs to keep track of the "requested permission bits", i.e. the permission bits that need to be read in. This is important, because while reading ACLs, the principle QUIT ON FIRST MATCH is used. In other words, once we know that the user should be granted or denied access to a certain operation, we're set, and subsequent attempts to change the permission are ignored (there are exceptions for sub-ACLs though) On each entry, the parser looks at the type of entry first. For standard entry, it tries to match the user ID. If the UID didn't match, it skips to the next ACL entry. However, if it succeeds, it ANDs the entry's masking bitmask with the requested permission bits to get the mask for this entry. It then ORs the already given permissions with the entry's permission ANDed by the mask for this entry. Finally, the bits in the entry's mask are cleared from the requested permission bits. Once the RPB is 0, we can exit the loop. For sub-ACLs, a recursive call is done to the ACL parser. The requested permission bits will be the current requested permission bits ANDed with the entry's masking bitmask. When the parsing of the sub-ACL is done, its results are ORed to the given permissions. Then, the requested permission bits are updated depending of the type of sub-ACL entry: - strict sub-ACLs: all bits from the entry's mask are removed from the requested permission bits - normal sub-ACLs: only those permission bits that were actually found in the sub-ACL (i.e. the entry's mask AND NOT the sub-ACLs requested permission bits on finishing the sub-ACL parser) - relaxed sub-ACLs: the requested permission bits are not changed - benevolent sub-ACLs: only the permission bits that were granted are removed from the requested permission bits - malevolent sub-ACLs: only the permission bits that were denied are removed from the requested permission bits As the granted permission bitfield is set to zero at the beginning of the parsing process, any non-declared access rights are denied by default. Example code (or: One line of sourcecode says more than 1000 words) ------------ /* no guarantee that this is correct... */ permmask_t parse_ACL(acl_t *acl, permmask_t *rqpm, uid_t uid) { acl_entry_t *acle; int i = 0; permmask_t granted = 0; permmask_t thismask; for(acle = (acl_entry_t *)(acl+1); i < acl->numentries; i++, acle++) { if (acle->type == NORMAL) { if (acle->uid == uid) { thismask = *rqpm & acl->mask; granted &= ~thismask; granted |= acl->perms & thismask; if (!(*rqpm &= ~thismask)) break; } } else { permmask_t submask, subgranted; submask = thismask = *rqpm & acl->mask; subgranted = parse_ACL(acl->subacl, &submask, uid); granted &= ~submask; granted |= subgranted; if (acl->type == SUBACL_STRICT) { *rpgm &= ~thismask; } else if (acl->type == SUBACL_NORMAL) { *rqpm &= ~thismask | submask; /* &= ~(thismask & ~submask) */ } else if (acl->type == SUBACL_BENEVOLENT) { *rqpm &= ~subgranted; } else if (acl->type == SUBACL_MALEVOLENT) { *rpgm &= ~thismask | subgranted; /* &= ~(thismask & ~subgranted) */ } /* do nothing on SUBACL_RELAX */ if (!*rqpm) break; } } return granted; } ACL notation ------------ I use a standard form of ACL notation which goes like this: Name of ACL (owner: name of owner) ----------- 0: type of entry uid perms mask or: sub-ACL mask For perms and mask, the following chars are used: r - read w - write x - exec M - ACL modify Details on ACL modification --------------------------- When a user is given the Modify ACL permission bit (bit 0), he may modify the ACL for which he has got this permission. In particular, he is allowed to: - delete an ACL entry below the one in which he was given the Modify ACL permission if all bits in both the Mask field and the Permission field of the entry are empty (= set to zero) - add an ACL entry below the one in which he was given the Modify ACL permission; this entry will have the Mask field and the Permission field empty (= set to zero) - change in an ACL entry below the one in which he was given the Modify ACL permission any bits in the Mask field and the Permission field for which he himself has permission as of the ACL entry in which he was given the Modify ACL permission. Check the section "What about Unix-like groups?" below for some examples... Note that you DO NOT have the right to move an ACL entry, because this would complicate permission semantics a lot. However, deleting and adding an ACL entry could be combined into one action to simulate moving... Also, system calls should allow the combination of several ACL entries at once (and combined actions such as add ACL entry + change entry bits) to reduce some overhead. ANNOTATION: Modify ACL set/unset limitations I'm not quite sure about these myself, whether they are necessary/useful or not. Any input on this problem will be appreciated You may NOT set or unset the Modify ACL bit in the Mask and/or Permission fields of an entry if the user the entry applies to has a permission that you do not have. This should especially apply for _setting_ the Modify ACL bit. However, there are several detail questions as far as this is concerned: - when checking the other user's permissions, should only the modified entry be taken into account, or previous entries as well? Maybe, to resolve this peacefully, we could restrict the ability to change permission bits to those bits that were given to the modifier in the entry with the Modify ACL bit, and exclude permissions given in the entries above. However, this creates new problems when you are trying to force-deny a certain permission in a previous ACL entry.. oh well... - What with ACLs that are included in other ACLs? Should you take permissions granted by the calling ACL as well? No, because this couldn't be made... After going through this again, I tend to opt against this limitation, as it will only complicate the modification semantics and might confuse users due to unclean behaviour. We should just make the users design their ACLs carefully, and there shouldn't be any problems... I hope ;) SOME ISSUES BROUGHT UP AND RESOLVED =================================== This idea sucks!!!!11 --------------------- Uhh.. maybe it does.. then why don't you send me some constructive criticism - that's always a good thing.. send it to , or discuss it on our IRC channel. Oh, and maybe you should look at the sections below.... What about Unix-like groups? ---------------------------- Guess what.. I thought about this as well. That's why I came up with sub-ACLs... Consider a Unix setup where you have a dummy user "games" for a number of games installed on the machine. Anyone who wants to waste time with them must be part of the group "games". So the file permissions for a game would look like this: games games rwxr-x--- somegame Now with ACLs you'd implement this like the following: ACL for file somegame (owner: games) --------------------- 0: NORMAL games rwxM rwxM 1: SUBACL_NORMAL Group-games r-x- Group-games (owner: root) ----------- 0: NORMAL user1 rwx- rwx- 1: NORMAL user2 rwx- rwx- 2: NORMAL user3 rwx- rwx- 3: NORMAL user4 rwx- rwx- This scenario is a pretty good mapping of the Unix-scenario. In effect, all users in group games have exactly the same rights as in the Unix example. They do have write access inside their group-ACL, but as write permission is masked out in the calling ACL, they can only read or execute the file. Now in a Unix environment, only root can add/remove users from the group. However, using ACL the founder of group "games" could "elect" some more admins for his group. Here's an example of how this could work: Group-games (owner: games-admin) ----------- 0: NORMAL games-admin rwxM rwxM 1: NORMAL user1 rwx- rwx- 2: NORMAL admin2 rwxM rwxM 3: NORMAL user2 rwx- rwx- 4: NORMAL user3 rwx- rwx- 5: NORMAL lower-admin r-xM r-xM 6: NORMAL lower-admin -w-- -w-- 7: NORMAL untrusted1 r-x- r-x- Now what do the permissions look like? First of all, everybody in this ACL can read and execute files associated with the ACL. Everybody except user "untrusted1" can also write to those files. "games-admin" is the first user in the group ACL, and he has the Modify ACL permission set. This means that he can give or withdraw any of the rights rwxM to/from all the users below him, including the other users with Modify ACL rights. "user1" is fairly protected, because nobody but "games-admin" (and the ACL owner, which happens to be the same) can change his permission. However, user1 can not change any of the permissions inside the ACL. admin2 has exactly the same rights as games-admin, except that he cannot modify the entries for games-admin or user1. user2 and user3 have full access rights (rwx) to any of the files that use this ACL, however they have no right to modify the ACL. User lower-admin is an interesting case, because he has two different entries: the first one gives him r-x permission, plus the permission to add/remove users with any of the access rights r-xM below this entry. But there's more to come. The entry below gives him write permission as well. However, HE STILL DOESN'T HAVE THE RIGHT TO CHANGE WRITE PERMISSION OF OTHER USERS IN THE ACL!!! The interesting thing about this is that on the first sight you might think that he could cheat himself into the permission of adding the -w-- flag to someone else by modifying entry 6: 5: NORMAL lower-admin r-xM r-xM 6: NORMAL lower-admin -w-M -w-M However, as the M permission is already given to him in entry 5, and the rule for ACL parsing is first match takes it all, lower-admin still won't have the right to add/remove w right to anyone below him in the ACL. This might be confusing for list admins especially if the ACL lists grow large. Programs should warn list admins about things like these - however, they are perfectly valid within this declaration of ACLs. Sub-ACLs and the Modify ACL permission -------------------------------------- One very important thing to consider with system security is that the Modify ACL permission bit will be inherited from sub-ACLs unless it is masked off in the corresponding entry. Consider the example in the section above (using the second, more complex Group-games ACL). In its current form, none of the admins in Group-games have the right to modify the main ACL. However, what if the main ACL were changed to the following: ACL for file somegame (owner: games) --------------------- 0: NORMAL games rwxM rwxM 1: SUBACL_NORMAL Group-games r-xM In this case, users who have the Modify ACL permission for Group-games will inherit it into the main ACL, so that games-admin, admin2 and lower-admin will have the right to add/delete permission bits from entries below entry 1 (they may add new entries of course). However, as the write permission is masked off, they will not be allowed to give any new user write permission. This inheritance functionality needs to be considered for system security. However, it could prove useful in several cases (especially on big systems with many users), so there's no point in removing it. Of course users need to be properly warned about possible security issues because of it. What are the different sub-ACL types for? ----------------------------------------- As you will have noticed, there are a lot of different types of sub-ACLs. They only differ in how the Requested Permission Bitmask is changed after the sub-ACL was parsed. Consider the following set of ACLs: ACL for some file (owner: games-admin) ----------------- 0: NORMAL games-admin rwxM rwxM 1: SUBACL_STRICT game-developers rwx- 2: SUBACL_STRICT gamers r-x- game-developers (owner: gamedev-admin) --------------- 0: NORMAL gamedev-admin rwxM rwxM 1: NORMAL dev-john rwx- rwx- . . . gamers (owner: games-admin) ------ 0: NORMAL games-admin rwxM rwxM 1: NORMAL joepublic rwx- rwx- 2: NORMAL someguy rwx- rwx- . . . It is quite obvious that all the people in game-developers (which have write permission in this list) are allowed read/write/exec-access to the file while the users in the gamers ACL are only allowed read/exec-access. This is all very nice, but what if joepublic beats the egocentric gamedev-admin in his own game, and this guy gets so pissed off that he wants to have his revenge outside the game... Well easy... imagine he simply adds the following entry at the end of his ACL game-developers: n: NORMAL joepublic ---- rwxM This entry will explicitly withdraw all access rights from joepublic. Now because the sub-ACL is called strictly, all the declared permission bits (i.e. read, write and exec) are cleared in the Requested Permission Bitmask. In other words, the read/exec permission given by the gamers ACL is simply ignored, and joepublic can no longer play his beloved games. Of course he will complain loudly to games-admin and gives him all the blame because he neither understand the inner workings of GiX, nor the evil plots of gamedev-admin. How do you get around this problem as the games-admin? Well, of course you should kick gamedev-admin. But the situation could be a bit more subtle when several people have Modify permission to the game-developers ACL, and the problem shouldn't have arised in the first place anyway. So the real solution is to change the sub-ACL type. Let's evaluate the alternatives: - normal sub-ACLs: The declared permission bits are removed from the RPB, so in effect this is the same as strict ACLs in this case. Not a good solution - relaxed sub-ACLs: The RPB are not changed. This seems like a good solution, because joepublic's read/write permission from the gamers ACL are now taken into account. However, now the game developpers could get problems with a malicious gamers ACL admin. If somebody added the following entry at the end of gamers ACL: n: NORMAL gamedev-admin ---- rwxM Now gamedev-admin wouldn't have read/exec permission on the file any more, because this part is removed by the gamers ACL (write permission is masked out for the gamers ACL, so it isn't affected). So, this isn't a good solution either - benevolent sub-ACLs: Only the permission bits that were granted are removed from the requested permission bits. This finally seems like a good thing. joepublic isn't given any permission in the game-developers ACL, but so what? After all, the RPB isn't affected, so the read/exec permission he gains later on in the gamers ACL counts. This is the solution we want. - malevolent sub-ACLs: Only the permission bits that were denied are removed from the requested permission bits. This has the same effect as the original strict rule, so it's not a good solution. After this, it seems like benevolent sub-ACLs are the only thing you'll ever need. However, depending on the situation, you may one day appreciate one of the other types... THOUGHTS ON IMPLEMENTATION ========================== Using ACLs in multiple places ----------------------------- This may sound obvious, but it should be possible to assign an ACL to more than one file, as well as it should be possible to assign an ACL to more than one ACL as sub-ACL. This saves memory and can speed up ACL parsing significantly, especially in combination with a caching scheme. However, there is one drawback: There doesn't seem to be a really quick way of determining what file(s) and/or ACL(s) an ACL is used for (if you know one, tell me about it), so users should be warned about security issues when modifying an ACL (who knows what security-relevant files are linked to an ACL you're giving someone write permission to?). A link counter definitely needs to be included, along with warnings in all programs that touch ACLs. With the ability to use an ACL several times, access right management could become much cleaner. A user could for example just have three default ACLs: one for read/only-files, one for read/write files, and one for executables ACL cache --------- The permission results of ACL queries should be cached in some way or the other. Especially when users use ACLs efficiently, this can speed up permission checks a lot. For this to work, every user logged into the system needs a seperate cache, preferably managed in a small hash-table with a small (1-2 entries) array holding recent test results per hash-table entry. ACL naming ---------- For the users' convenience, it should be possible to assign a descriptive text with all ACLs (which can only be modified by the ACL owner). E.g. one could call an ACL "Read/write files of HyperGame project". This ACL would control access rights for files of the HyperGame project, a fictional game, possibly giving additional access rights to other users (apart from the owner) who work on the project as well. Of course these descriptive texts are in no way associated with the content of the ACL, so if you call an ACL for read/write files "Really private read/only files", it's your own fault. These names should be kept out of the kernel - it's just unnecessary stuff.