Midterm Exam Solutions

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.(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?

2 (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. 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).

3 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). 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?(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.

4 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. 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?(a) The one time pad would be more secure.

5 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. 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.

6 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). a large prime andgbe a generator ofZ logarithm problemis the task of computingagivengamodp,whereais an exponent randomly selected Diffie-Hellman problemis the task of computinggabmodpgivengamodpandgbmodp, whereaandbare exponents randomlyselected of the following best describes the relationship between these prob-lems?

7 (a) They are equivalent; if either can be efficiently solved, the other can.(b) If the computational Diffie-Hellman problem can be efficiently solvedthen the discrete logarithm problem can be efficiently solved, but theconverse is not known to be true.(c) If the discrete logarithm problem can be efficiently solved then thecomputational Diffie-Hellman problem can be efficiently solved, butthe converse is not known to be true.(d) None of the :The correct answer is (c). To show that the computationalDiffie-Hellman problem reduces to the discrete logarithm problem, imagineyou have an algorithm to efficiently compute discrete logs and you are giventhe task of solving the Diffie-Hellman problem. Then you could easily com-puteafromgamodpand then compute (gb)amodp=gabmodp. Noreduction in the other direction is a large prime andgbe a generator ofZ we are considering the functionh:Z Z pfor use as a hashfunction, whereh(m) = basic properties are typically desired of cryptographic hash func-tions.

8 Thecompressionproperty requires that messages of any length behashed to a finite domain. Thepreimage resistance( one-way) prop-erty requires that it be hard to find a message that hashes to a particularvalue. Thesecond preimage resistance( weak collision resistance)property requires that, given one message, it is hard to find a second mes-sage with the same hash as the first message. Thecollision resistance( collision resistance) property requires that it be hard to find any twomessages with the same we treat messages as arbitrary integers (not just members ofZ p),hsatisfies the compression we assume the difficulty of the discrete logarithm problem inZ p, whichof the other three properties doeshsatisfy?(a) All of them: preimage resistance, second preimage resistance, and col-lision resistance.(b) Only preimage resistance and second preimage resistance.(c) Only preimage resistance.(d) None of :The correct answer is (c).It can be shown thathsatisfies preimage resistance with a reductionfrom the discrete logarithm problem.

9 The reduction is trivial in that theyare almost exactly the same problem. If you have an algorithm which canproduce preimages, you need only reduce them modulopto produce thecorrect answer for the discrete logarithm see that it is not second preimage resistant, note that for any messagem, the messagem+p 1 will hash to the same value (andm+ 2(p 1),m+3(p 1),..). And if it is not second preimage resistant, there is no way itcan be collision resistant, because that is a strictly stronger following protocol is used to establish a shared keyKabbetween twopartiesAandB, assumingAandBeach share a key with a mutually A S:na,A,B2. S B:EKas(na,A,B,Kab),EKbs(na,A,B,Kab)3. B A:EKas(na,A,B,Kab),EKab(na),nb4. A B:EKab(nb)The valuesnaandnbare nonces selected byAandB. Like the NeedhamSchroeder protocol, this protocol is vulnerable to a key freshness specifically, assume an eavesdropper records the messages above inone execution of the protocol, then at some later point manages to compro-mise the session keyKab.

10 With this information, an active adversary canthen trickBinto reusingKabin a session with the mistak-enly believe it is communicating withAand thatKabis a fresh key generatedfor the two of them how this may be the adversary can arbitrarily intercept messages and drop ormodify them before the intended recipient sees them. The adversary canalso send new or replayed messages to any party, making them appear tocome from any other party. However, the adversary has not compromisedeither of the long-lived keys (KasandKbs).Answer:The following is the most straightforward way of accomplish-ing this attack. Assume the adversary has already observed one run of theprotocol and subsequently adversary replays message 2 toB, making it appear to come (who maintains no state between executions of the protocol, as wasclarified during the exam) thinks thatAis once again trying to initiate asession with it and thatShas generatedKabfor sends a new message 3 toA; it differs from the previous message3 only inB s choice of nonce:EKas(na,A,B,Kab),EKab(na),n adversary intercepts this message before it reachesAand repliestoBwith a messageEKab(n b), making it appear to come fromA.