##
This **preview** shows page *1*
out of 2 **pages**.

*View Full Document*

End of preview. Want to read all 2 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

CPSC/ELEN 689 Topics in Network SecuritySpring 2004Homework 1Due: Tuesday, February 24, before classPlease give concise answers, and type them neatly.Problem 1 Alice and Bob want to check whether they share the same secretkey. Alice generates a random bit string r of the same length as the key, xors itwith the key and sends the resulting bit string s to Bob. Then Bob xors his keyto s and sends the resulting random string back to Alice. Alice checks whetherthe string that she has received from Bob coincides with the string r that shehad created. Alice announces the result of her comparison. Is there a flaw inthis scheme?Answer this question in 1-2 sentences.Problem 2 In the lectures, we have encountered the birthday paradox severaltimes; this exercise allows you to discover some background information.Suppose we want to find a collision of a good cryptographic hash function hthat can produce v possible values. So our goal is to find two messages m andm0such that h(m) = h(m0). We randomly choose sufficiently long messagesm1, m2, . . . and compute their hash value. A good cryptographic hash functionproduces uniformly distributed values in such a case. The probability that nocollision occurs among the n values is approximatelyPr[h(m1), . . . , h(mn) take all different values] ≈ e−n2/2v,assuming that v À n.Let nmeddenote the median of the number of the trial on which the firstcollision occurs. We can define this number nmedby the relationPr[h(m1), . . . , h(mnmed) take all different values] = 1/2.Your task is to show that nmed≈ 1.2√vTo get a feeling for the power of collision attacks, check out the neat applet athttp://www-stat.stanford.edu/~susan/surprise/Birthday.htmlProblem 3 Take a graylevel image of 8 bit depth in pgm format (or some othersimple image format that directly represents the gray values without compli-cated encoding). Take DES and encrypt the image (a) using electronic codebook(ECB) mode, and (b) using cipher block chaining (CBC) mode. Include origi-nal, ECB and CBC mode images in your document, that is, visualize the resultof your experiment. Explain the result of your experiment in technical terms,and explain the cryptographic relevance. Your answer should not exceed 3-4sentences.You can use, for example, the cryptographic library contained in opensslfor this experiment, www.openssl.org. Incidentally, this library is interestingsince it contains implementations of all cryptographic primitives that we havediscussed so far.Breaking a Feistel Cipher. The following problems discuss a small single-round Feistel cipher that operates on a block of 64 bits. The plaintext is splitinto two blocks left and right of equal size. The left part is replace by left= left ⊕f(K, right). The function f consists of an expansion function thatreplicates bits of right, an xor of the key, followed by nonlinear S-boxes. Itis similar to a single step in DES, but the permutation after the S-boxes isomitted.The source code realizing the cipher is available from the course web page(but the key settings k[0],...,k[7] are different). And an executable it avail-able as well.Problem 4 Draw the expansion function that maps 32 bits into 48 bits. Youcan omit the middle part, but give enough detail so that input bits 1-6 and26-32, and all their output bits are covered.Problem 5 (a) Determine an input difference of f that affects just the S-boxS2=S[1], and no other S-boxes. (b) Tabulate the XOR profiles for S2 for thisinput difference. (c) Derive a characteristic of S2 for (one of) the most likelyoutput differences, given the input differences chosen earlier. (d) Find a pairof inputs satisfying the characteristics for the posted cipher. (e) Determine therestricted set of potential key settings of K[1]=K2 using your characteristicsand this input pair.Problem 6 Determine the key settings in the cipher using differential crypt-analysis. Give a (very brief!) outline how you have accomplished that (forinstance, what difference pairs have you used, and how many key settings re-mained after that).Note: Exhaustive search or other methods can be used to get the key settingsas well, but that would completely miss the point of this exercise.Reference: E. Biham, A. Shamir: Differential Cryptanalysis of DES-like Cryp-tosystems, J. Cryptology, 4(1), pp. 3-72,

View Full Document