EE 720: An Introduction to Number Theory and Cryptography (Spring 2020)

Instructor: Saravanan Vijayakumaran

Indian Institute of Technology Bombay
Midsem Exam : 25 points February 27, 2020

1. (5 points) Let f : {0, 1}n → {0, 1}n be any function. The Feistel transform of f is the function
F ST Lf : {0, 1}2n → {0, 1}2n defined by

F ST Lf (LkR) = Rkf (R) ⊕ L

where L and R both belong to {0, 1}n , ⊕ denotes the bitwise XOR operator, and k denotes the string
concatenation operator.
Let F : {0, 1}n × {0, 1}n → {0, 1}n be a length-preserving pseudorandom function. Define F 0 :
{0, 1}n × {0, 1}n × {0, 1}2n → {0, 1}2n as

F 0 (k1 , k2 , LkR) = F ST LFk2 F ST LFk1 (LkR)

If k1 , k2 are chosen independently and uniformly from {0, 1}n , prove that F 0 (k1 , k2 , ·) : {0, 1}2n →
{0, 1}2n is not a pseudorandom permutation. Note that the distinguisher knows the structure of F 0
but does not have access to the keys k1 , k2 .
Note: F 0 (k1 , k2 , ·) is a pseudorandom permutation if for every PPT distinguisher D, there is a negligible function
negl such that:
0
 h i h i
Pr DF (k1 ,k2 ,·) (1n ) = 1 − Pr Dg(·) (1n ) = 1  ≤ negl(n),
 

where the first probability is taken over uniform choice of k1 , k2 ∈ {0, 1}n and the randomness of D, and the second
probability is taken over uniform choice of g ∈ Perm2n and the randomness of D. The set Perm2n is the set of all
0
bijections with domain equal to {0, 1}2n and range equal to {0, 1}2n . By DF (k1 ,k2 ,·) (1n ) and Dg(·) (1n ), we mean
distinguishers D who have oracle access to F 0 (k1 , k2 , ·) and g respectively.

2. (a) (21/2 points) Let Π = (Gen, Enc, Dec) be a private-key encryption scheme with message space
M = {0, 1}n where n is the security parameter. Let C be the ciphertext space of Π. Define
Π0 = (Gen0 , Enc0 , Dec0 ) to be another private-key encryption scheme with message space M0 =
{0, 1}2n as follows:
• Gen0 is the same algorithm as Gen. Both algorithms output a key k from a keyspace K.
• For key k and message m = m1 km2 ∈ {0, 1}2n where m1 ∈ {0, 1}n and m2 ∈ {0, 1}n , the
ciphertext output by Enc0 is (c1 , c2 ) ∈ C × C where c1 ← Enck (m1 ) and c2 ← Enck (m2 ).
• For key k and ciphertext (c1 , c2 ) ∈ C × C, the message output by Dec0 is m1 km2 where
m1 = Deck (c1 ) and m2 = Deck (c2 ).
Prove that Π0 is not CCA-secure, even if Π is CCA-secure.
(b) (21/2 points) Let Π1 = (Gen1 , Enc1 , Dec1 ) and Let Π2 = (Gen2 , Enc2 , Dec2 ) be two private-
key encryption schemes with the same message space M and ciphertext space C. Define
Π0 = (Gen0 , Enc0 , Dec0 ) to be another private-key encryption scheme with message space M
and ciphertext space C × C as follows:
• The key generated by Gen0 is (k1 , k2 ) where k1 ← Gen1 (1n ) and k2 ← Gen2 (1n ).
• For key (k1 , k2 ) and message m ∈ M, the ciphertext output by Enc0 is (c1 , c2 ) ∈ C × C
where c1 ← Enc1,k1 (m) and c2 ← Enc2,k2 (m).
• For key (k1 , k2 ) and ciphertext (c1 , c2 ) ∈ C ×C, the decryption algorithm Dec0 first computes
m1 = Dec1,k1 (c1 ) and m2 = Dec2,k2 (c2 ). If m1 6= m2 , Dec0 outputs ⊥ to indicate decryption
failure. If m1 = m2 , Dec0 outputs m1 .
Prove that Π0 is not CCA-secure, even if Π1 and Π2 are CCA-secure.
Note 1: The CCA indistinguishability experiment PrivKcca
A,Π (n) where Π = (Gen, Enc, Dec) is described below.

1. A key k is generated by running Gen(1n ).

2. The adversary A is given 1n and oracle access to Enck (·) and Deck (·). It outputs a pair of messages m0 , m1 ∈ M
with |m0 | = |m1 |.
3. A uniform bit b ∈ {0, 1} is chosen. Ciphertext c ← Enck (mb ) is computed and given to A. c is called the
challenge ciphertext.
4. The adversary A continues to have oracle access to Enck (·) and Deck (·), but is not allowed to query the latter
on the challenge ciphertext itself. Eventually, A outputs a bit b0 .
5. The output of the experiment is defined to be 1 if b0 = b, and 0 otherwise. If output is 1, we say that A succeeds.
 Note 2: A private-key encryption scheme Π = (Gen, Enc, Dec) has indistinguishable encryptions under a chosen-
ciphertext attack, or is CCA-secure, if for all probabilistic polynomial-time adversaries A there is a negligible
function negl such that, for all n,
h i 1
Pr PrivKcca
A,Π (n) = 1 ≤ + negl(n).
2

3. (a) (21/2 points) Show that the CBC block cipher mode encryption scheme is not CCA-secure.
(b) (21/2 points) Show that the CTR block cipher mode encryption scheme is not CCA-secure.
Note 1: Cipher Block Chaining (CBC) mode works as follows:

• Let m = m1 , m2 , . . . , ml where mi ∈ {0, 1}n .

• Let F be a length-preserving pseudorandom permutation with block length n.
• A uniform initialization vector (IV) of length n is first chosen.
• Set c0 = IV . For i = 1, . . . , l, set ci := Fk (ci−1 ⊕ mi ). The ciphertext is (c0 , c1 , . . . , cl ).
• For i = 1, 2, . . . , l, mi := Fk−1 (ci ) ⊕ ci−1 .

Note 2: Counter (CTR) mode works as follows:

• Let m = m1 , m2 , . . . , ml where mi ∈ {0, 1}n .

• Let F be a length-preserving pseudorandom function with block length n.
• A uniform value ctr of length n is first chosen.
• Set c0 = ctr. For i = 1, . . . , l, set ci := Fk (ctr + i) ⊕ mi . The ciphertext is (c0 , c1 , . . . , cl ).
• For i = 1, 2, . . . , l, mi := Fk (ctr + i) ⊕ ci .

4. Recall that the PKCS #5 padding scheme is used to pad a message x having length some integral
number of bytes into a encoded data m having length jL bytes where L is the block length in bytes.
The number of bytes which are appended to x to get m is b where 1 ≤ b ≤ L. Each of these padding
bytes is equal to the byte representation of the integer b. Assume that L < 256.
Suppose the encoded data m has length 2L bytes, i.e. m = (m1 , m2 ) where |mi | = L bytes for i = 1, 2.
Recall that the encoded data m is obtained by padding the message x. Let F be a length-preserving
pseudorandom permutation where Fk : {0, 1}n 7→ {0, 1}n where n = 8L. (Note: 8L bits = L bytes)
Now suppose the encoded data is encrypted using CBC mode as described below.
• The ciphertext corresponding to m = (m1 , m2 ) is given by c = (c0 , c1 , c2 ) where
– c0 is uniformly chosen from {0, 1}n .
– ci = Fk (mi ⊕ ci−1 ) for i = 1, 2.
Suppose an adversary has access to a padding oracle. On input some ciphertext block c0 of the form
(c00 , c01 , c02 ) or (c00 , c01 ), the padding oracle only returns a message from the set {ok, padding error}.
The ok is returned when there is no padding error in the encoded data m0 obtained from c0 . If there
is a padding error, then padding error is returned.
(a) (2 points) Describe a procedure by which the adversary can recover the length b of the padding
in the encoded data m. Be specific about the inputs sent to the padding oracle and the decisions
made by your procedure on receiving the oracle’s responses.
(b) (3 points) Describe a procedure by which the adversary can recover all the message bytes in
the encoded data m. The adversary is allowed to send ciphertext blocks of the form c0 = (c00 , c01 )
or of the form c0 = (c00 , c01 , c02 ).
5. (5 points) Recall the construction of a CBC-MAC using a length-preserving pseudorandom function
F with key/input/output length equal to n bits. Let m ∈ {0, 1}dn be a message for a fixed integer
d > 1.
• Gen: Choose key k uniformly from {0, 1}n .
• Mac: Parse the message m into d blocks m1 , . . . , md of length n bits each.
Set t0 = 0n . For i = 1, . . . , d, set ti = Fk (ti−1 ⊕ mi ).
Output td as the tag.
• Vrfy: For a message-tag pair (m, t) output 0, if the message is not of length dn.
Otherwise, output 1 if and only if t = Mack (m).
Consider the following variation of the CBC-MAC. Prove that this variation (Gen, Mac0 , Vrfy0 ) is an
insecure MAC.
• Mac0 : Parse the message m in to d blocks m1 , . . . , md of length n bits each.
Choose an initialization vector IV uniformly from {0, 1}n .
Set t0 = IV . For i = 1, . . . , d, set ti = Fk (ti−1 ⊕ mi ).
Output (IV, td ) as the tag.
• Vrfy0 : For a message-tag pair (m, (IV, t)) output 0, if the message is not of length dn.
Parse the message m into d blocks m1 , . . . , md of length n bits each.
Set t0 = IV . For i = 1, . . . , d, set ti = Fk (ti−1 ⊕ mi ).
Output 1 if and only if t = td .
Note: A message authentication code Π = (Gen, Mac, Vrfy) is existentially unforgeable under an adaptive chosen-
message attack, or just secure, if for all PPT adversaries A, there is a negligible function negl such that:
h i
Pr Mac-forgeA,Π (n) = 1 ≤ negl(n).

The message authentication experiment Mac-forgeA,Π (n) is defined as follows:

1. A key k is generated by running Gen(1n ).

2. The adversary A is given input 1n and oracle access to Mack (·). The adversary eventually outputs (m, t). Let
Q denote the set of all queries that A asked its oracle.
3. A succeeds if and only if (1) Vrfyk (m, t) = 1 and (2) m ∈
/ Q. If A succeeds, the output of the experiment is 1.
Otherwise, the output is 0.