Assignment 7, due Apr 2

Part of the homework for 22C:169, Spring 2010
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday), and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

  1. Background: The posted solutions to the midterm exam include this wrapper for launching a Unix shell script with the set UID bit, defeating the disabling of the set UID bit in the underlying system.
            /* wrapper for shell script.
               The setuid bit can be set on the executable of the wrapper file */
            #include <unistd.h>
            int main(int argc, char* argv[]) {
                    execve( "script", argv, envp );

    In their solutions to the exam, many students proposed the following alternative wrapper:

            /* wrapper for shell script.
               The setuid bit can be set on the executable of the wrapper file */
            #include <string.h>
            #include <stdlib.h>
    	#define LEN 4096
            int main(int argc, char* argv[]) {
    		char command[LEN];
    		int i;
    		strncat( command, "script", LEN );
    		for (i = 1; i < argc; i++) {
    			strncat( command, " ", LEN );
    			strncat( command, argv[i], LEN );
                    system( command );

    In the remainder of this problem, ignore the problem of LEN. Yes, this constant is a problem, but the problem can be solved by the simple expedient of computing the length of all the strings to be concatenated and then dynamically allocating the command buffer to be that big before starting to concatenate everything.

    Note that parameter validation code could be added to either of these, and most of this code would be the same.

    a) Does one of these pose a potential problem that the other does not? Explain the problem, and give an example. (0.5 points)

    b) What kind of extra parameter validation code would you write to detect and prevent the problem described above? (0.5 points)

  2. Background: The developers of the Rijnland Internet Election System (at Radboud University, Nijmegen, Netherlands) had to solve a number of problems. At the close of the polls on this system, the ballot box is published, so all voters can check that their encrypted ballots are present. After a suitable delay, the codebook for decrypting the ballots is published, so everyone can decode all the ballots and verify that the official result is correct. One obvious way for a dishonest government to change the election result is to adjust the codebook to produce the desired election result before publishing the codebook.

    Note that publication is a powerful tool for establishing that a document existed at a particular date. Publishing the ballot box and publishing the codebook make it very difficult for an attacker after the date of publication to attempt to claim that a different version of the document is authentic.

    a) How can the government use a cryptographically secure hash function to prove that it has not changed the codebook since the start of the election? (0.5 points)

    b) Is publication on a web site as strong a defense as publication on paper? Why or why not? What is it about paper or the web that makes one of these stronger? (0.5 points)

  3. Background: The RIES system encrypted ballots as follows: Each candidate had a unique candidate number. Each voter was issued an encryption key in order to authorize that voter to cast one ballot. To vote for candidate x using key k, the voter would submit a ballot containing the value f(x,k), where f is a one-way function. In RIES, the hash function and network protocols required to cast a ballot were disclosed by embedding them in a client-side web applet. The codebook published at the close of the polls listed, for each candidate x, the values of f(x,k) for all valid keys. The actual values of the keys distributed to the voters is not retained after keys distribution.

    a) Imagine that you successfully steal a copy of the codebook from the election authority. Is there any attack you could carry out using the codebook if it contained keys that you could not carry out if you did not have the keys? (0.5 points)

    b) Does publishing the codebook and ballot box contents threaten the voter's right to a secret ballot? (0.5 points)

    c) If you were a RIES voter and I offered to pay you to vote for a particular candidate, how could you prove to me that you had carried out your side of the bargain? (0.5 points)

  4. Background: The Amoeba system uses one-way functions in several places. Here, we are concerned about the possibility that someone might find a way to invert one of these hash functions.

    a) Suppose someone figured out how to invert the one-way function that maps a server's private ID to its public ID. What could a malicious user do with this? Explain how! (0.5 points)

    b) Suppose someone figured out how to invert the one-way function used to compute the check field on capabilities. What could a malicious user do with this? Explain how! (0.5 points)

  5. Background: Classical work on distributed operating systems imagined that process migration from one machine to another would be automated by the system.

    A Question: How does Amoeba's view of process migration differ from this? (0.5 points)