CS 431 homework assignment #3

This homework assignment is due on October 22 (the day of the midterm).

Backgound material for problem 1

Recall the definition of a Feistel block cipher: It operates on 2n-bit blocks, consisting of two n-bit half-blocks L and R (left half and right half). A single round consists of the following operations to derive (L_i,R_i) from (L_{i-1},R_{i-1}):

  L  = R
   i    i-1

  R  = L    XOR f(R   , K )
   i    i-1        i-1   i

This is repeated for r rounds. The input block is called (L₀,R₀), and the output block is called (L_r,R_r). At round i there is a k-bit round key K_i, and the function f maps takes an n-bit argument and a k-bit argument, and produces an n-bit result.

     n    k     n
 f: Z  x Z  -> Z
     2    2

Problem 1

Define a Feistel block cipher as follows. Use n=32 for the half-block size, and r=2 rounds, and use independent 32-bit round keys K₁ and K₂ (for a total key size of 64 bits). Define the combiner function f by f(A,K) = A XOR K (the bitwise exclusive or function).

a) describe an efficient known plaintext against this cipher that will recover the secret key.

b) Carry out the attack on the plaintext/ciphertext pair (in hex notation)

 p = fa621f3e 35819fa2
 c = 67b19d51 53173901

(you may find this easiest to do with a program).

Problem 2

Suppose party A wants to send a large confidential file to multiple recipients, namely parties B, C, and D - all of whom have RSA key pairs. The file is to be sent encrypted, such that no party other than A, B, C, or D can determine its contents by monitoring the transmission. Rather than send separate messages to B, C, and D, A wants to generate only one message containing only one encrypted version of the file contents. How can this be accomplished?

Problem 3

a) what happens if the output of the mangler function f(R,K) in DES produces an output of all zeros?

b) for a fixed right hand side R_{i-1} in DES, how may choices are there for the round key K_i for which the output f(R_{i-1},K_i) will produce an output of all zeros?

c) for a fixed round key K_i, how may choices are there for the right hand side R_{i-1} for which the output f(R_{i-1},K_i) will produce an output of all zeros? NOTE: Your answer cannot be given in any simple form, but what can you say about the number of such values? Also, how many are there when the input K_i is all zeros? In case it helps you to analyze it, here are the S boxes of DES and here is the expansion function E.

Return to the CS431 page.