Consider the following encryption scheme. The message space consists of messages of 5n bits and the key space consists of keys of 5n - 5 bits. To encrypt, you remove 5 bits from the message, i.e., bits located at positions n, 2n, 3n, 4n, 5n, and then you XOR with the key, outputting a ciphertext of 5n - 5 bits. 1. Describe a decryption algorithm for the above scheme. Your decryption algorithm need not always be correct, i.e., it should be succeeding to output the correct plaintext with a certain probability < 1.="" (2.5="" points)="" 2.="" what="" is="" the="" probability="" of="" success="" of="" your="" decryption="" algorithm?="" (2.5="" points)="" 3.="" prove="" rigorously="" that="" the="" above="" encryption="" scheme="" is="" perfectly="" secure.="" you="" must="" use="" the="" definition="" of="" perfect="" secrecy.="" intuitive="" explanation="" will="" not="" suffice.="" (10="" points)="" 4.="" clearly,="" the="" key="" space="" of="" the="" above="" encryption="" scheme="" is="" smaller="" than="" the="" message="" space.="" explain="" why="" theorem="" 2.10="" (katz="" and="" lindell,="" page="" 35)="" that="" we="" proved="" in="" class="" fails="" to="" apply="" for="" this="" encryption="" scheme.="" in="" particular,="" indicate="" where="" the="" proof="" of="" theorem="" 2.10="" breaks.="" (5="">
Final - ENEE 456 / CMSC 456 / MATH 456 - S21 Papamanthou Out 5/17/21 at 9 am; Due: 5/18/21 at 9:00 am. Use only books and notes. We strongly prefer if you type your solutions. DO NOT USE GOOGLE SEARCH. DO NOT COLLABORATE. Problem 1 (Perfect Secrecy with Small Key Space) Consider the following encryption scheme. The message space consists of mes- sages of 5n bits and the key space consists of keys of 5n− 5 bits. To encrypt, you remove 5 bits from the message, i.e., bits located at positions n, 2n, 3n, 4n, 5n, and then you XOR with the key, outputting a ciphertext of 5n− 5 bits. 1. Describe a decryption algorithm for the above scheme. Your decryption al- gorithm need not always be correct, i.e., it should be succeeding to output the correct plaintext with a certain probability < 1. (2.5 points) 2. what is the probability of success of your decryption algorithm? (2.5 points) 3. prove rigorously that the above encryption scheme is perfectly secure. you must use the definition of perfect secrecy. intuitive explanation will not suf- fice. (10 points) 4. clearly, the key space of the above encryption scheme is smaller than the message space. explain why theorem 2.10 (katz and lindell, page 35) that we proved in class fails to apply for this encryption scheme. in particular, indicate where the proof of theorem 2.10 breaks. (5 points) problem 2 (strong pseudorandom permutations and cca security) consider the following private-key encryption scheme π: on input a message m of n/2 bits, and a key k of n bits, the ciphertext is computed as pk(r||m), where pk is a strong pseudorandom permutation and r is a uniform string of n/2 bits. 1. how does the the decryption algorithm work? (2 points) 2. write down the definition of a strong pseudorandom permutation. (1 point) 3. write down the definition of cca security along with the cca indistin- guishability experiment privkccaa,π(n); (1 point) 1 4. prove the the above scheme π is cca-secure. for your proof of security perform the following steps (you are urged to follow the same proof logic as the proof of theorem 3.31, katz and lindell, page 83): • first prove that, assuming pk is a strong pseudorandom permutation, the following holds |privkccaa,π(n)− privkccaa,π̄(n)| ≤ negl(n) , where π̄ is the same as π except that it uses a truly-random permuta- tion, and not a pseudorandom one. (5 points) • then prove that privkccaa,π̄(n) ≤ 1/2 + negl(n) . for the above you need to consider bad events about the challenge phase of the cca indistinguishability experiment, namely what needs to happen during the encryption of the challenge plaintexts m0 and m1 so that the adversary can trivially figure out which plaintext from the two is encrypted when the encryption oracle is called. (8 points) • finally argue that π is cca-secure based on the two findings above. (3 points) problem 3 (hash functions and digital signatures) 1. to overcome attacks in the textbook rsa signature, it is suggested to hash the message before signing using the following collision-resistant hash func- tion h(x) = h1(h2(x) ‖ x) ‖ h2(h1(x) ‖ x) , where at least one of h1, h2 is a collision-resistant hash function and ‖ denotes string concatenation. prove that h is collision-resistant using a re- duction. (8 points) 2. consider a signature scheme (keygen, sign,verify) that works for fixed- length messages of size 100 bits. let σ = signsk(m) be a signature on message m. you would like to sign a longer message m of 800 bits using the aforementioned signature scheme and you propose the following con- struction. break the message m into 10 blocks m = m1 ‖ m2 ‖ · · · ‖ m10 where the size of each block mi is 80-bits and compute σ(m) = (signsk(10 ‖ 1 ‖ m1), . . . ,signsk(10 ‖ 10 ‖ m10)) , 2 where each index 1, . . . , 10 is represented using 10 bits and the value 10 is also represented using 10 bits. • describe how signature verification works. (4 points) • show why the proposed signature scheme is not secure against exis- tential unforgeability. (4 points) • propose a way to fix the construction so that it is no longer vulnera- ble under your described attack (there is no need for a reduction, just informally argue why the attack does not work anymore.) you cannot use hash functions for your solution. (4 points) problem 4 (discrete logarithm and algebraic hashes) 1. as we learned in class, the discrete logarithm (dl) assumption for cyclic groups states the following: given a cyclic group g of prime order p, gen- erator g of g and a uniform h ∈ g, it is computationally-hard to find z such that gz = h. consider the hash function f(x, y) = hxgy that takes two inputs x and y in [0, p). after working very hard, bob was able to find a collision (a, b) and (c, d) for f . show how bob can use the collision he found to break the discrete logarithm assumption. specifically, compute the value of z (that the dl assumption is looking for) as a function of a, b, c, d. (5 points) 2. other assumptions can be used in cryptography. e.g., consider the knap- sack assumption (ka) that states the following: given a large prime p and a random vector m of even dimension n that is filled with numbers from zp (namely m ∈ znp ), it is computationally-hard to find another non-zero vector z of dimension n that is filled with numbers from the set {−1, 0, 1} (namely z ∈ {−1, 0, 1}n) such that m · z = 0 mod p. (a) will it still be computationally-hard to break the above assumption if we allow z ∈ znp (instead of z ∈ {−1, 0, 1}n)? explain. if not, find one z ∈ znp that breaks the assumption. (5 points) (b) let k = n/2 and let v and w be two random vectors of dimension k filled with numbers from zp. consider the hash function g(x, y) : {0, 1}k × {0, 1}k → zp where g(x, y) = v · x + w · y mod p. i. what should be the relation between n and p so that g compresses the input by at least a factor of 2? (5 points) 3 ii. after working very hard, bob was able to find a collision (a,b) and (c,d) for g. show how bob can use the collision he found to break the knapsack assumption. specifically, compute the value of z (that the ka assumption is looking for) as a function of a,b, c,d. (5 points) problem 5 (dropbox and deduplication) when a file f is uploaded to dropbox from the user’s machine, the dropbox client software first computes a hash of the file, h(f ), and sends it to the dropbox servers. if the hash matches a hash that dropbox already received before (possibly from another user), dropbox assumes that the files are the same and does not trigger the client to upload the new file. when the user syncs (a.k.a downloads) the file to another machine, dropbox sends the copy of the file it has on its servers. 1. why do you think this is useful for dropbox to do? (2 points) 2. suppose the hash function h used by dropbox is such that for any file f and malware m it is easy to find a suffix s such that h(f ) = h(m ||s) where || denotes concatenation. describe how an attacker can use this to easily spread the malware m to many dropbox users from his own machine. for simplicity, assume the attacker obtains a copy of a popular movie before it is released. (4 points) 3. what standard property should the dropbox hash function satisfy to prevent this attack? (2 points) 4. suppose a movie studio is about to release a blockbuster (very popular) movie m . the studio wants to test if the movie has been pirated and up- loaded to dropbox. explain how this can be done using the dropbox client software, without any special dropbox server access. (4 points) 5. suppose dropbox is used by the students in 456 to submit so- lutions to a true/false problem given by the professor. the problem has 10 questions. bob did not study at all, and therefore he decides to guess all the answers and then submit his file. the submission file is a .txt file and must have the following format enee456:1:t;2:f;3:t;4:t:5:f;6:t;7:f;8:f;9:t;10:f;. is there any better strategy for bob assuming that most of the students have already submitted? would his better strategy be feasible if the number of questions was 100? (4 points) 4 6. you are hired by dropbox to make the system more secure. in particular, you tell your manager that prof. papamanthou taught you encryption, and instead of a user hashing f and storing f , it is much more secure if the user hashes enck(f ) and subsequently stores enck(f ), where k is the user’s secret key and enc is a cpa-secure encryption scheme. the manager however rejects your proposal. what do you think the reason might be? (4 points) 5 1.="" (2.5="" points)="" 2.="" what="" is="" the="" probability="" of="" success="" of="" your="" decryption="" algorithm?="" (2.5="" points)="" 3.="" prove="" rigorously="" that="" the="" above="" encryption="" scheme="" is="" perfectly="" secure.="" you="" must="" use="" the="" definition="" of="" perfect="" secrecy.="" intuitive="" explanation="" will="" not="" suf-="" fice.="" (10="" points)="" 4.="" clearly,="" the="" key="" space="" of="" the="" above="" encryption="" scheme="" is="" smaller="" than="" the="" message="" space.="" explain="" why="" theorem="" 2.10="" (katz="" and="" lindell,="" page="" 35)="" that="" we="" proved="" in="" class="" fails="" to="" apply="" for="" this="" encryption="" scheme.="" in="" particular,="" indicate="" where="" the="" proof="" of="" theorem="" 2.10="" breaks.="" (5="" points)="" problem="" 2="" (strong="" pseudorandom="" permutations="" and="" cca="" security)="" consider="" the="" following="" private-key="" encryption="" scheme="" π:="" on="" input="" a="" message="" m="" of="" n/2="" bits,="" and="" a="" key="" k="" of="" n="" bits,="" the="" ciphertext="" is="" computed="" as="" pk(r||m),="" where="" pk="" is="" a="" strong="" pseudorandom="" permutation="" and="" r="" is="" a="" uniform="" string="" of="" n/2="" bits.="" 1.="" how="" does="" the="" the="" decryption="" algorithm="" work?="" (2="" points)="" 2.="" write="" down="" the="" definition="" of="" a="" strong="" pseudorandom="" permutation.="" (1="" point)="" 3.="" write="" down="" the="" definition="" of="" cca="" security="" along="" with="" the="" cca="" indistin-="" guishability="" experiment="" privkccaa,π(n);="" (1="" point)="" 1="" 4.="" prove="" the="" the="" above="" scheme="" π="" is="" cca-secure.="" for="" your="" proof="" of="" security="" perform="" the="" following="" steps="" (you="" are="" urged="" to="" follow="" the="" same="" proof="" logic="" as="" the="" proof="" of="" theorem="" 3.31,="" katz="" and="" lindell,="" page="" 83):="" •="" first="" prove="" that,="" assuming="" pk="" is="" a="" strong="" pseudorandom="" permutation,="" the="" following="" holds="" |privkccaa,π(n)−="" privkccaa,π̄(n)|="" ≤="" negl(n)="" ,="" where="" π̄="" is="" the="" same="" as="" π="" except="" that="" it="" uses="" a="" truly-random="" permuta-="" tion,="" and="" not="" a="" pseudorandom="" one.="" (5="" points)="" •="" then="" prove="" that="" privkccaa,π̄(n)="" ≤="" 1/2="" +="" negl(n)="" .="" for="" the="" above="" you="" need="" to="" consider="" bad="" events="" about="" the="" challenge="" phase="" of="" the="" cca="" indistinguishability="" experiment,="" namely="" what="" needs="" to="" happen="" during="" the="" encryption="" of="" the="" challenge="" plaintexts="" m0="" and="" m1="" so="" that="" the="" adversary="" can="" trivially="" figure="" out="" which="" plaintext="" from="" the="" two="" is="" encrypted="" when="" the="" encryption="" oracle="" is="" called.="" (8="" points)="" •="" finally="" argue="" that="" π="" is="" cca-secure="" based="" on="" the="" two="" findings="" above.="" (3="" points)="" problem="" 3="" (hash="" functions="" and="" digital="" signatures)="" 1.="" to="" overcome="" attacks="" in="" the="" textbook="" rsa="" signature,="" it="" is="" suggested="" to="" hash="" the="" message="" before="" signing="" using="" the="" following="" collision-resistant="" hash="" func-="" tion="" h(x)="H1(H2(x)" ‖="" x)="" ‖="" h2(h1(x)="" ‖="" x)="" ,="" where="" at="" least="" one="" of="" h1,="" h2="" is="" a="" collision-resistant="" hash="" function="" and="" ‖="" denotes="" string="" concatenation.="" prove="" that="" h="" is="" collision-resistant="" using="" a="" re-="" duction.="" (8="" points)="" 2.="" consider="" a="" signature="" scheme="" (keygen,="" sign,verify)="" that="" works="" for="" fixed-="" length="" messages="" of="" size="" 100="" bits.="" let="" σ="Signsk(m)" be="" a="" signature="" on="" message="" m.="" you="" would="" like="" to="" sign="" a="" longer="" message="" m="" of="" 800="" bits="" using="" the="" aforementioned="" signature="" scheme="" and="" you="" propose="" the="" following="" con-="" struction.="" break="" the="" message="" m="" into="" 10="" blocks="" m="m1" ‖="" m2="" ‖="" ·="" ·="" ·="" ‖="" m10="" where="" the="" size="" of="" each="" block="" mi="" is="" 80-bits="" and="" compute="" σ(m)="(Signsk(10" ‖="" 1="" ‖="" m1),="" .="" .="" .="" ,signsk(10="" ‖="" 10="" ‖="" m10))="" ,="" 2="" where="" each="" index="" 1,="" .="" .="" .="" ,="" 10="" is="" represented="" using="" 10="" bits="" and="" the="" value="" 10="" is="" also="" represented="" using="" 10="" bits.="" •="" describe="" how="" signature="" verification="" works.="" (4="" points)="" •="" show="" why="" the="" proposed="" signature="" scheme="" is="" not="" secure="" against="" exis-="" tential="" unforgeability.="" (4="" points)="" •="" propose="" a="" way="" to="" fix="" the="" construction="" so="" that="" it="" is="" no="" longer="" vulnera-="" ble="" under="" your="" described="" attack="" (there="" is="" no="" need="" for="" a="" reduction,="" just="" informally="" argue="" why="" the="" attack="" does="" not="" work="" anymore.)="" you="" cannot="" use="" hash="" functions="" for="" your="" solution.="" (4="" points)="" problem="" 4="" (discrete="" logarithm="" and="" algebraic="" hashes)="" 1.="" as="" we="" learned="" in="" class,="" the="" discrete="" logarithm="" (dl)="" assumption="" for="" cyclic="" groups="" states="" the="" following:="" given="" a="" cyclic="" group="" g="" of="" prime="" order="" p,="" gen-="" erator="" g="" of="" g="" and="" a="" uniform="" h="" ∈="" g,="" it="" is="" computationally-hard="" to="" find="" z="" such="" that="" gz="h." consider="" the="" hash="" function="" f(x,="" y)="hxgy" that="" takes="" two="" inputs="" x="" and="" y="" in="" [0,="" p).="" after="" working="" very="" hard,="" bob="" was="" able="" to="" find="" a="" collision="" (a,="" b)="" and="" (c,="" d)="" for="" f="" .="" show="" how="" bob="" can="" use="" the="" collision="" he="" found="" to="" break="" the="" discrete="" logarithm="" assumption.="" specifically,="" compute="" the="" value="" of="" z="" (that="" the="" dl="" assumption="" is="" looking="" for)="" as="" a="" function="" of="" a,="" b,="" c,="" d.="" (5="" points)="" 2.="" other="" assumptions="" can="" be="" used="" in="" cryptography.="" e.g.,="" consider="" the="" knap-="" sack="" assumption="" (ka)="" that="" states="" the="" following:="" given="" a="" large="" prime="" p="" and="" a="" random="" vector="" m="" of="" even="" dimension="" n="" that="" is="" filled="" with="" numbers="" from="" zp="" (namely="" m="" ∈="" znp="" ),="" it="" is="" computationally-hard="" to="" find="" another="" non-zero="" vector="" z="" of="" dimension="" n="" that="" is="" filled="" with="" numbers="" from="" the="" set="" {−1,="" 0,="" 1}="" (namely="" z="" ∈="" {−1,="" 0,="" 1}n)="" such="" that="" m="" ·="" z="0" mod="" p.="" (a)="" will="" it="" still="" be="" computationally-hard="" to="" break="" the="" above="" assumption="" if="" we="" allow="" z="" ∈="" znp="" (instead="" of="" z="" ∈="" {−1,="" 0,="" 1}n)?="" explain.="" if="" not,="" find="" one="" z="" ∈="" znp="" that="" breaks="" the="" assumption.="" (5="" points)="" (b)="" let="" k="n/2" and="" let="" v="" and="" w="" be="" two="" random="" vectors="" of="" dimension="" k="" filled="" with="" numbers="" from="" zp.="" consider="" the="" hash="" function="" g(x,="" y)="" :="" {0,="" 1}k="" ×="" {0,="" 1}k="" →="" zp="" where="" g(x,="" y)="v" ·="" x="" +="" w="" ·="" y="" mod="" p.="" i.="" what="" should="" be="" the="" relation="" between="" n="" and="" p="" so="" that="" g="" compresses="" the="" input="" by="" at="" least="" a="" factor="" of="" 2?="" (5="" points)="" 3="" ii.="" after="" working="" very="" hard,="" bob="" was="" able="" to="" find="" a="" collision="" (a,b)="" and="" (c,d)="" for="" g.="" show="" how="" bob="" can="" use="" the="" collision="" he="" found="" to="" break="" the="" knapsack="" assumption.="" specifically,="" compute="" the="" value="" of="" z="" (that="" the="" ka="" assumption="" is="" looking="" for)="" as="" a="" function="" of="" a,b,="" c,d.="" (5="" points)="" problem="" 5="" (dropbox="" and="" deduplication)="" when="" a="" file="" f="" is="" uploaded="" to="" dropbox="" from="" the="" user’s="" machine,="" the="" dropbox="" client="" software="" first="" computes="" a="" hash="" of="" the="" file,="" h(f="" ),="" and="" sends="" it="" to="" the="" dropbox="" servers.="" if="" the="" hash="" matches="" a="" hash="" that="" dropbox="" already="" received="" before="" (possibly="" from="" another="" user),="" dropbox="" assumes="" that="" the="" files="" are="" the="" same="" and="" does="" not="" trigger="" the="" client="" to="" upload="" the="" new="" file.="" when="" the="" user="" syncs="" (a.k.a="" downloads)="" the="" file="" to="" another="" machine,="" dropbox="" sends="" the="" copy="" of="" the="" file="" it="" has="" on="" its="" servers.="" 1.="" why="" do="" you="" think="" this="" is="" useful="" for="" dropbox="" to="" do?="" (2="" points)="" 2.="" suppose="" the="" hash="" function="" h="" used="" by="" dropbox="" is="" such="" that="" for="" any="" file="" f="" and="" malware="" m="" it="" is="" easy="" to="" find="" a="" suffix="" s="" such="" that="" h(f="" )="h(M" ||s)="" where="" ||="" denotes="" concatenation.="" describe="" how="" an="" attacker="" can="" use="" this="" to="" easily="" spread="" the="" malware="" m="" to="" many="" dropbox="" users="" from="" his="" own="" machine.="" for="" simplicity,="" assume="" the="" attacker="" obtains="" a="" copy="" of="" a="" popular="" movie="" before="" it="" is="" released.="" (4="" points)="" 3.="" what="" standard="" property="" should="" the="" dropbox="" hash="" function="" satisfy="" to="" prevent="" this="" attack?="" (2="" points)="" 4.="" suppose="" a="" movie="" studio="" is="" about="" to="" release="" a="" blockbuster="" (very="" popular)="" movie="" m="" .="" the="" studio="" wants="" to="" test="" if="" the="" movie="" has="" been="" pirated="" and="" up-="" loaded="" to="" dropbox.="" explain="" how="" this="" can="" be="" done="" using="" the="" dropbox="" client="" software,="" without="" any="" special="" dropbox="" server="" access.="" (4="" points)="" 5.="" suppose="" dropbox="" is="" used="" by="" the="" students="" in="" 456="" to="" submit="" so-="" lutions="" to="" a="" true/false="" problem="" given="" by="" the="" professor.="" the="" problem="" has="" 10="" questions.="" bob="" did="" not="" study="" at="" all,="" and="" therefore="" he="" decides="" to="" guess="" all="" the="" answers="" and="" then="" submit="" his="" file.="" the="" submission="" file="" is="" a="" .txt="" file="" and="" must="" have="" the="" following="" format="" enee456:1:t;2:f;3:t;4:t:5:f;6:t;7:f;8:f;9:t;10:f;.="" is="" there="" any="" better="" strategy="" for="" bob="" assuming="" that="" most="" of="" the="" students="" have="" already="" submitted?="" would="" his="" better="" strategy="" be="" feasible="" if="" the="" number="" of="" questions="" was="" 100?="" (4="" points)="" 4="" 6.="" you="" are="" hired="" by="" dropbox="" to="" make="" the="" system="" more="" secure.="" in="" particular,="" you="" tell="" your="" manager="" that="" prof.="" papamanthou="" taught="" you="" encryption,="" and="" instead="" of="" a="" user="" hashing="" f="" and="" storing="" f="" ,="" it="" is="" much="" more="" secure="" if="" the="" user="" hashes="" enck(f="" )="" and="" subsequently="" stores="" enck(f="" ),="" where="" k="" is="" the="" user’s="" secret="" key="" and="" enc="" is="" a="" cpa-secure="" encryption="" scheme.="" the="" manager="" however="" rejects="" your="" proposal.="" what="" do="" you="" think="" the="" reason="" might="" be?="" (4="" points)="">