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⁻¹ : {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:

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}^blen to itself. In practical terms, we must modify the libraries that define PRF security.

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}^blen → {0,1}^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:

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}ⁿ → {0,1}ⁿ be any function. The Feistel transform of ? is the function FSTL_? : {0,1}²ⁿ → {0,1}²ⁿ defined by:

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⁻¹_? (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⁻¹_? 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

is a 3-round Feistel cipher whose round functions are ?₁, ?₂, and ?₃. Its inverse would then be:

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}ⁿ has the syntax of a keyed round function, where the first argument of F is the round key. For each round key k, the function F(k,·)maps {0,1}ⁿ to itself, so 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):

The sequence of keys k₁,k₂,k₃ 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₁,. . . ,k_r and keyed round function F:

Interestingly, when F is a secure PRF and k₁,k₂,k₃ 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}^3λ × {0,1}^2λ → {0,1}^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⁻¹. For instance, F ⁻¹ is used to decrypt ciphertexts in many encryption schemes that we will see, and unpredictability in F⁻¹ is useful when an adversary generates invalid ciphertexts.

It is possible to insist that both F and F⁻¹ are PRPs, which would mean that ℒ_prp-real and ℒ_prp-rand are indistinguishable when instantiated with F and when instantiated with F⁻¹. In doing so, we have some interactions where a distinguisher queries F and other interactions where a distinguisher queries F⁻¹. A stronger requirement would be to allow the distinguisher to query both F and F⁻¹ 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⁻¹).

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}^blen → {0,1}^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}^4λ × {0,1}^2λ → {0,1}^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}¹²⁸. Suppose I choose a permutation on {0,1}¹²⁸ 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}ⁿ → {0,1}ⁿ is chosen uniformly among all such functions. What is the probability that there exists an x ∈ {0,1}ⁿ 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 wherein ≠ 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⁻¹ 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⁻¹.