# Chapter 7: Pseudorandom Permutations

### Return to Table of Contents

A pseudorandom function behaves like a randomly chosen function. In particular, a randomly chosen function need not have a mathematical inverse. But very often in cryptography it is convenient to have cryptographically interesting algorithms which can be efficiently inverted.

A **pseudorandom permutation (PRP)** is essentially a PRF that is invertible (when given the key). Since the PRP is known to be a permutation, we do not require it to be indistinguishable from a randomly chosen function. Rather, we require it to be indistinguishable from a randomly chosen *permutation*.

**7.1 Definitions**

### Definition 7.1: PRP Syntax

*Let F, F*^{−1} : {0,1}^{λ} × {0,1}^{blen} → {0,1}^{blen} *be deterministic and efficiently computable functions. Then F is a pseudorandom permutation (PRP) if for all keys k* ∈ {0,1}

^{λ},

*and for all x*∈ {0,1}

^{blen}, we have:*F*

^{−1}(

*k,F*(

*k,x*)) =

*x*.

*That is, if F*−1(*k*,·) *is the inverse of F* (*k*,·). *In particular, this implies that F* (*k*,·) *is a permutation on* {0,1}* ^{blen} for every key k. We refer to blen as the blocklength of F and any element of* {0,1}

*.*

^{blen}as a**block**Outside of the world of academic cryptography, pseudorandom permutations are typically called **block ciphers**. We will use both terms interchangeably.

As mentioned above, our security definition will require a PRP to be indistinguishable from a randomly chosen *permutation* on {0,1}* ^{blen}*, rather than a randomly chosen function from {0,1}

*to itself. In practical terms, we must modify the libraries that define PRF security.*

^{blen}As with PRFs, we could consider sampling a permutation on {0,1}* ^{blen}* uniformly at random, but this requires exponential time when

*blen*is large. Instead, we will sample the truth table of a random permutation on-the-fly, and store the mappings in an associative array

*T*in case a query is repeated. This is the same approach taken in our PRF definition.

However, we must ensure that we always sample truth table values that are consistent with a permutation. It suffices to ensure that the function is *injective*. Injectivity is guaranteed by making sure that no two inputs map to the same output. Concretely, when we sample the value of the function at input *x*, we choose it uniformly among the *set of values not used as function outputs so far*. This ensures that the library’s behavior is consistent with a random permutation. The formal details are below:

### Definition 7.2: PRP Security

*Let F* : {0,1}* ^{λ}* × {0,1}

*→ {0,1}*

^{blen}

^{blen}be a deterministic function. For an associative array T, define:*We say that F is a secure PRP if* ℒ

^{F}

_{prp-real}≋ ℒ

^{F}

_{prp-rand},

*where:*

The changes from the PRF definition are highlighted in yellow. In particular, the ℒ_{prp-real} and ℒ_{prf-real} libraries are identical.

**7.2: Switching Lemma**

We have modified ℒ_{prf-rand} to provide access to a random permutation rather than a random function. How significant is the change that we made?

Consider the ℒ_{prf-rand} library implementing a function whose domain is {0,1}* ^{λ}*. This domain is so large that a calling program can see only a

*negligible fraction*of the function’s behavior. In that case, it seems unlikely that the calling program could tell the difference between a random

*permutation*and a random (arbitrary)

*function*.

More formally, we expect that ℒ_{prf-rand} (which realizes a random function) and ℒ_{prp-rand} (which realizes a random permutation) will be indistinguishable, when the parameters are such that their interfaces are the same (*blen* = *in* = *out* = *λ*). This is indeed true, as the following lemma demonstrates.

### Lemma 7.3: PRP Switching

*Let* ℒ_{prf-rand} *and* ℒ_{prp-rand} *be defined as in Definitions 6.1 & 7.2, with parameters in = out = blen = λ. Then* ℒ_{prf-rand} ≋ ℒ_{prp-rand}.

#### Proof

Recall the replacement-sampling lemma, Lemma 4.7, which showed that the following libraries are indistinguishable

ℒ_{samp-L} samples values with replacement, and ℒ_{samp-R} samples values without replacement. Now consider the following library ℒ^{∗}:

When we link ℒ^{∗} ◊ ℒ_{samp-L} we obtain ℒ_{prf-rand} since the values in *T*[*x*] are sampled uniformly. When we link ℒ^{∗} ◊ ℒ_{samp-R} we obtain ℒ_{prp-rand} since the values in *T*[*x*] are sampled uniformly subject to having no repeats. Then from Lemma 4.7, we have:

_{ℒprf-rand}≡ ℒ

*ℒ*

^{∗}◊_{samp-L}≋ ℒ

*ℒ*

^{∗}◊_{samp-R}≡ ℒ

_{prp-rand},

which completes the proof.

#### Discussion

- It is possible to define PRFs/PRPs and random functions over domains of any size. However, the switching lemma applies only when the domains are sufficiently large — in this case, at least
*λ*bits long. This comes from the fact that ℒ_{samp-L}and ℒ_{samp-R}in the proof are indistinguishable only when dealing with long (length-*λ*) strings (look at the proof of Lemma 4.7 to recall why).

Exercise 7.3 asks you to show that a random permutation over *small domains* can be distinguished from a random function.

- The switching lemma refers only to the idealized ℒ
_{prf-rand}and ℒ_{prp-rand}libraries. But a secure PRF has behavior that is indistinguishable to that of ℒ_{prf-rand}, and similarly a secure PRP to that of ℒ_{prp-rand}. That means that a secure PRF with*in*=*out*=*λ*will have outputs that are indistinguishable from those of a secure PRP with*blen*=*λ*.

**7.3: Feistal Ciphers**

A PRF takes an input *x* and “scrambles” it to give a pseudorandom output. A PRP asks for more: there should be a way to “unscramble” the result and recover the original *x*. This seems much harder! Nevertheless, in this section we will see an elegant and simple way to transform a (not necessarily invertible) PRF into a PRP!

### Definition 7.4: Feistal Transform

*Let* ? : {0,1}* ^{n}* → {0,1}

^{n}*be any function. The*?**Feistel transform of***is the function FSTL*_{?}: {0,1}*→ {0,1}*^{2n}^{2n}*defined by:**FSTL*

_{?}(

*L,R*) = (

*R*, ?(

*R*) ⊕

*L*).

*We treat the 2n-bit input and output of FSTL*_{?} *as a pair of n-bit inputs; thus L and R each have n bits.*

Surprisingly, even though ? need not be invertible, the Feistel transform of ? is *always* invertible! See for yourself. Define FSTL^{−1}_{?} (*X,Y*) = (*Y* ⊕ ?(*X*),*X*). Then,

In fact, FSTL_{?} and its inverse are essentially mirror images of each other: see Figures 7.1 and 7.2. The similarity of FSTL_{?} and FSTL^{−1}_{?} makes hardware and software implementations much simpler, as many components can be reused.

#### Feistel Ciphers

A **Feistel cipher** is a block cipher built by composing several Feistel transforms. For example, let ◦ denote composition of functions, so ? ◦ *g* denotes the function *x* ↦ ?(*g*(*x*)). Then

_{?3}◦ FSTL

_{?2}◦ FSTL

_{?1}

is a 3-round Feistel cipher whose **round functions** are ?_{1}, ?_{2}, and ?_{3}. Its inverse would then be:

^{−1}

_{?1}◦ FSTL

^{−1}

_{?2}◦ FSTL

^{−1}

_{?3}.

Note how the round functions are reversed.

It is useful for the round functions of a Feistel cipher to be different. But rather than using totally unrelated functions, a typical Feistel cipher uses a single **keyed round function**; that is, the round function is the same for each round, but it takes an extra argument (a **round key**) which is different in each round.

For example, *F* : {0,1}* ^{λ}* × {0,1}

*→ {0,1}*

^{n}*has the syntax of a keyed round function, where the first argument of*

^{n}*F*is the round key. For each round key

*k*, the function

*F*(

*k*,·)maps {0,1}

*to itself, so*

^{n}*F*(

*k*,·) is a suitable round function. The following is a 3-round keyed Feistel cipher with (keyed) round function

*F*(also Figures 7.3 & 7.4):

_{F(k3,·)}◦ FSTL

_{F (k2,·)}◦ FSTL

_{F(k1,·)}.

The sequence of keys *k*_{1},*k*_{2},*k*_{3} is called the **key schedule** of the cipher. To invert this Feistel cipher, we take its mirror image and reverse the key schedule. Below is a procedural way to compute and invert an *r*-round keyed Feistel cipher *C*, with key schedule *k*_{1},. . . ,*k*_{r} and keyed round function *F*:

Interestingly, when *F* is a secure PRF and *k*_{1},*k*_{2},*k*_{3} are chosen uniformly and independently, such a 3-round Feistel cipher is a pseudorandom permutation (when the block length is large enough). In the exercises, you will show that 1 and 2 rounds do not lead to a secure PRP.

### Theorem 7.5: Luby-Rackoff

*Let F* : {0,1}* ^{λ}* × {0,1}

*→ {0,1}*

^{λ}*=*

^{λ}be a secure PRF with in*out*=

*λ, and define F*

^{∗}: {0,1}

*× {0,1}*

^{3λ}*→ {0,1}*

^{2λ}*:*

^{2λ}as*Then F ^{∗} is a secure PRP.*

**Instantiation**

The Data Encryption Standard (DES) was the most commonly used block cipher, until it was phased out in favor of the newer Advanced Encryption Standard (AES). DES was designed as a standard Feistel network with 16 rounds. Its blocklength is 64 bits, so the input/output length of the round function is 32 bits.

While we have theoretical results (like the one above) about the security of Feistel ciphers with *independent* round keys, Feistel ciphers in practice typically do not use independent keys. Rather, their round keys are derived in some way from a master key. DES follows this pattern, with each 48-bit round key being derived from a 56-bit **master key**. The reason for this discrepancy stems from the fact that an *r*-round Feistel network with *independent* keys will have an *rλ*-bit master key but give only *λ* bits of security. In practice, it is desirable to use a small *λ*-bit master key but derive from it many round keys in a way that “mixes” the entire master key into all of the rounds in some way.

**7.4: Strong Pseudorandom Permutations**

Although every PRP has an inverse, it is not necessarily true that a PRP and its inverse have comparable security properties (the exercises explore this idea further). Yet, it is sometimes very convenient to argue about pseudorandom behavior of *F*^{−1}. For instance, *F* ^{−1} is used to decrypt ciphertexts in many encryption schemes that we will see, and unpredictability in *F*^{−1} is useful when an adversary generates invalid ciphertexts.

It is possible to insist that both *F* and *F*^{−1} are PRPs, which would mean that ℒ_{prp-real} and ℒ_{prp-rand} are indistinguishable when instantiated with *F* and when instantiated with *F*^{−1}. In doing so, we have some interactions where a distinguisher queries *F* and other interactions where a distinguisher queries *F*^{−1}. A stronger requirement would be to allow the distinguisher to query both *F* and *F*^{−1} in a *single* interaction. If a PRP is indistinguishable from a random permutation under that setting, then we say it is a **strong** PRP (SPRP). In our previous example, such security would be useful to model an adversary who can see encryptions of plaintexts (where encryption involves evaluating *F*) and who can also ask for decryptions of invalid ciphertexts (where decryption involves evaluating *F*^{−1}).

The security definition for an SPRP then considers two libraries. The common interface of these two libraries provides *two* subroutines: one for forward queries and one for reverse queries. In the ℒ_{sprp-real} library, these subroutines are implemented by calling the PRP or its inverse accordingly. In the ℒ_{sprp-rand} library, we would like to emulate the behavior of a randomly chosen permutation that can be queried in both directions. For convenience, we therefore maintain two associative arrays to maintain the forward and backward mappings. The formal details are below:

### Definition 7.6: SPRP Security

*Let F* : {0,1}* ^{λ}* × {0,1}

*→ {0,1}*

^{blen}*ℒ*

^{blen}be a deterministic function. We say that F is a**secure strong pseudorandom permutation (SPRP)**if^{F}

_{sprp-real}≋ ℒ

^{F}

_{sprp-rand},

*where:*

Earlier we showed that a 3-round Feistel network can be used to construct a PRP from a PRF. The resulting PRP is *not a strong* PRP. However, a 4-round Feistel network *is* a strong PRP! We present the following theorem without proof:

### Theorem 7.7: Luby Rackoff

*Let F* : {0,1}* ^{λ}* × {0,1}

*→ {0,1}*

^{λ}*=*

^{λ}be a secure PRF with in*out*=

*λ, and define F*: {0,1}

^{∗}*× {0,1}*

^{4λ}*→ {0,1}*

^{2λ}

^{2λ}as:*Then F ^{∗} is a secure strong PRP.*

**Exercises:**

7.1: Let *F* be a secure PRP with blocklength *blen* = 128. Then for each *k*, the function *F*(*k*,·) is a permutation on {0,1}^{128}. Suppose I choose a permutation on {0,1}^{128} uniformly at random. What is the probability that the permutation I chose agrees with a permutation of the form *F*(*k*,·)? Compute the probability as an actual number — is it a reasonable probability or a tiny one?

7.2: Suppose *R* : {0,1}^{n} → {0,1}^{n} is chosen uniformly among all such functions. What is the probability that there exists an *x* ∈ {0,1}* ^{n}* such that

*R*(

*x*) =

*x*?

*Hint:* First find the probability that *R*(*x*) ≠ *x* for all *x*. Simplify your answer using the approximation (1 − *y*) ≈ *e ^{−y}*.

7.3: In this problem, you will show that the PRP switching lemma holds only for large domains. Let ℒ_{prf-rand} and ℒ_{prp-rand} be as in Lemma 7.3. Choose any small value of *n* = *in* =

*out* that you like, and show that ℒ_{prf-rand} ≇ ℒ_{prp-rand} with those parameters. Describe a distinguisher and compute its advantage. *Hint:* remember that the distinguisher needs to run in polynomial time in *λ*, but not necessarily polynomial in *blen*.

7.4: Let ? be a (not necessarily invertible) function that takes in *in* bits of input and gives *out* bits of output. The Feistel transform introduced in the notes works *as long as in* = *out*.

Describe a modification of the Feistel transform that works for round functions even where*in* ≠ *out*, giving an invertible function with input/output length *in* + *out*. Be sure to show that your proposed transform is invertible!

7.5: Show that any function *F* that is a 1-round keyed Feistel cipher **cannot** be a secure PRP. That is, construct a distinguisher to demonstrate that ℒ^{F}_{prp-real} ≢≡ ℒ^{F}_{prp-rand}, knowing only that *F* is a 1-round Feistel cipher. In particular, the purpose is to attack the Feistel transform and not the round function, so your attack should work no matter what the round function is.

7.6: Show that any function *F* that is a 2-round keyed Feistel cipher **cannot** be a secure PRP. As above, your distinguisher should work without knowing what the round functions are, and the attack should work with different (independent) round functions for the 2 rounds.

*Hint:* Make two queries, where the second query depends on the answer to the first. With carefully chosen queries, it is possible to identify a property that is always satisfied by a 2-round Feistel network but that is rarely satisfied by a random function.

7.7: Show that any function *F* that is a 3-round keyed Feistel cipher **cannot** be a secure *strong* PRP. As above, your distinguisher should work without knowing what the round functions are, and the attack should work with different (independent) round functions.

7.8: In this problem you will show that PRPs are hard to invert without the key (if the blocklength is large enough). Let *F* be a candidate PRP with blocklength *blen* ⩾ *λ*. Suppose there is a program ? where:

In the above expression, ?(*y*) indicates that ? receives *y* as an input, and *k* refers to the private variable within ℒ_{prf-real}. So, when given the ability to evaluate *F* in the forward direction only (via ℒ_{prf-real}), ? can invert a uniformly chosen block *y*.

Prove that if such an ? exists, then *F* is not a secure PRP. Use ? to construct a distinguisher that violates the PRP security definition. Where do you use the fact that *blen* ⩾ *λ*? How do you deal with the fact that ? may give the wrong answer with high probability?

7.9: Construct a PRP *F* such that *F ^{−1}* is

**not**a PRP.

*Hint:* Take an existing PRP and modify it so that *F*(*k,k*) = 0* ^{blen}*. Argue that the result is still a PRP, and show an attack against the PRP security definition applied to

*F*.

^{−1}