CS 526 Fall 2004

 

Assignment 3 Solutions

 

Note: The points add to 8.0 for a correct homework.

Please see Ferit Erin for any questions about grading and answers first.

 

(3.9.1)

We want to show that multiple create commands in a sequence of commands that leak a right r are equivalent and can be replaced by a single create for safety analysis purposes.

 

A mono-operational command in our Access Control Matrix model can test for right(s) in access matrix entries A[s1, o1] and A[s2, o2] and based on the outcome can perform a primitive command that leaks a right r. If multiple creates are equivalent then we can perform the same test with entries A[s1, o1] and A[s1, o2], where A[s1, o2] is now union of A[s2, o2] and A[s1, o2], and get the same outcome for the test as before.

 

To justify the statement we consider the nature of the tests in the model. In Access Control Matrix model we only check for presence of right(s) in a matrix entry. We can not test for the absence of right(s). A test, hence, comprises of a conjunction and/or disjunction of simple primitive tests, each checks for the presence of a right in an access control matrix entry.

 

When we are considering A[s1, o1] and A[s2, o2], some of the primitive tests check for presence of a right in A[s1, o1] and others in A[s2, o2]. When we consider the same test for A[s1, o1] and A[s1, o2] = A[s1, o2] U A[s2, o2], all the primitive tests previously on A[s2, o2] will now be carried out on A[s1, o2]. The outcome of the primitive tests on A[s1, o1] will remain the same, since A[s1, o1] hasn’t changed. A[s1, o2] is now a superset of A[s2, o2] since we have added all the rights in A[s2, o2] in A[s1, o2] that were not there already (the enter command doesn’t fail if a right added already exists). Hence the tests on A[s1, o2] will also give the same output as before, since we are always checking for presence of a right. The overall output of the test will not change, since the output of constituent primitive tests hasn’t changed.

 

Let’s consider an example to clarify the argument.

 

Let A[s1, o1] = { r }, A[s2, o2] = { w } and A[s1, o2] = { x } , where r, w and x be instances of generic rights.

Let the test be check for presence of r in A[s1, o1] and w in A[s2, o2]. The test succeeds when are we considering A[s1, o1] and A[s2, o2].

 

Now A[s1, o2] is set to { w, x }. Primitive test for w in A[s1, o2] succeeds since A[s1, o2] is now a superset of A[s2, o2].

 

 

Would it be true if we check for absence of rights?

 

No. This will not work in case when we are checking for absence of a right r in A[s2, o2] and the right is not there. However, when we take the union of A[s1, o2] and A[s2, o2] and  r is present in A[s1, o2] initially, the test will succeed on the modified A[s1, o2].

 

If we consider the above example, if are testing for absence of right x in A[s2, o2]. The test will succeed on A[s2, o2] but after the union A[s1, o2] = { w, x } and the test will fail because of presence of x initially in A[s1, o2].

 

Note from TA: 1.5 points 

Standard deductions were:

  • -0.5 to -1.0 for incorrect answer.
  • -0.5            for not answering the last part of the question (Would it be true if we     check for the absence of rights?)

 

(3.9.6)

 

Dropping take will affect the expressive power of the take-grant model.

One example: If an object x has a right r, then without take command, this right r could never be obtained by others, since x could not do any operation actively(x is an object, only subjects can act).

 

Note from TA: 1.5 points 

Standard deductions were:

  • -0.5 to -1.0 for incorrect answer.
  • -0.5            for not mentioning that objects can’t do any operations

 

Problem 3:

 

Components of the ESPM:

1. Subject types - TS

2. Object types - TO

3. Rights - R

4. Can-create relations - CC

5. Link predicates - {linki}

6. Filter functions - fi

7. Create rules - CR

To model the graduate school database, these are the components:

1. Subjects: users of the database

    Subject types (TS): {s-app, s-std, s-fac, s-adm}

    Note: s-app = applicant

             s-std = student

             s-fac = faculty

             s-adm = administrator

 

2. Objects: data in the database

   Object types (TO): {o-app, o-reg, o-pos}

   Note: o-app = application

             o-reg = registration info

             o-pos = plan of study

3. Rights (R):

   Let O/r be a read right on object O

       O/w be a write/change right on object O

       every ticket O/r and O/w has the corresponding copyable ticket O/rc and O/rw, respectively.

   R(s-adm) = {o-app/r} -> an administrator can read the application, say for evaluation

   R(s-app) = {o-app/w} -> an applicant can write/change his/her application

   R(s-std) = {o-reg/r, o-pos/r} -> a student can only read his/her registration info and plan of study

   R(s-fac) = {o-reg/w, o-pos/w} -> a faculty can write/change a student's registration info and plan of study

   R(o) = {}, for o any object in TO -> an object has no right over anything

 

4. Can-create relations (CC):

   The can-create relations defines who can create what.

   {CC(s-adm,s-adm),      -> an administrator can create another administrator

    CC(s-adm,s-app),        -> an administrator can create an applicant

    CC(s-adm,s-fac,s-std),  -> an administrator and a faculty can jointly create a student

    CC(s-adm,s-fac),         -> an administrator can create a faculty

    CC(s-adm,s-app,o-app),  -> an administrator and an applicant can jointly create an application

    CC(s-adm,s-fac,o-reg),  -> an administrator and a faculty can jointly create a registration information

CC(s-fac,s-std,o-pos)   -> a faculty and a student can jointly create a plan of study}

 

5. Link predicates (linki):

   Every link predicate defines the relationship between two subjects.

   (Let E be a symbol of "an element of")

   link1(s-adm,s-adm) = true

   link2(s-adm,s-app) = o-app/r E dom(s-adm)  AND  o-app/w E dom(s-app)

                                    (an administrator and an applicant are related if:

                                     - the administrator has a read right over an application, and

                                     - the applicant has a write/change right over that application)

   link3(s-std,s-fac) = (o-reg/r E dom(s-std)  AND  o-reg/w E dom(s-fac))

                                                                        OR

                                    (o-pos/r E dom(s-std)  AND  o-pos/w E dom(s-fac))

                                    (a student and a faculty are related if:

                                     - the student has a read right over a (his/her) registration information, AND

                                     - the faculty has a write/change right over that registration information

                                    OR

                                     - the student has a read right over a (his/her) plan of study, AND

                                     - the faculty has a write/change right over that plan of study)

   link4(s-fac,s-fac) = true -> any two faculties are always related

   In this simple model, only those relationships are valid, there is no relationship between

   two other subjects besides the universal link.

6. Filter functions (fi):

   A filter function define the conditions when transfer of tickets between two subjects--

   linked by linki--can occur.

   f1(s-adm,s-adm) = T x R

   f2(s-adm,s-app) = {}

   f3(s-std,s-fac) = T x RI (a student can give a faculty a read right)

   f4(s-fac,s-fac) = T x R (a faculty can give another faculty both read and write rights)

7. Create rules (CR):

   CR(s-adm,s-adm) ->CRp = {s/rc,s/wc}

                                     CRc = {s/rc,s/wc}(administrators share all rights over any subjects)

   CR(s-adm,s-app) -> CRp = {}

                                    CRc = {} (an administrator and an applicant do not share rights)

   CR(s-adm,s-fac,s-std) -> CRp-adm = {}

                                           CRp-fac = {}

                                           CRc = {}

   CR(s-adm,s-fac) -> CRp = {}

                                   CRc = {}

   CR(s-adm,s-app,o-app) = {} (no sharing of rights in creation of an object)

   CR(s-fac,s-std,o-reg) = {} (no sharing of rights in creation of an object)

   CR(s-fac,s-std,o-pos) = {} (no sharing of rights in creation of an object)

 

Safety analysis:

The model is safe if no creation s (of a subject of an object) will leak a right r to s, for which s is not supposed to own at all. For example, in my model, an administrator does not and should not have the write/change write over a student's plan of study. If this leaking of right r happens, it will cause x/r:c to exists in the dom(s-adm), which can further transferred/shared to other subjects' domain in case of joint creation. This leaks thus can imply what rights that other subjects can have later on (either legally or illegally).

 

 

 

 

Note from TA: 3 points 

Standard deductions were:

  • -0.5 to -2.0 for incorrect or insufficient answers.

 

 

Problem 4:

Cryptography

 

There are 4 variants of oblivious transfer. The one described in class was chosen one out of 2 OT ((2/1)-OT) where Alice has 2 input bits b0 and b1, Bob chooses c and gets bc (c is either 0 or 1) and Alice does not learn c. A slight generalization of this is String-OT(2/1-OT^k) where Alice has 2 k bit strings w0 and w1 and Bob chooses c and obtains wc and Alice does not learn c. We saw that there would be problems in the scheme if the public-private key encryption used in the protocol was commutative in which Bob could get both the elements that Alice has.

Let the model for the above problem be as follows. There are 2 main entities namely the user and the seller. The user has a list of prices some of which he is willing to pay and some not. This fact about the willingness is kept hidden where are the prices are displayed. The seller can see the prices and can choose any price in an oblivious way such that the user does not learn which of his price the seller is looking at is. The fact that the choice of the seller is oblivious to the user ensures that the user does not change his willingness to pay depending on the choice of the seller. The user does not know the actual price of the seller. The seller does not learn anything about the rest of the list of user’s choices such that he can increase his price if he finds out the user is willing to pay more.

An example is as follows (The italic elements are hidden)

            User                                                                             Seller

Willing to pay | Price                                         Price of the Seller

YES                  | $100                                                 $125

YES                  | $150

NO                   | $200

The seller chooses $150 (User does not know) and at the end of the transaction since the User is willing to pay this amount there is a sale. Here there is a problem in which a greedy Seller can gain an extra $25 since he got a better offer than what he was originally selling. This can be removed by having a commitment by the Seller (for example by sending the padded, time stamped hash of the price) before the transfer is complete.

There are other problems too depending on the number of times such a transfer is being allowed to be made. A seller can start a guessing game in which he can try the highest prices and then guess his way down irrespective of the price he is offering. The User can attack the system too if there are multiple chances. He can first have all the prices with NO’s to most value and increase the price he is willing to pay depending on the sales.

There could be other problems too, inherent from the OT model itself where if the public-private key encryption is commutative the seller can know everything about the users choices.

This is similar to priceline in the sense of the user giving his own price. But here this price is what he is committed to and will have to pay it if someone is offering it. Thus there is no uncertainty about the offer. There is also information from the system about the approximate prices running for a particular product at that time. Also the user can work his way up by bidding more if required. This can be done in our model based on certain probabilities but is much harder because the user does not know which price was rejected. In priceline the closest available price is actually mailed to the user, which is not the case in this model.

 

Note from TA: 2 points 

Standard deductions were:

  • -0.5 to -1.0 for incorrect or insufficient answers.