CSE3400 Problem Set 4
1. Show a man-in-the-middle attack against ElGamal. In particular, assume an adversary captures a cipher-text c = (c1,c2) which is the encryption of message m. Now, the adversary cannot learn m, but show an attack allowing the adversary to construct a new ciphertext c′ = (c′1 , c′2 ) which is a valid encryption for a message α·m, for some number α of the adversary’s choosing. Your answer should show how an adversary, on input a ciphertext c, and after choosing any α, can send an encryption for the message α · m even though m is never learnt by the adversary.
2. (Based on Ex. 5.11 of the text): Let Fk be a PRF. Consider the protocol shown in Figure 1. Show that it is insecure against a man-in-the-middle attack. In particular, show how an adversary, who can intercept and tamper with any message sent between A and B, can decrypt and learn message m1 sent on the last step. This protocol is a variant of the DH key exchange protocol. Namely, g is a publicly known number and all arithmetic is done modulo a publicly known N. First A picks a random number a and sends the message ga. (Again, g is publicly known.). Next, B picks a random b and sends gb. Both parties can now compute gab which they use as a shared secret key. The extension in Figure 1 adds an extra step: using this key k = gab, run the message gb through a PRF to “verify” that Bob really sent that message and not an adversary; if this does not check out, parties abort before sending the message. Show that this is not secure and the adversary can pass this additional test and learn m1 assuming the adversary can tamper with messages and send messages of his/her own.
3. Exercise 5.12 (page 181 of course text)
4. Explain why it is important to ensure that you have an authentic public key before encrypting anything. In particular, consider the protocol shown in Figure 2.
Assume that AES-Enc is CBC mode using the AES cipher (thus it is CPA secure); you may assume “Enc” is any secure public key encryption system (e.g., RSA-OAEP). Show how a man-in-the-middle adversary may learn all 3 messages. The adversary may eavesdrop and tamper with any messages transmitting between A and B. Give exact details on what the adversary does. Explain why, even though we are using two secure systems (AES and secure public key system), the overall system is insecure.
Next, show how the adversary can send any message she likes to either A or B. Again, give exact details on the attack.
Do your attacks work if the adversary can only eavesdrop?
5. Consider the following scenario: A has a secret key and public key pair for text-book RSA (denoted sk and pk respectively); that is RSA without OAEP. B has an authentic copy of pk; as does an adversary. Now, B wants to send his PIN to A, which is a four digit number. He encrypts it as follows: First he chooses a nonce N0, a number chosen randomly from a large domain. He then sends the encryption: N0||RSA(pk,[PIN||N0]) = N0||([PIN||N0]e(mod N)) where (e,N) is the RSA public key. That is, he constructs the new message PIN||N0 (you may assume that he is able to embed [PIN||N0] as a number in Z/NZ∗) and encrypts that with text-book RSA; and he also sends N0 to A “in the clear”. Show an attack which allows the adversary to learn the PIN using only eavesdropping abilities.
1
Figure 1: Figure for Problem 2. Assume a man-in-the-middle adversary can intercept and tamper with any message sent. All arithmetic is done using a publicly known N. Also g and F are publicly known.
Figure 2: Figure for Problem 4. Assume a man-in-the-middle adversary can intercept and tamper with any message sent. Enc is a secure public key encryption scheme; AES-Enc is the CPA secure AES in CBC mode.
2