Popa and 2021
Cryptography I
Question 1 IND-CPA
CS 161 Computer Security
Discussion 4
()
When formalizing the notion of confidentiality, as provided by a proposed encryption scheme, we introduce the concept of indistinguishability under a chosen plaintext attack, or IND-CPA security. A scheme is considered IND-CPA secure if an attacker cannot gain any information about a message given its ciphertext. This definition can be defined as an experiment between a challenger and adversary, detailed in the diagram below:
Eve (adversary) repeat
repeat
Alice (challenger)
M −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−▷
Enc(K, M) ⊲−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
M0 and M1 −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−▷
Enc(K, Mb) ⊲−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
M −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−▷
Enc(K, M) ⊲−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
′
b ∈{0,1}
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−▷
Consider the one-time pad encryption scheme discussed in class. For parts 1.1-1.3, we will prove why one-time pad is not IND-CPA secure and, thus, why a key should not be reused for one-time pad encryption.
Q1.1 With what messages 𝑀1 and 𝑀0 should the adversary provide the challenger?
Q1.2 Now, for which message(s) should the adversary request an encryption from the chal- lenger during the query phase?
Q1.3 The challenger will now flip a random bit 𝑏 ∈ {0, 1}, encrypt 𝑀𝑏 , and send back 𝐶 = 𝐸𝑛𝑐(𝑘, 𝑀𝑏) = 𝑀𝑏 ⊕ 𝑘 to the adversary. How does the adversary determine 𝑏 with proba- bility > 12 ?
Attacker wins if b = b’
Page 1 of 3
Q1.4 Putting it all together, explain how an adversary can always win the IND-CPA game with probability 1 against a deterministic encryption algorithm. Note: Given an identical plaintext, a deterministic encryption algorithm will produce identical ciphertext.
Q1.5 Assume that an adversary chooses an algorithm and runs the IND-CPA game a large number of times, winning with probability 0.6. Is the encryption scheme IND-CPA secure? Why or why not?
Q1.6 Now, assume that an adversary chooses an algorithm and runs the IND-CPA game a large number of times, winning with probability 0.5. Is the encryption scheme IND-CPA secure? Why or why not?
Discussion 4 Page 2 of 3 CS 161 – Fall 2021
Question 2 Block ciphers () Consider the Cipher feedback (CFB) mode, whose encryption is given as follows:
{
IV, 𝑖 = 0
𝐶𝑖 =
𝐸𝐾(𝐶𝑖−1)⊕𝑃𝑖,otherwise
Q2.1 Draw the encryption diagram for CFB mode.
Q2.2 What is the decryption formula for CFB mode?
Q2.3 Select the true statements about CFB mode:
Encryption can be parallelized The scheme is IND-CPA secure
Decryption can be parallelized
Q2.4 What happens if two messages are encrypted with the same key and nonce? What can the attacker learn about the two messages just by looking at their ciphertexts?
Q2.5 If an attacker recovers the IV used for a given encryption, but not the key, will they be able to decrypt a ciphertext encrypted with the recovered IV and a secret key?
Discussion 4 Page 3 of 3 CS 161 – Fall 2021