3b. enc enc

BS

Protocol 3.2: An Improved Provably Secure 3PKD Protocol

The primitives used in Protocol 3.2 are the notions of a secure encryption scheme

and a secure message authentication scheme described in Chapter 2.1.4.

3.2.3 Security Proof for the Improved 3PKD Protocol

In this section, we present the proof for Protocol 3.2.

Theorem 3.2.1 Protocol 3.2 is a secure key establishment protocol in the sense of

De¬nition 2.3.7 if the underlying message authentication scheme is secure in the

sense of existential unforgeability under adaptive chosen message attack (ACMA)

as described in De¬nition 2.1.16 and the underlying encryption scheme is in-

distinguishable under chosen plaintext attack (IND-CPA) as described in De¬ni-

tion 2.1.13.

The proof of Theorem 3.2.1 generally follows that of Bellare and Rogaway [4], but

is adjusted to the different partnering function used. The validity of the protocol is

straightforward to verify and we concentrate on the indistinguishability requirement.

The security of Protocol 3.2 is proved by ¬nding a reduction to the security of the

encryption scheme and the message authentication scheme. Let Ns be the maximum

number of sessions between any two parties in the protocol run and Np be the max-

imum number of players in the protocol run, where both Ns and Np are polynomial

in the security parameter k. Security is proved by ¬nding a reduction to the secu-

rity of the underlying message authentication scheme and the underlying encryption

scheme.

The general notion of the proof is to assume that there exists an adversary A who

can gain a non-negligible advantage in distinguishing the test key in game G (i.e.,

AdvA (k) is non-negligible), and use A to break the underlying encryption scheme

or the message authentication scheme. In other words, we consider an adversary A

that breaks the security of the protocol.

Using results of Bellare, Boldyreva and Micali [1], we may allow an adversary

64 3 A Flawed BR95 Partnership Function

against an encryption scheme to obtain encryptions of the same plaintext under dif-

ferent independent encryption keys. Such an adversary is termed a multiple eaves-

dropper, M E . In Protocol 3.2, upon receiving a message from the responder prin-

cipal, the server sends out two ciphertexts derived from the encryption of the same

plaintext under two independent encryption keys. Hence, we consider a multiple

eavesdropper M E who is allowed to obtain encryptions of the same plaintext under

two different independent encryption keys. The formal de¬nition of M E is given

by De¬nition 3.2.1.

De¬nition 3.2.1 ([1, 4]) Let © = (K , E , D) be an encryption scheme with security

parameter k, S E be the single eavesdropper and M E be the multiple eavesdrop-

per, and OkA and OkB be two different independent encryption oracles associated

with encryption keys kA and kB . We de¬ne the advantage functions of S E and M E

to be:

AdvS E (k) = 2 — Pr[S E ← OkA ; (m0 , m1 ∈R S E ); θ ∈R {0, 1}; γA ∈R OkA (mθ )

: S E (γA ) = θ ] ’ 1

AdvM E (k) = 2 — Pr[M E ← OkA , OkB ; (m0 , m1 ∈R M E ); θ ∈R {0, 1};

γA ∈R OkA (mθ ), γB ∈R OkB (mθ ) : M E (γA , γB ) = θ ] ’ 1

Lemma 3.2.1 ([1]) Suppose the advantage function of S E against the encryption

scheme is µk . Then the advantage function of M E is at most 2 — µk .

As a consequence of Lemma 3.2.1, an encryption scheme secure against IND-CPA

in the single eavesdropper setting will also be secure against IND-CPA in the mul-

tiple eavesdropper setting [1].

The proof is divided into two cases since the adversary A can either gain her advan-

tage against the protocol while forging a MAC digest with respect to some user™s

MAC key or gain her advantage against the protocol without forging a MAC digest.

The proof assumes that there exists an adversary A who has a non-negligible ad-

vantage against the protocol, and shows that this implies that either the encryption

scheme or the message authentication scheme is insecure.

3.2.3.1 Adaptive MAC Forger F

Following the approach of Bellare, Kilian and Rogaway [2], we quantify security

of the MAC scheme in terms of the probability of a successful MAC forgery under

adaptive chosen-message attack, which we denote by Pr[SuccF (k)]. For the MAC

scheme to be secure under chosen-message attack, Pr[SuccF (k)] must be negligi-

ble. In other words, the MAC scheme is considered broken if a forger F is able to

produce a valid MAC forgery for a MAC key unknown to it.

For the ¬rst part of the proof, assume that at some stage A asks a SendClient(B,

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

j j

A, j, (±B, j , βB, j )) query to some fresh oracle, ΠB,A , such that ΠB,A accepts, but the

MAC digest value βB, j used in the SendClient(B, A, j, (±B, j , βB, j )) query was not

previously output by a fresh oracle. Hence, Pr[MACforgery] is non-negligible. We

construct an adaptive MAC forger F against the security of the message authenti-

cation scheme using A . We de¬ne an attack game GF as follows.

• Stage 1: F is provided permanent access to the MAC oracle Ox associated with

the MAC key x throughout the game GF .

“ F randomly chooses a principal U, where U ∈ {U1 , . . . ,UNp }. U is F ™s guess

at which principal A will choose for the MAC forgery.

“ F randomly generates the list of MAC keys for the {U1 , . . . ,UNp } \ {U} prin-

cipals.

“ F randomly generates the list of encryption keys of the {U1 , . . . ,UNp } princi-

pals.

• Stage 2: F runs A and answers all oracle queries from A . This can be done in

a straightforward manner since F can respond to all oracle queries from A as

required using the keys chosen in Stage 1 and Ox . In addition, F records all the

MAC digests it receives from Ox . If, during its execution, A makes an oracle

query that includes a forged MAC digest for U, then F outputs the MAC forgery

as its own, and halts. Otherwise, F halts when A halts.

The random choice of U by F means that the probability that U is the party for

whom A generates a forgery (if A generates any forgery at all) is at least 1/Np .

Hence, the success probability of F is

Pr[MACforgery(k)]

Pr[SuccF (k)] ≥ .

Np

Hence

Pr[MACforgery] ¤ Np · Pr[SuccF (k)].

Since we know that Np is polynomial in the security parameter k and AdvF (k)

is negligible by de¬nition of the security of the message authentication scheme,

Pr[MACforgery] is also negligible.

3.2.3.2 Multiple Eavesdropper Attacker M E

The second part of the proof assumes that the adversary A gains her advantage

without forging a MAC digest. We construct another algorithm M E that uses A

against the security of the encryption scheme, whose behaviour is described by the

attack game GM E shown below and in Figure 3.1. Recall that M E hands a pair of

messages (m0 , m1 ) to the challenger and receives γA = EkA (mθ ) and γB = EkB (mθ ),

which are encryptions under two different keys of one of the messages. The objec-

tive of M E is to correctly predict the challenge bit θ in the game simulation GM E

(i.e., have θ = θ ).

66 3 A Flawed BR95 Partnership Function

Oracle Queries

Stage 1

Test Query

Stage 2

Access to OkA and OkB

Oracle Queries

Stage 3

m0 , m1

Output b

Stage 4

γA , γB