Network Security Fall 2000: Homework 3

This homework is due by class time October 17, 2000. Note: K2/3 denotes homework problem 3 from chapter 2 of the class text. Programming problems may be done in C, C++ or Java; please do not use Perl or other scripting languages.

  1. (Programming Problem) Break a simple monoalphabetic substitution cipher automatically by, for example, computing letter frequencies across a substantial body of English-language text and possibly other techniques. You may need to automatically try several variations. Your program should recognize a correct plaintext string with high probability. Test your algorithm on the ciphertext example on p. 42.

    You may assume that all words in the plaintext are found in /usr/dict/words or can be derived from those words. Note that different versions of this dictionary may contain different sets of conjugations, declinations and abbreviations. For example, the dict files on Linux include many common extensions, like "ed", "ing", "ly", but do not include common contractions like "'re", "'ll", "'t", "'ve", which the Solaris dict files include. You can assume that the ciphertext has the same capitalization as the plaintext and that punctuation is mapped to itself, i.e., there are only 26 entries in the mapping table, not 52 or even one for each ASCII value. You may find that for short ciphertext strings such as the one in the book, techniques other than those based on letter-frequency work better. (20 pts.)

  2. (K3/3) How many DES keys, on the average, encrypt a particular plaintext block to a particular ciphertext block? (9 pts.)
  3. (K3.5) Suppose the DES mangler function mapped every 32-bit value to zero, regardless of the value of its input. What function would DES then compute? (9 pts.)
  4. (K3.6) Are all 56 bits of the DES key used an equal number of times in the Ki? Specify, for each of the Ki, which bits are not used. (9 pts.)
  5. (K3.10) What pseudo-random block stream is generated by 64-bit OFB with a weak DES key? (9 pts.)
  6. (K4.6) Why do MD4, MD5, and SHS require padding of messages that are already a multiple of 512 bits? (9 pts.)
  7. Compute the number of 64-bit encryption operations performed for an n bit plaintext using CBC, k-bit OFB and k-bit CFP. Count all encryption operations, not just operations performed on the plaintext itself. (6 pts.)
  8. Reverse the order of xor-ing and encryption in Fig. 3-27, i.e., c1 is computed as E(m1) xor IV. Does this work? Does it matter? Justify your answer using the vulnerabilities and issues identified in the book and in class. (9 pts.)
  9. (Programming problem) Implement a single round of DES and IDEA (even round) encryption. Test with the round keys 0x123456789abc for DES and 0x1234, 0x5678 for IDEA. Measure the respective execution speed of the two implementations using the time service. You only need to encrypt a single block. (You may need to execute the function more than once to get meaningful results.)

    The S boxes for DES are available. (20 pts.)

  10. (Programming problem) If your birth year is odd, measure the speed of DES, using any DES library you can find. If your birth year is even, measure the execution speed of Rijndael. Speed is measured in bytes per second processed, assuming a long text string (e.g., a 10 MB file, text or binary), read from stdin and written to stdout. Use CBC mode. Your program should be invoked as 
    time des password IV < inputfile > /dev/null
time rijndael password IV < inputfile > /dev/null
    Be sure to report which library you used, the OS, the machine type and CPU speed. On Unix, use the time mechanism. Execution times below a second are unreliable, so you will need to use a large file, such as /opt/bin/netscape (other suggestions appreciated...).

Last updated by Henning Schulzrinne