Midterm Exam Solutions - University of California, Berkeley

1 Midterm Exam SolutionsCS161 Computer Security, Spring encrypt a series of plaintext blocksp1,p2,..pnusing a block cipherE operating in electronic code book (ECB) mode, each ciphertext blockc1,c2,..cnis computed asci= Ek(pi).Which of the followingis nota property of this block cipher mode?(a) Any repeated plaintext blocks will result in identical correspondingciphertext blocks.(b) Decryption can be fully parallelized.(c) If a ciphertext block is modified or corrupted, then after decryption thecorresponding plaintext block and all the following plaintext blocks willbe affected.

2 (d) None of the above; that is, (a), (b), and (c) are all properties of theECB block cipher :The correct answer is (c). In ECB, altering a ciphertext blockonly affects a single plaintext encrypt a series of plaintext blocksp1,p2,..pnusing a block cipherE operating in cipher block chaining (CBC) mode, each ciphertext blockc1,c2,..cnis computed asci= Ek(pi ci 1), wherec0is a public initializa-tion vector (IV) which should be different for each encryption of the followingisa property of this block cipher mode?

3 (a) Any repeated plaintext blocks will result in identical correspondingciphertext blocks.(b) Decryption can be fully parallelized.(c) If a ciphertext block is modified or corrupted, then after decryption thecorresponding plaintext block and all the following plaintext blocks willbe affected.(d) None of the above; that is, neither (a), (b), nor (c) are properties ofthe CBC block cipher :The correct answer is (b). Each plaintext block can be com-puted using only two ciphertext blocks, independent of the other plaintextblocks:pi= Dk(ci) ci that (c) is not a property of CBC.

4 A modification to a ciphertextblock will affect that plaintext block and the one immediately following it,but none after ak-bit hash functionh:{0,1} {0,1}k. Assumehoperatesideally in the sense that each distinct input tohis mapped to a randommember of{0,1}k. Assume an attacker is trying to finding a collision ofh, that is, any twox1,x2 {0,1} such thath(x1) =h(x2). How does theexpected number of tries (evaluations ofh) before the attacker succeeds growwith respect tok?(a) (2k)(b) (2 k)(c) (2k/2)(d) (2logk)Answer:The correct answer is (c), (2k/2), , ( 2k).

5 Diffie-Hellman protocol is used to generate a shared secret key betweentwo parties using a public channel. It proceeds as a large prime andgbe a generator ofZ p; both arepublicly known parameters. Alice selects a randoma Zpandsendsx=gamodpto Bob. Bob selects a randomb Zpandsendsy=gbmodpto Alice. The shared key isgabmodp,which Alice may compute asyamodpand Bob may compute asxbmodp. A messagem Z pmay be encrypted using this keyasc=m of the following public key encryption and digital signature schemesis most similar to the Diffie-Hellman protocol?

6 (a) RSA encryption.(b) RSA signatures.(c) ElGamal encryption.(d) ElGamal :The correct answer is (c). Diffie-Hellman and ElGamal encryp-tion are exactly the same operations used in a somewhat different precisely, suppose Alice generates an ElGamal public key and sendsit to Bob, then Bob encrypts a message under that key and sends the ci-phertext to Alice. Then Alice and Bob have computed and communicatedexactly the same values they would have if they performed a Diffie-Hellmankey exchange then sent the message using the shared key, as described knows that she will want to send a single 128-bit message to Bob atsome point in the future.

7 To prepare, Alice and Bob first select a 128-bit keyk {0,1}128uniformly at the time comes to send a messagex {0,1}128to Bob, Aliceconsiders two ways of doing so. She can use the key as a one time pad,sending Bobk x. Alternatively, she can use AES to encryptx. Recall thatAES is a 128-bit block cipher which can use a 128-bit key, so in this case shewould encryptxas a single block and send Bob AESk(x).Assume Eve will see eitherk xor AESk(x), that Eve knows an initialportion ofx(a standard header), and that she wishes to recover the remainingportion Eve is an all powerful adversary and has time to try outevery possiblekeyk {0,1}128, which scheme would be more secure?

8 (a) The one time pad would be more secure. Even if Eve tried all possiblekeys, she would not be able to recover the unknown portion ofx. IfAES was used, Eve could eventually learn the unknown portion ofx.(b) AES would be more secure. Even if Eve tried all possible keys, shewould not be able to recover the unknown portion ofx. If the one timepad was used, Eve could eventually learn the unknown portion ofx.(c) They would be equally secure. Either way, Eve could eventually learnthe unknown portion ofx.(d) They would be equally secure.

9 Either way, Eve would not be able tolearn the unknown portion :The correct answer is (d). Even after trying every possible key(including the actual one), Eve will have no way of recognizing the correctplaintext or even narrowing down the possibilities in any is this? Well, since AES is a distinct permutation on{0,1}128undereach possible key, and the key was selected uniformly at random, given anyplaintext, each possible ciphertext is equally likely. So when AES is used fora single block with a random key of the same length, the effect is exactly thesame as using a one time pad: the ciphertext reveals no information aboutthe authentication codes (MAC) and digital signatures both serve toauthenticate the content of a message.

10 Which of the following best describeshow they differ?(a) A MAC can be verified based only on the message, but a digital signa-ture can only be verified with the secret key used to sign the message.(b) A MAC can be verified based only on the message, but a digital signa-ture can only be verified with the public key of the party that signedthe message.(c) A MAC can only be verified with the secret key used to generate it,but a digital signature can be verified based only on the message.(d) A MAC can only be verified with the secret key used to generate it,but a digital signature can be verified with the public key of the partythat signed the :The correct answer is (d).