cryption standard. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp.

305“323. Springer, Heidelberg (2004)

11. Vaudenay, S.: Security ¬‚aws induced by CBC padding “ applications to SSL,

IPSEC, WTLS. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332,

pp. 534“546. Springer, Heidelberg (2002)

12. Yau, A.K.L., Paterson, K.G., Mitchell, C.J.: Padding oracle attacks on CBC-mode

encryption with secret and random IVs. In: Gilbert, H., Handschuh, H. (eds.) FSE

2005. LNCS, vol. 3557, pp. 299“319. Springer, Heidelberg (2005)

13. Zhou, Y., Feng, D.: Side-channel attacks: Ten years after its publication and the

impacts on cryptographic module security testing. Cryptology ePrint Archive, Re-

port 2005/388 (2005), http://eprint.iacr.org/

Appendix

Proof (of Theorem 1). Assume A1 is an adversary attacking CBCPAD in the

LOR-PO-CPA sense. We can use this adversary to construct a new adversary

A2 attacking CBCPAD in the ROR-PO-CPA sense.

Let E2 (·) be A2 ™s encryption oracle and P(·) its padding oracle. A2 will run

A1 using its oracles to provide a simulation of A1 ™s oracles.

For b ∈ {0, 1} and any x0 , x1 , we de¬ne E1 (LR(x0 , x1 , b)) to be E2 (xb ). So when

A1 queries its encryption oracle with E1 (LR(x0 , x1 , b)) then A2 will respond with

the response given by the output given by its oracle for E2 (xb ).

E (·),P(·)

Algorithm A2 2 (k)

r

let b ← {0, 1}

E (LR(·,·,0)),P(·)

if b = 0 then d ← A1 1 (k)

E1 (LR(·,·,1)),P(·)

else d ← A1 (k)

if b = d return 1

else return 0

Now we ¬nd A2 ™s advantage. We have:

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

CBCPAD ,A CBCPAD ,A2 CBCPAD ,A2

Immunising CBC Mode Against Padding Oracle Attacks 355

Let us ¬rst consider Pr[Expror-po-cpa-0 (k) = 1]. In this case the encryption ora-

CBCPAD ,A2

cle E2 (·) = E2 (RR(xb , 0)) returns the encryption of a randomly chosen plaintext

r. Therefore since we de¬ned E1 (LR(x0 , x1 , b)) to be E2 (xb ), this means that

E1 (LR(x0 , x1 , 0)) and E1 (LR(x0 , x1 , 1)) return identically distributed answers

for any (x0 , x1 ). The encryption oracle for this case therefore only outputs ci-

phertexts of randomly chosen plaintexts. This means that the padding oracle

can only be called on a randomly generated ciphertext or on the random out-

put from the encryption oracle. The Padding Oracle therefore only provides

information relating to the random ciphertext and its underlying plaintext and

does not output any information which can be used to distinguish between the

plaintext inputs x0 , x1 . We can therefore say that any input from the Padding

Oracle is independent of the bit b. Thus the Padding Oracle gives no assistance

in determining xb . Therefore Pr[Expror-po-cpa-0 (k) = 1] = 1 . Hence,

CBCPAD ,A2 2

Advror-po-cpa 2

CBCPAD ,A

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

CBCPAD ,A2 2

= 2 Pr[ExpCBCPAD ,A1 (k) = 1] ’ 1 Pr[Explor-po-cpa-01 (k) = 0] ’ 1

lor-po-cpa-1

1

CBCPAD ,A

2 2

lor-po-cpa-1 lor-po-cpa-0

= 2 Pr[ExpCBCPAD ,A1 (k) = 1] ’ 2 (1 ’ Pr[ExpCBCPAD ,A1 (k) = 1]) ’

1 1 1

2

= 1 (Pr[Explor-po-cpa-11 (k) = 1] ’ Pr[Explor-po-cpa-01 (k) = 1])

CBCPAD ,A CBCPAD ,A

2

lor-po-cpa

1

= 2 AdvCBCPAD ,A1

Since Expror-po-cpa-1 (k) = 1 provides a perfect simulation of A1 against the

CBCPAD ,A2

LOR-PO-CPA game. The algorithm simulating A2 outputs 1 only when b = d

and this is the same as A1 winning the LOR-PO-CPA game.

Since A1 is an arbitrary adversary we have,

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

CBCPAD CBCPAD

Proof (of Theorem 2). Assume A2 is an adversary attacking CBCPAD in the

ROR-PO-CPA sense. We can use this adversary to construct a new adversary

A1 attacking CBCPAD in the LOR-PO-CPA sense.

Let E1 (·) be A1 ™s encryption oracle and P(·) its padding oracle. A1 will run

A2 using its oracles to provide a simulation of A2 ™s oracles.

For any x ∈ {0, 1}—, de¬ne E2 (x) to be E1 (r, x), where r is chosen randomly

for each call to the oracle. So when A2 queries its encryption oracle with E2 (x)

then A1 will respond with the response given by the output given by its oracle

for E1 (r, x).

E (·,·),P(·)

Algorithm A1 1 (k)

E2 (·),P(·)

return A2 (k)

If A2 ™s hidden bit b is 0, then all responses from the encryption oracle are

random and this corresponds to the left response in A1 ™s encryption oracle.

Similarly, if A2 ™s hidden bit b is 1, then all responses are real and this corresponds

to the right response in A1 ™s encryption oracle. So A1 ™s advantage will be:

356 K.G. Paterson and G.J. Watson

Advlor-po-cpa 1 (k) = Pr[Explor-po-cpa-11 (k) = 1] ’ Pr[Explor-po-cpa-01 (k) = 1]

CBCPAD ,A CBCPAD ,A CBCPAD ,A

= Pr[ExpCBCPAD ,A2 (k) = 1] ’ Pr[Expror-po-cpa-0 (k) = 1]

ror-po-cpa-1

CBCPAD ,A2

ror-po-cpa

= AdvCBCPAD ,A2 (k)

Since A2 is an arbitrary adversary we have,

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

CBCPAD CBCPAD

Proof (of Theorem 3). Assume A3 is an adversary attacking CBCPAD in the

FTG-PO-CPA sense. We can use this adversary to construct a new adversary

A1 attacking CBCPAD in the LOR-PO-CPA sense.

Let E1 (·) be A1 ™s encryption oracle and P(·) its padding oracle. A1 will run

A3 using its oracles to provide a simulation of A3 ™s oracles.

For any x ∈ {0, 1}—, de¬ne E3 (x) to be E1 (x, x). So when A3 queries its

encryption oracle with E3 (x) then A1 will respond with the response given by

the output given by its oracle for E1 (x, x).

E (·,·),P(·)

Algorithm A1 1 (k)

E3 (·,·),P(·)

Let (x0 , x1 , s) ← A3 (k, ¬nd)

E3 (·),P(·)

return A3 (k, guess, E1 (x0 , x1 ), s)

If A3 ™s hidden bit b is 0, then all responses from the encryption oracle cor-

respond to the left response in A1 ™s encryption oracle. Similarly, if A2 ™s hidden

bit b is 1, then all responses correspond to the right response in A1 ™s encryption

oracle. So A1 ™s advantage will be:

Advlor-po-cpa 1 (k) = Pr[Explor-po-cpa-11 (k) = 1] ’ Pr[Explor-po-cpa-01 (k) = 1]

CBCPAD ,A CBCPAD ,A CBCPAD ,A

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

CBCPAD ,A3 CBCPAD ,A3

ftg-po-cpa

= AdvCBCPAD ,A3 (k)

Since A3 is an arbitrary adversary we have:

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

CBCPAD CBCPAD

Proof (of Theorem 4). Assume A1 is an adversary attacking CBCPAD in the

LOR-PO-CPA sense. We can use this adversary to construct a new adversary

A3 that attacks CBCPAD in the FTG-PO-CPA sense.

Let E3 (·) be A3 ™s encryption oracle and P(·) its padding oracle. A3 will run

A1 using its oracles to provide a simulation of A1 ™s oracles.

For b ∈ {0, 1} and any x0 , x1 , we de¬ne E1 (LR(x0 , x1 , b)) to be E3 (xb ). So when

A1 queries its encryption oracle with E1 (LR(x0 , x1 , b)) then A3 will respond with