Questions
1. Matsumoto, Takashima, Imai (MTI) proposed a family of Key Agreement protocols
which extended the Diffie-Hellman exchange by combining both long-term and
ephemeral keys in the derivation of the session key.
Assume that a party U has a long-term key pair (YU = g
XU, XU) where the public key YU
is known by all the other users. Consider the following three protocols where RU denotes
a random number chosen by user U in each session.
MTI A(0)
1: A  B: gRA
2: B  A: gRB

Shared Key KAB = g
RAXB + RBXA
MTI B(0)
1: A  B: YB
RA
2: B  A: YA
RB

Shared Key KAB = g
RA + RB
MTI C(0)
1: A  B: YB
RA
2: B  A: YA
RB

Shared Key KAB = g
RARB
a. Show the key derivation formulas of User A and User B for MTI B(0) and MTI
C(0). (2 marks)
b. Can MTI B(0) provide key authentication? Justify your answer. (2 marks)
c. Which protocol(s) can provide Forward Secrecy? Justify your answer.
(3 marks)
2. Alice and Bob share a common password PW which contains 6 alphanumeric characters
where each character can be an upper or lower case English letter or a number between
0-9. They want to establish a secure communication channel using the following
protocol.
A  B: A, EPW(KA)
B  A: B, EPW(KB), MACK(B, A, 0)
A  B: MACK(A, B, 1)
2
In the protocol, E denotes a secure symmtric key encryption algorithm, MAC denotes a
secure message authentication code function, KA and KB are both 128-bit random
strings, and the shared session key is K = SHA2(KA,KB).
(a) What is the size of the password space? Suppose you have a computer that can
enumerate 10,000,000 passwords per second, how long does it take to enumerate all
the possible passwords? (1 mark)
(b) Is this protocol secure? Justify your answer. (2 marks)
(c) The protocol does not provide forward secrecy (FS). Modify the protocol to achieve
FS. (2 marks)
3. Similar to the textbook Diffie-Hellman key exchange protocol, the Burmester-Desmedt
(BD) group key exchange protocol is only secure against passive attackers. Modify the
BD protocol to make it secure against active attackers. Describe clearly each step of your
modified protocol and justify its security under active attacks.
(Hint: consider the approach to modify the textbook Diffie-Hellman in order to achieve
active security.) (3 marks)
4. The 3GPP AKA is an improvement of the GSM (i.e., 2G) AKA scheme by allowing
mutual authentication between the MS and the VLR. However, as shown in the lecture,
the counter-based VLR authentication mechanism in 3GPP may encounter a desynchronisation
problem. Design a new approach to improve the GSM AKA scheme for
mutual authentication without bringing any synchronisation issue. You are allowed to
modify the message flows among the MS, the VLR and the HLR. However, same as the
GSM AKA scheme, you should assume there is only a long-term shared secret key
between MS and HLR and only symmetric-key operations are allowed in your design.
Describe clearly each step of your new scheme. (5 marks)