Assignment 6, due March 22

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday), and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

1. Background: Consider a pure capability-based file system that tries to mimic the Unix file system as follows:
   • Files still have types, as in Unix, either data file or directory, where a directory is a set of name-capability pairs.

   • The access rights on a capability are rwx as in Unix. Note, however, that there is no such thing as ownership or groups. When applied to directories, r gives the right to read the directory, w gives the right to add or delete entries in the directory, and x gives the right to traverse the directory as part of the path to a file.

   • Users can copy capabilities from any directory they can read to any directory they can write. In copying, the name associated with the capability can be changed, and the access rights reduced, but not increased.

   • When creating a file or directory, the user gets a capability for it with all rights.

   • The standard user environment has 3 capabilities, one for the public root of the file system, one for the user's home directory, and one for the user's current working directory.

   • There is no concept of file ownership. The rights you have to a file depend entirely on the capability or capabilties you can access for that file.

   a) Explain why this directory system is not very useful with with a Unix-style single-rooted directory tree where everyone has access to the root. (0.5 points)

   b) What files should be accessible from the public root of the file system? (0.5 points)

   c) The term "public root of the file system" suggests that there might be a second root, a private root (used only by the system, for example). Give an example of a system program that would need access to this, and explain why. (0.5 points)

   d) Explain why including an up-link (analogous to the .. link in each Unix directory) could be a bad idea with this file system. (0.5 points)

2. Each process in a modern Unix system has three user IDs:
   • The real user ID
   • The effective user ID -- used for access checking, set by the SUID bit
   • The saved user ID -- also set by the SUID bit

   The kernel call setuid(), if executed with root privileges, changes all three identically. Otherwise, if a process tries to set the user ID to x, only the effective user ID changes, and the only legal values are the real ID or the saved ID.

   a) What does this third user ID permit that you could not do with just two user ID's, effective and real? (0.5 points)

   b) If you have two mutually suspicious applications, mine and yours where your application needs to use mine, but you don't trust me and I don't trust you, why is the result very problematic. (0.5 points)

3. Consider a symmetric-key block cypher where successive blocks of plaintext are designated p[i] and consecutive blocks of cyphertext are designated e[i]. Each block is encrypted by e[i]=enc(k,p[i]) and decrypted by p[i]=dec(k,e[i]). We can view the key k and the blocks, both plain and encrypted, as integers.

   The course notes suggest that a good encryption function should also work as a pseudorandom number generator for a stream cypher. This creates a stream of keys sk[i] used to encrypt or decrypt the successive blocks of the mesage.

   a) What is the encryption key for a stream cypher constructed this way? It is more complex than just the k used in the corresponding block cypher. (0.5 points)

   b) Give the most straightforward stream_encrypt(p[i] ... ) and stream_decrypt(e[i] ... ) functions. You may find a need to reference sk[i-1] and you will certainly have to produce sk[i] as a side effect of each step. The ellipsis in this problem statement implies deliberate under-specification (0.5 points)

4. Background: A manufacturer of electronic voting machines made the following effort to protect the secrecy of voter's ballots: Instead of storing the ballots in the order they were cast, the ballots were randomly distributed into one of 16 bins, where the ballots in each bin were stored in sequential order. A pseudo-random number generator with 32-bit seed was used, with an initial seed that was genuinely random.

   US elections are complicated -- it is common to find 20 distinct contests on a single ballot. As a result, it takes an average of about 6 minutes for each voter to cast a ballot. If the polls are open for 12 hours on election day, that means each voting machine can accomodate 120 voters. This means that there will be, on average, about 7 ballots in each bin when the polls close. Here are the number of votes per bin after an actual election:

           2  11   7   6   7   4   7   7   7   8  11  12  13   6   8   4
   

   a) Give an informal argument that there is a high likelihood that the count of ballots in the bins at the close of polls uniquely determines the pseudorandom number seed and therefore, that the attempted randomization of the ballots did not actually protect voter privacy. (0.5 points)

   b) Assuming, for no good reason, that we must use that 32-bit pseudorandom number generator, would voter privacy be protected better if we used more bins or if we used fewer bins? (0.5 points)