Homework 2 CS161 Computer Security Spring 2008 Assigned 2 13 08 Due 2 25 08 1 Signatures and Attacks Recall that to use the ElGamal signature scheme Alice randomly selects her private signing key x Zp and computes her public verification key as y g x mod p where p is a large prime and g is a publicly known generator of Z p To sign a message m Z p Alice first picks a random integer 1 k p 1 such that gcd k p 1 1 Next she computes r g k mod 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 that y r rs g m mod p which will be true if it was computed as described a 3 points Mallory has discovered a bug in a system operated by Alice Under certain circumstances when signing a message within some protocol Alice s system will not pick k randomly as intended but instead use some specific value Mallory doesn t know which value this is but she has managed to intercept two different messages which have been signed using that same value for k Assume 1 r s1 and 2 r s2 are valid signatures on messages m1 and m2 respectively and that they were generated using Alice s private key and the same value for k thus also causing the r values to be equal Show how Mallory can compute k given m1 m2 1 and 2 Consider this this assignment a Valentine s Day present because we love you and want you to learn more cryptography b 3 points Once Mallory has done that she can do something much worse Show how Mallory can use m1 1 and k to achieve a total break of the signature scheme that is compute Alice s private key x c 6 points As Mallory was busy using Alice s private key to rob defame and mock her Bob was implementing his own system which employs ElGamal signatures Fortunately his implementation did not have the same bug However Mallory next noticed a more subtle problem with the ElGamal signature scheme as described above even when it is implemented correctly She found a flaw in the scheme allowing an existential forgery that is the production of a signature on some message but not necessarily any message you want Show how using only Bob s public key y 0 Mallory can compute a valid signature on some message m The message need not be anything meaningful in particular it is fine if it is a random element in Z p d 5 points What is a simple way to modify the naive version of ElGamal signatures given in this problem to prevent this existential forgery attack 2 Secret Sharing In one of lectures covered by this homework we discuss schemes for sharing a secret among a group of people so that various subsets of the group will be able to reconstruct the secret by combining their shares It turns out you don t need computers or sophisticated mathematics to accomplish this you can implement even some of the more complex secret sharing scenarios using nothing but sheets that can be overlaid on one another If you are reading a hardcopy of this homework assignment that was handed out in class you have probably already noticed that the last page is a transparency with a pattern on it You have received one of five different such transparencies Share A Share E each one is a share of a secret image To reconstruct the secret image briefly get together with some of your classmates to collect one copy of each of the five shares Try overlaying various combinations of two or more shares to see if you can reveal the image Some combinations of shares in particular any share by itself will yield zero information about the secret The other combinations all completely reveal the image although some make it easier to see than others Here are a couple practical tips If the sheets are misaligned by even a few pixels the image will not reconstruct properly Since the pixels are so 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 white background for better contrast Collaboration is acceptable on parts a and b of this problem and necessary to obtain the secret but not on part c Also we have posted a pdf of the transparencies and png s of the raw patterns at http inst eecs berkeley edu cs161 sp08 hw02images tar gz If you prefer feel free to download these and print out your own sheets or assemble the images in an image editor If you are curious about how all this is accomplished http tinyurl com 3c8o6m is a good starting point a 1 point Find a combination of shares that reconstructs the image and list the letters of those shares here What does the image look like b 3 points Experiment with other combinations of shares to determine which sets of shares reconstruct the image and which reveal no information State the access policy these shares implement For example your answer might be 2 out of 5 5 out of 5 or some more complicated access policy like A B C B D E c 5 points Having seen a demonstration of these techniques Alice decides to try to devise her own scheme specifically a 3 out of 3 scheme Her idea works as follows Each pixel of the source image will be represented by a 3 by 3 grid of subpixels in the shares To generate the shares for a white pixel in the original image Alice randomly selects three subpixels and darkens those same subpixels in the each of the shares To generate the shares for a black pixel in the original image Alice randomly selects three subpixels to darken in the first share Next she randomly selects three subpixels other than those to darken in the second share Finally the remaining three subpixels which were darkened in neither of the first two shares are darkened in the third share black original pixel white original pixel original image shares reconstructed image An example of this process is shown above As you can see when all three shares are combined a region corresponding to a black pixel in the original image will be completely dark while a region corresponding to a white pixel will be two thirds white Does Alice s scheme offer perfect i e information theoretic security If your answer is yes show that any set of shares other than all three reveals nothing about the original image If your answer is no explain why this is not the case 3 Zero Knowledge There are known knowns These are things we know that we know There are known unknowns That is to say there are things that we know we don …
View Full Document