Assignment 7, due Apr 1

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: Here is a dangerously weak encryption program.

   /* crypt key */
   /* dangerously weak encryption program */
   #include <stdio.h>
   #include <stdlib.h>
   
   int main( int argc, char * argv[] ) {
           long int key;
           char * endptr;
           if (argc != 2) {
                   fprintf( stderr, "%s requires one argument\n", argv[0] );
                   exit( EXIT_FAILURE );
           }
           key = strtol( argv[1], &endptr, 10 );
           if ( *endptr != '\0' ) {
                   fprintf( stderr, "%s argument must be integer\n", argv[0] );
                   exit( EXIT_FAILURE );
           }
           srandom( key );
           { /* now copy input to output through crypt transformation */
                   char ch;
                   while (!feof( stdin )) {
                           putc( (getc(stdin) ^ random())&0xFF, stdout );
                   }
                   fclose( stdout );
           }
   }
   

   a) Identify the class of cryptographic mechanism being used here? Is it a block cypher, a stream cypher, a symmetric key cypher, a public key cypher or what? You may need to look at the man pages for the subroutines called here. (0.5 point)

   b) If the cyphertext was encrypted like this: crypt 121 <plaintext>cyphertext
   What command would you use to recover the plaintext? (0.5 point)

   c) How big is the encryption key for this code, in bits? (Several parts of this code use different numbers of bits, so you have to find the bottleneck that determines the actual size. You may need to read the man pages on the different subroutines that get called.) (0.5 point)

   d) A careful reading of the man pages for the functions does not fully define how to exploit a larger key, but there is sufficient information in the man page to clearly identify the potential, in the subroutines used here, to use a larger cryptographic key. How big is the largest key that this code has the potential to utilize? This would involve using the same basic cryptographic algorithm, with only the initialization code changed. (0.5 point)

2. Background: The Amoeba system suggests how a web site could prevent visitors from meaningfully tampering with cookies that the site plants on visitor's computers. Assume that the web server has a good database system maps keys to associated data in the main table. The purpose of cookies held by the visitors are to serve as handles on data in the main table, so ultimately, each cookie holds the key associated with a database entry. However, you want to prevent users from altering or forging cookies. Of course, you cannot prevent alteration or forgery, you can only make it extremely likely that the alteration or forgery will destroy the value of the cookie.

   To protect the cookie, you may include additional keys in it, and you may use secondary tables in the database to associate those keys with other information. Assume the following primitive operations are available on the server:

   1. lookup(key,table) returns an item from a database table.
   2. set(key,table,item) sets an item in a table in the database.
   3. oneway(x) a one-way one-to-one and onto function.
   4. hash(x) a hash secure hash function
   5. random() returns a random value

   For the purpose of this problem, you aren't constrained by any particular type system. Just assume that variables can represent cookies and keys and database items, and that items can be used to hold cookies and keys if that is needed.

   a) Outline the implementation of a function make_cookie(k) that returns a cookie you could safely give a user. (1 point)

   b) Outline the implementation of a function unmake_cookie(c) that takes a cookie and returns the associated k if the cookie was valid, and raises an appropriate exception if the cookie is not valid. (1 point)

3. Background: The classic DES symmetric key cypher has a key size of only 56 bits (8 bytes of 7 bits each) to encrypt blocks of 64 bits each. The AES symmetric key cypher supports key sizes of 128, 192 and 256 bits to encrypt blocks of 128 bits each. To gain security comparable to DES with the RSA public key cryptosystem, the key size must be 1024 bits, and to gain security comparable to AES, DES keys may need to be 2K bytes long.

   a) If the data block being encrypted is only 128 bits, how could it possibly be meaningful to use a 256 bit key? (Hint: It may pay off here to think in terms of an encryption function on a block of n bits as a permutation on a set of 2ⁿ elements. Also, consider some basic discrete math about the size of the set of permutations of a set.) (0.5 points)

   b) Why must DES keys be so much bigger than the keys used for symmetric key cyphers offering the same security? (0.5 points)