CS513 Homework 3

General Instructions. You are expected to work alone on this assignment.

Due Nov. 13 on paper at the beginning of class. Assignments may be submitted via CMS. See class information for policies on grading and late assignments.

To facilitate grading, format your solutions as follows.

Solutions that do not satisfy the formatting guidelines may be returned ungraded.


Problem 1

Simple Public Key Infrastructure (SPKI) emphasizes the use of authorization certificates as opposed to authentication, or identity, certifcates. The main idea is that, instead of attaching some identity or name to a public key, a certificate attaches an authorization to the public key.

In effect, a SPKI authorization certificate is a signed statement saying, "The principal holding the private key corresponding to public key K is allowed to perform action A."

Suppose you want to create a client-server service where requests need to be authorized. This can, for example, be a web server, where requests are HTTP GET or POST messages, or a database server, where the client is sending SQL queries.

Design a protocol using authorization certificates that will allow the server to determine whether a request should be allowed. Discuss the security properties of your protocol. In particular, consider various forms of attacks and explain why they can't succeed. (Note that these requests may modify data on the server, so even if an attacker cannot read the reply, damage can be done.)

Problem 2

Microsoft's Encrypting File System (EFS) allows users to encrypt files so that they can be decrypted by multiple principals (while preventing intruders who gain physical access to the file from reading its contents). This is done by generating a random file key kf for each encrypted file, and then encrypting this key with the public key of each user who is allowed to access the file. That is, each allowed user gets his own encryption of kf. (These encryptions are kept with the file ACL, for example.) Reading a file is simply a matter of first decrypting kf (with the user's private key), and then decrypting the file itself with kf.

The problem with this system is revocation. Once a user is granted access to a file, he essentially knows the file key kf. To revoke access to future versions of a file, one possible remedy is to use a new file key k'f, and re-encrypt the file.

If we do this, however, we would have to encrypt the new file key for every user again (excluding the revoked user, of course). If there are a lot of users, this can be inefficient. Remember, these encryptions are done with public key cryptography.

Design a scheme where we can change the file key more efficiently when a revocation occurs. That is, reduce the number of new (key) encryptions that need to be performed. Hint: Recall from class the problem of maintaining a hash value for a file. How were we able to update the hash efficiently when small changes were made to the file?

Problem 3

Classify each of the following security conditions as safety properties, non-safety properties, or non-properties, and explain why.

  1. No write access is performed on a read-only file.
  2. If a program calls setuid, it cannot call exec afterwards.
  3. Whenever a program calls mlockall, it eventually calls munlockall later on.
  4. Every time a program starts, it calls chroot with the same argument.
  5. On a call to strncpy(d, s, n), the value of n cannot depend on user input.

Problem 4

Consider the following C code:

void vuln()
{
    char sql[256];
    char *p = sql;
    char userid[64];
    char passwd[64];

    strcpy(p, "UPDATE user_accts SET passwd = '"); p += strlen(p);
    gets(userid);
    gets(passwd);
    strcpy(p, passwd); p += strlen(p);
    strcpy(p, "' WHERE userid = '"); p += strlen(p);
    strcpy(p, userid); p += strlen(p);
    strcpy(p, "'");
    db_query(sql);
}

In addition to the obvious SQL injection attacks, this function is vulnerable to stack smashing even when a canary is used. Show how an attacker, by providing appropriate input, can change this function's return address on the stack frame without killing a canary inserted to protect it.