Homework 2CS161 Computer Security, Spring 2008Assigned 2/13/08∗Due 2/25/081. Signatures and AttacksRecall that to use the ElGamal signature scheme, Alice randomly se-lects her private signing key x ∈ Zpand computes her public verificationkey as y = gxmod p, where p is a large prime and g is a publicly knowngenerator of Z∗p. To sign a message m ∈ Z∗p, Alice first picks a randominteger 1 ≤ k < p − 1 such that gcd(k, p − 1) = 1. Next she computesr = gkmod p and s = k−1(m − xr) mod p − 1. The signature on m isσ = (r, s). If Bob wishes to verify whether a purported signature (r, s)corresponds to a message m and Alice’s public key y, he checks thatyrrs≡ gmmod p, which will be true if it was computed as described.(a) (3 points) Mallory has discovered a bug in a system operatedby Alice. Under certain circumstances, when signing a messagewithin some protocol, Alice’s system will not pick k randomly asintended, but instead use some specific value. Mallory doesn’tknow which value this is, but she has managed to intercept twodifferent messages which have been signed using that same valuefor k.Assume σ1= (r, s1) and σ2= (r, s2) are valid signatures on mes-sages m1and m2respectively, and that they were generated usingAlice’s private key and the same value for k (thus also causing the“r” values to be equal). Show how Mallory can compute k givenm1, m2, σ1, and σ2.∗Consider this this assignment a Valentine’s Day present ... because we love you andwant you to learn more cryptography.(b) (3 points) Once Mallory has done that, she can do something muchworse. Show how Mallory can use m1, σ1, and k to achieve a totalbreak of the signature scheme, that is, compute Alice’s private keyx.(c) (6 points) As Mallory was busy using Alice’s private key to rob,defame, and mock her, Bob was implementing his own systemwhich employs ElGamal signatures. Fortunately, his implementa-tion did not have the same bug. However, Mallory next noticeda more subtle problem with the ElGamal signature scheme as de-scribed above, even when it is implemented correctly. She founda flaw in the scheme allowing an existential forgery, that is, theproduction of a signature on some message (but not necessarilyany message you want).Show how, using only Bob’s public key y0, Mallory can computea valid signature on some message m. The message need notbe anything meaningful; in particular, it is fine if it is a randomelement in Z∗p.(d) (5 points) What is a simple way to modify the (naive) version ofElGamal signatures given in this problem to prevent this existen-tial forgery attack?2. Secret SharingIn one of lectures covered by this homework, we discuss schemes forsharing a secret among a group of people so that various subsets of thegroup will be able to reconstruct the secret by combining their shares.It turns out you don’t need computers or sophisticated mathematics toaccomplish this – you can implement even some of the more complexsecret sharing scenarios using nothing but sheets that can be overlaidon one another.If you are reading a hardcopy of this homework assignment that washanded out in class, you have probably already noticed that the lastpage is a transparency with a pattern on it. You have received one offive different such transparencies (“Share A” - “Share E”); each one isa share of a secret image.To reconstruct the secret image, briefly get together with some of yourclassmates to collect one copy of each of the five shares. Try overlayingvarious combinations of two or more shares to see if you can reveal theimage.Some combinations of shares (in particular, any share by itself) willyield zero information about the secret. The other combinations allcompletely reveal the image (although some make it easier to see thanothers).Here are a couple practical tips. If the sheets are misaligned by even afew pixels, the image will not reconstruct properly. Since the pixels areso small, you need to align the sheets very precisely for this to work.Also, it will be easier to see the image if you lay the sheets on a whitebackground for better contrast.Collaboration is acceptable on parts (a) and (b) of this problem (andnecessary to obtain the secret!), but not on part (c). Also, we haveposted a pdf of the transparencies and png’s of the raw patterns athttp://inst.eecs.berkeley.edu/~cs161/sp08/hw02images.tar.gz.If you prefer, feel free to download these and print out your own sheetsor assemble the images in an image editor. If you are curious abouthow all this is accomplished, http://tinyurl.com/3c8o6m is a goodstarting point.(a) (1 point) Find a combination of shares that reconstructs the imageand list the letters of those shares here. What does the image looklike?(b) (3 points) Experiment with other combinations of shares to deter-mine which sets of shares reconstruct the image and which revealno information. State the access policy these shares implement.For example, your answer might be 2 out of 5, 5 out of 5, or somemore complicated access policy like (A ∧ B) ∨ C ∨ (B ∧ D ∧ E).(c) (5 points) Having seen a demonstration of these techniques, Alicedecides to try to devise her own scheme, specifically, a 3 out of 3scheme. Her idea works as follows.Each pixel of the source image will be represented by a 3 by 3grid of subpixels in the shares. To generate the shares for a whitepixel in the original image, Alice randomly selects three subpixels,and darkens those same subpixels in the each of the shares. Togenerate the shares for a black pixel in the original image, Alicerandomly selects three subpixels to darken in the first share. Next,she randomly selects three subpixels other than those to darkenin the second share. Finally, the remaining three subpixels whichwere darkened in neither of the first two shares are darkened inthe third share.reconstructed image:shares:original image: black original pixel white original pixelAn example of this process is shown above. As you can see, whenall three shares are combined, a region corresponding to a blackpixel in the original image will be completely dark, while a regioncorresponding to a white pixel will be two thirds white.Does Alice’s scheme offer perfect (i.e., information theoretic secu-rity)? If your answer is yes, show that any set of shares other thanall three reveals nothing about the original image. If your answeris no, explain why this is not the case.3. Zero-Knowledge“There are known knowns. These are
View Full Document
Unlocking...