A

Output θ

ME

Fig. 3.1 Game GM E

M E runs A to determine whether m0 or m1 was encrypted as γA and γB . By exam-

ining all oracle queries made by A , M E outputs her prediction, θ . The details of

the game GM E in Figure 3.1 are explained as follows.

Stage 1: M E is provided permanent access to two different encryption oracles OkA

and OkB associated with encryption keys kA and kB respectively.

Stage 2: M E chooses a pair of messages (m0 , m1 ) of equal length and hands

them to the challenger. The challenger then chooses a random challenge bit, θ (i.e.,

θ ∈R {0, 1}), and returns the ciphertexts γA and γB to M E , where γA = EkA (mθ ) and

γB = EkB (mθ ). M E then randomly chooses the following:

• target initiator and responder principals, A and B, where A, B∈R {U1 , . . . , UNp },

• target session between A and B whose instance at the server is u (i.e., the session

u

of ΨA,B ), where u∈R {1, . . . , Ns },

enc

• list of encryption keys (i.e., KUi ) for all participants except A and B, and list of

MAC

MAC keys (i.e., KUi ) for all participants.

Stage 3: M E runs A to determine whether m0 or m1 was encrypted as γA and γB .

By examining all oracle queries made by A , M E outputs her prediction, θ . A

makes a series of SendClient(U1 ,U2 , ι, m), SendServer(U1 ,U2 , ι, m), Reveal(U, ι),

and Corrupt(U, K) oracle queries to M E , which can be answered by M E as ex-

plained below. At some point during GM E , A makes a Test(U1 ,U2 , ι) query on

some fresh oracle (in the sense of De¬nition 2.3.1), which M E must also answer.

3.2 A Revised 3PKD Protocol in Bellare“Rogaway Model 67

On receipt of SendClient(U1 ,U2 , ι, m) queries:

• If U1 = initiator, U2 = responder, and m = —, then this will start a protocol run.

This query can be successfully answered by M E and the outgoing message

is some randomly chosen k-bit challenge RU1 .

• If U1 = responder, U2 = initiator, and m is some k-bit challenge RU1 , then M E

will successfully answer with RU1 , RU2 , where RU2 is some randomly chosen

k-bit challenge.

• If UI = initiator, UR = responder (where {U1 ,U2 } = {UI ,UR }), and the mes-

sage m = {SKU1 ,U2 ,ι }KU , [UI ,UR , RUI , RUR , {SKU1 ,U2 ,ι }KU ]K MAC . Since we as-

enc enc

U1

1 1

sume that A is not able to produce any MAC forgeries, all session keys (if

accepted) are known from the SendServer(U1 ,U2 , ι, m) queries. Hence, if the

MAC digest veri¬es correctly, the MAC digest must be authentic (i.e., must

have been generated by M E during a SendServer query) and in this case,

M E will output the decision δ = accept. Otherwise, M E will output the

decision δ = reject, as the protocol speci¬cation demands.

• If UI = initiator, UR = responder where {U1 ,U2 } = {UI ,UR }, and m ∈

{(γA , [UI ,UR , RUI , RUR , γA ]K MAC ), (γB , [UI ,UR , RUI , RUR , γB ]K MAC )}.

U1 U1

M E will be given γA and γB as input, and hence known to M E . With the

assumption that A is not able to produce any MAC forgeries, if the MAC

digest veri¬es correctly, then the MAC digest must have been generated by

M E during a SendServer query. In this case, M E will output the decision

δ = accept, otherwise M E will output the decision δ = reject, as the protocol

speci¬cation demands.

• In all other cases the input to the SendClient query is invalid, so M E will

randomly choose a bit θ as its response and hand it to the challenger. Hence,

SendClient queries can be correctly answered by M E .

On receipt of SendServer(U1 ,U2 , ι, m) queries:

Message m must be of the form (RU1 , RU2 ), where RU1 and RU2 are some k-bit

challenges, otherwise M E will randomly choose a bit θ as its response and

hand it to the challenger.

• If this is the target session (i.e., U1 = A, U2 = B, and ι = u), then M E

will compute the MAC digest using the respective MAC keys and output

(γA , [U1 ,U2 , RU1 , RU2 , γA ]K MAC ) and (γB , [U1 ,U2 , RU1 , RU2 , γB ]K MAC ) to U1 and

B

A

U2 respectively.

• If this is not the target session, M E will compute the MAC digest using

the respective MAC keys and output (±U1 , [U1 ,U2 , RU1 , RU2 , ±U1 )]K MAC ) and

U1

(±U2 , [U1 ,U2 , RU1 , RU2 , ±U2 )]K MAC ) to U1 and U2 respectively, where ±U1 =

U2

OkA (SKU1 ,U2 ,ι ) if U1 = A, ±U1 = {SKU1 ,U2 ,ι }KU if U1 = A, ±U2 =OkB (SKU2 ,U1 ,ι )

enc

1

if U2 = B, and ±U2 = {SKU2 ,U1 ,ι }KU if U2 = B.

enc

2

68 3 A Flawed BR95 Partnership Function

• In all other cases the input to the SendServer query is invalid, so M E will

randomly choose a bit θ as its response and hand it to the challenger. Hence,

SendServer queries can be correctly answered by M E .

On receipt of Reveal(U1 ,U2 , ι) queries:

ι

• If ΠU1 ,U2 has accepted and it forms the target session (i.e., {U1 ,U2 } = {A, B})

ι

and the last ¬‚ow that ΠU1 ,U2 received had the form (±, β ), where ± ∈ {γA , γB }),

then M E will randomly choose a bit θ as its response and hand it to the

challenger.

• If this session has accepted but it is not the target session, then M E will

output the session key SKU1 ,U2 ,ι , since all session keys are known from the

SendServer(U1 ,U2 , ι, m) queries.

• In all other cases the input to the Reveal query is invalid, so M E will ran-

domly choose a bit θ as its response and hand it to the challenger. Hence,

Reveal queries can be correctly answered by M E .

On receipt of Corrupt(U, K) queries:

• If U ∈ {A, B} (i.e., A is trying to corrupt the initiator or responder principal

of the target session), then M E will randomly choose a bit θ as its response

and hand it to the challenger.

• If U ∈ {U1 , . . . ,UNp } \ {A, B}, then M E will hand all internal information for

enc

U to A , update U as corrupted and also update KU to be K.

On receipt of Test(U1 ,U2 , ι) query:

ι

• If this is the target session (i.e., {U1 ,U2 } = {A, B} and the last ¬‚ow that ΠU1 ,U2

received had the form (±, β ), where ± ∈ {γA , γB }), then M E will answer the

query with m0 , else M E will randomly choose a bit θ as its response and

hand it to the challenger. After making a Test query and getting an answer of

the form SKU1 ,U2 ,ι from M E , A continues interacting with the protocol and

eventually outputs a guess bit b , where b ∈R {0, 1}. M E then outputs θ = b

as its response and hands it to the challenger.

The random choices of A, B, and u by M E mean that the probability that the target

session is the same as the session that A chooses as the Test session is N 21N . We

ps

claim that if the target session and Test session are the same, and the Test session

is fresh, then M E will succeed whenever A succeeds and fail whenever A fails.

j

i

To see that this is true, suppose ΠA,B and ΠB,A receive γA and γB and both accept. If

A attempts to reveal either of these oracles, then neither will be considered fresh.

This can be seen since the valid MAC digests mean that both oracles have the same

SID, and the random generation of both components of the SID implies that no other

j

i

(honest) party will have accepted with the same SID, and thus ΠA,B and ΠB,A are

partners (since it is easy to verify that the other partnership requirements are also

j

i

met). We also observe that no other oracle apart from ΠA,B and ΠB,A accepts after

receiving γA and γB since only one server instance outputs a valid MAC digest for

this pair of ciphertexts, and this server instance only outputs a valid MAC digest for

3.2 A Revised 3PKD Protocol in Bellare“Rogaway Model 69

one pair of nonces.