ńņš. 39 |

ting in the BR93 model, there is no way to observe such a possibility. The BR93

model is extended to allow more realistic adversary capabilities, under which the

proven secure protocol becomes insecure.

We then propose an equally efļ¬cient alternative protocol that provides protection

against the compromise of long-term keys without taking recourse to revocation

lists. We prove this alternative protocol secure in the extended BR93 model. We re-

mark that protocols proven secure in the extended model will also be secure in the

original model. An extension to this alternative protocol allows session keys to be

renewed in subsequent sessions without the serverā™s further involvement even in the

event that the long-term key or the earlier session key have been compromised. A

comparative summary is also presented.

Material presented in this chapter has appeared in the following publication:

ā¢ Colin Boyd and Kim-Kwang Raymond Choo and Anish Mathuria. An Exten-

sion to Bellare and Rogaway (1993) Model: Resetting Compromised Long-Term

101

102 6 An Extension to the Bellareā“Rogaway Model

Keys. In Lynn Margaret Batten and Reihaneh Safavi-Naini, editors, 11th Aus-

tralasian Conference on Information Security and Privacy - ACISP 2006, vol-

ume 4058/2006 of Lecture Notes in Computer Science, pages 371ā“382, Springer-

Verlag, 2006.

6.1 A Provably-Secure Revised Protocol of Boyd

Prior to deļ¬ning the protocol that we shall prove secure, we deļ¬ne the authenticated

encryption scheme that will be employed.

6.1.1 Secure Authenticated Encryption Schemes

A symmetric encryption scheme S E = (K , E , D) consists of three algorithms,

namely: the key generation algorithm K , the encryption algorithm E , and the de-

cryption algorithm D as described below.

ā¢ K is a probabilistic algorithm which, on input 1k , outputs a key K.

ā¢ E is a probabilistic algorithm which takes a key K and a message M drawn from

a message space M associated to K and returns a ciphertext C. This is denoted

by C āR EK (M).

ā¢ D is a deterministic algorithm which takes a key K and a ciphertext C and re-

turns the corresponding plaintext M or the symbol ā„ which indicates an illegal

ciphertext. This is denoted as x ā DK (C). We require that DK (EK (M)) = M for

every K ā K (1k ).

For security we use the deļ¬nitions of Bellare and Namprempre [3]. We require

that the symmetric encryption scheme provides conļ¬dentiality in the sense of in-

distinguishability under chosen plaintext attacks (IND-CPA security) and provides

integrity in the sense of preserving integrity of plaintexts (INT-PTXT security). We

note that each of these is the weakest of the properties deļ¬ned by Bellare and Nam-

prempre and are provided by either encrypt-then-MAC or by MAC-then-encrypt

constructions. Therefore there are many practical ways of implementing our proto-

col which can reasonably be expected to satisfy these assumptions. We now deļ¬ne

these concepts more precisely.

For any efļ¬cient (probabilistic, polynomial time) adversary X , the conļ¬dentiality

security is deļ¬ned in terms of the following game, which we call G1 .

1. The challenger chooses a key K ā K (1k ).

2. Given access to the encryption oracle, the adversary outputs two messages of

equal length M0 , M1 ā M of her choice.

3. The challenger computes Cb āR EK (Mb ) where b āR {0, 1}. The bit b is kept

secret from the adversary.

6.1 A Provably-Secure Revised Protocol of Boyd 103

4. The adversary is then given Cb and has to output a guess b for b.

We deļ¬ne the advantage of the adversary X playing the above game as

indā’cpa

(k) = |2 Ā· Pr[b = b]| ā’ 1.

AdvX

Deļ¬nition 6.1.1 The encryption scheme S E is IND-CPA secure if the advantage

of all efļ¬cient adversaries playing game G1 is negligible.

For any efļ¬cient adversary F , the integrity security is deļ¬ned in terms of the fol-

lowing game, which we call G2 .

1. Choose a key K ā K (1k ).

2. The adversary F is given access to the encryption oracle and also a veriļ¬cation

oracle which on input a ciphertext C outputs 0 if DK (C) =ā„ and outputs 1 if C

is a legitimate ciphertext.

3. The adversary wins if it can ļ¬nd a legitimate ciphertext Cā— such that the plaintext

M = DK (Cā— ) was never used as a query to the encryption oracle. In this case we

say the event forgery has occurred.

We deļ¬ne the advantage of the adversary playing the above game as

intā’ptxt

(k) = |2 Ā· Pr[forgery]| ā’ 1.

AdvF

Deļ¬nition 6.1.2 The encryption scheme S E is INT-PTXT secure if the advantage

of all efļ¬cient adversaries playing game G2 is negligible.

6.1.2 Revised Protocol of Boyd

Now that the authenticated encryption scheme to be employed in the protcol has

been deļ¬ned, we can deļ¬ne the protocol that we shall prove secure. All parameter

choices depend on a security parameter k. In Protocol 6.1, the following notations

are used: H denotes some secure cryptographic hash function; {m}K denotes an

encryption of some message m under symmetric key K; S denotes a server who

shares long-term symmetric keys KAS and KBS with A and B, respectively; NA , NB ,

and KS denote nonces generated by A, B and S, respectively.

Protocol 6.1 is a server-based protocol in which users A and B as well as the server

S contribute to the key value. The session key obtained by A and B at the end of the

protocol execution is denoted as KAB . We refer the protocol message ļ¬elds that are

encrypted using the long-term symmetric keys, KAS and KBS , as tickets. As Boyd

and Mathuria [9] pointed out, such protocols which employ tickets to re-establish

session keys are often known as repeated authentication protocols in the literature.

Protocol 6.1 is very similar to that proposed by Boyd [8]. Differences are as follows.

1. In the earlier protocol of Boyd, the session key is determined by a MAC function

so that the session key is KAB = MACKS (NA , NB ).

104 6 An Extension to the Bellareā“Rogaway Model

A S B

A, B, NA

NA āR {0, 1}k ā’ ā’ ā’ ā’ KS āR {0, 1}k

ā’ ā’ ā’ā’

{A, B, KS }KAS , {A, B, KS }KBS , NA

ā’ā’ā’ā’ā’ā’ā’ā’ā’

ā’ā’ā’ā’ā’ā’ā’ā’

NB āR {0, 1}k

{A, B, KS }K , NB

ā’ ā’ ā’ ā’ ā’ AS ā’ ā’

ā ā’ ā’ ā’ ā’ ā’ ā’ ā’ ā’ Decrypt {A, B, KS }KBS

ā’

Decrypt {A, B, KS }KAS

SIDA = NA NB SIDB = NA NB

KAB = H (KS SIDA ) KAB = H (KS SIDB )

Status: ACCEPTED Status: ACCEPTED

Protocol 6.1: A revised key agreement protocol of Boyd

2. There is no partnering mechanism (e.g., session identiļ¬ers) speciļ¬ed in the ear-

lier protocol of Boyd. Message exchanges in the real world are seldom conducted

over secure channels. Therefore, it is realistic to assume that any adversary is

able to modify messages at will, which is the case in the Bellareā“Rogaway style

models [1, 4, 5, 6, 7]. As Goldreich and Lindell [11, Section 1.3] have pointed

out, such an adversary capability means that the adversary is able to conduct

concurrent executions of the protocol (one with each party). Therefore, without

such partnering mechanism, communicating parties will be unable to uniquely

distinguish messages from different sessions. Hence, in Protocol 6.1, we deļ¬ne

partnership using the notion of session identiļ¬ers, SID1 .

3. The key conļ¬rmation messages have been removed, which consist of a hand-

shake using the shared secret. These can easily be added in a standard way [4].

The session key itself must not be used to authenticate the key conļ¬rmation mes-

ńņš. 39 |