Now A2 needs to provide simulations of A1 ™s oracles.

To handle A1 ™s queries to the padding oracle P on input a (q + 1)-block

ciphertext c = c0 c1 . . . cq , A2 acts as follows. A2 calls FK on cq’1 and compares

’1

FK (cq’1 ) to cq . If FK (cq’1 ) = cq and so cq’1 • FK (cq ) = 0l , then A2 outputs

0 as the response to A1 ™s query; otherwise A2 outputs 1. We see that A2 ™s

simulation of padding oracle queries is perfect and requires one query to FK for

each query made by A1 .

To handle A1 ™s queries to the encryption oracle on input an unpadded plain-

text m, A2 acts as follows. First it applies the OZ-PAD padding method to m to

obtain a padded plaintext m = m1 m2 . . . mq having q blocks for some q. Notice

˜ ˜˜ ˜

that q is at most 1 + |m|/l where |m| denotes the bit-length of m. Then A2

r

selects y0 ← {0, 1}l and sets yi = FK (yi’1 • mi ) for each 1 ¤ i ¤ q. Finally, A2

˜

outputs y0 y1 . . . yq . This is obviously a correct encryption of m for the scheme

CBCPAD [F ] with permutation FK ∈ F . It is also easy to see that if A1 makes

at most qe encryption queries totalling at most μe bits, then A2 makes at most

qe (1 + μe /l) queries to its oracle for FK in handling these encryption queries.

The ¬nal output of A1 is a guess at the plaintext corresponding to the de-

cryption of c— . Let b denote the last block of the OZ-PAD padded version of

A1 ™s output. If A1 ™s output is correct, then we have the decryption equation

’1 ’1

b = yj’1 • FK (y). From this equation we have FK (y) = b • yj’1 and so A2

outputs b • yj’1 as its guess for x. We see that A2 is correct if A1 is. Hence A2 ™s

success probability is the same as A1 ™s.

Counting the total number of oracle queries made by A2 and estimating its

running time as O(t) completes the proof.

From the above theorem, we can say that CBC mode used with OZ-PAD does o¬er

security against Vaudenay™s original attack. Despite this, and as we previously

showed, OZ-PAD does not o¬er security in the stronger indistinguishability sense

that we desire. We therefore recommend using a padding method which does o¬er

this greater level of security. We now turn our attention to such methods.

3.2 Padding Methods With No Invalid Paddings

We ¬rst provide some examples of padding methods which have no invalid

padded messages (i.e. |I| = 0).

352 K.G. Paterson and G.J. Watson

Black and Urtubia [3] suggest the use of the Arbitrary Tail padding method.

Below, we de¬ne both the bit- and byte-oriented versions of this padding method;

the latter only applies for messages that are guaranteed to be a whole number

of bytes, and so does not strictly comply with our bit-oriented de¬nitions.

De¬nition 8. [Abit Pad] Study the last bit b of the message m. Pad the mes-

sage with the opposite of bit b. At least one padding bit must be added. For the

empty string m = , pad with either 0 or 1 with equal probability.

Note that we slightly alter Black and Urtubia™s original de¬nition of Abit Pad

to pad the empty string with a randomly chosen bit 0 or 1. This eliminates the

possibility of 1l being an invalid padded message. With this modi¬cation, Abit

Pad has no invalid padded messages.

De¬nition 9. [Abyte Pad] For a message m with k complete bytes, study the

last byte X of the message m. Pick some distinct random byte Y and pad the

message with this byte. At least one padding byte must be added.

Again, Abyte Pad has no invalid padded messages.

We prove the following simple result concerning the security of all padding

methods which have no invalid padded messages.

Theorem 6. [Security of CBCPAD for a padding method containing

no invalid paddings] Suppose F is a permutation family with length l. Let

PAD, DPAD be the padding and depadding functions for some padding method

with no invalid paddings. If CBC is LOR-CPA secure then CBCPAD is LOR-

PO-CPA secure. Concretely, for any t, qe , qp , μe

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

CBCPAD [F CBC[F

Proof. Assume we have an adversary A1 that attacks CBCPAD in the LOR-

PO-CPA sense. We then use this adversary to construct a new adversary A2 to

attack CBC in the LOR-CPA sense.

A2 will use its encryption oracle to provide a simulation of A1 ™s encryption

oracle on input x. A2 ¬rst runs PAD on x, and sends the padded message

to its encryption oracle, so E-CBCK,PAD (x) = E-CBCK (PAD(x)). Since the

padding method being used has no invalid padded messages this means that

any chosen ciphertext corresponds to a valid padded plaintext and so A2 models

A1 ™s padding oracle by returning 1 to any query. Finally, A2 outputs whatever

A1 outputs. It is evident that A2 ™s success probability is equal to that of A1 and

the result follows.

Note that this theorem can be strengthened to show that

Advlor-po-cpa ] (k, t, qe , μe , qp ) = Advlor-cpa ] (k, t, qe , μe )

CBCPAD [F CBC[F

under the assumption that the padding method satis¬es PAD(DPAD(y)) = y

for all y. Any deterministic padding scheme meets this requirement.

Immunising CBC Mode Against Padding Oracle Attacks 353

From the results of Bellare et al. [1], we know that CBC mode without padding

is secure in the LOR-CPA sense if F is a pseudo-random permutation family.

From the above theorem, we see that CBCP AD [F ] is secure in the LOR-PO-CPA

sense under the same condition on F , for any padding method having |I| = 0.

Given their strong security guarantees, we therefore recommend the use of the

methods such as the Abit Pad method with CBC mode.

4 Conclusion

In this paper we have extended existing security models for CBC mode encryp-

tion to incorporate padding and attacks based on padding oracles in the chosen

plaintext setting. We have then used these models to study the security of par-

ticular padding methods. We proved that, for a large number of padding meth-

ods where invalid padded messages do exist, a trivial attack can be performed

against CBC mode using such a method. We showed that the OZ-PAD method

recommended for use with CBC mode in ISO/IEC 10116:2006 provably resists

Vaudenay™s original padding oracle attack, even though it does not attain our

strongest indistinguishability notion. We also showed that any padding method

that has no invalid padded messages automatically achieves immunity against

padding oracle attacks, as it meets our IND-PO-CPA notion when combined

with CBC mode encryption built using a pseudo-random permutation family.

The Abit pad method is a very simple padding method with this property.

Given the results of this paper, we suggest that any future version of the

ISO/IEC 10116 standard be revised to recommend the use of a padding method

such as Abit pad in place of OZ-PAD.

In a companion paper to this, we further develop the theory of padding oracle

attacks and security models to cover the case of CCA security. We also examine

the question of how encryption and padding should be combined with integrity

protection in order to provably defeat padding oracle attacks, even in the face

of imperfect implementations of the type studied in [5].

References

1. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of

symmetric encryption. In: Proceedings of 38th Annual Symposium on Foundations

of Computer Science (FOCS 1997), pp. 394“403. IEEE, Los Alamitos (1997)

2. Bellare, M., Kohno, T., Namprempre, C.: Breaking and provably repairing the

ssh authenticated encryption scheme: A case study of the encode-then-encrypt-

and-MAC paradigm. ACM Transactions on Information and Systems Security 7,

206“241 (2004)

3. Black, J., Urtubia, H.: Side-channel attacks on symmetric encryption schemes: The

case for authenticated encryption. In: Proceedings of the 11th USENIX Security

Symposium, San Francisco, CA, USA, August 5-9, 2002, pp. 327“338 (2002)

4. Boldyreva, A., Kumar, V.: Provable-security analysis of authenticated encryption

in kerberos. In: IEEE Symposium on Security and Privacy, pp. 92“100. IEEE Com-

puter Society, Los Alamitos (2007)

354 K.G. Paterson and G.J. Watson

5. Canvel, B., Hiltgen, A.P., Vaudenay, S., Vuagnoux, M.: Password interception in

a SSL/TLS channel. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp.

583“599. Springer, Heidelberg (2003)

6. Degabriele, J.P., Paterson, K.G.: Attacking the IPsec standards in encryption-only

con¬gurations. In: IEEE Symposium on Security and Privacy, pp. 335“349. IEEE

Computer Society, Los Alamitos (2007)

7. Kent, S.: IP encapsulating security payload (ESP). RFC 4303 (December 2005)

8. Krawczyk, H.: The order of encryption and authentication for protecting commu-

nications (or: How secure is SSL?). In: Kilian, J. (ed.) CRYPTO 2001. LNCS,

vol. 2139, pp. 310“331. Springer, Heidelberg (2001)

9. Mitchell, C.J.: Error oracle attacks on CBC mode: Is there a future for CBC mode

encryption? In: Zhou, J., L´pez, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS,

o

vol. 3650, pp. 244“258. Springer, Heidelberg (2005)