Massachusetts Institute of Technology Handout 36.857: Network and Computer Security February 18, 2009Professor Ronald L. Rivest Due: March 2, 2009Problem Set 2This problem set is due via email, to [email protected] on Monday, March 2 by the beginning of class.You are to work on this problem set in groups of three or four people. You should have received anemail with your group assignment for this problem set. If not, please email [email protected]. Be surethat all group members can explain the solutions. See Handout 1 (Course Information) for our policy oncollaboration.Homework must be submitted electronically! Each problem answer must appear on a separate page. Markthe top of each page with your group member names, the course number (6.857), the problem set numberand question, and the date. We have provided templates for LATEX and Microsoft Word on the course website(see the Resources page).Grading and Late Policy: Each problem is worth 10 points. Late homework will not be acceptedwithout prior approval.With the authors’ permission, we will distribute our favorite solution to each problem as the “official”solution—this is your chance to become famous! If you do not wish for your homework to be used as anofficial solution, or if you wish that it only be used anonymously, please note this on your homework.Problem 2-1. MAC AttackAlice and Bob work at different branches of the super-secure Nottingham Stargazer’s Association, and haveneed, from time to time, to send each other authenticated but non-confidential messages about their recentdiscoveries. They know, having taken 6.857 when they were both at MIT, that they need a “messageauthentication code,” or MAC. They agree on the following procedure for computing a MAC of a messageM, given a 128-bit key K. The procedure uses AES with 128-bit keys and 128-bit message blocks. LetAES(K, B) denote the encryption of the 128-bit plaintext block B with the 128-bit key K.The procedure first extends the message to a length that is a positive multiple of 128 bits by appending a1 to the end of M, then appending just enough 0 bits to make its length a mutiple of 128. (This is called“padding”.) Let M1, M2, ..., Mndenote the resulting 128-bit blocks of PAD(M).To compute MAC(K, M):1. Let V = K2. For i = 1, 2, ..., n:(a) Let V = AES(Mi, V )3. Return V as the output value of MAC(K, M )Here the message blocks Miare used as keys in the AES calls.(a) Do you believe that this MAC procedure is a good one? Explain why or why not.Alice and Bob decide to add a checksum to their MAC procedure. After padding the message, the 128-bitchecksum C = M1⊕ M2⊕ ... ⊕ Mnis appended to the message. The new message M1, M2, ..., Mn, C istreated just like an n + 1 block message for the rest of the MAC procedure.(b) Does the checksum improve the security of this MAC procedure? Why or why not?Problem 2-2. Truncated-Key AESLet AES(K, M) denote the standard AES encryption algorithm with a 128-bit key K and a 128-bit messageM.2 6.857 : Handout 3: Problem Set 2Let AESs(K, M) denote a derived function AESs(K, M) = AES(0128−s||K, M) where K is an s-bit key and|| denotes concatenation. Thus AESsis similar to AES, except that it only has s-bit keys (since the first128 − s bits are forced to be zero.)Let Es(K, K0, M ) denote the “double encryption” of the 128-bit message M using two s-bit keys K and K0:Es(K, K0, M ) = AESs(K0, AESs(K, M)).Your group has been assigned a plaintext ciphertext pair (Ps, Cs) for s = 1, 2, ..., 64, i.e. Cs= Es(Ks, K0s, Ps)for some unknown pair of s-bit keys (Ks, K0s). You should have received the (Ps, Cs) pairs as an attachmentto the email with your group assignment.Find (Ks, K0s) for the largest value of s that you can. Turn in these key values together with your programfor finding them. Explain the time and memory resource usage of your program as a function of s. Is timeor memory the most limiting resource?(We have posted code for generating the (Pi, Ci) pairs to help you program calls to AES, etc. This code isposted on the course site under “Resources.”)Problem 2-3. Ben’s Block CipherBen Bitdiddle proposes the following block cipher. Ben’s cipher operates on 128-bit input blocks and produces128-bit output blocks.Let In= 0, 1, ..., n − 1. A key K consists of three parts (p, S, q):• A permutation p of I128. (i.e., p[i] ∈ I128for all i ∈ I128, and p[i] 6= p[j] if i 6= j.)• A invertible byte-substitution table S that maps I256to itself one-to-one. That is, S maps every possible“input” byte to exactly one “output” byte. (Such a table is known as an S-box and is a favorite tool ofcryptographers.)• A second permutation q of I128.The block cipher E works as follows, on an input message bit vector M [i], i = 0, 1, ..., 127:1. The bits are permuted according to p: R[i] = M [p[i]] for i = 0, 1, ..., 127.2. The bits of R are grouped into bytes in T0, T1, ..., T15.3. Each byte Tiis replaced by S[T [i]], yielding byte sequence U0, U1, ..., U154. The bytes are interpreted as a bit sequence again; call this sequence V [i] for i in I128.5. The bits are permuted according to q: C[i] = V [q[i]] for i in I128.6. C[0...127] is the output ciphertext.(a) In Ben’s scheme, there are many equivalent keys. These keys have different values for p, S, and q, butproduce the same ciphertext for any given plaintext. Describe how to generate all keys equivalent toa given key (p, S, q).(b) Describe a chosen-plaintext attack on Ben’s cipher that recovers the unknown key (p, S, q) or anequivalent
View Full Document
Unlocking...