complexity t, making at most qe queries to the encryption oracle, totalling at

most 2μe bits, and qp queries to the padding oracle. The scheme is said to be

LOR-PO-CPA secure if Advlor’po’cpa is negligible for any adversary A whose

CBCPAD

time complexity is polynomial in k.

Real-or-Random Indistinguishability. Here, the attacker submits a message

x to a real-or-random encryption oracle and its challenge is to determine whether

it receives the encryption of x or the encryption of some random r, in response.

In our new model the two messages x, r need not be of equal length but must be

of equal length once they are padded, otherwise a trivial attack is possible1 . The

attacker will also be supplied with access to a padding oracle P. For b ∈ {0, 1},

we de¬ne the real-or-random oracle E-CBCPAD,K (RR(·, b)) by:

Oracle E-CBCPAD,K (RR(x, b))

if b = 1, then C ← E-CBCPAD,K (x)

r

else, r ← {0, 1}— such that |E-CBCK (r)| = |E-CBCK (x)|

C ← E-CBCPAD,K (r)

return C

1

We must therefore assume that it is easy to generate r at random subject to this

constraint; this is the case for padding methods used in practice.

346 K.G. Paterson and G.J. Watson

De¬nition 4. [ROR-PO-CPA] Consider the encryption scheme CBCPAD .

Let b ∈ {0, 1} and k ∈ N. Let A be an attacker that has access to the oracles

E-CBCPAD,K (RR(·, b)) and P(·). The game played is as follows

Experiment Expror-po-cpa’b (k)

CBCP AD ,A

r

K ← K-CBC(k)

b ← AE-CBCPAD,K (RR(·,b)),P(·) (k)

return b

The attacker wins when b = b and its advantage is de¬ned to be:

Advror-po-cpa (k) = Pr[Expror-po-cpa-1 (k) = 1] ’ Pr[Expror-po-cpa-0 (k) = 1].

CBCPAD ,A CBCP AD ,A CBCP AD ,A

The advantage function of the scheme is de¬ned to be:

Advror’po’cpa (k, t, qe , μe , qp ) = max{Advror’po’cpa (k)}

CBCPAD CBCPAD ,A

A

for any integers t, qe , μe , qp . The maximum is over all adversaries A with time

complexity t, making at most qe queries to the encryption oracle, totalling at

most μe bits, and qp queries to the padding oracle. The scheme is said to be

ROR-PO-CPA secure if Advror’po’cpa is negligible for any adversary A whose

CBCPAD

time complexity is polynomial in k.

Find-then-Guess Security. Here, the security game is de¬ned in two stages.

First the attacker must ¬nd two messages x0 , x1 upon which it wishes to be

challenged. The challenger then sends y, the encryption of either x0 or x1 , to the

attacker. In the second stage, the attacker must guess which of these two mes-

sages x0 , x1 , is the decryption of y. Note that the two messages x0 , x1 need not

be of equal length but must be of equal length once they are padded, otherwise

a trivial attack is possible.

De¬nition 5. [FTG-PO-CPA] Consider the encryption scheme CBCPAD . Let

b ∈ {0, 1} and k ∈ N. Let A be an attacker that has access to the oracles

E-CBCPAD,K (·) and P(·). The game played is as follows

Experiment Expftg-po-cpa-b (k)

CBCP AD ,A

r

K ← K-CBC(k)

(x0 , x1 , s) ← AE-CBCPAD,K (·),P(·) (k, ¬nd)

y ← E-CBCPAD,K (xb )

b ← AE-CBCPAD,K (·),P(·) (k, guess, y, s)

return b

The attacker wins when b = b and its advantage is de¬ned to be:

Advftg-po-cpa (k) = Pr[Expftg-po-cpa-1 (k) = 1] ’ Pr[Expftg-po-cpa-0 (k) = 1].

CBCPAD ,A CBCP AD ,A CBCP AD ,A

The advantage function of the scheme is de¬ned to be:

Advf tg’po’cpa (k, t, qe , μe , qp ) = max{Advf tg’po’cpa (k)}

CBCPAD CBCPAD ,A

A

Immunising CBC Mode Against Padding Oracle Attacks 347

for any integers t, qe , μe , qp . The maximum is over all adversaries A with time

complexity t, making at most qe queries to the encryption oracle, totalling at

most μe bits, and qp queries to the padding oracle. The scheme is said to be

FTG-PO-CPA secure if Advf tg’po’cpa is negligible for any adversary A whose

CBCPAD

time complexity is polynomial in k.

2.4 One-Way Security

As we shall see, many padding methods are not secure in the above models,

but do provide a weaker form of security, in that they prevent an attacker using

access to a padding oracle to perform decryption (i.e. they prevent Vaudenay™s

original attack). We next de¬ne a notion of security appropriate to this weaker

requirement. Now the attacker™s challenge is to ¬nd the decryption of a challenge

ciphertext c— . For simplicity of presentation, we focus here on the case where

this ciphertext is selected uniformly at random from the set of valid ciphertexts

having at most n + 1 blocks, for some value n = n(k). This uniform distribution

on ciphertexts will in turn imply a padding-speci¬c distribution D on the space

of unpadded messages. Our de¬nition is easily extended to the case of arbitrary

distributions on this space.

De¬nition 6. [OW-PO-CPA] Consider the encryption scheme CBCPAD . Let

k ∈ N. Let A be an attacker that has access to the oracles E-CBCPAD,K (·) and

P(·). The game played is as follows

Experiment Expow-po-cpa,A (k)

CBCP AD

r

K ← K-CBC(k)

r

x←D

c— ← E-CBCPAD,K (x)

x ← AE-CBCPAD,K (·),P(·) (k, c— )

return x

The attacker wins when x = x and its advantage is de¬ned to be:

Advow-po-cpa (k) = Pr[Expow-po-cpa,A (k) = x].

CBCPAD,A CBCP AD

The advantage function of the scheme is de¬ned to be:

Advow’po’cpa (k, t, qe , μe , qp ) = max{Advow’po’cpa (k)}

CBCPAD CBCPAD,A

A

for any integers t, qe , μe , qp . The maximum is over all adversaries A with time

complexity t, making at most qe queries to the encryption oracle, totalling at

most μe bits, and qp queries to the padding oracle. The scheme is said to be

OW-PO-CPA secure if Advow’po’cpa is negligible for any adversary A whose

CBCPAD

time complexity is polynomial in k.

Note that this model does allow us to study an adversary which strictly adheres

to Vaudenay™s original attack model, i.e. where the adversary makes no queries

to the encryption oracle (qe = μe = 0).

348 K.G. Paterson and G.J. Watson

2.5 Relations between Models

We can prove that the same relations between the models without padding

oracles, established in [1], also hold for these new models. Proofs of the following

results are given in the appendix.

Theorem 1. [ROR-PO-CPA ’ LOR-PO-CPA] For the encryption

scheme CBCPAD ,

Advlor-po-cpa (k, t, qe , μe , qp ) ¤ 2.Advror-po-cpa (k, t, qe , μe , qp ).

CBCPAD CBCPAD

Theorem 2. [LOR-PO-CPA ’ ROR-PO-CPA] For the encryption

scheme CBCPAD ,

Advror-po-cpa (k, t, qe , μe , qp ) ¤ Advlor-po-cpa (k, t, qe , μe , qp ).

CBCPAD CBCPAD

Theorem 3. [LOR-PO-CPA ’ FTG-PO-CPA] For the encryption scheme