Homework 1

CS255, Spring 2006

Due: Thursday, May 4th

Problem 1

(b) Can you adapt the LibSafe mechanism to work in the heap? If so explain how and what additional functionality you would need from the memory manager. If not, explain why not.

(c) Suppose the OS marks the stack memory pages as non-execute. Can a stack overflow be used to get a root shell on the machine? If so, briefly explain how. If not, explain why not.

Problem 2

A vulnerability in the Bourne Shell, discovered in late 2000, allowed arbitrary writing to files. The problem involves  insecure creation of files in the /tmp directory. When using redirection, files are created in the /tmp directory without first checking for existence of the file. This enables a symbolic link attack that may corrupt any file that is writable by the owner of the redirecting shell. Here is some example code illustrating the problem. (Redirection <<word causes a command's standard input to come from.standard input,  until word appears on a line by itself.)

/tmp# echo 'hello world' > rootfile
/tmp# chmod 600 rootfile
/tmp# ln -s rootfile sh$$
/tmp# chown -h 666.666 sh$$
/tmp# ls -l rootfile sh$$
-rw------- 1 root root 12 Oct 29 03:55 rootfile
lrwxrwxrwx 1 666 666 8 Oct 29 03:56 sh12660 -> rootfile
/tmp# cat <<BAR
? FOO
? BAR
FOO
o world
/tmp# ls -l rootfile sh$$
/bin/ls: sh12660: No such file or directory
-rw------- 1 root root 12 Oct 29 03:56 rootfile
/tmp# cat rootfile
FOO
o world
/tmp#

Explain the contents and relation between the two filenames used before the cat command.

Explain what cat << BAR seems to be doing and say why this is a problem.

Problem 3

(a) Race conditions are a common problem in operating system protection mechanisms. An easy example involves Unix symbolic links, which contain a path and are resolved at access time. To avoid problems with symbolic links, a programmer may write code with the function of the following pseudo-code:

    lstat (myfile, sb);

      if (sb is not a symlink) {

          rm myfile;

      }

The lstat command returns the status of a symbolic link. The purpose of the test is to make sure that the rm command is not applied to a symbolic link. However, there is a race condition here. Explain how another program running in parallel could cause this program to delete an arbitrary file.

(b) Explain generally why race conditions are an issue in system call interposition tools such as Janus. 

Problem 4

Here are some desirable properties for cryptographic hash functions:

These properties below are generally considered prerequisites:

• Preimage resistant: given h it should be hard to find any m such that h = hash(m).
• Second preimage resistant: given an input m₁, it should be hard to find another input, m₂ (not equal to m₁) such that hash(m₁) = hash(m₂).
• Collision-resistant: it should be hard to find two different messages m₁ and m₂ such that hash(m₁) = hash(m₂).

For each of the following applications of hash functions, explain which of these three properties are needed and which are not.

(a) Alice poses to Bob a tough math problem and claims she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, appends some random bits, computes its hash and tells Bob the hash value (keeping the solution secret). This way, when Bob comes up with the solution himself a few days later, Alice can verify his solution but still be able to prove that she had a solution earlier.

(b) Passwords are stored in a password file, in hashed form. To authenticate a user, the password presented by the user is hashed and compared with the stored hash. A user who gains read access to the password file should not be able to log in by this method. (Assume that the mischeivious user does not modify the system in any way before trying to log in.)

(c) A system administrator, concerned about possible breakins, computes the hash of important system binaries and stores the hash values in a read-only file. A program periodically recomputes the hash values of the files containing the system binaries, and compares them to the stored values. A malicious user who is able to overwrite one of the "protected" files should not be able to change the file without detection.

(d) Cryptographic signatures are produced by computing a hash of a message, then applying a signature function to the hash of the message. Suppose Eve has a list of messages m₁,...m_n, and their signatures computed using Bob's signing key, but does not have Bob's signing key. Assuming that the signature function is not susceptible to attack, it should not be possible for Eve to present Bob's signature on any message other than m₁,...m_n.

(e) Suppose that Eve works for a Certificate Authority. She does not have access to the special harware that computes digital signatures, but she knows the hash function. In addition, Eve can get messages signed, but every message that is signed automatically goes into a log file that Eve cannot change. Eve should not be able to produce a certificate signed by the Certificate Authority that does not appear in the log file.

Problem 5

Recall that modern processors have an on chip data cache (called an L2 cache) used to reduce the number of accesses to main memory. Reading from the L2 cache is about 10 times faster than reading from main memory. Explain how the L2 processor cache can result in a covert channel on the local system. Give a sample short (pseudo) code to exploit this channel.
Hint: use memory access timing information.