Article 4214 of rec.games.mud.lp: Path: newsflash.concordia.ca!utcsri!utnut!torn!spool.mu.edu!howland.reston.ans.net!xlink.net!math.fu-berlin.de!cs.tu-berlin.de!tubmud From: tubmud@cs.tu-berlin.de (TUB Multi User Domain) Newsgroups: rec.games.mud.lp Subject: A security system for LPmuds Date: 21 Jun 1993 22:14:31 GMT Organization: Technical University of Berlin, Germany Lines: 188 Message-ID: <205bs7$l2@news.cs.tu-berlin.de> Reply-To: r_behren@informatik.uni-kl.de NNTP-Posting-Host: dragon.cs.tu-berlin.de Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit DESIGN PRINCIPLES FOR A SECURITY SYSTEM There are many conditions a good security system should satisfy. Ease of use, consistent design, and of course security. The current uid system used in many muds fails to satisfy all of them. It is unnecessarily complicated to use, its design has to many twists and it has been broken to often to be considered safe. Therefore I have tried to design a system that performs better in all three areas. BASIC CONCEPT The security system described in this article is based on the concept of 'permissions' and 'protections'. Every object gets a certain permission level assigned, every file a protection. Access is then granted based on the comparison of the permissions of the objects involved in the computation and the protection of level of the file that is to be accessed. If the 'total' (the meaning of total will be explained later) permission level of all the objects involved is greater than or equal to the protection level of the file, the access is successful. DEFINITIONS We no need a more precise notation of what 'permissions' and 'protections' are and how the 'total' value is computed. Basically, all permission and protection values are drawn from a finite set S. We define an operation ^ on S such that (S,^) is a lower semilattice and the relation <= induced by a<=b iff a = a ^ b is a partial order. We will further assume that S contains at least two elements, <1> and <0>, where <1>>=s for all s in S and <0><=s for all s in S. ^ is normally known as the "greatest lower bound" operator. Example: We define S to be the set { <1>, <a>, <b>, <c>, <0> } and use the following diagram to define ^ and <=. <1> / | \ / | \ <a> <b> <c> \ | / \ | / <0> We have x <= y iff x = y or x is below y in the above graph and there is a straight connection between x and y. x ^ y = z iff z is the topmost element in the graph such that z <= x and z <= y. For example, <a> ^ <1> = <a>, <b> ^ <0> = <0>, <a> ^ <c> = 0. Of course, more complex orderings can be thought of. The above ordering is a simple example with permissions/protections for three wizards, as well as for root and an /open directory (in MUD terms). We proceed now to assign values from S to directories. In the above example, /players/a, /players/b and /players/c would have been assigned <a>, <b> and <c> respectively. /open would have been assigned <0> and all the other directories like /obj would have gotten a value of <1>. Any file within a directory now automatically inherits the value assigned to the directory it resides in as its protection. If the directory has no value assigned to it, the above directory is checked, then the one above that until we find a value. So /players/a/obj/test.c would get <a> as its protection level. On the other hand, /players/guest.o would have protection level <1>, not that of <guest>, because the file resides in the directory /players, not in /players/guest. For objects, they inherit the protection of the files they were created from as their maximum permissions. However, they automatically get an initial protection level of <0> and have to raise them if they need more permissions, the maximum permission level derived from the file name being the upper bound for that. So for example, /obj/player.c could get any permissions because <1>, the maximum permission level is higher than all the other permissions available. On the other hand, in most cases the player object will get permissions like <a> or <b>, for the instances of the object will be wizards who are not meant to have global access. The 'total' permissions of a set { ob1, ob2, ..., obn } of objects is their greatest lower bound, namely: perm(ob1) ^ perm(ob2) ^ ... ^ perm(obn), where perm(ob) desribes the current permissions of object ob. HOW IT WORKS Now what is done to decide about the validity of a file access attempt of an object? Let us assume that our current computation made the stack look as follows: ob1->ob2->ob3->...->obn, where ob1 called ob2, ob2 called ob3 and so forth until computation reached obn, which is equal to this_object(). If obn no attempts a write access, say, by write_file(), we check the following: Are the total permissions of { this_interactive(), ob1, ..., obn } >= the protection of the argument of write_file()? If yes, the write_file() succeeds, otherwise it fails. It should be noted that in any case where this_interactive() is 0, the total permissions will automatically be 0 (as in heart_beat()). We will solve this problem later. So far, so good. We can now without problems assign permissions <1> to any tool that writes files because the total permissions will be those of the player who uses it. Likewise, it is impossible for objects to force other players to do unsafe actions because in the process they will reduce the total permissions to what they can do (or less). However, that leaves certain interesting cases out. For example, every save command issued by players without permissions <1> would fail because they can't bypass the protection of the save file. We need an additional LPC construct to handle this case. The LPC statement: unguarded (p) { ...; } will temporarily (i.e. during execution of the statements within the braces { ... } ) reset the permission level to p, where p has to be equal to less than the maximum permission level of the object executing the statement. Effectively, if in stack state ob1->...->obn the statement gets executed by obi, the total permissions will be computed as p ^ perm(ob(i+1)) ^ ... ^ perm(obn). Therefore the statement: unguarded (1) { save_object("/players/"+name); } will succeed. Note that the (p) argument to argument is optional and defaults to the objects maximum permissions. ADVANCED STRUCTURING OF THE PERMISSION/PROTECTION GRAPH Of course, the simple example semilattice defined above is insufficient in many respects. For example, what if wizard <a> wants to give his friend wizard <b> access to directory /players/a/foo, because he wants him to add some stuff to bar.c? He has to create a new permission level, let's call it <ab> and assign it to directory /players/a/foo. It will have still higher protection than <0> (so that wizard c can't write to it) but lower protection than both <a> and <b> so that they both can write to it. Interestingly, all objects from /players/a/foo can now only write to their own directory and /open, so giving access to wizard b to one directory doesn't compromise the security of the rest of /players/a. Access to domains and other schemes can be handled in a similar way. Define where the new protection level will reside within the graph, define it and assign it to a directory. INTERFACE The following efuns are needed: query_permissions(file|object[,mode]) will return the permissions/protection of the file or object given as the argument. Mode is an integer. If querying the protections of a file, zero stands for read protection and non-zero for write protection. For an object, zero will return current permissions, non-zero will return maximum permissions. Mode defaults to 1 for files and 0 for objects. set_permissions(permissions) will set the permissions of this_object() to permissions if permissions is equal to or less than the maximum value allowed for this_object(). create_permissions(directory,above,below) will create new permission levels between the permission levels listed in the arrays above and below. The efun checks if this would introduce a cycle and report an error in this case. create_permissions() will fail if at this point the total permissions are less than or equal to the new permission level created. Write access to the directory with the new permissions is also required. copy_permissions(directory1,directory2) will transfer the protection level of directory1 to directory2. Write access to directory2 is required and the current permissions must be greater than the protection level that is transferred. delete_permissions(directory) will result in directory no longer having a protection/permission value assigned to it and instead inherit the value of the parent directory. The value of / cannot be deleted and will always be <1>. How permissions are represented internally doesn't matter much. Strings or integers are obvious choices. The database needed to store the structure should be in human readable form, however, to ease emergency changes when the mud is down. IMPLEMENTATION The implementation of semilattice operations is definitely not trivial, especially if the structure needs being changed dynamically. Normally the worst case performance in the general case to determine the value of a ^ b is O(|S|). Of course caching should result in substantial speedups. Better implementations of the average case have been done, but the best choice should probably be to restrict oneself to a structure that has been specialized to handle the permission structure of muds well and can compute a ^ b still in O(1) time. Please feel free to comment, criticize and inquire about this scheme. Reimer Behrends