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: [email protected] 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 Fnd, where d is a parameter on which the construction depends. (The impatient reader can jump to Section 3 to see how Fnd 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 Fnd 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 Fnd 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 ann-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 mapE 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 2n/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 2n/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 kand 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 functionEk 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 Fis 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 = x1 · · · 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 = 2n/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 ≥ 2n/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 = 2n/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 thisFk(·) you effectively have an oracle for Ek(·): for any query x you can computeEk(x) as x⊕Fk(x). So Fk will resemble a random function no more than Ekdoes.
There are many natural alternatives to the Fnd 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}2n → {0, 1}2n.
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 2n/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 2n/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 2n. 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 MACk1,k2(M ) =(ctr, Ek2(ctr)⊕hk1(M )), but the security would degrade by Θ(q22−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, Fk2(ctr)⊕hk1(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 = Fn0E byF (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, letx 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 = FndE takes a κj bitkey k1 · · · kj and an n-bit input x to return an n-bit output y as follows: function F (k1 · · · kj, x)begin k ← E(k1, 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 k1, the derived key k is the first 56 bits of DESk (x ), and the output is DESk (x). If E is TDES (two-key triple-DES), so that κ = 112 andn = 64, we would have j = 2, so the key for F is a pair k1k2 of TDES keys, thederived key k is the first 112 bits of TDESk (x )TDES (x ), and the output is Notice that for fixed k1 · · · 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 2n−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)2d, ., i2d − 1.
Efficiency. Recall that the nominal way to encrypt using F = FndE 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 every2d 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 + j2−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 = FndE 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 = Fnd).
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 tog ← {y}.) Let Permn denote the set of all permutations π : {0, 1}n → {0, 1}n.
Let Randn 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, ·) ∈ Permn 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, ·) ∈ Randn. 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 Randngiven 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 G1, G2 be two families offunctions with the same block length. We define 1 : Dg = 1 ] − Pr [ g ← G2 : 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 eachEk is taken to be random permutation on n-bit strings. Let FE 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 = Fnd and κ∗ = jκ wherej = κ/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 = FE 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 ← (FE)k∗ : AE,E−1,f = 1 − Pr E ← BCκ,n ; f ← Randn : 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) = maxA {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 ← Permn : 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 = Fn0E. Its security asa PRF is described by function (·, ·) which for any number of queries q ≤ 2n/2 and time t can be bounded as follows: where t = t + O(q) · (κ + n + TimeE). 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 q2/22n,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 q2−κ so the second term in our bound looks like q22−κ. Since κ = nthis is q22−n.
Fig. 1. Right curve: Illustrating Theorem 2, our upper bound on the adversary’s
advantage in distinguishing F = FndE 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 = FndE 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/2d) 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 = Fnd. 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 = FndE 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 t5 · 2−4κ + j2 + 2jˆq+ tj + t · 2−κ + ˆq22d−n+3 + tˆt2d−n−κ+2 . Thus the advantage remains low until q ≈ 24κ/5, t ≈ 24κ/5, q ≈ 2n, 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κ, 2n−2d}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 FndE. We presenttwo adversaries: one which becomes successful when q ≈ 2n−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 = Fnd. 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− q2−d ·(2d−1)·2d−n−1 . Proposition 2. Let n, κ be positive integers and t, d, c be non-negative integers
with 0 ≤ d < n, let F = Fnd, 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κ} − t2−cn . The first lower bound is around 1 − e−q2d−n−1, while the second one is aroundt2−jκ. These become significant when q ≈ 2n−d or t ≈ 2jκ. 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 37thSymposium 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 90Proceedings, 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