Homework 2

Due Date: February 2, 1999
Points: 200

  1. (20 points) Consider an RSA system in which p = 97, q = 109, and e = 865. Please determine the ciphertext corresponding to the messages M = 124, M = 506, and M = 321.
  2. (20 points) An iteration attack on the RSA cipher is one in which repeated encipherings of the ciphertext produce the plaintext. Consider the ciphertext C = 3, n = 25, and e = 17. Please show that this message can be broken with the iteration attack.
  3. (20 points)A protected subsystem is a subject that is invoked by other subjects, and acts on their behalf. It is typically constrained, so that it can alter local variables and parameters, but nothing else (including other global information). Please extend the access control matrix model discussed in class to allow for the explicit existance of protected subsystems. To enter a protected subsystem S, use the primitive enter S with parameters (o1, r1), ..., (on, rn), where oi is an object that the subsystem can access and ri the set of rights that the subsystem may use to access oi; to exit the protected subsystem, use the primitive exit S with parameters (o1, r1), ..., (on, rn). In your answer, define each of these operations in terms of the changes they induce on the access control matrix at the time of entry and of exit.
  4. (40 points)This question uses the Take-Grant model. Consider a graph G0 with two subjects x and y connected by a path composed of one or more objects with only take and grant edges between them. In G0, y has [[alpha]] rights over an object z. Prove from the definition that can*share([[alpha]], x, z, G0) is true if, and only if, the path between x and y is a bridge. (Note: you may not use Theorem 6.12. Hint: Consider using induction on the length of the path between x and y.)
  5. (30 points) Consider the following situation: a site security policy states that: (1) it includes all general rules of conduct for the college; and (2) each user's account is private. Tom, a student in a literature class, turned in a paper on Aristotle's Ethics. His teacher, Jenny, remembered that another student, Anna, had turned in a very similar paper a year ago, when she last taught the class. Jenny logged into the computer system and looked in the publicly readable areas of Anna's account. Jenny found the exact same paper. Jenny referred the student to the university disciplinary committee for plagiarism. Both Anna and Tom filed charges against Jenny, arguing that she had no right to look in Anna's account without permission.
    1. Assume that the college's overall policy forbids plagiarism, either by copying or by allowing copying to occur. By this standard, should Tom and/or Anna be held guilty of violating the security policy (and the college's policy against plagiarism)?
    2. Did Jenny breach security at any time during this incident?
    3. What do you think should happen to all parties, and why?
    (Note: This incident is fictionalized a bit, but really happened - no, not at UC Davis!)
  6. (70 points) This continues our penetration testing of lassen. In the last exercise you hypothesized flaws in the system's networking implementation. Now it is time to test them!
    1. In each of your three vulnerability descriptions was a short item about how to test for the vulnerability (at least, there was supposed to be!) Expand each of these into a full description, as follows:
      your name;
      server with the vulnerability;
      how to verify the vulnerability in the absense of source code (if an "attack program" is required, you may use pseudocode to describe the attack program). Be very detailed here; what would "correct" behavior be, and what would erroneous behavior be? If you did this in the previous assignment, you may repeat it here, but please be sure that any competent programmer could reproduce what you plan to do.
      effects of exploiting the vulnerability; would you gain access? would you simply deny service or affect the response speed?
      disruptions caused by exploiting the vulnerability: would you interfere with normal use of the network? Could you accidentally (or intentionally) interrupt or disrupt others' use of the network, or others' systems?
      Please post your description to the newsgroup ucd.class.ecs253.d. Also, as your classmates post this information, please consider their posts and see if they suggest other vulnerabilities or exploits. Post that, too.
    2. If possible, check to see if the vulnerability exists. Act ethically - if disruptions could occur other than to the users of lassen, don't launch the attack!!!

Extra Credit

  1. If messages are enciphered using the RSA system, determined for the modulus n = pq (where p and q) are primes, and the public key is e, then there are (1 + gcd(e-1,p-1))(1 + gcd(e-1,q-1)) messages that are unconcealable (i.e., the ciphertext is the plaintext message itself). Please prove this theorem.
  2. Consider the set of messages that are idempotent in the set Zn (that is, m2 = m mod n). Please prove that the ciphertexts corresponding to these messages in an RSA system with modulus n are the messages themselves, regardless of the choice of public key.

You can get this document in ASCII text, Framemaker+SGML version 5.5, PDF (for Acrobat 3.0 or later), or Postscript.
Send email to cs253@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562

Page last modified on 1/24/99