Homework 4: Authorization

Hard deadline: Friday, April 24, 11:59 pm.
Soft deadline: Wednesday, April 22, 11:59 pm

A man has no ears for that to which experience has given him no access. —Friedrich Nietzsche

Problem 1: DAC

based on [Bishop, chapter 14, problem 9]

In the Unix file system access control model, only the owner of a file (or root) can modify the ACL for that file. We can think of ACL modification as a right that is granted only to the owner.

A CS 5430 student has an idea: it should be possible to authorize principals other than the owner to modify ACLs. Describe how to implement this idea using ACLs. Discuss how to grant and revoke ACL-modification rights.

What to submit: a file named problem1.pdf or problem1.txt with your answers to the above question.

Problem 2: MAC

Sometimes the secrecy of individual data are less sensitive than their aggregate. For example:

Aggregation is particularly relevant in the context of databases. For the purpose of this problem, suppose that a database comprises a number of datasets. (A dataset might be a table or a view.) Further, suppose that each dataset is assigned a sensitivity label such as Unclassified, Secret, or Top Secret. (We ignore compartments in this problem.) Then it might be the case that datasets A and B are both Unclassified, but that their aggregation is Secret. To model this, let the function L(R), where R is a set of datasets—for example, R={A,B}—denote the sensitivity of the aggregation of all the datasets in R. As healthiness conditions on L, we require that:

Our goal in this problem is to develop a MAC model for this scenario. Suppose that an object is a document containing information derived from the database—e.g., the result of queries on datasets. A subject, as usual, is a process executing on behalf of a user. An entity is either a subject or an object.

  1. Construct your own real-world example, using the database model above, of aggregate data that are more sensitive than their constituents. (However, the particular examples above are off-limits. Be original. If you need inspiration, begin by supposing that one of the datasets is a set of photographs.) Your example should include at least three datasets. Identify what L(R) is for each possible subset R of your datasets.
  2. Suppose that each object (and subject) is labelled with its sensitivity (or clearance). We could then attempt to employ the Bell and LaPadula security conditions ("no read up, no write down"). However, we claim that these conditions are insufficient to guarantee the following policy:

    P1: An object never contains information whose sensitivity is higher than the object's label.

    Using your example database from part 1, prove this claim by exhibiting a series of read and write operations that effect such an information flow. You may freely invent entities and their labels.
  3. Instead of sensitivity, suppose that each entity is labelled with a set of datasets. Give new conditions for reading and writing. Your conditions should guarantee the following policy:

    P2: If X is labelled with R, then the information in datasets R should be allowed to flow to X, and information from datasets other than those in R should not be allowed to flow to X.

    Your conditions should be general—not specific to the particular example you gave in part (1).

What to submit: a file named problem2.pdf or problem2.txt with your answers to the above questions.

Problem 3: Capabilities

based on [Schneider, chapter 7, problem 19]

You have been engaged as a security consultant by Yangtze,* a new company providing cloud storage. Yangtze's new system is named Remote Repository, or R2 for short. With R2, Yangtze's engineers seek to build an ultra-high performance cloud storage system. They've solved most of the problems, but they need your help with the access control subsystem. (*The Yangtze is the next-longest river in the world after the Amazon.)

Yangtze built a prototype of R2 that uses access control lists. They've encountered a serious problem, though: every request that a client makes to read from or write to an object in storage has to be authenticated, the client has to be mapped to a subject, and the subject's entry in the ACL for the object has to be consulted. All that work is slowing down the system, keeping it from achieving Yangtze's performance goals.

Luckily, you studied capabilities in CS 5430. You know that with an access control subsystem based on capabilities, the storage system would need to do very little work, because the client would simply present the capability along with its request. The storage system would need only verify that the capability permits the request. Also, Yangtze is excited about the possibility of subjects delegating access rights without ever having to contact R2 at all, because this would further enhance performance.

But there is one big problem: you've read about how to implement capabilities with asymmetric cryptography, digital signatures in particular, but that kind of crypto is too slow for use in R2. You're going to have to find a way to implement capabilities with symmetric cryptography.

So far, you've invented the following architecture for the system:

R2 Architecture

You've already taken care of the authentication subsystem—it doesn't play much, if any, role in the work you're doing now. Furthermore, you've already arranged that the security node and storage node can share an arbitrary number of symmetric keys—you don't need to concern yourself with how to accomplish that key distribution. However, generating and distributing keys is somewhat expensive, so Yangtze insists that you keep the number of keys used to a minimum. Finally, you can assume that all communication channels between client nodes and server (i.e., security and storage) nodes are secured with SSL in unilateral authentication mode: the client authenticates the identity of the server, all communication is encrypted to protect confidentiality, and replay of messages sent over the SSL channel is detected.

One more thing: Yangtze has provided you with an implementation of globally unique identifiers (GUIDs) for objects, so that every object in the system has its own unique 128-bit identifier.

Your remaining work is to figure out how to handle the following concerns:

Taking into account all the constraints and goals above, you now need to produce a design for R2's access control subsystem. You will want to carefully specify what capabilities are: what fields they contain, how to interpret those fields, etc. You'll also want to explain in detail how each of the above concerns will be implemented in R2. If there are any cryptographic protocols involved, you need to write those down using proper notation, and explain each step. Finally, explain why you introduce each symmetric key that is used in your design, and explain why you've used the minimum of number of keys necessary.

Karma extension to the above problem: Yangtze wants to enable subjects to delegate restricted rights to other subjects. For example, Bob might have a capability that grants him read and write access to object O. Normally that would enable him to easily give both read and write access to Alice. But with restricted delegation, he should also be able delegate just read access or just write access to Alice. Yangtze insists, for performance reasons, that Bob should not have to contact any server nodes at all to perform this delegation. Extend your design to incorporate restricted delegation.

What to submit: a file named problem3.pdf or problem3.txt with your answers to the above questions.

Problem 4: Information Flow for Integrity

The security policy noninterference for integrity can be informally stated as,

"Changes in untrusted inputs do not cause changes in trusted outputs."

Intuitively, untrusted (i.e., tainted) information should not be allowed to corrupt trusted (i.e., untainted) information.

  1. Examine the following statements and explain which statements satisfy noninterference for integrity, which don't, and why. A security type τ can now be either T, for Trusted, or U, for Untrusted. Assume that typing context Γ assigns types to variables as follows: Γ(x) = Γ(y) = T and Γ(v) = Γ(z) = U.

    1. x := y + z;
    2. v := y + z;
    3. if (x) then
          y := x;
          v := z;
    4. if (v) then
          y := x;
          v := z;
  2. We will now reformulate the type system from lecture, which enforced only noninterference for confidentiality, to make it enforce both noninterference for confidentiality and noninterference for integrity.

    1. Let a security type τ now be a pair of a confidentiality type and an integrity type—for example, if Γ(x) = (H,T), then variable x contains information that is both high confidentiality and trusted. Define the ≤ relation for these extended security labels. τ1 ≤ τ2 should hold if and only if information at level τ1 is allowed to flow to level τ2.
    2. Give syntax-directed inference rules for assignment and if statements that enforce both noninterference for confidentiality and noninterference for integrity. You should give a single rule for each kind of statement (so two rules total), and your rules should forbid implicit flows.

What to submit: a file named problem4.pdf or problem4.txt with your answers to the above questions. You do not need to provide fancy type-setting of your inference rules, as long as they are readable.


Include your name and NetID as a header in every file. For type-set solutions, use 10 point or larger type. Try to keep your solutions concise. Submit your files to CMS.

Submissions that do not adhere to the requirements stipulated here will lose points.


You will be evaluated on the quality (including correctness and clarity) of your solutions and on your adherence to the submission stipulations above.