Massachusetts Institute of Technology Handout 56.857: Network and Computer Security March 3, 2008Professor Ronald L. Rivest and Professor Shafi Goldwasser Due: March 17, 2008Problem Set 3This problem set is due via email, to [email protected] on Monday, March 17 by the beginning of class.You are to work on this problem set in groups of three or four people. Problems turned in by individuals,pairs, pentuples, etc. will not be accepted. Be sure that all group membe rs can explain the solutions. SeeHandout 1 (Course Information) for our policy on collaboration. If you do not have a group, let us know.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 use d anonymously, please note this on your homework.Problem 3-1. Secret SharingSupp ose the 6.857 staff decide to use the ElGamal encryption scheme in order to receive secret mail. However,the staff does not want to have one secret key which decrypts any encrypted e-mail, as then if one of thestaff members has their laptop stolen, then the thief can decrypt all of the secret 6.857 e-mail. Instead, thestaff would like to implement a scheme where multiple staff members must cooperate in order to decryptencrypted messages. The staff members should be able to cooperatively decrypt any encrypted messagewithout having to reveal their own shares of the secret to each other. Essentially, each staff member shouldbe able to compute a “share” of the decrypted message.(a) Design a public-key encryption scheme where the encryption algorithm and public key are the sameas in ElGamal, but the secret key is shared amongst 4 decryptors (2 professors and 2 TA’s), and inorder to decrypt any message, either both professors must cooperate, or any one professor and bothTA’s must cooperate. Show how the private key shares are generated and distributed, and show howdecryption is accomplished.(b) Now suppose the staff decide they prefer to use RSA public-key encryption. Can you easily extendyour solution to use RSA, or do you see some typ e of difficulty in doing this?(c) How would you define a Chosen Ciphertext Attack in the context of this cryptosystem? Is this systemvulnerable to Chosen Ciphertext Attacks as you have defined them?Problem 3-2. RSA Timing AttacksA cryptosystem that seems secure on paper might be vulnerable, in practice, to attacks that exploit outof-band information. One such style of attacks uses the time required to exponentiate a given value with asecret exponent (mod a known modulus) to deduce the value of the secret exponent. This attack works whenthe time required to do multiplication and modular reductions depends on the input data, as is often thecase.To learn more about this attack, read the first 6 sections of Paul Kocher’s paper: Timing Attacks onImplementations of Diffie-Hellman, RSA, DSS, and Other Systems. As usual, you can find a link under theResources section of the course web site.2 6.857 : Handout 5: Problem Set 3For this problem, we ask you to use the attack outlined in section 5 to figure out the secret exponent beingused by a simple server setup by the TAs. Specifically, we have constructed a server that accepts, over asocket connection, a data request of the form: (start, iters, exp, j). The server then returns:V ar[iters−1Xi=0t((start + i)kj) −iters−1Xi=0t((start + i)exp)]such that:•the function V ar returns variance,•kjis a secret exponent for group j, 0 ≤ j ≤ 13,•all exponentiations are done mod pj, 0 ≤ j ≤ 13,•the function t(abmod p) returns the time required for the calculation when using the square andmultiply algorithm. (To help reduce the effects of random network—and local—overhead, we are, forthis problem, s imulating the values returned by t so they are more consistent with what you wouldexpect for square and multiply, so you should disregard the specific magnitude of the timing values asthe units are arbitrary).Each group has been sent a group number from 0 to 13. Your goal will be to recover kj, where j is yourgroup number. Each secret exponent and public modulus is of size 64 bits. The value of your public modulusisn’t really important, but can be found at the bottom of the python code we provide.To make your life easier, we have constructed a python program skeleton to handle the socket communicationwith our server. You can download the file, client.py, from the Resources section. Scroll down to the bottomof the source file and you will see an example function call that returns the information described above.Your TAs are not the world’s most brilliant server programmers, so we are not exactly sure how we ll ourserver, 6857.csail.mit.edu will hold up under heavy loads. If you have trouble connecting to the server, letus know right away so we can fix it.To prevent undue slow downs, we have programmed the servers to reject excessively large number of iter-ations. Here’s a hint: we have found that around 1500 to 2000 iterations per bit is enough to achieve theneeded significance for the variance calculations. Also, client.py includes code for you to do local calcula-tions, so that you can check your algorithm locally (you will need to generate a “secret” exponent and amodulus).Hand-in your groups secret exponent value (kj) in base-10, hex, or binary. We ask that you also hand inyour modified client.py used to produce the value, and provide a written explanation of how your attackworked, and what values you used. Partial credit will be awarded for partially correct exponents.Problem 3-3. Public Key Infrastructure(Compare and constrast X.509 certificates and SPKI/SDSI certificates.)An X.509 certificate roughly says: “I am the principal with distinguished name /A/B/C and public keyK1, and I hereby certify that the principal with name /A/B/C/D has public key K2. (Certificate issuedmm/dd/yyyy; expires mm/dd/yyyy.)(signed by
View Full Document
Unlocking...