## Springer-final.dvi

**Luby-Rackoff Backwards: Increasing Security by**
**Making Block Ciphers Non-Invertible**
Mihir Bellare1, Ted Krovetz2, and Phillip Rogaway2
1 Dept. of Computer Science & Engineering, University of California at San Diego,
9500 Gilman Drive, La Jolla, California 92093, USA. E-Mail: mihir@cs.ucsd.edu
2 Dept. of Computer Science, University of California at Davis,
Engineering II Bldg., One Shields Ave., Davis, CA 95616, USA
E-mail:

*{*krovetz,rogaway

*}*@cs.ucdavis.edu
URL: http://www.cs.ucdavis.edu/

*{*~krovetz,~rogaway

*}*
**Abstract. **We argue that the invertibility of a block cipher can reduce

the security of schemes that use it, and a better starting point for scheme

design is the non-invertible analog of a block cipher, that is, a pseudoran-

dom function (PRF). Since a block cipher may be viewed as a pseudo-

random permutation, we are led to investigate the

*reverse *of the problem

studied by Luby and Rackoff, and ask: “how can one transform a PRP

into a PRF in as security-preserving a way as possible?” The solution we

propose is

*data-dependent re-keying. *As an illustrative special case, let

*E *:

*{*0

*, *1

*}n × {*0

*, *1

*}n → {*0

*, *1

*}n *be the block cipher. Then we can con-

struct the PRF

*F *from the PRP

*E *by setting

*F *(

*k, x*) =

*E*(

*E*(

*k, x*)

*, x*).

We generalize this to allow for arbitrary block and key lengths, and to

improve efficiency. We prove strong quantitative bounds on the value of

data-dependent re-keying in the Shannon model of an ideal cipher, and

take some initial steps towards an analysis in the standard model.

**Introduction**
This paper describes a transformation — turning a “pseudorandom permuta-tion” (PRP) into a “pseudorandom function” (PRF) using “data-dependent re-keying.” It can be applied to a block cipher to increase the block cipher’s secu-rity in certain ways, and, in particular, the method leads to block cipher basedmessage encryption and authentication techniques which are approximately asefficient as ones in current use, but have better security.

In Section 2 we explain our (at first paradoxical sounding) thesis: that in-
vertibility of a block cipher can be a liability, not an asset, when it comes tothe security of schemes that use the cipher. We will then explain what are PRFsand PRPs, how the former are a better starting point for constructions but thelatter a better model for block ciphers, and how all this leads us to consider theproblem of transforming PRPs into PRFs in a security-preserving way.

In Section 3 we describe our way to do the PRP to PRF transformation.

We call our transform Fn

*d*, where

*d *is a parameter on which the construction

depends. (The impatient reader can jump to Section 3 to see how Fn

*d *works. Itis very simple.)
Our main result is an analysis1 in the Shannon model which shows that if
the block cipher is ideal then its transform under Fn

*d *is close to an ideal randomfunction. The provided bounds are strong, showing the transform is close tosecurity preserving.

The interpretation of the above is that the Fn

*d *transform gives good security
against “generic” attacks. To guage its strength against cryptanalytic attacks wealso analyze it in the standard complexity theoretic or “reductionist” framework.

We do succeed in providing a reduction, but the quality of the bounds is not asgood as in the Shannon model, and thus we view these results as preliminary,hopefully to be improved.

The results are presented, discussed, and displayed graphically in Section 5.

Just before that, in Section 4, we provide the precise definitions of the securitynotions, but these can be skipped at first reading, or skipped entirely by anexpert. In this truncated version of the paper we do not have space to includeproofs of theorems. The reader interested in these is referred to the full versionof this paper [7] which is available on the web.

**The Problem**
We begin with a simple example, then relate these issues to PRFs and PRPs,then describe the problem that results, and conclude with a discussion of relatedwork.

**Invertibility can hurt when using block ciphers: An example**
A block cipher is a function

*E*:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n *which transforms an

*n*-bit message block

*x *into an

*n*-bit string

*y *under the control of a

*κ*-bit key

*k*:

*y *=

*E*(

*k, x*). The function is invertible in the sense that for each key the map

*E *def

*k *=

*E*(

*k, ·*) is a permutation of

*{*0

*, *1

*}n*, and knowledge of

*k *permits computation
of

*E−*1. Concrete examples are DES, triple-DES and RC5.

Message encryption is done by using the block cipher in some mode of opera-
tion, such as “CBC.” Using even a very “good” block cipher (say triple-DES, oreven an ideal cipher), CBC encryption becomes insecure once 2

*n/*2 blocks havebeen encrypted, in the sense that at this point partial information about themessage begins to leak2, due to birthday attacks.3 Furthermore, this is true formany other common modes of operation, too. Thus direct use of a 64-bit block
1 All analyses in this paper are concrete and quantitative, meaning providing explicit,
non-asymptotic bounds on the success probabiilty of an adversary as a function ofits resources.

2 A good encryption scheme is much more than one that prevents key recovery from
a ciphertext: it should have the property that even partial information about theplaintext is not revealed [10, 4].

3 The attacks are well known. See [4] for an analysis of their effectiveness relative to
formal notions of security for encryption.

size block cipher usually enables one to safely encrypt no more than 232 blocks,which is quite small.

We stress that these attacks arise because the cipher is a permutation, and
their cost depends only on the block length, not the key length or the securityof the block cipher. So the attacks are just as effective for triple-DES, or evenan ideal block cipher, as they are for DES. In summary, block cipher basedschemes are often subject to birthday attacks arising from the very nature ofblock ciphers as permutations.

So how can we safely encrypt more than 2

*n/*2 blocks? One answer is to use a
slightly different type of primitive in an appropriate mode of operation: specif-ically, a “pseudorandom function” (PRF) in CTR (counter) mode, as discussedin [4, 12] and explained further below. This way to encrypt is easy and has noextra overhead if a PRF of cost comparable to the block cipher is available.

The above is only one example of an issue that arises in many places: that
the permutivity of a block cipher can hinder the security of schemes which useit. To effectively address this we need to explain what are PRFs and PRPs andhow they relate to block ciphers.

**PRPs, PRFs, and their relation to block ciphers**
Let us first back up and look at how the security of a block cipher is bestcaptured.

Security of a block cipher: PRPs. It is natural to view a real block cipheras constructed to “approximate”, as closely as possible, an ideal block cipher(that is, a random permutation) in the sense that if you don’t know the key

*k*and only see input/output examples of

*Ek *then these should appear like in-put/output examples of a random permutation. The quality of a given blockcipher

*E *as a PRP (pseudorandom permutation) is thus captured by a func-tion
(

*q, t*) which returns the maximum “advantage” that one can obtain
in distinguishing

*Ek *from a random permutation if you see

*q *input/output ex-amples and are allowed further computational resources bounded by

*t*. (In thecomplexity-theoretic model,

*t *will bound computing time; in the information-theoretic model,

*t *will bound the number of known (

*k, x, Ek*(

*x*)) values. Theadvantage is a number between 0 and 1 given as the difference of two proba-bilities: the probability that the adversary outputs 1 given a random function

*Ek *from

*E*, and the probability that the adversary outputs 1 given a randompermutation

*π*. See Section 4 for more details.)
Each specific cipher (eg. DES) will have such an associated security function,
which depends on (and to a large extent comprises) its cryptanalytic strength.

Of course we won’t know for sure what is this function, but we can work withwhat we know from cryptanalytic results. For example, if the linear cryptanalysisof [14] is the best attack on DES, we might assume
to 0) until

*q, t *reaches around 243. From now on, “block cipher” and “PRP” aresynonymous, from the security point of view.

Ciphers without invertibility: PRFs. Like a block cipher, a pseudorandomfunction (PRF) is a map

*F *:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n*, but now

*F *def
not required to be invertible. The required security property is to approximate,as closely as possible, a random function. The quality of a given function

*F*is captured by
(

*q, t*) which returns the maximum “advantage” that one
can obtain in distinguishing

*Fk *from a random function if you see

*q *input-output examples and are allowed computational resources

*t*. (This advantage isthe difference between probability that the adversary outputs 1 given a randomfunction

*Fk *from

*F *and the probability that the adversary outputs 1 given arandom function

*ρ*. See Section 4 for more details.)
The example revisited. Counter mode encryption with a PRF

*F *means thatto encrypt an

*m*-block plaintext

*M *=

*x*1

*· · · xm*, send

*· · · Fk*( ctr +

*m *)

*⊕xm *)
where

*i *is the binary encoding of

*i *into

*n *bits, “
and where you increment ctr by

*m *after doing each encryption. (Notice thatto decrypt you need only apply

*Fk*, so that you don’t need this function to beinvertible.) Counter-mode encryption with a good PRF is pretty much “idealencryption”: it is shown in [4] that an adversary’s chance of obtaining partialinformation about some plaintext, after

*q *blocks have been encrypted, is atmost
(

*q, t*), the strength of

*F *as a PRF. In particular if we had a PRF

*F*
with the same numerical security as DES but as a PRF not a PRP, namely
(

*q, t*), then we could encrypt nearly 243 blocks, well above
In contrast, when we use a block cipher (PRP) directly in CBC (or CTR)
mode, we are not able to recoup all of the cryptographic strength captured byits
(

*·, ·*) value, because at

*q *= 2

*n/*2 (which is

*q *= 232 for DES) birthday
The conclusion can be put like this: to get quantitatively good security,
what is most useful and convenient about

*F *is that
(

*q, t*). To make the former as low as possible the family

*F *must

*not *be a
family of permutations, since no family of permutation will have a good valueof
(

*q, t*) if

*q ≥ *2

*n/*2. This is because of birthday attacks: if

*F *is a family
of permutations then the adversary

*A*(

*q*) who guesses “random function” if andonly if she sees a collision in the answers returned from

*q *distinct but other-wise arbitrary queries already accrues advantage of about 1

*/e *if

*q *= 2

*n/*2. Theadversary’s advantage then goes quickly to 1 with

*q*
**Luby-Rackoff backwards**
The above is part of an emerging view or understanding, emanating from workslike [4–6, 21], that when it comes to designing higher-level primitives (like en-cryption schemes or MACs) a PRF is a better tool than a PRP, from two pointsof view: it permits easier and more effective

*analysis *of the designed scheme,and the resulting schemes have a greater proven

*quantitative security*. This leadsus to suggest that for the purpose of protocol design, what we really want arePRFs, not block ciphers (PRPs).

So the question is how to get PRF families of high security and low cost. One
possibility is to make these directly, in the same way we make block ciphers now.

We suggest that this indeed be kept in mind for the future, but at the momentis not a very pragmatic view, for two reasons. First, we have lots of (good) blockciphers available, and we want to use them well. Second, permutivity may beimportant to the design process of block ciphers; for example, using the roundstructure of a Feistel-network gives rise to a permutation.4
We propose instead to transform PRPs into PRFs. That is, starting with a
good PRP

*E *(realized by a block cipher), convert it into a good PRF

*F *. This iseffectively the reverse of the problem considered by Luby and Rackoff [13], whowanted to turn PRFs into PRPs.

A crucial issue is to make transformations that are as “security preserving”
(

*q, t*) to remain low even for

*q*
Let us now discuss some related work. Following that we present our con-

**History and related work**
Our construction is related to the cascade construction of [3].

The notion of a PRF was first defined in the polynomial-time framework by
Goldreich, Goldwasser and Micali [9]. A concrete security treatment of PRFs,together with the idea that concretely defined PRFs/PRPs can be used to modelblock ciphers, originates with [6]. Luby and Rackoff use the term PRP to referto a family of permutations that is a PRF family in the sense of [9]. Our notionis different in that we measure the advantage relative to random permutations,not functions. This makes no difference in the polynomial-time framework, butin the concrete-security framework the difference is crucial; indeed, if concretesecurity is ignored, the problem we are considering does not exist.

The ideal block cipher model we use for some of our results is that of [20],
There are many natural ways to try to do the PRP-to-PRF conversion. One
of the first to come to mind is to define

*Fk*(

*x*) =

*x⊕Ek*(

*x*). This construction isof value in some contexts, but not in ours. For if you are given an oracle for this

*Fk*(

*·*) you effectively have an oracle for

*Ek*(

*·*): for any query

*x *you can compute

*Ek*(

*x*) as

*x⊕Fk*(

*x*). So

*Fk *will resemble a random function no more than

*Ek*does.

There are many natural alternatives to the Fn

*d *transformation. For example,
truncate

*Ek*(

*x*), defining

*Fk*(

*x*) to be some appropriate-length prefix of

*Ek*(

*x*).

This scheme was partially analyzed by [2]. Another natural method is

*Fk*
*Ek *(

*x*)

*⊕E *(

*x*). This has not been analyzed.

Aiello and Venkatesan [1] give a general construction for turning a PRF

*E *:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n *into a PRF

*F *:

*{*0

*, *1

*}*6

*κ × {*0

*, *1

*}*2

*n → {*0

*, *1

*}*2

*n*.

But this is a different problem. Although they too want to circumvent some
4 Another possibility is to make sure that the block size

*n *is large enough (

*n ≥ *128)
that attacks of complexity 2

*n/*2 are irrelevant. This too is a good idea, but theconstruction we give has merit which goes beyond the birthday attacks which wehave been using to motivate this problem.

birthday attacks, their starting point is a random function (not permutation)and the problem is to double the number of bits the function can take as input.

They are bound by the original security of the starting function as a PRF:birthday attacks are only prevented in the sense that the construction does notinduce such attacks itself. So if a block cipher is the starting point, it is viewedas a PRF, meaning the security is only 2

*n/*2. There is no notion of modeling acipher as a random permutation. In contrast, we go above the original birthdaythreshold, to a security close to 2

*n*. Our construction is also more efficient, andit yields a map of the same key size and block length as the original one.

In constructing a Wegman-Carter message authentication code (MAC) [22]
one needs to symmetrically encrypt the universal-hash of each message

*M *. Ifa PRP is in hand for doing the encryption, one could define MAC

*k*1

*,k*2(

*M *) =(ctr

*, Ek*2(ctr)

*⊕hk*1(

*M *)), but the security would degrade by

*Θ*(

*q*22

*−n*) comparedto using a PRF. (Here

*q *is the number of MACed messages.) Shoup [21] describesan alternative with better exact security. Our methods allow the simpler andmore general (ctr

*, Fk*2(ctr)

*⊕hk*1(

*M *)), where

*F *is the result of PRP-to-PRFconversion starting from

*E*.

As we explained, Luby and Rackoff consider the complementary problem of
turning a PRF into a block cipher [13]. Luby and Rackoff spawned much fur-ther work, including [15–18, 23], and our work shares their emphasis on concretebounds, efficiency, and tight reductions.

**The Fn Construction**
We have described in Section 2.4 some simple suggestions that don’t work andsome related constructions. Now we present our solution. We let

*E*:

*{*0

*, *1

*}κ ×*
*{*0

*, *1

*}n → {*0

*, *1

*}n *be the given block cipher (PRP).

The values

*n *and

*κ *vary across real block ciphers; for example, for DES we
have

*κ *= 56 and

*n *= 64; for (two-key) triple DES we have

*κ *= 112 and

*n *= 64.

We want to handle all these cases. Accordingly, our construction depends on therelative values of

*κ *and

*n*. It also depends on a parameter

*d*, where 0

*≤ d < n*.

Simple Case. The simplest case of our construction is when the given PRP hasthe property that

*κ *=

*n*, and we choose

*d *= 0. One then defines

*F *= Fn0

*E *by

*F *(

*k, x*) =

*E*(

*E*(

*k, x*)

*, x*). That is,

*Fk*(

*x*) =

*Ek *(

*x*), where

*k *=

*Ek*(

*x*). We callthis “data-dependent re-keying” since we are applying

*E *to

*x*, but using thedata-dependent “derived key”

*k *=

*Ek*(

*x*). The cost of computing

*F *is twicethe cost of computing

*E*, in the sense that there are two applications of

*E *foreach application of

*F *. The general construction includes a provision aimed atreducing this overhead.

The General Case. Let 0

*≤ d < n *be given. If

*x *is an

*n*-bit string, let

*x*
*d *denote

*x *shifted to the right by

*d *positions, with 0-bits filling the vacated
positions. If

*k *is any string of length at least

*i*, let [

*k *]
of the first

*i *bits of

*k *. Set

*j *=

*κ/n *. The function

*F *= Fn

*dE *takes a

*κj *bitkey

*k*1

*· · · kj *and an

*n*-bit input

*x *to return an

*n*-bit output

*y *as follows:

function

*F *(

*k*1

*· · · kj, x*)begin

*k ← E*(

*k*1

*, x *)

*· · · E*(

*kj, x *) //

*Construct the “extended” derived keyk ← *[

*k *]
//

*We only need κ bits of derived key*
We call

*x *the

*group selector *and

*k *the

*derived key*. The

*j *applications of

*Ek *are
to deal with the possibility that

*κ > n*, and the truncating of

*k *to

*κ *bits is tohandle the possibility that the key length

*κ *might not be a multiple of the blocklength

*n*. (More strange is the discarding of bits from the

*x*, namely the

*x*
This is for efficiency, as we will explain below.) As an example, if

*E *= DES,so that

*κ *= 56 and

*n *= 64, we would have

*j *= 1, so the key of

*F *is just a56-bit DES key

*k*1, the derived key

*k *is the first 56 bits of DES

*k *(

*x *), and the
output is DES

*k *(

*x*). If

*E *is TDES (two-key triple-DES), so that

*κ *= 112 and

*n *= 64, we would have

*j *= 2, so the key for

*F *is a pair

*k*1

*k*2 of TDES keys, thederived key

*k *is the first 112 bits of TDES

*k *(

*x *)TDES (

*x *), and the output is
Notice that for fixed

*k*1

*· · · kj*, if two

*n*-bit strings determine the same group
selector then they generate the same derived key, and this happens if the twostrings agree in the first

*n − d *bits. Accordingly, we cluster together all pointsthat have the same group selector into what we call a

*common key group*. Thusthere are a total of 2

*n−d *common key groups. For any

*α ∈ {*0

*, *1

*}n−d *we defineckg =

*{ x *: [

*x*]
1

*.n−d *=

*α } *as the

*α*-th common key group. Identifying strings
with integers in the natural way, the

*i*-th common key group consists of theintegers (

*i − *1)2

*d, ., i*2

*d − *1.

Efficiency. Recall that the nominal way to encrypt using

*F *= Fn

*dE *involvesapplying

*F *to a single key

*k *and successive ctr-values. By dropping the leastsignificant

*d *bits of this counter, one needs to recompute

*k *only once every2

*d *invocations of

*F *. Of course an implementation would need to to record thelast derived key and refrain from re-computing it. Doing this makes the amor-tized cost to compute

*F *just (1 +

*j*2

*−d*) times the cost of computing

*E*. Formany ciphers this is is an underestimate because of additional cost associatedto changing the key. In fact, the cost of changing the key some block ciphers ishigh, which is why we don’t want to do it very often.

Variations. How exactly one drops bits of

*x *is not so important. For example,instead of shifting to the right one could zero-out the least significant

*d *bits.

This makes no difference in the analysis.

We have constructed

*F *= Fn

*dE *to be a map

*F *:

*{*0

*, *1

*}jκ ×{*0

*, *1

*}n → {*0

*, *1

*}n*.

If one prefers, define

*ki *by

*Ek*(

*i *) and then let

*F k*(

*x*) =

*Ek *(

*x*), where

*k *is thefirst

*κ *bits of

*Ek *(

*x*
*· · · E *(

*x d*). Now

*F *uses a

*κ*-bit key, just like

*F *.

The analysis of

*F *lifts to

*F *with just a tiny loss in quantitative security.

**Definitions**
Here we give the more precise definitions of security in the two models in whichwe will be analyzing our construction, namely the (standard) “complexity the-oretic” model and the Shannon model.

Recall that in Section 2 we discussed security of

*F *and

*E *via functions
(

*q, t*). Their meaning changes according to the model

**– **In the complexity theoretic model they are

respectively, these quantities being defined in Section 4.1 below, and

**– **In the ideal cipher model, they are

ISecF (

*q, t*) and ISec

*κ,n*(

*q, t*), respec-
tively, these quantities being defined in Section 4.2 below, where F refers tothe transformation that takes

*E *into

*F *. (In our case, F = Fn

*d*).

Preliminaries. If

*S *is a probability space then

*g ← S *denotes the operationof selecting

*g *at random according to the distribution specified by

*S*. If

*S *is aset it is viewed as endowed with the uniform distribution, so that

*g ← S *meansthat

*g *is selected uniformly at random from set

*S*. If

*y *is not a set then

*g ← y *isa simple assignment statement, assigning

*g *the value

*y*. (It is thus equivalent to

*g ← {y}*.) Let Perm

*n *denote the set of all permutations

*π *:

*{*0

*, *1

*}n → {*0

*, *1

*}n*.

Let Rand

*n *denote the set of all functions

*ρ *:

*{*0

*, *1

*}n → {*0

*, *1

*}n*. Let BC

*κ,n *bethe set of all maps

*E *:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n *such that

*E*(

*k, ·*)

*∈ *Perm

*n *forall

*k ∈ {*0

*, *1

*}κ*. Let RF

*κ,n *be the set of all maps

*R *:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n*.

A family of functions with key length

*κ *and block length

*n *is a map

*G *:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n*, that is,

*G ∈ *RF

*κ,n*. Each

*κ*-bit key

*k *specifies themap

*G *def

*k *=

*G*(

*k, ·*)

*∈ *Rand

*n*. This map is not necessarily a permutation. If

*Gk *is
a permutation for each

*k ∈ {*0

*, *1

*}κ *(ie.,

*G ∈ *BC

*κ,n*) then we call

*G *a family ofpermutations, or a block cipher. We view

*G *as a probability space over Rand

*n*given by choosing functions via a uniform choice of the underlying key; that is,

*g ← G *is the same as

*k ← {*0

*, *1

*}κ *;

*g ← Gk*.

Given a block cipher

*E*, the block cipher

*E−*1 :

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n*
is defined by

*E−*1(

*k, y*) being the unique point

*x *such that

*E*(

*k, x*) =

*y*. Weinterchangeably write

*E−*1(

*y*) and

*E−*1(

*k, y*).

An adversary is an algorithm

*A *with access to some number of oracles. Ora-
cles are denoted as superscripts to

*A*, as in

*AE,E−*1

*,F *. An oracle responds to itsquery in unit time.

**Complexity theoretic model**
We will have two measures of security: the strength of

*G *as a PRF and thestrength of

*G *as a PRP. We follow [6] in the manner in which the basic notionof [9] is “concretized.”
First, we need the concept of advantage, which for emphasis we call the
“computational advantage” and write CAdv. Let

*D *be an algorithm (a “dis-tinguisher”) taking an oracle for a function

*g*, and let

*G*1

*, G*2 be two families offunctions with the same block length. We define
1 :

*Dg *= 1 ]

*− *Pr [

*g ← G*2 :

*Dg *= 1 ]

*.*
Now, suppose

*F *is a family of functions, and

*E *is a family of permutations. Welet
Here the first quantity measures the advantage

*D *has in distinguishing randommembers of

*F *(resp.

*E*) from truly random functions (resp. permutations) of thesame block length. The second quantity is the maximum advantage attainableusing some amount of resources, in this case the number

*q *of oracle queriesand the running time

*t*. For simplicity, when we speak of an adversary’s timewe mean the adversary’s actual running time plus the size of the encoding ofthe adversary (relative to some fixed encoding scheme), so we have a singleparameter

*t *to capture time plus description size. The maximum here is overall distinguishers

*D *that make up to

*q *oracle queries and have running timebounded by

*t*.

**Ideal block cipher model**
The Shannon model [20] treats

*E *as a random block cipher. This means that each

*Ek *is taken to be random permutation on

*n*-bit strings. Let F

*E *be some operatoron

*E *which returns a new family of functions, and say the new family has keylength

*κ∗ *but the block length is still

*n*. (For us, F = Fn

*d *and

*κ∗ *=

*jκ *where

*j *=

*κ/n *.) As modeled by [8], the adversary that attacks F is given oraclesfor

*E*(

*·, ·*) and

*E−*1(

*·, ·*) — as well as an oracle

*f *where either

*f *(

*·*) =

*F *(

*k∗, ·*)for

*F *= F

*E *and

*k∗ *a randomly chosen key in

*{*0

*, *1

*}κ∗*, or else

*f *(

*·*) =

*ρ*(

*·*), for arandom function

*ρ *:

*{*0

*, *1

*}n → {*0

*, *1

*}n*. We investigate the adversary’s advantagein determining what type of oracle

*f *is. This is defined as:
IAdvF (

*A*) = Pr

*E ← *BC

*κ,n *;

*k∗ ← {*0

*, *1

*}κ∗ *;

*f ← *(F

*E*)

*k∗ *:

*AE,E−*1

*,f *= 1

*− *Pr

*E ← *BC

*κ,n *;

*f ← *Rand

*n *:

*AE,E−*1

*,f *= 1

*.*
The advantage

*A *gains depends, in part, on the number of queries

*q *she asksof

*f *and the total number of queries

*t *she asks of

*E *and

*E−*1. We are interestedin
ISecF (

*q, t*) = max

*A {*IAdvF (

*A*)

*} ,*
the maximum being over all adversaries that make up to

*q *queries to the

*f *oracleand up to

*t *queries to the

*E *and

*E−*1 oracles.

This is an information-theoretic setting: the adversary has unlimited compu-
tational power. If we think of

*E *as a concrete block cipher, and not an idealizedone, then attacks in this model correspond to attacks in which the adversaryexploits no characteristics specific to the block cipher, only “generic” features ofthe construction F we are analyzing. Thus, security guarantees from results inthis model are weaker than those from results in the model above, yet they dohave some meaning. We use the Shannon model when technical difficulties pre-vent us from getting bounds as good as we would like in the complexity theoreticmodel.

Note. The goal will be to upper bound ISecF (

*q, t*) as a function of

*t, q, κ, n*. As
such we don’t really need any notion of
ISec

*κ,n*(

*q, t*), the security of the block
cipher, because the latter is assumed ideal, but there are two reasons to defineit anyway. First, to maintain a uniform security treatment across the models,and in particular be consistent with Section 2; second, because it is indeed thequantity with which we wish to compare
(

*q, t*) as the maximum, over all adversaries

*A *of the speci-
Pr

*E ← *BC

*κ,n *;

*k ← {*0

*, *1

*}κ *;

*f ← Ek *:

*AE,E−*1

*,f *= 1

*− *Pr

*E ← *BC

*κ,n *;

*f ← *Perm

*n *:

*AE,E−*1

*,f *= 1

*.*
Notice that this quantity is not zero. For

*q > *1 and large

*n *we would expect itto be about

*t · *2

*−κ*, corresponding to an exhaustive key search attack.

**Security of the Fn Construction**
We summarize both proven security guarantees and attacks that indicate thetightness of the bounds in them.

**Security in the complexity theoretic model**
Here we refer to the notions of security of Section 4.1. We assume

*E *is a PRPfamily and show our construction is a PRF family, via a reduction. We do thisonly for the case where the key length,

*κ*, is identical to the block length,

*n*, andwe drop no bits, namely

*d *= 0.

**Theorem 1. ***Let κ *=

*n be a positive integer and let E*:

*{*0

*, *1

*}κ × {*0

*, *1

*}n →*
*{*0

*, *1

*}n be a family of permutations whose security as a PRP family is describedby security function*
(

*·, ·*)

*. Let F *:

*{*0

*, *1

*}κ × {*0

*, *1

*}n → {*0

*, *1

*}n be our*
*construction for the case of no bit dropping, namely F *= Fn0

*E. Its security asa PRF is described by function*
(

*·, ·*)

*which for any number of queries*
*q ≤ *2

*n/*2

*and time t can be bounded as follows:*
*where t *=

*t *+

*O*(

*q*)

*· *(

*κ *+

*n *+ Time

*E*)

*.*
The bound here looks good at first glance. The first term, namely
is saying the security of

*F *as a PRF is related to that of

*E *as a PRP foressentially the same resources: we can’t ask better. The last term, namely

*q*2

*/*22

*n*,is negligible. What about the middle term, namely

*q ·*
(3

*, t *) is small: what can you do in three queries? This view is deceptive
because one should not forget the time

*t *. One can spend it in exhaustive keysearch, and thus
(3

*, t *) can be

*Ω*(

*t *2

*−κ*). But (dropping constants) this
is at least

*q*2

*−κ *so the second term in our bound looks like

*q*22

*−κ*. Since

*κ *=

*n*this is

*q*22

*−n*.

**Fig. 1. ***Right curve: **Illustrating Theorem 2, our upper bound on the adversary’s*

advantage in distinguishing F = Fn

*dE from a random function, assuming n *= 64

*, κ *=

128

*, and d *= 8

*. Here E is a random permutation and the horizontal axis Q *= max(

*q, t*)

*is the maximum of the number of consecutive f-queries and the total number of E, E−*1

*queries. ***Left curve: **The birthday bound for the same choice of parameters.
So these bounds are not proof that the security of

*F *goes beyond the birthday
bound. It would be nice to improve the above result. However, even the proof ofthe above is not exactly trivial, and this is one reason we include the result inthis paper: we hope its ideas are food for thought towards an extension.

As far as we can tell, the difficulties in extending the above result are techncial
rather than arising from any weakness in the construction. (We could be wrong.)Is there any other way we can give some meaningful evidence of the strength ofthe construction? We do this by analyzing it in the Shannon model.

**Security in the ideal block cipher model**
The theorem below looks at the most general version of the

*F *= Fn

*dE *construc-tion, when the number

*d *of bits dropped is arbitrary and no restrictions aremade on

*κ, n*, in the model of Section 4.2, where

*E *is an ideal cipher. We obtainvery strong results, showing security not only beyond the birthday bound, butnearly as good as one could hope for.

As we noted in Section 2, an important mode of operation for our construc-
tion will be when the values to which

*Fk*
counter values. Indeed, the bit dropping is done precisely to have maximum effi-ciency in this mode: as explained in Section 3, in this case, the amortized cost ofcomputing

*F *is just (1 +

*j/*2

*d*) times that of computing

*E*, a negligible overhead.

Accordingly, this is the case to which the following security analysis pertains.

(Though some later analyses are more general.)

**Theorem 2. ***Let n, κ be positive integers and d, q, t, *ˆ

*with *0

*≤ d < n and let *F = Fn

*d. Let A be an adversary with three oracles,E*(

*·, ·*)

*, E−*1(

*·, ·*)

*, and f *(

*·*)

*, who asks the numbers *0

*, . . . , q − *1

*of its f -oracle (so*
k = 64, d = 12, n = 64k = 64, d = 16, n = 64

**Fig. 2. ***Varying the parameters of Theorem 2 — our upper bound on the adversary’s*

advantage in distinguishing F = Fn

*dE from a random function, with the horizontal axis*

Q = max(

*q, t*)

*as in the previous figure. ***Left: **Varying key length κ. **Right: **Varying

bits dropped d. For both pictures n = 64

*.*
*common key groups), and asks at most t total*
*queries of its E- and E−*1

*-oracles, these referring to no more than *ˆ

*key groups. Let j *=

*κ/n . Then*
*t*5

*· *2

*−*4

*κ *+

*j*2 + 2

*j*ˆ

*q*+

*tj *+

*t · *2

*−κ *+ ˆ

*q*22

*d−n*+3 +

*t*ˆ

*t*2

*d−n−κ*+2

*.*
Thus the advantage remains low until

*q ≈ *24

*κ/*5,

*t ≈ *24

*κ/*5,

*q ≈ *2

*n*, or

*t ≈*2(

*n*+

*κ*)

*/*2. We speculate that the first two of these conditions can be further im-proved to 2(1

*− *)

*κ *(and they are already very small in their current form), so a rea-sonable summary is to say that the construction is good until

*q ≈ *min

*{*2

*κ, *2

*n−*2

*d}*or

*t ≈ *min

*{*2

*κ, *2(

*d−n−κ*)

*/*2

*}*.

In Fig. 1 we illustrate our bound for the case of a block cipher with param-
eters

*n *= 64,

*κ *= 128, and dropping

*d *= 8 bits. The bound indicates thatone must ask about 255 queries before one can hope to distinguish

*Fk *from arandom function with advantage 1

*/e*. (This 1

*/e*-convention is a convenient wayto summarize security.) For comparison, if you let

*F *=

*E *you get the usualbirthday-attack curve, which indicates that it takes but 232 queries before anadversary can get like advantage at distinguishing

*Ek *from a random function.

In Fig. 2 we illustrate our bound by showing the effect on advantage of chang-
ing either the key length (left-hand plot) or the value of

*d *(right-hand plot). Weassume a block size of

*n *= 64 bits. The adversary’s maximum advantage decreas-es with increasing key length, but this effect soon saturates. The constructionhas worse demonstrated security for larger values of

*d*, but the effect is not thatdramatic, and there is little reason to select a very large value of

*d*, anyway.

It is important to understand the difference between the results here and the
result of Section 5.1. The “type” of security guarantee is better in the latter, since
Upper Bound, k = 64, d = 7, n = 64Lower Bound, k = 64, d = 7, n = 64

**Fig. 3. ***With typical parameters our bounds are tight. Illustrating Propositions 1 and*

2 and Theorem 2 for n = 64

*, κ *= 64

*, d *= 7

*. The horizontal axis Q is the same as in*

the previous figures.
we are saying that security in the sense of a PRP (using the standard notion ofa PRP) translates into security in the sense of a PRF (using the standard notionof a PRF). The results here are only about ideal ciphers, which only guaranteessecurity against generic attacks. Yet, generic attacks are an important and easyto mount class of attacks, and a proof of security against them, especially withsuch strong bounds, is certainly meaningful. Eventually we hope strong resultswill emerge in the other model (as well as for other PRP-to-PRF constructions).

**Attacks / Lower bounds**
In Propositions 1 and 2 we present the best attacks that we know on our con-struction. These translate into lower bounds on the security of Fn

*dE*. We presenttwo adversaries: one which becomes successful when

*q ≈ *2

*n−d*, and one whichbecomes successful when

*t ≈ *2

*κ*. This is done in the Shannon model, but inthis case (of attacks) this is not a restriction; if we can attack ideal cipherswe can certainly attack real ones. Thus, the results here should be viewed ascomplementing Theorem 2, telling us how close to tight is the analysis in thelatter.

**Proposition 1. ***Let n, κ be positive integers and d, q non-negative integers with*

0

*≤ d < n, and let *F = Fn

*d. Then there is an adversary CS which asks at most q*

of an f oracle, no queries of the E or E−1

*oracles, and achieves advantage*
IAdvF (

*CS *)

*≥ *1

*− e− q*2

*−d ·*(2

*d−*1)

*·*2

*d−n−*1

*.*
**Proposition 2. ***Let n, κ be positive integers and t, d, c be non-negative integers*

with 0

*≤ d < n, let *F = Fn

*d, and let j *=

*κ/n . Then there is an adversary*
*KS which asks c queries of her f oracle, t queries of her E oracle, and achievesadvantage*
IAdvF (

*KS *) = min

*{*1

*, t/*(

*cj *+

*c*)

*· *2

*−jκ} − t*2

*−cn .*
The first lower bound is around 1

*− e−q*2

*d−n−*1, while the second one is around

*t*2

*−jκ*. These become significant when

*q ≈ *2

*n−d *or

*t ≈ *2

*jκ*. The point of givingthese lower bounds is to see how tight is Theorem 2. As Fig. 3 illustrates, thebounds are quite close for realistic parameters. On the same plot we graph ourupper and lower bound for

*κ *= 56,

*n *= 64, and

*d *= 7. The curves almostcoincide.

**Acknowledgments**
The first author was supported by a 1996 Packard Foundation Fellowship inScience and Engineering, and by NSF CAREER Award CCR-9624439. The sec-ond two authors were supported by NSF CAREER Award CCR-9624560 and aMICRO grant from RSA Data Security, Inc.

**References**
1. W. Aiello and R. Vanketesan, “Foiling birthday attacks in output-doubling
transformations.”

*Advances in Cryptology – Eurocrypt *96

*Proceedings*, LectureNotes in Computer Science Vol. 1070, U. Maurer ed., Springer-Verlag, 1996.

2. M. Bellare, O. Goldreich and H. Krawczyk, personal communications,
3. M. Bellare, R. Canetti and H. Krawczyk, “Pseudorandom functions revis-
ited: The cascade construction and its concrete security.”

*Proceedings of the *37th

*Symposium on Foundations of Computer Science*, IEEE, 1996.

4. M. Bellare, A. Desai, E. Jokipii and P. Rogaway, “A concrete security

*Proceedings of the *38th

*Symposium on*
*Foundations of Computer Science*, IEEE, 1997.

erin and P. Rogaway, “XOR MACs: New methods for
message authentication using a finite pseudorandom function.”

*Advances in Cryp-tology – Crypto *95

*Proceedings*, Lecture Notes in Computer Science Vol. 963,D. Coppersmith ed., Springer-Verlag, 1995.

6. M. Bellare, J. Kilian and P. Rogaway, “The security of cipher block chain-
ing.”

*Advances in Cryptology – Crypto *94

*Proceedings*, Lecture Notes in Com-puter Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994.

7. M. Bellare, T. Krovetz and P. Rogaway, “Luby-Rackoff backwards: Increas-
ing security by making block ciphers non-invertible.” Full version of this paper,available at http://www-cse.ucsd.edu/users/mihir
8. S. Even and Y. Mansour, “A construction of a cipher from a single pseudo-
random permutation.”

*Advances in Cryptology – ASIACRYPT *91

*Proceedings*,Lecture Notes in Computer Science Vol. 739, H. Imai, R. Rivest and T. Matsumotoed., Springer-Verlag, 1991.

9. O. Goldreich, S. Goldwasser and S. Micali, “How to construct random
functions,”

*Journal of the ACM, *Vol. 33, No. 4, 1986, pp. 210–217.

10. S. Goldwasser and S. Micali, “Probabilistic encryption.”

*J. of Computer and*
*System Sciences*, Vol. 28, April 1984, pp. 270–299.

11. J. Kilian and P. Rogaway, “How to protect DES against exhaustive key search.”

*Advances in Cryptology – Crypto *96

*Proceedings*, Lecture Notes in ComputerScience Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.

12. M. Luby,

*Pseudorandomness and Crpyptographic Applications. *Princeton Uni-
13. M. Luby and C. Rackoff, “How to construct pseudorandom permutations from
pseudorandom functions.”

*SIAM J. Comput, *Vol. 17, No. 2, April 1988.

14. M. Matsui, “The first experimental cryptanalysis of the Data Encryption Stan-
dard.”

*Advances in Cryptology – Crypto *94

*Proceedings*, Lecture Notes in Com-puter Science Vol. 839, Y. Desmedt ed., Springer-Verlag, 1994, pp. 1–11.

15. U. Maurer, “A simplified and generalized treatment of Luby-Rackoff pseudoran-
dom permutation generators.”

*Advances in Cryptology – Eurocrypt *92

*Proceed-ings*, Lecture Notes in Computer Science Vol. 658, R. Rueppel ed., Springer-Verlag,1992, pp. 239–255.

16. M. Naor and O. Reingold, “On the construction of pseudo-random permuta-
tions: Luby-Rackoff revisited.”

*Proceedings of the *29th

*Annual Symposium onTheory of Computing*, ACM, 1997.

17. J. Patarin, “Improved security bounds for pseudorandom permutations.” Fourth
ACM Conference on Computer and Communications Security, 1997.

18. J. Patarin, “About Feistel schemes with six (or more) rounds.” To appear in

*Fast*
*Software Encryption *(FSE5), March 1998.

19. J. Pieprzyk, “How to construct pseudorandom permutations from single pseudo-
random functions.”

*Advances in Cryptology – Eurocrypt *90

*Proceedings*, LectureNotes in Computer Science Vol. 473, I. Damg˚
20. C. Shannon, “Communication theory of secrecy systems.” Bell Systems Technical
21. V. Shoup, “On fast and provably secure message authentication based on univer-
sal hashing.”

*Advances in Cryptology – Crypto *96

*Proceedings*, Lecture Notes inComputer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.

22. M. Wegman and L. Carter, “New hash functions and their use in authentica-
tion and set equality.”

*J. of Computer and System Sciences *22, 265–279 (1981).

23. Y. Zheng, T. Matsumoto and H. Imai, “Impossibility and optimality results on
constructing pseudorandom permutations.”

*Advances in Cryptology – Crypto *90

*Proceedings*, Lecture Notes in Computer Science Vol. 537, A. J. Menezes andS. Vanstone ed., Springer-Verlag, 1990, pp. 412-422.

Source: http://krovetz.net/csus/papers/p2f.pdf

Katrina Howard SC Selborne Chambers, Level 9 174 Phillip Street, Sydney, NSW, Australia Tel: +61 2 9233 5188 Fax: +61 2 9233 1137 Mob: +61 416 230 288 Katrina Howard read and practised at the Melbourne bar, before moving to the Sydney bar in 1993. She was appointed senior counsel in 2006. She was head of Wardell Chambers, level 15, from 2006 until she moved to Selborne

COLÉGIO ANCHIETA ENSINO MÉDIO – 2012 2ª SÉRIE SUGESTÕES DE BIBLIOGRAFIAS É importante que o aluno anchietano tenha a sua disposição material para consulta bibliográfica. A aquisição de livros deve ser realizada por escolha do aluno, entre os livros indicados. Com o objetivo de auxiliar na formação de biblioteca dos alunos, a escola sugere os livros abaixo relacion