Bruno_Kieba.SBDERX@xerox.com (06/23/88)
I have added a capability-based protection on MINIX 1.1 which should also be compatible with 1.2. The implementation allows users to access and protect objects (files, directories, named semaphores if need be, etc) with a capability. In fact any object traceable via a pathname can be protected with a capability. The capability protection designed sits on top of the normal protection and is thus provided as an additional (extension) protection feature. The normal protection is not made redundant, that's what I mean. Perhaps a little outline of the most important design features I implemented will help the readers understand how the scheme works and what capabilities in MINIX is all about. Outline: When a user first logs in the sytem (the first time ever), a capability file is created automatically and is stored in the user home directory. In subsequent logins, the capability is only opened and remains so during the entire login session. I added a new system call in the login procedure to do that. This system call is called by "login" after the redirection to the user home directory. The created file is of type "capfile" and considered as such by the system. ie: it is not a directory file or normal file. This distinction allows privileged operations such as deleting or moving capability files to be handled. Thus each user of the system owns a capability file that will contain the user private, copied (internally), or passed (externally) capabilities. When an object is created, a capability is not automatically generated. This option is up to the user. The library procedures added to manage and manipulate capabilities are: adcap Allows a user to add an encrypted capability (passed externally) in the user capability file. The capability may have been passed by phone, electronic mail or any fancy kind of media. The user simply types "adcap" on the terminal. The system will ask for the capability, which must be entered in hexadecimal notation, and will store it in the user own capability file. The capability is verified twice before being stored in the capability file (like entering passwords). As you may have noticed, capabilities are not stored in the kernel. Users have direct access to their capabilities. This implementation is more flexible and still secure. chcap To change the access rights contained in an encrypted capability. cpcap Allows a user to copy (internally) one or more of his/her encrypted capabilities to another user. The encrypted capability(ies) is/are copied in the capability file belonging to the destination user with restricted or extended rights. The copying is handled by the file system. lscap To list capabilities associated to specific objects or objects within a directory, either in their encrypted format, decrypted format or even both. More listing options are available. nwcap To create (assign) new capability(ies) for one or more objects. The capability rights and object name(s) must be given as parameters. If a capability for an object already existed, it is overwritten with the new one. rmcap To delete one or more capabilities from the user capability file. Only the owner of the capability(ies) can do that. The user simply provides the name of the object(s) and their associated capabilities are removed. zapcf To delete a (corrupted) capability file. Only the super user can do that. The system calls to support these procedures are: adcap, cfacc, chcap, cpcap, nwcap, rmcap, secap, sdcap, wakcf. Details of theses system calls can be seen in the source code if you are interested. A capability file cannot be deleted by its owner neither can it be copied or moved to another directory. A capability contains four fields (similar to an Amoeba capability). The first field contains the logical device number of the file system in which the protected object resides. The second field contains the i-node number of the protected object. The third field contains the access rights allowed on the object. Theses rights are Read, Write and Execute. The fourth and last field contains a 56-bit constant (validator) to validate the capability. The access rights and the constant are encrypted together. The encryption is necessary to keep the integrity of any capabilities and to make passed or copied capabilities tamper-proof. The first and second fields are not encrypted since they are used to locate a capability. When an attempt to access an object is made, the capability (fetched from the appropriate user capability file) is decrypted. After the decryption, if the constant matches the one expected by the kernel (file system), the capability is assumed genuine. In this case, the rights corresponding to the requested operation is compared with the access rights contained in the decrypted capability. If the requested rights are a subset of the rights contained in the capability, the operation is successful. Otherwise EACCES is returned. EACCEs is returned if the capability is invalid, does not contain the access rights requested or does not exist. If a decrypted capability is found invalid (bad constant), it is deleted from its capability file. This is to keep capability files garbage-free. The encryption of capabilities is done with the DES algorithm. DES uses the same key to perform an encryption/decryption operation. The keys in MINIX are DES-like and are stored in a key block(s). The number of key blocks is configurable depending on the number of available i-nodes. For a 127 i-nodes floppy disk for instance, one key block is only needed. Key block(s) are placed next to the inode blocks. My first attempt was to store the keys in the object i-nodes (extending the i-nodes from 32 bytes to 40 bytes) but I did not succeed in attempting such design. I know the reasons but I don't know how to get round it. The DES algorithm is implemented in C-language in the file system address space. I could not put it anywhere else because I had to make it transparent with the existing library routines that manipulate and access objects. The keys are generated with a random number generator. This generator needs to be reviewed because in its original implementation it uses floating points and the MINIX C compiler does not support floating point operations. However, by thinking of it now, a random number generator is not really necessary to generate DES-like keys. The routine "get-time" could be used for this purpose. Anyway, the generator is in MINIX too and is used to generate 64-bit DES keys. I noticed that there is a random routine somewhere in MINIX, at least for what the name says, called rand. Unfortunately, when I tried to access the source of this routine, either by trying to read it, copy it or print it , the system always crashes??!!?? so I gave up and implemented a generator in the file system address space. Altogether, the DES algorithm + the generator + the system calls + the addition of miscellaneous code increase the original size of the file system to way above 64K. I managed to reduce the code but I still had to remove 10 blocks off the buffer cache (nasty ...!). The total file system size is now around 58K I think (I lost my reminder on this one). The DES algorithm uses a lot of space because it needs many tables. There is much more to say about the capability-protection features and the software implemented but I should give it a break now. I mentionned the most interesting features above. If you want more details, please do so. I will be more than happy to tell you about the stuff that interest you most in my implementation. If you want the code, bits of it or all of it ! , then speak up. Bruno PS: If you noticed some incorrect english in this mail note and previous ones, don't worry about it. I am French and I eat english food every day. I try not to complain about the food so don't complain about my english!! The Abbot tastes good though!