We don’t exactly represent the ACM as a two-dimensional matrix, but as a list. [[02 - Design principles for secure systems#Least privilege|Least privilege]] implies that users should only have access to a small fraction of the total resources. Therefore, many elements of the access control matrix are empty, and only those with permissions are non-empty. Matrices where most cells are empty are called sparse matrices. The matrix is sparse and we don’t want to store empty entries of the matrix. Therefore we use alternate methods to store this information (column or row wise). ### Access control lists (ACLs) Columns of an [[Access control matrix]] - The ACL belongs to an object and is a list of all users and permissions associated with this object. - Every non-null entry is stored and the entries linked to create a list. - When a user references an object the permission is checked by seeing if the user is in the ACL. This is like going to a club and having your name on the list. - The ACL is stored as metadata for the object ### Capability lists (C-lists) Row of an [[Access control matrix]] - The C-lists belong to a subject (or user) and is a list of objects they have permissions for, and the specific permissions they have. - Every non-null entry from the matrix row can be linked to create this list. - A user is allowed to access an object if their C-list allows it. This is like having a ticket to the movie theater. - The C-list is stored with the user. - Should be unique, unforgeable, and sharable #### ACLs or C-lists Which is better? - Performance - Capability is a reference or handle for a resource whereas ACLs need to be traversed. Capabilities would have a lower overhead for checking. - Revocation - You can traverse the ACL and revoke access. However, it is harder to revoke capabilities. (When you give a key to someone, you kind of need their consent to take it back) - Accountability - Easier to understand who has access to a resource in ACLs. Whereas, capabilities might be propagated, and it might be harder to keep track. ### Confused deputy problem >Are there access control problems that can be addressed with one but not the other? Suppose we have a pay-per-user service where we compile files for customers. `% compile input output` We have a "billing" file that is updated after each time the service is used. What happens if a malicious user tries to compile a file and output the compiled file as "billing" to corrupt the “billing” file? `% compile input biling` >[!faq]- Can we ensure proper access to this file with ACLs or C-lists? >With ACLs there is not way to stop the corruption of the billing file. With C-lists it is possible. **ACLs** - The compile service must have access to the billing file so it can update the information. - The malicious client has to correctly guess the billing file name so it knows where to write to. - When the billing file is accessed the system doesn't know if this is due to the compile service updating the billing file appropriately or if it is due to the compile service's malicious request sent by the user. **C-lists** - A capability is never shared with the client. So, a malicious client will never have this capability. >In this example, the system is our confused deputy.