ITN581 - Cryptographic Fundamentals and Applications

Semester 1 2002 - Assignment 3 (12 marks)

Gavin Longmuir – n2804948 (answers in red)

Question 1

Consider the following protocols. In each case the goal is key establishment of a new session key K_AB. The notation {M}K denotes the message M encrypted with the key K. It is assumed that the encryption algorithm used preserves both confidentiality and integrity of M.

(i) (5 marks)

In this protocol N_A and N_B are nonces chosen by A and B respectively. K_AS and K_BS are key-encrypting keys initially shared between S and A, and between S and B respectively.

1. A ® B: A,B,N_A

2. B ® S: A,B,N_A,N_B

3. S ® B: {K_AB}K_AS,{N_B,A,B,K_AB}K_BS

4. B ® A: {K_AB}K_AS,{N_A,A,B}K_AB

B includes A's challenge in message 4, intended to give key confirmation and key freshness. Show that this fails by describing an explicit attack on the protocol in which an old key is replayed. Then consider, for both A and B, whether any of the following properties is achieved, and explain your conclusions.

· Far-end operative.

· Implicit key authentication.

· Key freshness.

· Key confirmation.

ASSUMPTION: An attacker is able to obtain the value of the session key (K_AB) used in any previous old run of the key transport protocol.

This protocol is vulnerable to a replay attack. Attacker E masquerades as B and it able to persuade A to use old key K_AB. Note that messages 2 and 3 don’t exist in the replay attack by E.

1. A ® B: A,B,N_A

4. E ® A: {K^/_AB}K_AS,{N_A,A,B}K^/_AB

For user A:

· The far-end operative property is not achieved as the final message in the protocol must come from user B, but we can not be sure that B is present.

· Implicit key authentication can not be assumed at completion of the protocol run. A can not be sure which other party has the key.

· Key freshness is not achieved, the nonce generated by user A is not utilised direct by A in the creation of the session key (it’s passed on by B). A better solution would be for A to send it’s nonce directly to S rather than B. Hence A has no assurance that the key is new for this protocol run.

· The key confirmation property is achieved as the last message of the protocol from user B to A includes a component that is encrypted with the session key. Hence user B is actually in possession of the session key. Note this doesn’t exclude a possible future replay attack.

For user B:

· The far-ended operative property is not achieved as the only message in the protocol from user A was for the initialisation of the protocol itself. Hence user B doesn’t really know if user A is alive and working.

· Implicate key authentication is assumed at completion of the protocol run. As all messages of protocol include both A’s and B’s identifiers, via assurance from S’s key. Hence only user A and user B (apart from server S) are in possession of the key.

· Key freshness is achieved as B’s nonce is utilised in all communications with S for the session key request component of the protocol. Hence B has assurance that the session key is fresh.

· The key confirmation property is not achieved as the only message in the protocol from user A was for the initialisation of the protocol itself. Hence B doesn’t really know if A is in possession of the session key.

(ii) (2 marks)

This protocol, published by Tatebeyashi, Matsuzaki and Newman in 1989, uses a public key scheme. K_S is the public key of the server which is assumed known by all users. The random number generated by A is used as a symmetric encryption key in message 4. The random number generated by B is used as the session key: K_AB = N_B.

1. A ® S: A,B,{N_A}K_S

2. S ® B: A

3. B ® S: A,B,{N_B}K_S

4. S ® A: B,{N_B}N_A

Find two explicit attacks on the protocol: one in which the attackers masquerades as A and the other in which the attacker masquerades as B.

E masquerades as A:

1. E ® S: A,B,{N_E}K_S

2. S ® B: A

3. B ® S: A,B,{N_B}K_S

4. S ® E: B,{N_B}N_E

Hence E is given the session key generated N_B by S

E masquerades as B:

1. A ® S: A,B,{N_A}K_S

2. S ® B: A

3. B ® S: A,B,{N_E}K_S

4. S ® A: B,{N_E}N_A

Hence E provides the session key N_E to A via S

(iii) (2 marks)

The following key agreement protocol was recently published by Park and suggested for use in a mobile communications environment. Entities A and B initially both have private keys xa and xb, public keys ya = g^-xa mod p and yb = g^-xb mod p, respectively. They select random values modulo p, ra and rb, respectively, where p is a large prime.

1. A ® B: g^{ra + xa} mod p

2. B ® A: {B,A}K_AB, rb + xb

3. A ® B: {A,B}K_AB

The new session key K_AB = g^{ra * rb} is calculated by B as K_AB = (g^{ra + xa} *ya)^rb mod p and by A as K_AB = (g^{rb + xb} *yb)^ra mod p

Show that any entity can find a value of g^{ra + xa} mod p, with a known ra value. Hence show that any user can masquerade as A and obtain the session key agreed with B.

Public knowledge:

ya = g^-xa mod p

yb = g^-xb mod p

g, p

Known value:

ra

Protocol knowledge:

K_AB = g^{ra * rb}

K_AB = (g^{ra + xa} . ya)^rb

g^{ra * rb} = (g^{ra + xa} . ya)^rb

g^ra = (g^{ra + xa} . ya)

g^ra / ya = g^{ra + xa}

Hence we able to calculate g^{ra + xa} mod p, with a known ra value

E masquerading as user A sends first message of protocol to user B. User B’s replies with concatenated identity information encrypted with new session key, along with the value
rb + xb. While E doesn’t have the private key value xa, the user has enough information to calculate the session key K_AB = (g^{rb + xb} . yb)^ra mod p and correctly send the final message in the protocol.

1. A ® B: g^{ra + xa} mod p

2. B ® A: {B,A}K_AB, rb + xb

3. A ® B: {A,B}K_AB

Question 2

The Kangaroo Bank has one president and seven managers denoted M_i for i=1,...,7. The president deposits a large sum of money in a bank vault using an integer K modulo p as the key to lock the vault where p denotes the prime p=10009. Suppose that the president gives shares in the key to each manager by selecting the polynomial f(x) = K+bx+cx² and giving to manager M_i the share f(i) which is evaluated modulo p.

(i) Given that f(3)=7146, f(4)=8824, f(7)=9474, derive K. (2 marks)

let

K + 3b + 9c = 7146 mod 10009

K + 4b + 16c = 8824 mod 10009

K + 7b + 49c = 9474 mod 10009

é 1 1 1 ù^-1 é 7146 ù é K ù

│ 1 4 16 │ ││ 8824 │ = b

ë 1 7 49 û ë 9474 û ë c û

é 7737 ù

│ 899

ë 2971 û

Thus K = 7737

(ii) Explain why knowledge of only f(3) and f(4) reveals no

information about K. (1 marks)

Shamir’s Shared Secret Scheme utilises a polynomial of degree t-1. The polynomial function used by Kangaroo Bank is of degree 2, thus 3 shares are required to solve for K without any guessing.