E (·),P(·)

Algorithm A3 3 (k, ¬nd)

r

“ Let i ← {1, . . . , qe }

“ Run A1 answering its encryption oracle queries with E1 (LR(·, ·, 0)) = E3 (x0 )

and any padding oracle queries with P(·), until the i-th encryption oracle

query, which we denote (xi , xi ). (Where A1 has made the query and is

0 1

waiting for the oracle to respond.) A1 ™s state at this point is denoted by s.

“ return (xi , xi , s)

0 1

Immunising CBC Mode Against Padding Oracle Attacks 357

r

Now A3 ™s challenger selects a bit b ← {0, 1} and gives A3 the value y, where

y = E3 (xb ).

E (·),P(·)

Algorithm A3 3 (k, guess, y, s)

“ Resume execution of A1 in state s by answering the i-th encryption query

(xi , xi ) with y then stop before another oracle query is made.

0 1

(Note: y = E1 (LR(xi , xi , b)) = E3 (xi ))

0 1 b

“ Continue execution of A1 , answering all encryption oracle queries now with

E1 (LR(·, ·, 1)) = E3 (x1 ) and any padding oracle queries with P(·), until A1

halts.

“ if A1 outputs 1 then return 1, else return 0

Now de¬ne a sequence of qe + 1 experiments, for j = 0, . . . , qe :

Experiment Exphyb-atk-j,A1 (k)

CBCPAD

r

K ← K(k)

Run A1

Answer ¬rst j encryption oracle queries of A1 by E1 (LR(·, ·, 0))

Answer the remaining encryption oracle queries by E1 (LR(·, ·, 1))

Answer any padding oracle queries by P(·)

return output of A1

We can now think of the experiment Expftg-po-cpa-b3 (k) in terms of this new

CBCPAD ,A

hyb-atk-j

experiment ExpCBCPAD ,A1 (k). If b = 0 then y = CBCK (xi ) and so the ¬rst i + 1

0

responses from A1 ™s encryption oracle are E1 (LR(·, ·, 0)), while the remaining

responses are E1 (LR(·, ·, 1)). Therefore A1 ™s output will be the same as the

output of Exphyb-atk-i+1 (k).

CBCPAD ,A1

On the other hand if b = 1 then y = CBCK (xi ) and so the ¬rst i responses

1

from A1 ™s encryption oracle are E1 (LR(·, ·, 0)), while the remaining responses

are E1 (LR(·, ·, 1)). Therefore A1 ™s output will be the same as the output of

Exphyb-atk-i,A1 (k).

CBCPAD

Note that there are two special cases of this new experiment

Exphyb-atk-j,A1 (k). If j = 0 then the experiment is the same as an LOR-PO-

CBCPAD

CPA game when the random bit b is 0. Similarly, if j = qe then the experiment

is the same as an LOR-PO-CPA game when the random bit b is 1.

Since i is chosen at random from {1, . . . , qe }, A3 ™s advantage is determined as

the average of all the advantages over the random choice of i. Hence:

Advftg-po-cpa 3 (k)

CBCPAD ,A

qe’1

= qe . i=0 (Pr[Exphyb-atk-i,A1 (k) = 1] ’ Pr[Exphyb-atk-i+1 (k) = 1])

1

CBCPAD CBCPAD ,A1

hyb-atk-0 hyb-atk-qe

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

1

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

CBCPAD ,A CBCPAD ,A

e

lor-po-cpa

1

= qe .AdvCBCPAD ,A1 (k)

Since A1 is an arbitrary adversary, the claimed relation holds.

Constructing Strong KEM from Weak KEM

(or How to Revive the KEM/DEM Framework)

Joonsang Baek1 , David Galindo2 , Willy Susilo3 ,

and Jianying Zhou1

1

Cryptography and Security Department

Institute for Infocomm Research, Singapore

{jsbaek,jyzhou}@i2r.a-star.edu.sg

2

Computer Science Department, University of Malaga

dgalindo@lcc.uma.es

3

Centre for Computer and Information Security Research

School of Computer Science and Software Engineering

University of Wollongong, Australia

wsusilo@uow.edu.au

Abstract. We propose a generic method that transforms a weakly

secure KEM, i.e. a KEM which is secure against constrained chosen ci-

phertext attack (CCCA), to a strongly secure KEM, i.e. a KEM which

is secure against full chosen ciphertext attack (CCA). The proposed

method does not depend on the random oracle nor any other non-

standard assumptions. Using this method, we obtain new e¬cient hybrid

encryption schemes based on Kurosawa&Desmedt and Hofheinz&Kiltz

weakly secure KEMs. These are the ¬rst hybrid encryption schemes

which are as e¬cient as Kurosawa&Desmedt and Hofheinz&Kiltz en-

cryption schemes, but whose security can be explained in the original

KEM/DEM framework.

1 Introduction

1.1 Motivation

As a systematic approach to build hybrid public key encryption schemes1 , the

KEM/DEM (Key Encapsulation Mechanism/Data Encryption Mechanism)

framework was introduced by Cramer and Shoup [9]. The KEM/DEM frame-

work captures the most basic intuition about hybrid encryption schemes: the

KEM on input a public key as input generates a DEM-key and the DEM en-

crypts a plaintext message using the DEM-key generated by the KEM. In terms

of security, [9] shows that if the KEM is secure against chosen ciphertext attack

(CCA-secure) and DEM is one-time CCA-secure, the resulting hybrid encryption

scheme is CCA-secure2 .

1

Hereinafter, we simply call them “hybrid encryption schemes”.

2

The term CCA-secure is somewhat abused here, since it has di¬erent (but related)

meanings depending on whether it refers to public key encryption, KEM or DEM

schemes.

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 358“374, 2008.

c Springer-Verlag Berlin Heidelberg 2008

Constructing Strong KEM from Weak KEM 359

However, it turned out the CCA-security for both KEM and DEM is not a

necessary condition but a mere su¬cient one. One of the famous examples is

Kurosawa and Desmedt™s [17] hybrid encryption scheme: Although the KEM

part of Kurosawa and Desmedt™s hybrid encryption scheme is not CCA-secure

as shown in [14], the hybrid encryption scheme itself is proven to be CCA-

secure [17,13]. It seemed that the KEM/DEM framework had to be modi¬ed or

extended to capture a larger class of hybrid encryption schemes.

Indeed, Abe et al. [1,2] introduced another framework, called “Tag-KEM/

DEM”. Di¬erent from the normal KEM, the Tag-KEM takes arbitrary string

called “tag” as input. In the Tag-KEM/DEM framework, the DEM part becomes

a tag. It was shown in [2] that the CCA-security of Kurosawa and Desmedt™s hy-

brid encryption scheme can fully be explained in the Tag-KEM/DEM framework.

Recently, Hofheinz and Kiltz [15] proposed another framework which combines

a KEM secure against “constrained chosen ciphertext attack (CCCA)”, which is

weaker than usual CCA on KEM3 , with a DEM which is one-time secure authen-

ticated encryption (AE-OT) to yield a CCA-secure hybrid encryption scheme.