Massachusetts Institute of Technology Handout ??6.857: Network and Computer Security October 10, 2002Professor Ronald L. RivestQuiz 1• DO NOT OPEN this quiz until instructed to do so.• You should not have more than one empty chair between you and the next person. Ifseating availability permits, do not sit directly next to another person.• This quiz is open book. You may use any of the results presented in class, in thehandouts, or in the problem sets.• There are fifteen (15) problems totaling 100 points. Problems are labelled with theirpoint values.• Put your name on the top of every page – these pages may be separated for grading.• Write your solutions in the space provided. Should you need extra space, write on theback of the sheet containing the question.• Be neat and write legibly. You will be graded not only on the correctness of youranswer, but also on the clarity with which you express it.Problem Q1-1. [4 pts]Fill in your name and the names of the people sitting next to you. If you are at the end ofa row, write ⊥ in the space provided.Your name:Name of person to your right:Name of person to your left:Handout ??: Quiz 1 Name: 2DO NOT WRITE ON THIS PAGEProblem Grade PointsQ1-1 4Q1-2 4Q1-3 4Q1-4 7Q1-5 12Q1-6 14Q1-7 5Q1-8 4Q1-9 5Q1-10 3Q1-11 7Q1-12 13Q1-13 6Q1-14 4Q1-15 8Total 100Handout ??: Quiz 1 Name: 3Problem Q1-2. [4 pts]For a parallel computer (which can do many operations simultaneously) programmed toperform CBC mode encryption (circle the correct answer):1 Encryption is faster than decryption.2 Decryption is faster than encryption.3 Encryption and decryption should run in approximately the same time.Problem Q1-3. [4 pts]Circle true or false for the following statements. If P = N P, then:True False The one-time pad still provides information-theoretically securemessage authentication.True False Secure encryption becomes impossible.True False Shamir’s secret-sharing technique becomes insecure.True False One-way functions do not exist.Handout ??: Quiz 1 Name: 4Problem Q1-4. [7 pts]Circle true or false for the following statements:True False Alma Whitten’s experiments show that PGP 5.0’s graphical user inter-face is not sufficiently effective to provide security for most users.True False The WSJ cookie authentication scheme was insecure because of sequen-tial session IDs.True False A cryptographically secure hash function h : Σ∗→ Σk(OW, CR) mustbe injective.True False Triple-DES uses uses three unique 56-bit DES keys.True False Consecutive Fibonacci numbers are the worst-case input for Euclid’sAlgorithm.True False The El Gamal encryption scheme is plaintext-aware.True False To make a deterministic public-key encryption scheme secure againstan adaptive chosen ciphertext attack, it suffices to pad the given plain-text with some random bits before encryption (such random bits beingdiscarded upon decryption).Handout ??: Quiz 1 Name: 5Problem Q1-5. [12 pts]Consider the following generalization of Lamport’s one-time signature scheme, for signing avalue m, where m is drawn from a finite set {1, 2, . . . , t} for some t > 2.The use-once portion of the key used to sign m consists of two values x0and y0. Here x0and y0are the roots of hash chains of length t + 1. That is, xi= h(xi+1) for 0 ≤ i < t andyi= h(yi+1) for 0 ≤ i < t, where h is a one-way hash function.To sign m, where 1 ≤ m ≤ t, the signer reveals both X = xmand Y = yt−m. The signaturecan be verified by checking that hm(X) = x0and ht−m(Y ) = y0.x0x1hoo· · ·hooGFED@ABCxmhoo· · ·hooxt−mhoo· · ·hooxt−1hooxthooy0y1hoo· · ·hooymhoo· · ·hooONMLHIJKyt−mhoo· · ·hooyt−1hooythoo(a) [6 pts]Why are two chains used per value signed? (Why not eliminate the y chain?)(b) [6 pts]Argue briefly that this scheme is secure, if h is indeed one-way. (Why can’t a forgerproduce a signature for a different value m0, after having seen the signature for m?)Handout ??: Quiz 1 Name: 6Problem Q1-6. [14 pts](a) [4 pts]Recall that the WSJ used crypt() in its MAC, MACk= crypt(username||secret)where || denotes concatenation. Assume that the secret can be any sequence of 8-bit(not necessarily printable) characters. Give the maximum number of Web queries aninterrogative adversary must make to achieve a total break (universal forgery).(b) [4 pts]The Backstreet Journal, a new branch of the WSJ catering to aging pop-star fi-nancial news, decided to use a cryptographically secure (OW, CR) hash functionh : {0, . . . , 255}k→ {0, . . . , 255}20instead of crypt() in MACk. Similar to crypt(),the h function truncates input after the kth byte. Give the maximum number ofWeb queries an interrogative adversary must make to achieve a total break (universalforgery) if the secret is any sequence of 8-bit (not necessarily printable) characters.You can assume that usernames can be any length.(c) [6 pts]If the WSJ had used SHA-1 instead of crypt() in its MAC, would you expect thescheme to be stronger? Why or why not?Handout ??: Quiz 1 Name: 7Problem Q1-7. [5 pts]For each of the following applications, list the necessary hash function properties (OW, CR,WCR):PGP fingerprintsUnix password filesSecure URLsHash cashOne-time passwordsProblem Q1-8. [4 pts]Ben Bitdiddle upgraded his plaintext telnet server to a telnet server with one-time passwordsbased on the Lamport password authentication scheme. Which of the following attacks isBen’s new system no longer or less susceptible to (circle all that apply):1 Replay attack2 Session hijacking3 Dictionary attack on stolen database4 Keystroke loggingHandout ??: Quiz 1 Name: 8Problem Q1-9. [5 pts]In the list below, circle the symmetric block ciphers:AES DES DSA/DSS El Gamal RC4RC5 RC Cola Rijndael RSA Triple-CBCProblem Q1-10. [3 pts]Name one cipher from previous question that is a Feistel cipher:Problem Q1-11. [7 pts]In the Digitarian World, people don’t have names, but numbers to identity themselves. Agroup of four students (12, 25, 20, 5) attending the university 13-9-20 is taking 6.857. Theyare having some issues trying to do problem set 3 problem 1: they just can’t find a largeprime p such that all their numbers are generators of Z∗p.Explain briefly why they could not succeed.Handout ??: Quiz 1 Name: 9Problem Q1-12. [13 pts]Let p be a prime, and g ∈ Z∗pbe an element of order q, where q is a prime ≥ 3 (note that gis not a generator of Z∗p).(a) [5 pts] What are valid formulas for the inverse of g modulo p? Circle all correctanswer(s).gq−1mod p
View Full Document
Unlocking...