|Date:||June 8, 2007 / year-entry #206|
|Summary:||So-called canonical order for ACEs in an access control list places deny ACEs ahead of allow ACEs. Why is this the canonical order? Because it gives results that are sensible. The algorithm for determining whether a user has access to an object protected by an ACL is as follows: let access-still-needed = access-requested for each...|
So-called canonical order for ACEs in an access control list places deny ACEs ahead of allow ACEs. Why is this the canonical order?
Because it gives results that are sensible.
The algorithm for determining whether a user has access to an object protected by an ACL is as follows:
In words, we go through the ACEs in the ACL in the order they appear, paying attention only to the ones that apply to the user, i.e. the ones whose SIDs are present in the user's token. If a permission is being denied, and the user is still looking for that permission, then access is denied. If a permission is being granted, then those permissions are subtracted from the permissions the user is still looking for. If, at the end of the day, all the permissions the user requests have been granted, then access is granted.
The key detail in the above algorithm is that deny ACEs apply to permissions not yet granted and not to the original set of permissions requested. If you deny write, but an earlier ACE grants it, then the deny has no effect.
Let's look at what happens if we apply this algorithm to an ACL that is not in canonical order. Our ACL is as follows:
Let's say that Alice wants write access. We start with access-still-needed = write, and the first ACE grants it, leaving access-still-needed equal to zero. The second ACE denies read and write, but Alice already got write access thanks to the first rule, and she never asked for read access, so this deny ACE has no effect. The third ACE also has no effect since Alice wasn't looking for read access. Result: Alice gets write access.
On the other hand, suppose Alice wants read access. The first ACE has no effect, since Alice isn't interested in write access. The second ACE then denies access since Alice is being denied read access which she hasn't gotten yet. Alice's request is rejected without even looking at the third ACE.
Notice that if the ACEs are not canonically-ordered, you can't use a simple rule like "deny ACEs take priority over allow ACEs". The rule is "Well, you have to go through each ACE one by one, and you get access if you get all the things you want before somebody denies them." It sort of turns into a game show.
Since graphical ACL editors typically don't show the order of the ACEs, some sort of canonical order needs to be established so that you don't run afoul of this "order of operations" problem. Notice that in the algorithm above, you can swap two adjacent allow ACEs and two adjacent deny ACEs without affecting the result, but you cannot swap the positions of an allow and a deny ACE. Therefore, the canonical ordering must either be "all deny ACEs come before all allow ACEs" or "all allow ACEs come before all deny ACEs".
Note, however, that if you choose to have all allow ACEs come before all deny ACEs, then you don't need deny ACEs at all! If you look at the algorithm above, if there is no ACE that mentions the permission you want, then access is denied. The deny ACEs don't add anything to the picture:
Notice that once you make it out of the first "for" loop, the return value is going to be access-denied if access-still-needed is nonzero. All the deny ACEs give you is another way to say "no". But you were going to say "no" anyway.
Therefore, for deny ACEs to be meaningful, the canonical ordering should place them ahead of allow ACEs. That way, you get three tiers of permission instead of just two:
Postscript: Our sample non-canonical ACL above can easily be converted to an equivalent canonical one:
Why does this work?
Well, first notice that the second rule ("Deny read and write access to Users") completely overrides the third rule ("Grant read access to Users"), since any attempt by the third rule to grant read access to Users will be thwarted by the second rule, which denies it.
But the second rule itself is unnecessary. We are taking advantage of the test outside the loop in the access algorithm:
<-- Back to Old New Thing Archive Index