Advlor-po-cpa (k, t, qe , μe , qp ) ¤ Advftg-po-cpa (k, t, qe + 1, μe , qp ).

CBCPAD CBCPAD

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

CBCPAD ,

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

CBCPAD CBCPAD

This last result establishes that if a scheme has security in the Find-then-Guess

sense then it is secure in the Left-or-Right sense, but the security shown is

qualitatively lower.

3 Padding Methods for Chosen Plaintext Security

We are now ready to consider the security of the scheme CBCP AD [F ] for par-

ticular functions PAD, DPAD and permutation families F , in the presence of

padding oracles. We recall that this scheme is already known to be insecure for

many padding methods [11,3]. We divide our study of padding methods into two

types:

“ Padding methods with invalid paddings (|I| > 0);

“ Padding methods with no invalid paddings (|I| = 0).

3.1 Padding Methods with Invalid Paddings

We recall the de¬nition of the OZ-PAD method from Section 2.1. Here, the only

invalid padded messages are those where the last block of plaintext is the all-zero

block, 0l . Since the likelihood of being able to generate a ciphertext where the

last block of plaintext is 0l is low, this suggests that OZ-PAD used with CBC

mode may provide some form of security. However, an adversary can exploit this

fact when performing a padding oracle attack against CBC mode using OZ-PAD

in our LOR-PO-CPA attack model, as follows:

Immunising CBC Mode Against Padding Oracle Attacks 349

1. Choose any two distinct messages m0 , m1 of length less than l.

2. Query the left-or-right encryption oracle on input (m0 , m1 ) to obtain output

of the form y0 y1 .

3. Submit (y0 • m0 )y1 to the padding oracle P. If the response is 0, then return

b = 0, otherwise return b = 1.

This very simple attack was ¬rst presented by Black and Urtubia in [3]. It

shows that OZ-PAD, as recommended in ISO/IEC 10116:2006 is not secure in

the sense of indistinguishability of encryptions. This attack can be applied to

many other padding methods which have invalid paddings:

Lemma 1. Consider a padding method de¬ned by functions PAD, DPAD. Let

V1 , I1 be the sets of one-block valid and invalid messages respectively. Then the

encryption scheme CBCPAD is not LOR-PO-CPA secure if either of the following

conditions is satis¬ed:

1. |V1 | > |I1 | > 0; or

2. |V1 | ≥ 3 and |V1 |, |I1 | are both odd.

Proof. We wish to perform a similar attack as was successful against CBC mode

with OZ-PAD in the LOR-PO-CPA model. In order to do this, we must ¬nd two

messages m0 , m1 such that their padded versions p0 , p1 ∈ V1 satisfy p0 • m ∈ V1

and p1 • m ∈ I1 for some mask m ∈ {0, 1}l: submitting (m0 , m1 ) to the left-or-

right encryption oracle gives an output of the form y0 y1 , and then the response

of the padding oracle to input (y0 • m)y1 will tell us which one of m0 , m1 was

encrypted.

Proof of 1: Select p1 arbitrarily from V1 and any value i1 ∈ I1 ; let m1 =

DPAD(p1 ), and set m = p1 • i1 , so p1 • m = i1 ∈ I1 . The map φm de¬ned by

φm (x) = x • m is an injective map from V1 to {0, 1}l. So |φm (V1 )| = |V1 | > |I1 |.

This shows that, no matter the value of m, there exists some p0 ∈ V1 with

p0 • m ∈ I1 ; hence p0 • m ∈ V1 . Now let m0 = DPAD(p0 ). Thus we have

/

constructed two messages m0 , m1 and a mask m with the required properties.

Proof of 2: Set p0 , v to be any two distinct values from V1 , and set m = p0 • v

and m0 = DPAD(p0 ). Clearly p0 • m = v ∈ V1 and m = 0l . We now wish to

construct p1 ∈ V1 satisfying p1 • m ∈ I1 , and take m1 = DPAD(p1 ). Suppose,

for a contradiction, that p1 • m ∈ V1 for every p1 ∈ V1 . Then, given that m = 0l ,

we can divide V1 into a covering of disjoint sets of size 2 of the form {p1 , p2 }

satisfying the equation p1 • m = p2 . This contradicts the fact that V1 has odd

cardinality. It follows that p1 • m ∈ I1 for some choice of p1 and we are done.

Perhaps surprisingly, this result shows that any padding method having small

(but non-zero) numbers of invalidly padded messages cannot be secure in the

sense of indistinguishability. It includes the method OZ-PAD as an extremal

case (|I1 | = 1). However, as we shall see, padding methods having no invalid

padded messages at all (implying |I1 | = 0) are actually immune to padding

oracle attacks, being secure in our LOR-PO-CPA sense.

350 K.G. Paterson and G.J. Watson

Despite CBC mode with OZ-PAD not having LOR-PO-CPA security, we can

prove that it satis¬es our weaker notion of OW-PO-CPA security, assuming that

the permutation family F used in its construction is a one-way permutation

family (a concept which we de¬ne formally below). This implies that CBC mode

with OZ-PAD provably resists Vaudenay™s original attack under a rather mild

assumption about the permutation family F .

De¬nition 7. [One-way Permutation Family] Let F = {FK : K ∈ K} be

a permutation family, with input and output length l and k-bit key. Let A be an

adversary with access to an oracle for F as de¬ned in the experiment below:

Experiment Expowp (k)

F,A

r

K←K

r

x ← {0, 1}l, y ← FK (x)

x ← AFK (·) (y)

return x

The advantage of the adversary A is de¬ned to be:

Advowp (k) = Pr[Expowp = x].

F,A F,A

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

Advowp (k, t, qF ) = max{Advowp (k)}

F F,A

A

where the maximum is over all A with time complexity t, each making at most

qF queries to the oracle for FK .

We informally say that F is a one-way permutation family to indicate that

Advowp (k, t, qF ) is “low” for “reasonable” values of t, qF .

F

Theorem 5. [Security of CBCPAD with OZ-PAD] Let F = {FK : K ∈ K}

be a permutation family on {0, 1}l with a k-bit key. Let PAD and DPAD be

the padding and depadding functions for OZ-PAD. Then CBCPAD [F ] is OW-

PO-CPA secure if F is a one-way permutation family. Concretely, for any

t, qe , μe , qp , we have:

1

Advow-po-cpa ] (k, t, qe , μe , qp ) ¤ Advowp (k, t , qF ) + .

CBCPAD [F F

2l

where t = O(t) and qF ¤ 1 + qp + qe (1 + μe /l).

Proof. Assume we have an adversary A1 , attacking CBCPAD [F ] in the OW-

PO-CPA sense. We assume that A1 should be given a challenge ciphertext c—

that is selected uniformly at random from the set of valid ciphertexts having at

most n + 1 blocks, for some value n. We use this adversary to construct a new

adversary A2 that breaks the one-wayness of the permutation family F . A2 ™s

input is a value y = FK (x) where K and x are selected uniformly at random,

and its job is to output the value x given oracle access to FK .

Immunising CBC Mode Against Padding Oracle Attacks 351

In the following construction for the adversary A2 we use its input y to construct

a ciphertext c— on which to challenge A1 . A2 selects c— uniformly at random from

the set {0, 1}il : 1 ¤ i ¤ n + 1, subject to the constraint that the last block

of c— equals y. Thus we may write c— = y0 y1 . . . yj for some j ≥ 1 and some l-

bit blocks yi , 0 ¤ i ¤ j, with yj = y. A2 then tests if FK (yj’1 ) = y by making a

query to its oracle for FK . If this equation holds, then A2 has successfully inverted

FK at y, so outputs yj’1 and halts. Since y is uniformly distributed, this event

’1

occurs with probability at most 2’l . Otherwise, we see that yj’1 • FK (y) = 0l ,

meaning that c— is a valid ciphertext (because the last block of the underlying

plaintext is validly padded according to the OZ-PAD method). By construction,

c— is uniformly distributed over the set of valid ciphertexts having at most n + 1