Homework Solutions 13

22C:116, Fall 1995

1. Part A: In the absence of a file server, what kind of protocol would you propose to use in an all-cache file system when a user program opens a file?

   The Answer: The key questions that must be addressed by the protocol are file naming, file location, and file system coherency. Because there is no central file server, file names must not relate to the position of a file in the system; instead, file names must be unique identifiers that are the same for all copies of the file anywhere in the system. Files may move freely in such a system, so the problem of locating a file is complicated, possibly involving falling back on a broadcast request for the machines holding copies of the file to identify themselves.

   Part B: Can you propose a way to deal with the problem of incoherency that results when multiple processes open a file for write access?

   An Answer: One solution is to invalidate all other copies of a file when one copy is updated, or when one copy is opened for writing. In all versions of this answer, the result of modifying a file is that one copy survives on some machine, and that machine acts as a file server for all users of that file until new copies are made. Such solutions probably require something akin to an election to be held to determine which copy survives when there are competing copies that could be used. Such solutions also probably require a protocol to allow users to dynamically change servers, in the event that the copy of the file they are using is invalidated.

   Another Answer: When a process opens a file for write access, the open protocol finds the locations of all copies of the file. With this scheme, all write operations involve duplicate updates of every copy. Updates must be serialized identically for every copy of the file, so that if two update messages from different clients arrive at two copies in different orders, they are reordered and applied in the same order. Group communications protocols are typically needed to solve this problem.

2. Part A: For each alternative, how would the system, on receiving U(R) from a user, reconstruct the rights R that the user has and verify that the set of rights R have not been tampered with?

   The Answer: In all of the following, R' is the set of rights the system thinks the user has presented.

   1. U(R) = E(K,R)
      R' = D(K,U(R)); there is no validity check!
   2. U(R) = E(K,<R,N>)
      <R',N'> = D(K,U(R)); if the server somehow remembers the value of N that was issued, the server can detect some tampering.
   3. U(R) = E(K,<R,C(R)>))
      <R',C'> = D(K,U(R)); the server can check that C'=C(R') to detect some tampering.
   4. U(R) = <E(K,R),H(E(K,R))>
      <E',H'> = U(R); the server can check that H'=H(E') to detect some tampering, then use R'=D(K,E').
   5. U(R) = <R,H(R)>
      <R',H'> = U(R); the server can check that H'=H(R') to detect some tampering.
   6. U(R) = <R,N,H(<R,N>)>
      <R',N',H'> = U(R); the server can check that H'=H(<R',N'>)> to detect some tampering; if the server somehow remembers the value of N that was issued, the server can detect some tampering.

   Part B: For each of the above, what must the user accomplish in order to defeat the system?

   The Answer:

   1. U(R) = E(K,R)
      The system will accept any X as a valid set of rights; furthermore, if the set of possible access rights is small, as is typical of real systems, the user may empirically determine which value of X confer which rights.
   2. U(R) = E(K,<R,N>)
      If the server somehow remembers the value of N that was issued, the user must make a brute force search over possible values of U to find one that is valid. Additionally, if K is fixed, the user may be able to crack the cypher through examination of large numbers of encrypted rights and thaking advantage of the fact that the plaintext of R is known (since it can be inferred from the set of allowed operations).
   3. U(R) = E(K,<R,C(R)>))
      This system will not accept any X as valid, but the set of possible values of U(R) has the same size as the set of possible values of R, and this is usually a small set, so the user can easily collect all possible values and empirically determine which confirs what.
   4. U(R) = <E(K,R),H(E(K,R))>
      The user can compute H(E(K,R)); thus, this system is no harder to crack than the first system. Furthermore, the set of possible values of U(R) still remains the same size as the set of possible values of R.
   5. U(R) = <R,H(R)>
      Again, the set of possible values of U(R) is the same size as the set of possible value of R.
   6. U(R) = <R,N,H(<R,N>)>
      Here, the user can easily compute H(<R,N>), but if the system somehow maintains a record of the correct value of N, the user must guess this to forge an access right.

   Part C: There is something fundamentally wrong with all of the above alternatives. What?

   The Answer: None of the above schemes provided the system a way to unbreakably associate a set of rights with the identity of an object. This was hinted at by the comment: ``If the system somehow can remember the value of N that was issued.''

   In fact, this can be solved for the those schemes that use N by breaking N into two fields, where one is used to identify the resource to which the rights apply and the other is used by the server to check for validity. In this case, scheme 6 fails to be secure because the plaintext of N is disclosed to the user, and scheme 2 is dangerous if the user manages to crack the encryption. On the other hand, if scheme 6 is modified to only disclose the resource identifier and not the validity check, it can be used as the basis of a secure system.