1. (a) Overall description of an SPN as iterated cipher (3 marks) – description and role
of S boxes as non-linear transformations (confusion), permutations (diffusion) and
key-mixing (2 marks). Advanced encryption standard is based on a SPN (Rijndael)
(1 mark). [6]
(b) Answer should explain that it is a chosen plaintext attack with the object of acquiring
targetted key bits (2 marks). The weakness it exploits is differential bias in the S
boxes of a SPN (explain what this means) (2 marks) — answer should explain the
process of identifying a differential trail with high bias, and testing candidate keys
against a predicted difference at the last round of decryption (2 marks) and why
the fact that S-boxes are the only non-linear component of the cipher makes this
possible (2 marks). Data requirements – c
p
chosen plaintexts, where c is a constant
and p is the probability bias of the differential trail (2 marks). [10]
(c) A secure model of operation is required because the determinacy of block encryption
may leave detectable patterns when encrypting multiple blocks (2 marks). Output
feedback mode can be used to create a stream cipher by repeatedly encrypting a
block of state (initialized to a given value) and taking the blocks of state after each
encryption as the key of the stream cipher. (2 marks)
2. (a) 1 mark for defining a hash function, 2 for each application (e.g. integrity testing,
digital signatures, password storage) – 1 mark for describing application, 1 for
explaining why hash functions provide security.
(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 (3 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 ). (2 marks).
(c) 1 mark for definition of MAC/keyed hash function. 2 marks for description of cipher-
block chaining mode, 2 marks for CBC-MAC (prepend length and take final block
as the authentication tag),
Using CBC-MAC with a known key as a message digest is susceptible to preimage
attack: an attacker can take any message m of length n, prepend it with n + 1,
encrypt using CBC and XOR the final block with the decryption of the original
message digest to get mn+1, and use m‖mn+1 as a forged message having the same
digest. (4 marks).
Page 2 of 3 CM30173
3. (a) Describe generation of RSA public and private key (including use of extended
Euclidean algorithm to find moduli of encryption (3 marks). Description of
encryption and decryption as modular exponentiation (1 mark). Proof that
encrytion followed by decryption is the identity using Fermat’s little theorem/Euler’s
theorem (2 marks).
(b) Statement of the CRT (2 marks). The CRT can be used to simplify decryption
by factorizing the modulus and computing exponentiation in the factor fields (2
marks). The CRT may be used to recover a plaintext which has been broadcast to
several users with the same small exponent by using Hastaad’s broadcast attack:
e.g. if the exponent is 3, then given x3 ≡ N1 mod(m1), x3 ≡ N2 mod(m2) and
x3 ≡ N3 mod(m3) such that m1,m2,m3 are coprime (which is likely if they have only
two large prime factors), then by the CRT we may find a unique value M < m1m2m3
satisfying these congruences, so taking x = M
1
3 returns the plaintext. (3 marks)
(c) An attacker can use the extended Euclidean algorithm to find s, t such that
s.e1+t.e2 = 1. He can then recover the message as y
s
1y
t
2mod(n) ≡ x
se1 .xte2mod(n) ≡
x1mod(n). (5 marks).
4. (a) Alice sends Bob 52mod(23), which is 25mod(23) — i.e. 2 (2 marks). Bob sends
510mod(23), which is (2)5mod(23) — i.e. 9 (2 marks). Shared vaue is 52.10mod(23)
which is 92mod(23) — i.e. 12 (2 marks). Attacker could compute this by obtaining
e.g. the discrete log5 of either 2 or 9, and hence computing 5
2.10mod(23) (1 mark).
An attacker could mount a man-in-the middle attack without acquiring the shared
secret by masquerading as Alice to Bob, and as Bob to Alice, and establishing shared
secret keys with both of them. (1 mark).
(b) Messages may be authenticated by using the digital signature algorithm (based on
the discrete logarithm problem) to sign them - description of signing (2 marks) and
verification (2 marks).
(c) 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. (4 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)
The index calculus method is only applicable in groups where the notion of prime
makes sense — not e.g. in elliptic curve groups (1 mark)
JDL/RJB Page 3 of 3 CM30173