CS 538 - Homework 3

                                                                                                                           CS 538
                                                                                                                           Spring 1999

                              Assignment 3


Date Due:  Thursday, March 4

Reading:  Chapters 4 and 5,  pages 114-190.

Problems:


1. (a). Page 110, #3.2.

(b). What does part (a) say about the exhaustive key search algorithm
for breaking DES ? In particular can it be used to cut down on the 
size of the space you need to search in order to find the key ? 

2. (a). # 3.3(a) on page 110

(b). Do # 3.3(b) on page 110, but only for the first 2 keys which are 
given there. 

3. #3.5 on page 110

4.(a) Assume that we are using the DES algorithm with one 
fixed key K. Is the encoding function for this algorithm
onto ? That is, is each of the $2 sup 64$ of the bit strings
of length 64 an encoding of some plaintext string ?
Explain your answer.

(b). Now assume we are give a plaintext string P and a ciphertext 
string C, each of 64 bits. Is there always a key k such that
DES with key k encodes  P into the ciphertext C ?
Justify your answer. 

5. If you want to strengthen DES triple DES is a good candidate.
However, triple DES is only defined in EBC mode. Two possible
CBC mode definitions of triple DES are pictured below, one loop CBC,
and three loop CBC. 

i. Which if the two would you choose for security ? Why ?

ii. Which if the two would you choose for performance ? Why ?


One loop CBC:

          Pn
          |
          |
          |
          v    
         x-or <----
          |       |
          |       |
       --------   |C(n-1)
K1,K2->|  EDE  |  |
         ----     |
          |       |
          |-------|
          |
          v C(n)


Three loop CBC:



          Pn
          |
          |
          |
          v    A(n-1)
         x-or <---|
          |       |
          |       |
          v       |
         ----     |
  K1 ->|  E   |   |
         ----     |
          |       |
          |-------|
          |
          | A(n)
          |
          v     B(n-1)
         x-or <---|
          |       |
          |       |
          v       |
         ----     |
  K2 ->|   D  |   |
         ----     |
          |       |
          |-------|
          |
          | B(n)
          |
          v     C(n-1)
         x-or <---|
          |       |
          |       |
          v       |
         ----     |
  K1 ->|   E  |   |
         ----     |
          |       |
          |-------|
          |
          v C(n)