security model used in [2] e¬ectively denies the adversary access to the decryp-

tion oracle as soon as he submits an invalid ciphertext to it. This re¬‚ects what

SSH does in practice, but severely limits the use that a theoretical adversary

might make of such a decryption oracle. A second example of formal analysis of

real-world protocols is provided by the work of Boldyreva and Kumar [4], who

provided a provable security treatment of authenticated encryption in the Ker-

beros protocol suite. This analysis seems to take into account every component

used in the Kerberos authenticated encryption algorithm except for padding. A

third example is provided by [8], in which Krawczyk studies the security prop-

erties of the “MAC-then-encrypt” paradigm as used in SSL/TLS (but his proof

does not take into account any padding).

A useful survey of side channel attacks, including padding oracle attacks, can

be found in [13].

Immunising CBC Mode Against Padding Oracle Attacks 343

2 De¬nitions and Models for Chosen Plaintext Security

2.1 CBC Mode for Arbitrary Length Messages

Let F = {FK : K ∈ K} be a family of permutations with input-length and

output-length l and k-bit key K. In [1], Bellare et al. de¬ne CBC mode based on

the permutation family F to be the scheme CBC[F ] = (E-CBC, D-CBC, K-CBC)

with inputs that are restricted to be a multiple of the block length l. In practice,

of course, plaintext messages may not satisfy this constraint, and so they need

to be padded before encryption and subsequently depadded after decryption.

Let B denote the set {{0, 1}il : i ≥ 0} of bit strings whose length is a non-

negative multiple of l, and let PAD : {0, 1}— ’ V ‚ B and DPAD : B ’

{0, 1}— ∪ {⊥P } be functions de¬ning a speci¬c padding method. These mappings

should both be easy to compute. We say that V is the set of all valid padded

messages. For each i ∈ N, let Vi be the set of messages of length il bits (i blocks)

in V , so that V = i Vi . Let I = B \ V and for each i ∈ N, let Ii be the set

of messages of length il bits in I, so that I = i Ii . We say that I is the set

of all invalid padded messages. For consistency, we require that for any x ∈ I,

DPAD(x) returns ⊥P , and that x = DPAD(PAD(x)) for any x ∈ {0, 1}—.

Given functions PAD, DPAD and family of permutations F , we de¬ne the

scheme CBCP AD [F ] = (E-CBCPAD , D-CBCDPAD , K-CBC) as follows. This

scheme uses the same key generation algorithm K-CBC as in [1], taking as

input a security parameter k ∈ N and outputting a random k-bit key K for

the underlying permutation family, specifying a function FK . We then de¬ne

E-CBCK,PAD (x) = E-CBCFK (x) and D-CBCK,DPAD (y) = D-CBCFK (y),

PAD DPAD

where:

function E -CBCFK (x) function D-CBCFK (y)

PAD DPAD

x = PAD(x)

˜ Parse y into l-bit blocks as y0 y1 . . . yn

’1

for i = 1, . . . , n do xi = FK (yi ) • yi’1

Parse x into l-bit blocks x1 x2 . . . xn

˜

r

y0 ← {0, 1}l x = DPAD(x1 x2 . . . xn )

for i = 1, . . . , n do yi = FK (yi’1 • xi ) return x

return y0 y1 y2 . . . yn

As an important illustrative example, we de¬ne OZ-PAD, as suggested by the

ISO standard ISO/IEC 10116:2006 for use with CBC mode:

De¬nition 1. [OZ-PAD] The respective padding and depadding functions are:

function PADOZ (x) function DPADOZ (˜) x

r = |x| mod l Parse x as a sequence of l-bit blocks x1 x2 . . . xn

˜

return x = x 1 0l’r’1 if xn = 0l , then set x =⊥

˜

else Parse xn as x 1 0l’r’1

Set x = x1 x2 . . . xn’1 x

return x

Note that with this de¬nition, a padded plaintext is invalid precisely when its

last block is all-zero.

344 K.G. Paterson and G.J. Watson

2.2 Padding Oracles

A padding oracle P(·) indicates whether the plaintext message underlying the in-

put ciphertext is correctly or incorrectly padded, based upon some ¬xed padding

method and for some ¬xed key.

De¬nition 2. A padding oracle P, takes as input any string y ∈ {0, 1}— and

outputs one bit of information. If the underlying plaintext is correctly padded

(i.e. lies in the set V ) the oracle outputs 1; otherwise it outputs 0. Formally:

Oracle P(y)

if D-CBCK,DPAD (y) =⊥P , then return 1

else return 0

Vaudenay [11] showed how an attacker, given repeated access to a padding oracle

for CBC mode implemented with the padding method CBC-PAD, can perform

decryption to recover plaintexts. His results were extended by Black and Urtubia

to other padding methods in [3] and to other attack scenarios in [10,12].

2.3 Security Models

We now extend the usual security models for symmetric encryption as de¬ned

in [1] to provide the adversary with additional access to a padding oracle as in

De¬nition 2. Here, we only consider the Chosen Plaintext Attack (CPA) setting.

We generalise the existing Left-or-Right Indistinguishability, Real-or-Random

Indistinguishability and Find-then-Guess Security de¬nitions to include padding

oracles, and establish the essential equivalence of these di¬erent de¬nitions (as

was done by Bellare et al. [1] for the usual case). Thereafter, we will prove results

using the Left-or-Right Indistinguishability de¬nition.

In fact, our models provide much stronger notions of security than are

required to resist Vaudenay™s original attack: roughly speaking they provide

semantic security against an attacker equipped with encryption and padding

oracles, whereas Vaudenay™s attack only gives the attacker access to a padding

oracle. This enhanced security is certainly desirable, but many padding meth-

ods used in, or recommended for, practice (e.g. OZ-PAD as recommended in

ISO/IEC 10116:2006) cannot achieve our new notions. So we also introduce a

weaker “one-way” notion of security to more exactly quantify the resistance of

these padding methods to Vaudenay™s original attack.

Note that these models could be used more generally with other modes of

operation that require padding. This would be an interesting area for future

work.

Left-or-Right Indistinguishability. In this model, the attacker submits two

messages (x0 , x1 ) to a left-or-right encryption oracle and its challenge is to de-

termine whether it receives the encryption of x0 or x1 in response. In our new

model, the two messages x0 , x1 need not be of equal length but must be of equal

length once they are padded, otherwise there is a trivial attack. The attacker

Immunising CBC Mode Against Padding Oracle Attacks 345

will also be supplied with access to a padding oracle P to which it may submit

arbitrary strings. For b ∈ {0, 1}, we de¬ne the left-or-right encryption oracle

E-CBCPAD,K (LR(·, ·, b)) by:

Oracle E-CBCPAD,K (LR(x0 , x1 , b))

if b = 0, then C ← E-CBCPAD,K (x0 )

else (b = 1), C ← E-CBCPAD,K (x1 )

return C

De¬nition 3. [LOR-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 (LR(·, ·, b)) and P(·). The game played is as follows

Experiment Explor-po-cpa’b (k)

CBCP AD ,A

r

K ← K-CBC(k)

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

return b

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

Advlor-po-cpa (k) = Pr[Explor-po-cpa-1 (k) = 1] ’ Pr[Explor-po-cpa-0 (k) = 1].

CBCPAD ,A CBCP AD ,A CBCP AD ,A

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

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

CBCPAD CBCPAD ,A

A