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?
Attacker wins if b = b’
Solution: The adversary can provide any two plaintexts A and B of same length to be encrypted.
Page 1 of 4
Solution: The adversary can request an encryption for either A or B, or both. Note that the adversary can request an arbitrary number of plaintexts to be encrypted and can request the encryption of the same messages provided in the challenge 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 ?
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?
Solution: Since one-time pad is a deterministic encryption scheme, the ciphertext C we receive from the challenger will be identical to one of the ciphertexts we receive in the query phase. The adversary can simply compare C to 𝐸𝑛𝑐(𝐴) and 𝐸𝑛𝑐(𝐵) received in the query phase to determine which message was encrypted with probability 1.
Solution: An adversary can provide two plaintexts A and B to be encrypted. Ad- versary gets back X, which is an encryption of either A or B. Then, the adversary requests an encryption of A again and compares it with X. If two are the same, X is the encryption of A, and vice versa.
Solution: The encryption scheme is not IND-CPA secure. By definition a scheme is IND-CPA secure if the adversary wins with probability 0.5 + 𝜖, where 𝜖 is a negligibly small number. In this case, the adversary has a non-negligible advantage in the IND-CPA game.
Solution: TheencryptionschemeisnotIND-CPAsecure.Theadversarycanachieve a success probability of 0.5 simply by guessing 𝑏 randomly.
Discussion 4 Page 2 of 4 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.
Solution:
Q2.2 What is the decryption formula for CFB mode?
Q2.3 Select the true statements about CFB mode: Encryption can be parallelized
Decryption can be parallelized
The scheme is IND-CPA secure
Solution:
𝑃𝑖 =𝐸𝑘(𝐶𝑖−1)⊕𝐶𝑖
Discussion 4 Page 3 of 4
CS 161 – Fall 2021
Solution: Encryptionisnotparallelizablebecausetheencryptionofthe𝑛′𝑡hblockof plaintext is dependent on the 𝑛 − 1′𝑡h ciphertext. Decryption is parallelizable because the decryption of the 𝑛′𝑡h block of ciphertext is dependent on the 𝑛 − 1′𝑡h ciphertext. The scheme is IND-CPA secure because an adversary cannot provide two messages of equal length such that they gain a non-negligible advantage in the IND-CPA game, as long as the IV is not reused. Note that if the IV is reused, the scheme would be deterministic.
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?
Solution: IftheIVisreusedinAES-CFB,theattackercandetermineiftwomessages have identical prefix, up to but not including the first block containing the difference. This is because the 𝑛th plaintext block affects the 𝑛th input to the block cipher, and any difference in the plaintext block results in a completely different block cipher output.
When we use non-repeating IVs for CFB-mode, even if we encrypt the same message multiple times, CFB-mode will generate distinct and random-looking ciphertexts each time.
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?
Solution:
No, the secrecy of the IV does not affect the security of the encryption scheme, as the IV is passed as part of the output of an encryption. In order for a scheme to be secure, the IV must not be reused and sufficiently unpredictable.
Discussion 4 Page 4 of 4 CS 161 – Fall 2021