1. (a) 1 mark for description of a Feistel cipher as an iterated block cipher, with 2 more
for an accurate description of the round function, and 1 for noting that the left and
right blocks of state are not swapped in the final round. Encryption is just the same
as encryption, but with the key schedule reversed. (1 mark). 3 marks for showing
that each round of decryption reverses a round of encryption.
(b) The DES S-boxes (1 mark) were designed to have a low differential bias — each pair
of input/output differences has a similar propagation ratio. It is therefore impossible
to identify a differential trail with a high bias, and so any differential attack will
require a large number of encryptions of chosen plaintexts (3 marks).
(c) 2 marks for definition of 3DES, 1 for observing that brute forcing now requires
searching a keyspace at least 2112. 5 marks for describing the “meet-in-the middle”
attack on 2DES: collection of candidate keys by searching tables of single encryptions
of a plaintext and single decryptions of a ciphertext for collisions, and verification
of the correct key by testing another plaintext/ciphertext pair. This allows brute
forcing of 2DES keys in around twice the time of DES keys (although requiring much
more storage space) which is known to be very feasible.
2. (a) 1 mark for defining a hash function. Only the hash of each user’s password is stored
with their login name — this is compared with the hash of the value entered at
each login attempt. In case of theft, an attacker only has the hash of each user’s
password which cannot be used directly for authentication (2 marks). 1 mark for
stating that a hash function used for this purpose must be first preimage resistant.
E.g. SHA-2 or SHA-3 are considered secure for such a purpose (1 mark).
(b) A collision is a pair of distinct messages which hash to the same value. (1 mark) A
birthday attack just computes valid pairs (x, h(x)) until a collision is found — which
is expected after O(N
1
2 ) hash values have been computed and stored (2 marks).
Some explanation of why this is the case — e.g. that n hash values give
(n2−n)
2
unordered pairs of hash values for distinct messages, each of which has probability
1
N
of being a collision, so we can expect to find one when n is O(N
1
2 ). (3 marks).
(c) 1 mark for definition of MAC/keyed hash function. 2 marks for description of cipher-
block chaining mode, 1 marks for CBC-MAC (prepend length and take final block
as the authentication tag).
An attacker could create a MAC forgery (m′′, hk(m
′)), where m′′ is obtained by
XORing hk(m) with the first block of m
′, and prepending m. (4 marks) One way
to prevent this is to add a representation of the length of the message as padding
before computing the CBC-MAC. (1 mark).
Page 2 of 3 CM30173
3. (a) Describe generation of RSA public and private key (3 marks). 1 mark for stating
Fermat’s little theorem, 3 for the proof that decryption and encryption are inverse
(bookwork).
(b) This system is susceptible to Hastaad’s broadcast attack: e.g. if the encryption
exponent is p and a user encrypts the same plaintext x for p different recipients
with (coprime) moduli m1, . . . ,mp, giving ciphertexts y1, . . . , yp, an eavesdropper
can then use the CRT to compute Y < m1 . . .mp such that Y ∼= yi mod mi for each
i ≤ p. But xp < m1 . . .mp, and so x = Y
1
p . (6 marks).
Coppersmith’s theorem states that the bounded roots of a monic polynomial with
respect to a given modulus can be found efficiently. Adding the recipient’s name to a
message is effectively a form of linear padding, and a set of ciphertexts generated by
encrypting the same message with different linear padding and a common exponent
can be used to generate such a polynomial. (2 marks).
(c) Description of RSA digital signature to sign a message m by using the private key
to “decrypt” h(m), where h is a cryptographic hash function (3 marks). This is
secure against existential forgery, on the assumption that h is preimage resistant,
since computing a valid pair (m,x) would require either to solve the RSA problem
to find x = dk(h(m)) for some choice of m or to find a preimage m under h for ek(x)
for some choice of x. (2 marks)
4. (a) Alice sends Bob 58mod(23), which is (52)4mod(23) — i.e. 16 (2 marks). Bob sends
516mod(23), which is (58)2mod(23) — i.e. 3 (2 marks). Shared vaue is 58.16mod(23)
which is 38mod(23) — i.e. 6 (2 marks). Attacker could compute this by obtaining
e.g. the discrete log5 of either 16 or 3, and hence computing 5
8.16mod(23) (1 mark).
A man-in-the-middle attack could be used to establish a session key with Alice (as
Bob) and with Bob (as Alice) and so read all traffic between them. (1 mark).
(b) Description of factor base method: select factor base of small primes {p1, . . . , pB}
and collect enough congruences of the form gx ≡ pn11 . . . p
nB
B , giving relations between
the discrete logs of the factor base, sufficient to compute them. (3 marks) To
compute the discrete log of β, attempt to factorize γ = β.gsmod(p) over the
factor base (for random s), and so compute the discrete logarithm of γ as a linear
combination of logarithms of primes in the factor base. (3 marks)
(c) Elliptic curves etc. lack a notion of prime element (1 mark). 1 mark for identifying
e.g. Shanks’ algorithm as an optimal general method for finding discrete logarithms,
and 4 marks for describing it (bookwork).
JDL/RJB Page 3 of 3 CM30173