Assignment 7, Solutions

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

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)

It is a symmetric key stream cypher.

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

Because it exclusive-ors the key stram with the data stream, the identical command will decrypt:
crypt 121 < cyphertext > plaintext

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)

The key is declared as a long int, using strtol() to extract its value from the textual argument, but when it is passed to srandom(), it is used as an unsigned int. This means that it is highly unlikely to be more than 32 bits and (due to the vague definition of int in C) it could be as small as 16 bits.

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)

The period of the generator is guaranteed to be about 16 × (2³¹ - 1)
This suggests that the state of the generator ought to be at least 16 words of 31 bits each, probably represented as 64 bytes but only containing 62 bytes of information.
The discussion of initstate() and setstate() both also suggest that the internal state of the generator big, stating that there are "optimal" values for the size of the state array that range from 8 to 256 bytes. The documentaiton does not explain more, but it is reasonable to assume that the default state is 64 bytes long.
It is highly likely that alternative versions of setstate() or initstate() could be written that used keys that were on the order of the same size as the state array. For the default state, this is 62 bytes.
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)
We assume that, in addition to the main table, we maintain a secret table. Cookies will be represented as tuples containing a key k and a hashed secret ts.
```
make_cookie( k ) {
    secret = random()
    set( k, secret_table, secret )
    return( make_tuple( k, oneway( secret ) ) )
}
```
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)
```
unmake_cookie( c ) {
    k, ts = unmake_tuple( c )
    secret = lookup( k, secret_table )
    if oneway( secret ) = ts
        return k
    else
        gripe loudly about an invalid cookie
}
```
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)

Encrypting of an n-bit value replaces one of 2ⁿ values with a different value from the same range. The replacement is a permutation over 2ⁿ values, and if there are x values in a range, there are x! (that is, x factorial) permutations of that range. Thus, the key used to encrypt an n-bit value selects one of 2ⁿ! (that is, 2ⁿ factorial) permutaitons. It takes many more than n bits to select an arbitrary permutation from among the set of all permutations!

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

This problem is totally nonsense. Nobody asked a question about it. Did anyone read it and notice the typo?
The question was supposed to read: "Why must RSA keys be ..."
The answer to that question is straightforward. Typically, in an N-bit key to a symmetric-key cypher, all possible combinations of N bits are allowed. In contrast, RSA keys have special restrictions related to the pair of prime numbers that were selected during the creation of the cypher. The set of bit patterns that are legal keys for use with any particular set of primes is very sparse.