Problem 1.1, 10 points. Alice wants to securely send Bob an arbitrary number M from the set {0,1,…,N − 1} for some positive integer N. She wants to have a scheme with perfect secrecy. She heard of the One Time Pad (OTP), but OTP is for bitstrings, not numbers. She decides to use the following scheme. The key space is {0,1,…,N − 1}. A ciphertext C for M is computed as (M + K) mod N and decryption performs (C − K) mod N.
Prove that this scheme is correct and perfectly secure.
Problem 1.2, 15 points. Alice and Bob have a good scheme to use (described above), but they don’t share any secrets. Alice shuffles a deck of 36 cards (6s to aces) and deals them face down to herself and Bob (each of them gets a half). No one else can see what cards they get. In order to send a secret message to Bob, Alice explains to Bob (publicly) how to get the key. (This does not involve any further exchange of cards.) After that, using the scheme above and without the use of cards, Alice is able to send Bob a message with perfect secrecy.
What is the maximum N (the size of the set the messages chosen from) possible for perfect secrecy?
Problem 1.3, 10 points. Let F:{0,1}k × {0,1}m → {0,1}n be a secure PRF. Consider the following function family F ′:{0,1}k × {0,1}m → {0,1}2n specified for all x ∈ {0,1}m and all K ∈ {0,1}k by F ′(K,x) = F(K,x)∥F(K,x)
Above x∥y means concatenation of x and y, and z means bitwise complement of z.
Prove that F ′ is not a secure PRF.
Problem 1.4, 15 points. Let E:{0,1}k × {0,1}ℓ → {0,1}ℓ be a block cipher. Consider the following symmetric encryption scheme ), whose message space is the set of messages whose length is multiple of ℓ bits and whose encryption and decryption algorithms are defined for each K ∈ {0,1}k as follows:
Algorithm EK(M)Algorithm DK(C)
Break M into l-bit blocks: M1∥…∥MnBreak C into ℓ-bit blocks:
IV ← {$ 0,1,…,2ℓ − 1}IV ∥C1∥…∥Cn
For i=1,…, n doFor i=1,…, n do
Ci ← EK(⟨IV + i⟩ ⊕ Mi)Mi ← EK−1(Ci) ⊕ ⟨IV + i⟩
EndForEndFor
Return IV ∥C1∥…∥CnReturn M1∥…∥Mn
Above “+” denotes addition modulo 2ℓ and ⟨j⟩ denotes the binary representation of integer j as ℓ-bit string.
Show that SE is not IND-CPA secure, regardless of how secure E is. Hints. The advantage of your adversary doesn’t have to be 1. your attack should work for large ℓ, e.g. ℓ = 128.
Problem 1.5, 15 points. We studied that CBC$ and other modes are not INDCCA secure. Consider the following attempt to prevent IND-CCA attacks. As before, the message space is a set of all strings whose length is multiple of n bits and the scheme uses a blockcipher E : {0,1}k×{0,1}n → {0,1}n. A key-generation algorithm of CBC’=(Kg,SE,SD) simply outputs a random k-bit string K, which specifies a function E(K,·) with a domain and range {0,1}n. The modifications are that we encrypt the IV and also make the IV to contain the l-bit encoding (0 < l < n) of the block-count p of the message, and make the decryption algorithm to verify that. We assume that p ≤ 2l − 1. The encryption and decryption algorithms of CBC’ are defined as follows:
SEK(M) SDK(C)
Parse M as M1∥…∥Mp, Parse C as C0∥…∥Cp,
[ s.t. |Mi| = n for 1 ≤ i ≤ p ][ s.t. |Ci| = n for 1 ≤ i ≤ p ]
IV ← {$ 0,1}n−l ; L ←< p >l ForMi = 1i ←,…,pE−1(K,Cdo i) ⊕ Ci−1
C0 ← E(K,IV ∥L) EndFor
For i = 1,…,p do M ← M1∥…∥Mp
Ci ← E(K,Ci−1 ⊕ Mi) T ← E−1(K,C0)
EndFor Parse T as IV ∥ < p′ >l
Return C0∥C1∥…∥Cp If p′ = p then Return M else return ⊥
Above |x| for a string x means its bitwise length. Show that CBC’ is not INDCCA secure.
Problem 1.6, 15 points. Show that the CBC MAC we studied is not UF-CMA secure if the domain contains messages of arbitrary length (but multiple of n bits), where n is the underlying blockcipher’s block length.
Problem 1.7, 5 points. Find (by using the Internet) blockcipher-based MACs that are provably secure (UF-CMA) for variable-length messages assuming the underlying block cipher is a PRF. Provide the constructions names and cite the sources. 3 examples are sufficient.
Problem 1.8 The coding problem, will be released separately.
