# T4
**Deadline:** Wednesday, November 28, 11:59 pm
*This assignment should be done individually. See collaboration policy below
for details.*
### Problem 1
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 181S. 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:
- The **client node** is used to access R2.
- The **security node** authenticates clients and issues capabilities.
- The **storage node** verifies capabilities when they are used to
access objects.
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:
- How R2 will **grant access** to clients by issuing capabilities when
they are requested.
- How R2 will **determine access** by deciding whether a subject may
read or write an object.
- How R2 will enable **delegation of access** between subjects.
- How R2 will enable **revocation of access** to objects.
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.
### Problem 2
Consider a new scheme for implementing MLS confidentiality, where labels on
files and programs can be changed according to the following rules.
* At any time, the label L(F) on a file F (i) can be increased or (ii) can be
decreased to the largest label on any item that has been written so far to
that file.
* At any time, the label L(Pgm) on any program Pgm (i) can be increased or (ii)
can be decreased to the largest label on any item that has been read so far
by that program.
Moreover, assume that
* If L(Pgm) > L(F)then a write to file F by program Pgm---that is, a
“write-down”---is implemented as a “no-op” (but does not cause program
execution to be blocked or terminated).
* If L(Pgm) < L(F) then a read to file F by program Pgm---that is, a
“read-up”---returns “file unavail” as if that is the contents of the file.
Is there an environment where it is possible for a program Pgm to learn whether
the contents of a file F satisfy some given predicate, even though
L(Pgm) < L(F) holds at the time the predicate is evaluated? (We define
environment to mean: some set of files and
other executing programs.) If so, describe the environment and the attack; if
not, give an argument that explains why the information cannot be learned by
Pgm.
### Problem 3
In class, we studied information flow control for confidentiality. We
saw a simple lattice with two labels, L and H, which were interpreted as
policies constraining the flow of information: data tagged L were
public, whereas data tagged H were secret.
In this problem, we examine information flow control for integrity. So
instead of secrecy, we turn our attention to the *trustedness* of data:
some data are trusted, whereas some data are untrusted.
For brevity, let's give those two policies names:
* **P1:** trusted
* **P2:** untrusted
As in class, we use a lattice to model information flow:
* Let Λ be the set {L,H} of labels.
* Let ⊑ be a relation on labels that characterizes when information
may flow, where L ⊑ L; L ⊑ H; and H ⊑ H.
* Let ⊔ be an operation on labels that characterizes the label that results
when data are combined, where L ⊑ H, L ⊔ L = L, L ⊔ H = H,
and H ⊔ H = H.
But we now want to use labels L and H to represent integrity policies, not
confidentiality policies.
1. Which label, L or H, represents policy P1, and which represents policy P2?
Explain why your answer is in accordance with the fact that L ⊑ H, i.e.,
that L may flow to H. Also explain why your answer in accordance with
the fact that L ⊔ H = H, i.e., that the combination of L and H should
be H.
2. Here is a definition of noninterference for integrity:
\\[\\forall m_1, m_2 \\mathrel\{.\} m_1 =_L m_2 \Rightarrow C(m_1) =_L C(m_2).\\]
The intended intuition behind that definition is that changes to untrusted
variables should not cause changes to trusted variables. You'll notice
that it is, in fact, syntactically the same definition of noninterference
that we gave for confidentiality.
The type system we discussed in lecture soundly but incompletely
enforces that definition of noninterference for integrity—that is, the type
system rejects insecure programs but also rejects some secure programs.
Give two example programs that demonstrate this incompleteness.
The first example should be an assignment statement. The second example
should be an `if` statement whose guard contains at least one variable.
For both examples, provide a mapping Γ from variables to labels.
Also, if your examples include any constants, state whether the tag on
those constants is H or L.
3. With confidentiality, some functions could be treated as changing the secrecy
of data—for example, encrypting a secret plaintext could be treated as producing
a non-secret ciphertext. Give an example of a function that could be treated
as increasing the integrity of data. And give an example of a function that
decreases the integrity of data.
### Feedback
This is the first time this course has been offered. In the interest of
improving future iterations of this course, please answer the following
questions:
1. How long did you spend on this assignment?
2. Any comments or feedback? Things you found interesting? Things you
found challenging? Things you found boring?
### Collaboration Policy
Each student should submit their own solution to this assignment. You may
discuss ideas with other students, but under no
circumstances should you be looking at another student’s solution. Any
ideas that originated with another person should be cited.
### What to Submit
Submit your solution as a 4-page pdf named t4-yourname.pdf to
submit.cs.pomona.edu.
Start each problem’s solution on a new page. Use at most 1 page per
problem. (Use the fourth page to answer the feedback questions.)
Submissions that fail to follow the submission guidelines may be subject
to a 10% deduction.