Pseudorandom Permutations

In a simple substitution cipher, each letter is replaced with another letter, for example:

Under this particular substitution, $\bit{cabbage}$ becomes $\bit{rgaagdl}$. If we want to be able to reverse this process, then the substitution must be a permutation over the set of letters $\{ \bit{a}, \ldots, \bit{z} \}$.

Substitution ciphers of individual letters are not difficult to break, and frankly not very interesting. However, a substitution cipher that operates on pairs of letters is slightly more interesting:

In this example, the individual letter $\bit{a}$ can be mapped to $\bit{m}, \bit{i}, \bit{k}, \bit{r},$ etc., depending on its neighboring letters. The cipher must again be a permutation, this time over the set $\{ \bit{aa}, \ldots, \bit{zz} \}$.

A substitution cipher that operates on large blocks of letters is more interesting still. Here's an example that uses blocks of twenty-four letters:

A substitution cipher like this would require a truly enormous amount of storage—in fact, more bytes than there are atoms in the universe.

Just as a PRF emulates an enormous (lazy) random dictionary, a pseudorandom permutation (PRP) emulates an enormous (lazy) random permutation over large blocks of bits. A PRP can expand a short secret key into a permutation (both the forward and reverse directions) that is indistinguishable from a uniformly sampled permutation.

7.1. Defining PRPs

Pseudorandom permutations operate on blocks of bits, not blocks of characters.

This chapter's introduction gives some hint about how to define security for a PRP—it should be indistinguishable from a lazy random permutation. But how does one implement a lazy random permutation? We can take inspiration from lazy random dictionaries, and realize that a permutation is simply a dictionary whose entries do not repeat:

In this code, $\mathcal{Y}$ contains all of the values stored so far in the dictionary. It always samples the next value to avoid repeating any in $\mathcal{Y}$. Thus, the function implemented by $\subname{query}$ is a permutation.

I can already hear you asking, Wait, that's only the forward direction of a permutation. What about the reverse direction? Indeed, a pseudorandom permutation must implement both directions. However, many applications that use pseudorandom permutations expose only the forward direction to the adversary. So for the purposes of security, we will start with this simple attack scenario, in which the adversary gets access to the forward direction only; it must be indistinguishable from the forward direction of a lazy random substitution. Later, in section 7.5, we introduce a stronger security model that provides the adversary access to both directions of the permutation.

PRPs are also commonly called block ciphers, and in this book we will use both names interchangeably.

Be careful! This chapter is about permutations over the set $\bits^n$, meaning that they map an $n$-bit string $X \in \bits^n$ to another arbitrary $n$-bit string $Y$. We are not talking about rearranging the bits of $X$ in a regular way (e.g., move bit 1 of $X$ to bit 10 of the output; move bit 2 of $X$ to bit 3 of the output). This would be one way to map $n$-bit strings to $n$-bit strings, but not a very good one (see exercise 7.1).

7.2. Comparing PRPs and PRFs, and the switching lemma

Compare the $\lib{prp-rand}$ library from the PRP security definition to the $\lib{prf-rand}$ library from the PRF security definition. The former library samples outputs without replacement, and the latter with replacement. If the PRF/PRP outputs are long enough (specifically, $\secpar$ bits) then we expect this difference to be indistinguishable thanks to the birthday bound (lemma 4.5.7). This observation is known as the the (PRF-PRP) switching lemma:

What does it mean that the security goals for PRPs and PRFs are indistinguishable?

This is all potentially confusing, but just remember: A PRF and PRP provide very different functionality to someone who knows the key. But when we talk about PRF security, we are talking about the perspective of an adversary who doesn't know the secret key, and who has access only to the forward direction of the function. The PRF security definition says that, in this situation, outputs are pseudorandom. The definition neither demands nor forbids the existence of an inverse. Just knowing that a function is a PRF tells you nothing about whether it is a permutation. Secure PRPs satisfy the definition of PRF security while having an inverse; some other PRFs do not have inverses.

7.3. How to construct a PRP: The Feistel construction

Can we upgrade a PRF into a PRP? How can we add an inverse to a function that may not have one? This section describes a clever way to do just that.

Definition 7.3.1 (Feistel cipher)

An $r$-round Feistel cipher with round functions $F_1, \ldots, F_r$ is defined as follows:

$\mathbb{F}( X_0 \| X_1 )$:

for $i = 1$ to $r$:

$X_{i+1} := X_{i-1} \oplus F_i(X_i)$

return $X_r \| X_{r+1}$

$\qquad$

If the round functions each map $n$ bits to $n$ bits, then the Feistel cipher $\mathbb{F}$ maps $2n$ bits to $2n$ bits.

Proof:

Each round of a Feistel cipher computes the next block as:

$X_{i+1} = X_{i-1} \oplus F_i(X_i).$

To invert this round, we can rearrange the equation to solve for $X_{i-1}$ in terms of $X_i$ and $X_{i+1}$:

$X_{i-1} = X_{i+1} \oplus F_i(X_i).$

Importantly, we do not require $F_i$ to have an inverse. Both the forward and inverse direction of the Feistel cipher evaluate $F_i$ in the forward direction!

The diagram below illustrates the case of a single round and its inverse:

We can invert the entire Feistel cipher by inverting each round in this way, starting from the last round:

$\mathbb{F}^{-1}( X_r \| X_{r+1} )$:

for $i = r$ down to $1$:

$X_{i-1} := X_{i+1} \oplus F_i(X_i)$

return $X_0 \| X_1$

$\qquad$

Like any Feistel cipher, a keyed Feistel cipher is invertible. In order to invert a Feistel cipher, you must evaluate its round functions (in the forward direction). If the round functions require a key, then that key is required to evaluate both directions of the Feistel cipher.

Since a Feistel cipher is a keyed permutation, we might ask whether it can be a secure PRP. The answer depends on the number of rounds. In exercise 7.5 you are asked to show that a 2-round Feistel cipher cannot be a secure PRP. However, three rounds is enough, assuming that the round function is a secure PRF:

Theorem 7.3.4 (Security of three-round Feistel cipher)

Let $F$ be a secure PRF with input/output length $\secpar$. Then a three-round keyed Feistel cipher with round function $F$ is a secure PRP (with blocklength $2\secpar$).

$\mathbb{F}\Bigl( \key_1\|\key_2 \|\key_3, ~ X_0 \| X_1 \Bigr)$:

$X_2 := X_0 \oplus F(\key_1, X_1)$

$X_3 := X_1 \oplus F(\key_2, X_2)$

$X_4 := X_2 \oplus F(\key_3, X_3)$

return $X_3 \| X_4$

$\qquad$

We already know that any Feistel cipher is invertible, so it suffices to show that this Feistel cipher is pseudorandom. From lemma 7.2.1, it is enough to show that $\mathbb{F}$ is a secure PRF. In other words:

if $\quad$

$\lib{prf-real}^F$

$\key \gets \bits^\secpar$

$\prfquery_F(X)$:

return $F(\key,X)$

$\indist$

$\lib{prf-rand}^F$

$\prfquery_F(X)$:

if $\prftable[X]$ undefined:

$\prftable[X] \gets \bits^\secpar$

return $\prftable[X]$

then $\quad$

$\lib{prf-real}^{\mathbb{F}}$

$\key_1\|\key_2\|\key_3 \gets \bits^{3\secpar}$

$\prfquery_{\mathbb{F}}(X_0 \| X_1)$:

// $\mathbb{F}\bigl( \key_1\|\key_2 \|\key_3, ~ X_0 \| X_1 \bigr)$

$X_2 := X_0 \oplus F(\key_1, X_1)$

$X_3 := X_1 \oplus F(\key_2, X_2)$

$X_4 := X_2 \oplus F(\key_3, X_3)$

return $X_3 \| X_4$

$\indist$

$\lib{prf-rand}^{\mathbb{F}}$

$\prfquery_{\mathbb{F}}(X_0\|X_1)$:

if $\prftable[X_0\|X_1]$ undefined:

$\prftable[X_0\|X_1] \gets \bits^{2\secpar}$

return $\prftable[X_0\|X_1]$

Proof idea: Our goal is to show that the Feistel cipher's outputs are pseudorandom. What can we say about these outputs?

The output is $X_3 \| X_4$, and each of these is an xor-expression:

We can think of any xor expression as an OTP ciphertext. Here, it makes most sense to think of $X_1, X_2$ as the OTP plaintexts and $F(\key_2,X_2)$ and $F(\key_3,X_3)$ as OTP keys. Thus, if we can show that these “OTP keys” are pseudorandom, we will be able to easily conclude that $X_3$ and $X_4$ are also pseudorandom. So what can we say about $F(\key_2, X_2)$ and $F(\key_3, X_3)$?

Clearly these values are outputs of a secure PRF $F$. So they are pseudorandom, provided that the PRF inputs (in this case, $X_2$ and $X_3$) do not repeat. Most of the proof is devoted to showing that $X_2$ and $X_3$ repeat with only negligible probability.

7.4. PRPs in theory and practice

7.4.1. Feistel ciphers in practice

The block ciphers you will encounter in practice are not built from the Feistel cipher recipe presented in lemma 7.3.4, for a few reasons:

• If we build a Feistel cipher from a PRF, and the PRF is built from a PRG according to construction 6.5.1, the result would be slow. It would require $3\secpar$ calls to the PRG to evaluate the PRP on a single input.

• Theorem 7.3.4 doesn't provide great concrete security, which is important in practice. (Recall the discussion of concrete vs. asymptotic security in chapter 4.) The Feistel cipher has blocklength $2\secpar$ but gives only $\sim\secpar/2$ bits of concrete security. The proof of theorem 7.3.4 involves a bad event with probability at most $O(q^2/2^\secpar)$. If an adversary makes $q \sim 2^{\secpar/2}$ queries to $\prfquery$, the bound becomes useless, telling us only that the bad event happens with probability at most 1.

In practice, we use fast block ciphers that don't generally have security proofs that reduce their security to simpler components like PRGs. So theorem 7.3.4 does not describe any real-world block ciphers design. However, some real-world PRPs do use the basic structure of the Feistel cipher. So the practical implication of theorem 7.3.4 is to provide justification for a general design principle for real-world PRPs.

Later in the book, many constructions and security proofs do explain exactly how things are built in the real world. For example, the CBC, CTR, GCM constructions explain exactly how to a PRP is used to build real-world encryption schemes.

The Digital Encryption Standard (DES) was the most widely used block cipher in the '80s and '90s. DES is fundamentally a Feistel cipher; thus, its security rests, to a great extent, on the security of its round function. There are a few important differences between the “theoretical” Feistel cipher and a “practical” one like DES:

• Three rounds are enough for a theoretical Feistel cipher, because in the world of theory you can be confidently assume that your round function is a PRF. (Four rounds are needed to achieve a stronger security property—see section 7.5.) Real-world Feistel ciphers usually have many more rounds, reflecting the fact that the round functions are not proven to be secure PRFs, or even conjectured to be full-fledged PRFs. DES, for example, is a 16-round Feistel cipher.

• A theoretical Feistel cipher uses the simplest possible key schedule, in which the round keys are independent. The proof of theorem 7.3.4 relies heavily on the fact that the round keys are independent, giving rise to completely independent pseudorandom round functions. A theoretical $r$-round Feistel cipher requires a key that is $r$ times longer than the round function's key. Long keys are inconvenient, so real-world Feistel ciphers derive the round keys from a single, short master key. For example, DES has a 56-bit master key, and each of its 48-bit round keys are simply a different subset of bits from the master key.

7.4.2. Meet-in-the-middle attack

There is another reason for real-world Feistel ciphers deriving round keys from a single, short master key. It has to do with an attack called meet-in-the-middle.

The meet-in-the-middle attack requires exponential time $2^{\secpar/2}$, which is why it does not invalidate theorem 7.3.4. Meet-in-the-middle is relevant only when considering concrete security. A block cipher with $\secpar$-bit keys that is vulnerable to a meet-in-the-middle attack can be broken in $O(2^{\secpar/2})$ time; ideally we prefer $\secpar$-bit block ciphers to have $\secpar$ bits of concrete security.

7.4.3. Recommendations and Alternatives

DES is the traditional example of a real-world Feistel cipher and a good illustration of how the real world differs from theory. But DES is sorely outdated; you should never use it. The most glaring problem with DES is that its key is only 56 bits long.

DES was supplanted in the early 2000s by its successor, the Advanced Encryption Standard (AES). There are three standardized variants of AES, supporting keys of length 128, 192, and 256 bits. All three variants use a blocklength of 128 bits. AES is still widely regarded as secure, and it should be your default choice of PRP. Thanks to its position as a global standard, fast hardware-accelerated AES operations are now incorporated into many modern CPUs.

AES is not a Feistel cipher; it is designed using an entirely different methodology. Later, in section 12.3, we discuss a theoretical approach for PRPs that is closer to AES's design.

7.5. ☆ Strong PRPs

You may have noticed that the PRP security definition involves only the forward direction $F$ and not the reverse direction $F^{-1}$. The security definition therefore models an attack scenario in which the adversary can control a victim's inputs only to the PRP's forward direction. This limited attack scenario suffices for many applications of PRPs, which we will see in the next chapters.

However, other applications use PRPs in a way that allows an adversary to control the victims' inputs to both the PRP and its inverse. We need a different security definition for PRPs to reflect this kind of attack scenario.

An adversary who has access to both directions of a PRP should not be able to distinguish what it sees from a lazy random permutation and its inverse. Therefore, the new security definition involves a library that implements a lazy random permutation alongside its inverse. This library is slightly more cumbersome, because it must do significant bookkeeping to efficiently implement a permutation along with its inverse.

Modern real-world block ciphers are designed to be secure SPRPs.

Exercises

1. Let $F$ be a secure PRP with blocklength $\ell$ bits (think of $\ell$ as a small integer, like 7 or 8). For this exercise we will interpret inputs and outputs of $F$ not as $\ell$-bit strings, but as numbers in the range $\{1, \ldots, 2^\ell\}$ in the natural way.

   Now consider the following keyed permutation $F'$, with blocklength $2^\ell$:

   $F'(\key,X)$:

   for $i=1$ to $n$:

   // $i$th bit of $Y$ = $F(\key,i)$'th bit of $X$

   $Y[i] := X\bigl[ F(\key,i) \bigr]$

   return $Y$

   Thus, $F'$ rearranges the bits of $X$ according to the permutation $F$. Show that $F'$ is not a secure PRP.

2. Let $F_1$ and $F_2$ be keyed permutations, both with blocklength $n$, and define the following function $H$:

   $H\bigl( \key_1 \| \key_2, X \bigr) = F_2\bigl( \key_2, F_1(\key_1, X) \bigr).$

   Prove that $H$ is a secure PRP if either of $F_1$ or $F_2$ is a secure PRP. The proof should be split into two cases. In the first case, assume that $F_1$ is secure, and assume nothing from $F_2$ other than the fact that it is indeed a keyed permutation (i.e., it has an inverse). In the second case, swap the roles of $F_1$ and $F_2$.

3. Lemma 7.2.1 requires the PRP to have blocklength (at least) $\secpar$. Suppose that $F$ is a secure PRP with blocklength only $n=16$. Are the libraries from lemma 7.2.1 still indistinguishable?

4. Show that an $r$-round keyed Feistel cipher is not a secure PRP, for any $r$, if its round function is $F(\key_i,X) = \key_i \oplus X$.

5. Show that a 2-round keyed Feistel cipher cannot be a secure PRP, even if the round function is a secure PRF.

6. Let $F$ be a secure PRF with input and output length $\secpar$, and consider the three-round Feistel cipher with round function $F$. Its key schedule normally consists of three independent keys $(\key_1, \key_2, \key_3)$; in this problem we consider the security of simpler key schedules.

   1. Show that the cipher is not a secure PRP if $\key_1 = \key_3$ (and $\key_2$ is chosen independently).

   2. Prove that the cipher is a secure PRP if $\key_1 = \key_2$ (and $\key_3$ is chosen independently).

   3. Prove that the cipher is a secure PRP if $\key_2 = \key_3$ (and $\key_1$ is chosen independently).

7. Let $F$ be a secure PRF with input and output length $\secpar$. In this problem we consider a Feistel cipher variant where the key schedule is $\key_1 = \key_2 = \cdots$, but where the last round function is iterated twice. The three- and four-round variants are therefore:

   $\mathbb{F}( \key, X_0 \| X_1 )$:

   $X_2 := X_0 \oplus F(\key, X_1)$

   $X_3 := X_1 \oplus F(\key, X_2)$

   $X_4 := X_2 \oplus F\bigl(\key,F(\key, X_3)\bigr)$

   return $X_3 \| X_4$

   $\quad$

   $\mathbb{F}( \key, X_0 \| X_1 )$:

   $X_2 := X_0 \oplus F(\key, X_1)$

   $X_3 := X_1 \oplus F(\key, X_2)$

   $X_4 := X_2 \oplus F(\key, X_3)$

   $X_5 := X_3 \oplus F\bigl(\key,F(\key, X_4)\bigr)$

   return $X_4 \| X_5$

   1. Show that the three-round variant above is not a secure PRP.

   2. $\star$ Prove that the four-round variant above is a secure PRP.

8. A standard PRF is secure against an adversary who chooses the PRF inputs. Suppose we do not allow the adversary to choose the inputs; instead, the victim will sample inputs uniformly, and tell the adversary the choice of input. If a PRF's outputs are pseudorandom in this attack scenario, we call it a weak PRF. More formally, $\mathbb{F}$ is a weak PRF if the following two libraries are indistinguishable:

   $\lib{wprf-real}$

   $\key \gets \bits^\secpar$

   $\subname{wprf.query}(\,)$:

   $X \gets \bits^n$

   return $\bigl(\hl{X,} \mathbb{F}(\key,X)\bigr)$

   $\indist$

   $\lib{wprf-rand}$

   $\subname{wprf.query}(\,)$:

   $X \gets \bits^n$

   if $\prftable[X]$ undefined:

   $\prftable[X] \gets \bits^m$

   return $\bigl(\hl{X,} \prftable[X]\bigr)$

   1. Prove that a 2-round keyed Feistel cipher (with independent round keys) is a weak PRF, if its round function is a secure PRF.

   2. How does the answer change if the 2-round Feistel cipher uses the trivial key schedule $K_1 = K_2$?

9. Describe a more detailed implementation of the meet-in-the-middle attack in example 7.4.1. What data structures should you use, and how should you identify values common to two sets, to ensure that the overall running time remains $O(2^{\secpar/2})$?

10. Show that a 3-round keyed Feistel cipher is not a secure strong PRP (definition 7.5.1), even if its round function is a secure PRF.

11. $\star$ Prove that a 4-round keyed Feistel cipher (using independent round keys) is a secure strong PRP (definition 7.5.1) if its round function is a secure PRF.

12. $\star$ Let $F^\pm$ be a secure SPRP with blocklength $\secpar$. In this exercise we will construct a new PRP $H$ that is almost identical to $F$ but with two of its inputs swapped. Specifically, let $X_0 := F^{-1}(\key, \bit0^\secpar)$ and let $X_1 := F^{-1}(\key, \bit1^\secpar)$. Then $H$ will be identical to $F$ except that it will swap the outputs for $\overline{X_0}$ (the bitwise complement of $X_0$) and $X_1$.

    $H(\key, X)$:

    $X_0 := F^{-1}(\key, \bit0^\secpar)$

    $X_1 := F^{-1}(\key, \bit1^\secpar)$

    if $X == \overline{X_0}$:

    return $\bit1^\secpar$

    else if $X == X_1$:

    return $F(\key, \overline{X_0})$

    else:

    return $F(\key, X)$

    $\quad$

    $H^{-1}(\key, Y)$:

    $X_0 := F^{-1}(\key, \bit0^\secpar)$

    $X_1 := F^{-1}(\key, \bit1^\secpar)$

    if $Y == \bit1^\secpar$:

    return $\overline{X_0}$

    else if $Y == F(\key, \overline{X_0})$:

    return $X_1$

    else:

    return $F^{-1}(\key, Y)$

    Pictorially:

    

    $H^{-1}$ cannot be a secure PRP: $H^{-1}(\key, \bit0^\secpar)$ and $H^{-1}(\key, \bit1^\secpar)$ are always bitwise complements, and so $H^{-1}$ is easily distinguished from a random dictionary.

    Despite that, prove that $H$ is a (plain) PRP. Thus, it is possible for $H$ to be a secure PRP while $H^{-1}$ is not.

Chapter Notes

The Feistel cipher methodology first appeared in the Lucifer block cipher, developed by Horst Feistel at IBM in 1971 [100]. Luby and Rackoff were the first to prove that a three-round Feistel cipher is a secure PRP (theorem 7.3.4) if the round function is a secure PRF [149]. Patarin proved that a four-round Feistel cipher is a secure strong PRP (exercise 7.11) [176].

The results of exercise 7.6, involving simplifications to the key schedule of a three-round Feistel cipher, were shown by Ohnishi [173] (in Japanese, as reported in [222]). The attack on a three-round Feistel cipher with key schedule $\key_1 = \key_2 = \key_3$ was also shown independently by Rueppel [197]. The secure (four-round) single-key Feistel cipher variant from exercise 7.7 was proposed by Pieprzyk [182]; the attack against the three-round variant (and many generalizations thereof) was given by Zheng, Matsumoto, and Imai [222].

1. Previous Chapter6. Pseudorandom Functions
2. Next Chapter8. Chosen-Plaintext Attacks Against Encryption