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 cor-
responding 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 pro-
duce the plaintext. Consider the ciphertext C = 3, n = 25, and e = 17. Please show that this message can be bro-
ken 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 typ-
ically 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 a rights
over an object z. Prove from the definition that can*share(a, 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.
a. 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 col-
lege's policy against plagiarism)?
b. Did Jenny breach security at any time during this incident?
c. 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 sys-
tem's networking implementation. Now it is time to test them!
a. 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 veritfy 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' sys-
tems?
Please post your description to the newsgroup ucd.class.ecs253.d. Also, as your classmates post this infor-
mation, please consider their posts and see if they suggest other vulnerabilities or exploits. Post that, too.
b. 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
7. 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 unconceal-
able (i.e., the ciphertext is the plaintext message itself). Please prove this theorem.
8. 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.