Assignment 7, Solutions
Part of
the homework for 22C:169, Spring 2011

/* 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 exclusiveors 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^{31}  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.
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:
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 }
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^{n} elements. Also, consider some basic discrete math about the size of the set of permutations of a set.) (0.5 points)
Encrypting of an nbit value replaces one of 2^{n} values with a different value from the same range. The replacement is a permutation over 2^{n} 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 nbit value selects one of 2^{n}! (that is, 2^{n} 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 Nbit key to a symmetrickey 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.