Massachusetts Institute of Technology Handout 36.857: Network and Computer Security September 28, 2004Professor Ronald L. Rivest Due: October 5, 2004Problem Set 3Submit this problem set in PostScript, PDF, or MS Word format to [email protected] lecture on the due date. We have provided templates for LATEX and Microsoft Word on thecourse website. Each solution must appear on separate sheets of paper. Mark the top of each sheetwith your name (s), the course number (6.857), the problem set number and question, and the date.You are to work in groups of three or four people and should submit a single set of solutionsfor all problems parts designated [Group]. You should turn in a separate, individual solution toany problems designated [Individual].We may distribute our favorite solution to each problem as the “official” solution. If you donot wish for your homework to be used as an official solution, or if you wish that it only be usedanonymously, please note this on your homework.Problem 3-1. Term Project Ideas [Individual]For the 6.857 project due at end of term, you have a great degree of freedom in your choice of topic.In general, you must pick an interesting topic related to network and computer security, and aresubject to common-sense restraints (regarding ethics, project size/difficulty, etc.). The topic itself,however, is yours to decide.The term project does not need to be an implementation; it could be a literature survey, a theoreticalstudy of some security or cryptographic mechanism, a vulnerability analysis of some real system(careful about ethics and legalities here!), a proposal for solving some security problem, etc.Brainstorm ideas for a project that you, personally, would like to work on. Write up a brief (one-page) summary of between one and three ideas you might like. You may find the list of suggestionsat http://crypto.csail.mit.edu/classes/6.857/projects.html useful. This is not binding inany way, and we will b e discussing the projec t at length later; this as signment is just to get youstarted thinking.The answers to this problem will be posted publicly on the class website. You will be required towork in a group of three or four for the term project. You may work in the same team as yourhomework group, or you may switch teams. This assignme nt is partially so that you may findothers who are interested in working on the same things as you are; even if you are comfortablewith your homework group and want to keep it for the project, this assignment will let your groupget a pool of ideas to think about.Problem 3-2. Adding One-Time Pads [Group]Peter Padadder knows from 6.857 that he shouldn’t e ver re-use a one-time pad. He has eightmessages M1, M2, . . . , M8to encrypt for his friend Mary. Each message contains the title of a sci-fimovie recommendation. The titles are of varying lengths; none are longer than 34 characters. Peter2 6.857 : Handout 3: Problem Set 3encodes the upper case alphabet and the space character as integers modulo 27 as follows:(space) = 0A = 1B = 2...Z = 26Peter thus wants to create eight pads P1, P2, . . . , P8so that he can encrypt his messages for Mary.Peter then encrypts each message Mi’s character j as Cij= Mij+Pijmod 27. Note that ciphertextCiis as long as the plaintext; if Miis shorter than Pithen the extra pad characters are ignored.Peter and Mary try to be clever. They create two random strings (“proto-pads”) A and B of length34 characters each, where each character has been chosen randomly modulo 27. They then definetheir eight pads as:P1= AP2= BP3= A + BP4= A − BP5= −AP6= −BP7= −A − BP8= −A + BPeter figures this is OK since no pad is repeated. Peter encrypts his eight movie recommendationsusing these pads, and sends them to Mary. His encrypted messages (in arbitrary order) consist of:‘‘COFBMEGCOFBAVGWVXXOURVIYE’’‘‘CESYIPCUNMAKFZRBKUGNM’’‘‘HMFBDKVPGUMGU HHQC’’‘‘X VM ONSHNRYFBFPNRUGZQQOGUPL’’‘‘ZIWAMFRYCCIDCPQV’’‘‘M WSPN GUJYR FIWSJZQYPADETTACFRA’’‘‘BLEIJGLAISASZZRXBLALXJHASNS’’‘‘XGKXLCUSXQYIUUQCCPPXHAAT GSMFMELLP’’These eight ciphertexts are available on the 6.857 web site at:http://crypto.csail.mit.edu/classes/6.857/ciphers.html.Show that Eve, the eavesdropper, can reconstruct these movie recommendations. Explain yourwork, and explain why Peter’s reasoning was faulty.Problem 3-3. Ballot Anonymizer [Group]6.857 : Handout 3: Problem Set 3 3Suppose an electronic polling station is going to store ballots B0, . . . , Bt−1in an array of s ize p,where p is prime and t < p. Although the ballots do not have any identifying information, if theyare stored sequentially, someone with access to the final ballot array could associate the ballotstored at location i with the ith voter.Consider a scheme that places ballot Biin array index ai+b mod p, where a, b ∈ Z∗pand 1 ≤ a ≤p−12.This scheme is intended to jumble the ballot ordering so that someone cannot associate a ballot’sstorage location with a particular voter.(a) Explain why the ballot positions are distinct.(b) Suppose just three voters have cast their vote and their ballots are stored under this scheme.Explain how you can determine the order that the ballots were cast, based on where theyare stored.(c) Suppose the adversary sees that the ballots A, B, C, D, E have been placed in memorypositions 0, 1, . . . , 6 as follows:0 1 2 3 4 5 6A - B C D E -Can an adversary who sees this pattern of ballots in the memory array determine the orderof voting? If so, how? What was the order of voting?(d) Show how to determine the location of the (t−12)th vote cast, given the final location of tballots. You may assume that t is odd. (Hint: Consider adding up the indices of the filledmemory slots.)(e) For some values of t, there are multiple a and b values which could lead to a given finalplacement of ballots. However, in other case s a final placement of ballots will uniquelyspecify a and b. Find out which values of t unambiguously define a and b values. Show howto find a and b in those cases.You don’t need to perform a brute force search. Given a and (t−12) ∗ a + b, can numericallysolve for b modulo p. (Hint: Consider squares of indices of filled memory slots.)Problem 3-4. TSA Database [Group]The Tasmanian Security Administration wants to keep a database of all people on their “no-fly”list. They wish to keep the list itself secret from casual inquiries, but want airline
View Full Document
Unlocking...