CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173: Cryptography
May 2010
No calculators may be brought in and used.
Full marks will be given for correct answers to THREE questions.
Only the best three answers will contribute towards the assessment.
CM30173
CM30173 2.
1. (a) Can use any appropriate encryption system: key distribution will be difficult for
private key encryption, and messages are short enough that public-key is reasonably
efficient [5 marks]
Known plaintext attacks are possible, as the attacker can deduce the contents of
messages. Should note the possibility of replay attacks and dictionary attacks (so a
new key needed each time) and attacks on data integrity (e.g. malleability of RSA).
The known, stereotyped component of the messages makes them vulnerable to e.g.
Coppersmith’s attack. Some description of padding, hashing, choice of exponents
to defeat the identified attacks. [5 marks]
(b) The company can be given a list of clients and the MDCs of their passwords — the
client’s computer determines the MDC of his password and transmits it, and it can
be checked against the list held by the company. If the list is stolen, then a new
hash function can be used. [5]
(c) Digital signature can provide assurance of integrity and authenticity to arbitrary
many users, but signing large amounts of data rapidly as it is broadcast may not
be practical. Using MACs could work if there is a very small number of clients
— MACs for each message would need to be provided separately for each client.
[3 Marks] System should be secure against first and second pre-image attacks and
collision attacks. [2 Marks]
[5]
CM30173 continued
CM30173 continued 3.
2. (a) Should include descriptions of S-boxes, P-boxes, generation of round keys, and
their use at each round (4 marks). Diagram should show how they are connected
correctly. [6]
(b) This SPN is vulnerable to differential attack, as it preserves all differences with
probability 7
8
(except 0). Thus it is possible to identify differential trails leading to
output differences before encryption with the final round key having much higher
probability than would be expected from a pseudorandom encryption function.
Having determined the probability of such an output difference for a particular
input difference, in order to determine the final round key, an attacker obtains the
encryptions of all plaintext pairs with the required input difference. He can test
a candidate final round key by XORing it with each ciphertext, and determining
whether this results in the given output difference: the key producing the output
difference with the expected probability is taken to be the correct one. Resources
required: many chosen plaintext/ciphertext pirs (e.g. all with a given difference),
time and space to perform exhaustive search of all candidate keys (216 in this
case). [8]
(c) Should describe e.g. cipher-block chaining, cipher feedback mode and output
feedback mode. (1 mark each) OFB does not propagate errors at all, and allows the
key to be precomputed, so that encryption is just bitwise XOR.
[6]
3. (a) Should describe HMAC itself, or some reasonable alternative, i.e. mentioning length
padding, appending and prepending a key and then hashing.
3 marks for a keyed hash function, 3 marks for something which is actually
secure. [6]
(b) Collision: pair of messages with the same MDC. Computational security means that
there is no way of finding collisions which is more efficient than computing hashes
for a large set of messages and searching them for matches, which requires time and
storage proportional to 2
n
2 , where n is the message length. [4]
(c) The CBC-MAC of a message is equal to the last block of the CBC encryption of
the message under the same key. Therefore, an attacker can use as a forgery any
message which has the same final ciphertext block. [4]
(d) Suppose y consists of blocks y1, . . . , yn. Define z = x‖y1 ⊕ hk(x)‖ . . . ‖yn. Then
computing CBC-MAC for z will XOR the MAC for x (which is hk(x)) with the
y1 ⊕ hk(x), giving y1, and then compute the CBC-MAC for y1‖ . . . ‖yn, which is
hk(y), so (z, hk(y)) is the forgery. [6]
CM30173 continued
CM30173 continued 4.
4. (a) 187 factorizes as 17.11. Thus the totient is 16.10 = 160,and the private key is 7−1
mod 160, which can be calculated using the extended Ecuclidean algorithm:
160 = 22.7 + 6
7 = 6 + 1
Thus 1 = 23.7− 160, so 7−1 mod 160 is 23, which is the private key. [6]
(b) 3 encrypts as 37 mod 187, which is 130.
2 decrypts as 223 mod 187, which is 162.
Both can be computed using square and multiply algorithm. [4]
(c) Bob sends y1 ≡ x3 mod l, y2 ≡ x3 mod l, y3 ≡ x3 mod l. An attacker can then
compute Y < lmn such that:
Y ∼= y1 mod l,
Y ∼= y2 mod m,
Y ∼= y3 mod n,
But x3 < lmn, and so x = Y
1
3 . [6]
(d) Can mention RSA malleability based on multiplicativity, broadcast attacks,
insecurity of stereotyped messages (Coppersmith’s attack, Hastad’s attack).
Need for non-simplistic padding, large private exponents, avoidance of common
modulus. [4]
5. (a) Should accurately describe key generation (2 marks), signature generation (3 marks)
and signature verification (1 mark). [6]
(b) Something along the lines of:
H(m) ∼= xr + sk mod p− 1 by definition of the signature generation. (where H(m)
is the hashed message, x is the secret key, k is a freshly chosen ”random” value,
(p, g, y) is the public key and (r, s) is the signature.
Thus gH(m) ∼= gxr.gks ∼= (gx)r.(gk)s ∼= yr.rs mod p, by Fermat’s little theorem. This
is the condition for accepting the signature (r, s) for message m.
[6]
(c) Hashing simplifies the computation of the signature by reducing message length,
and prevents existential forgery by key-only attack. (2 marks)
The hash function must be collision resistant, as it is the hashed message tht is
signed, so a collision allows existential forgery. (2 marks) [4]
(d) Security for correctly implemented signature reduces to the discrete log problem,
which is believed to be hard. (2 marks). It is necessary to choose a new random
value k for each signature: knowledge of two messages signed using the same key
and value k permits computation of the private key, [4]
JDL/RJB CM30173