Introduction to Cryptography 2018 Sheet 2 4 pm Thursday 25/10/2018
Preamble
This sheet is split into two parts. Problems 1-6 may be attempted after the lesson of Thursday
18/10/2018 and problems 7-8 should be attempted after the lesson of Monday 22/10/2018.
Questions
Problem 1
Show that the CBC and OFB modes of encryption do not yield CCA-secure encryption schemes.
Problem 2
DES possesses a key-size of 56-bits and produces an encryption of size 64-bits. As it is now com-
putationally feasible to break DES, someone suggests using double-DES (encrypting the message
twice with separate keys) to encrypt messages with 112-bits of security. This appears to be feasible
until someone from https://www.zerodium.com/ contacts you claiming to be able to break the
scheme with a Meet In The Middle attack. The attack works on any double-symmetric encryption
scheme and will take 2k+1 operations and require 2k encryptions which must be stored, where k is
the size of the key. Assume that you have an oracle which can generate the required encryptions.
Attempt to cost the attack based upon storage requirements alone. What about AES? (You may
assume a cost of 0.01 per Gigabyte).
Problem 3
What is the output of an r-round Feistel network when the input is (L0 , R0 ) in each of the following
two cases:
(a) Each round function outputs all 0s, regardless of the input.
(b) Each round function is the identity function.
Problem 4
Having considered Problem 2, you decide that you require triple-Encryption. Let F be a block
cipher with n-bit block length and key length and set Fk0 1 ,k2 (x) := Ff1 (Fk−1
2
(Fk1 (x))).
(a) Assume that given a pair (m1 , m2 ) it is possible to find in constant time all keys k2 such that
m2 = Fk−12
(m1 ). Show how to recover the entire key for F 0 (with high probability) in time
roughly 2n using three known input/output pairs.
(b) In general, it will not be possible to find k2 as above in constant time. However, show that
by using a pre-processing step taking 2n time it is possible, given m2 , to find in (essentially)
constant time all keys k2 such that m2 = Fk−1 2
(0n ).
(c) Assume k1 is known and that the pre-processing step above has already been run. Show how
to use a single pair (x, y) for a chosen input value x to determine k2 in constant time.
(d) Put the above components together to devise an attack that recovers the entire key by running
in roughly 2n time and requesting the encryption of roughly 2n chosen inputs.
1
Introduction to Cryptography 2018 Sheet 2 4 pm Thursday 25/10/2018
Problem 5
Show that DES has the property that for every key k and input x it holds that DESk (x) = DESk̄ (x̄)
(where z̄ denotes the bitwise complement of z, or equivalently z̄ = z ⊕ 1|z| ). This property is called
the complementary property of DES.
Problem 6
How can the complimentary property (see previous question) of DES be used to find the secret key
k in DES using a strict maximum of 255 local computations of DES if we are allowed two queries
to the oracle DESk (·)?
Problem 7
Say Π = (Gen, Mac, Vrfy) is a secure MAC, and for k ∈ {0, 1n } the tag-generation algorithm Mack
always outputs tags of length t(n). Prove that if t(n) = O(log n) then Π cannot be a secure MAC.
Problem 8
Consider the following fixed-length MAC for messages of length l(n) = 2n − 2 using a pseudoran-
dom function F :
On input message m0 ||m1 with |m1 | = |m2 | = n − 1 and key k ∈ {0, 1}n , an algorithm Mack
outputs the tag t = Fk (0||m0 )||Fk (1||m1 ). The algorithm Vrfy is performed in the usual manner of
computing t0 = Mack (m) and comparing it to the provided tag t.
Is (Gen, Mac, Vrfy) existentially unforgeable under a chosen-message attack? Prove your answer.
