6.3 An Ef¬cient Protocol in Extended Model 111

2. Suppose the adversary, A , compromises the long-term key of A, KAS . With

knowledge of KAS , A can decrypt the earlier message, {A, B, gNA }KAS , and learn

gNA . A also knows gNB from observing the Protocol 6.2™s execution. However,

¬nding gNB NA is equivalent to solving the CDH problem (recall that NA has been

deleted from the internal state of A upon completion of the execution of Proto-

col 6.2). Moreover, this implies that Protocol 6.2 provides forward secrecy since

the knowledge of the compromised long-term keys, KAS or KBS , does not allow

the adversary to ¬nd the session key, KAB = H0 (A||B||gNA ||gNB ||gNB NA ).

6.3.2 Security Proof

Theorem 6.3.1 Assuming the Computational Dif¬e-Hellman (CDH) assumption is

satis¬ed in G, Protocol 6.2 is a secure key agreement protocol providing key con¬r-

mation and forward secrecy when H0 and H1 are modeled as random oracles and

if the underlying message authentication scheme and encryption scheme are secure

in the sense of existential unforgeability under adaptive chosen-message attack and

indistinguishable under chosen-plaintext attack respectively.

The validity of Protocol 6.2 is straightforward to verify and we concentrate on the

indistinguishability requirement. The security is proved by ¬nding a reduction to

the security of the underlying message authentication scheme and the underlying

encryption scheme.

The security of Protocol 6.2 is based on the CDH problem in the random ora-

cle model. An adversary, A , can get information about a particular session key

Ki j = H0 (i|| j||SIDk ||gNi N j ) if A has queried the random oracle on the point

i

i|| j||SIDk ||gNi N j . This will allows us to solve the CDH problem with probability

i

related to that of A ™s success probability.

The general notion follows that of the proof presented in Chapter 6.1.3. For consis-

tency, let Q be the upper bound of the number of parties in G , QS be the maximum

number of Send queries that A will ask of the server, and QH be the maximum

number of hash queries that A will ask of the server. The proof is divided into

two parts since the adversary, A , can either gain her advantage against Protocol 6.2

while forging a MAC digest or gain her advantage against Protocol 6.2 without forg-

ing a MAC digest.

The proof then concludes by observing that AdvA (k) is negligible when H0 , and

H1 are modeled as random oracles and if the underlying message authentication

scheme and encryption scheme are secure in the sense of existential unforgeability

under adaptive chosen-message attack and indistinguishable under chosen-plaintext

attack respectively, and therefore Protocol 6.2 is also secure.

112 6 An Extension to the Bellare“Rogaway Model

6.3.2.1 Integrity Breaker

We assume that there exists an adversary, A , against Protocol 6.2. We then construct

an integrity breaker, F1 , that make use of A to break the underlying message au-

thentication scheme. Let Forge be the event that, for some instance Πik with partner

Pj , the adversary queries Send(i, k, m) and (1) neither Pi nor Pj were ever corrupted;

(2) m was never sent by Pj and (3) Πik computes a valid session key.

Lemma 6.3.1 There is an ef¬cient algorithm F1 de¬ned using A such that if Forge

occurs with non-negligible probability then successF1 occurs with non-negligible

probability.

The integrity breaker, F1 , is able to simulate the view of A and answers all the or-

acle queries of A . F1 will continue the simulation until either the event that Forge

occurs or until A halts.

Let Pr(Forgei, j ) be the probability that Forge occurs for a speci¬c pair of parties

i, j. Clearly, we have Pr(Forge) ¤ N 2 · Pr(Forgei, j ) since we can embed an instance

of the CDH problem within the one-time MAC key. Now, if we replace the key,

Ki j = gU1U2 by a random element from G, this does not affect Pr(Forgei, j ) by more

than a factor loss of µ. However, the probability that Pr(Forgei, j ) occurs when Ki j is

truly random is at most µ by the security of the MAC. Therefore, we arrive at the

upper bound

Pr(Forge) ¤ N 2 (µ + µ ).

All queries by the adversary, A , can be answered normally by F1 . F1 continues the

simulation until Pr(Forge) happens or until A terminates. Thus, the simulation is

perfect so long F1 does not terminate. We then arrive at the following upper bound.

Pr(Forge) ¤ Q · N 2 (µ + µ ) · Pr(successF1 ). (6.3)

6.3.2.2 Con¬dentiality Breaker

We construct a con¬dentiality breaker, X1 , using A , as shown in the attack game,

GX1 . The idea underlying this proof follows that presented in Chapter 6.1.3.2. X1

is given access to the encryption oracles associated with the two random keys K and

K . X1 then generates the long-term key for all users, except two randomly selected

users, Ui and U j .

Let Pr(SuccessA |Forgei,j ) be the probability that the adversary, A , manages to gain

an advantage without forging a MAC digest for a speci¬c pair of parties i, j. Clearly,

we have Pr(SuccessA ) ¤ N 2 ·Pr(SuccessA |Forgei,j ) since we can embed an instance

of the CDH problem. Now, if we replace the key, Ki j = gU1U2 by a random element

from G, this does not affect Pr(Forgei, j ) by more than a factor loss of µ. However,

the probability that Pr(Forgei, j ) occurs when Ki j is truly random is at most µ by the

6.3 An Ef¬cient Protocol in Extended Model 113

security of the MAC. Therefore, we arrive at the upper bound

Pr(Forge) ¤ N 2 (µ + µ ).

X1 runs A and answers all oracle queries from A , as follows:

• For queries H0 (i|| j||SIDk ||Z), if this query was asked before, then return the

i

previous answer. Otherwise, return a random value, v ∈R {0, 1}k . In addition,

store this answer together with the query in a list of DH-tuples.

• For Send, Reveal, Corrupt, and Test queries, X1 answer them honestly.

• In the event that a Reset(U) query is asked, X1 is also able to answer this cor-

rectly by returning a new random long-term key generated using the key gen-

eration algorithm Kk . X1 has to maintain a table containing the internal state

associated with U.

1. If U has been corrupted, then the status of U is updated to be fresh. Otherwise,

X1 halts the simulation.

2. Then any oracle(s) U 1 , . . . ,Uiδ ’1 that were activated before the Reset query

are considered unfresh, while subsequent oracles Uiδ ,Uiδ +1 , . . . are considered

fresh.

• At the conclusion of the game simulation if X1 has not terminated, X1 randomly

chooses a tuple, (Ua ,Ub ,Uab ), from its list of DH-tuples, ¬nds a and b such that

Ua = U1 ga and Ub = U2 gb , and outputs U aUabgab .

Ub

2 1

Let

• event1 be the event that, for some i, j ∈ [q p ], A at some point queries the ran-

dom oracle at a point i|| j||SIDk ||gw , whereby both Pi and Pj are fresh (i.e., not

i

corrupted) in the entire course of G , and W = gNi N j .

• event2 be the event that, for some i, j ∈ [q p ], A at some point queries the random

oracle at a point i|| j||SIDk ||gx for some k, SIDk = U||V = gNi gN j and X = gNi N j .

i i

The probability that X1 returns the correct answer is at least PrA [event1§corrupted] ,

QH ·N 2 ·µ

since the simulation of GX1 is perfect until the point, if any, that event1 or event2

occurs. In the event that event2 occurs, with probability Q1H , X1 selects a tuple,

(Ua ,Ub ,Uab ), from its list of DH-tuples, for which Uab = g±1 ±2 where ±1 := loggUa

and ±2 := loggUb . In other words, this tuple, (Ua ,Ub ,Uab ), selected by X1 is a DH-

tuple. Then X1 has outputed a correct solution to the CDH instance. Thus,

PrA (event2) ¤ QH · µ.

Since we have shown that both PrA [event1§corrupted] ¤ QH ·N 2 ·µ and PrA

[event2] ¤ QH · µ, we have

Pr(successA |Forge) ¤ (QH · N 2 · µ + QH · µ) · Pr(successX1 ). (6.4)

114 6 An Extension to the Bellare“Rogaway Model

6.3.2.3 Conclusion of Security Proof

We know that N, QS , and QH are polynomial in the security parameter k and µ is