Return to Answer

What is $\Pr[F]$, the probability of stumbling upon a fixed point in $q$ queries to a uniform random permutation? Let's suppose they are all distinct—obviously repeating a query can only reduce $\Pr[F]$, and we are looking for an upper bound. Let $F_i$ be the event that the $i^{\mathit{th}}$ query is a fixed point: $\pi(x_i) = x_i$. Let $N_i$ be the event that none of the first $i - 1$ queries are fixed points: $\pi(x_1) \ne x_1, \dots, \pi(x_{i-1}) \ne x_{i-1}$. For a single input the output is uniformly distributed, so we have $$\Pr[F_i] = \Pr[\pi(x_i) = x_i] = 1/2^b.$$ The event $F$ can be written as: either $N_1$ and $F_1$, or $N_2$ and $F_2$, or $N_3$ and $F_3$, etc. By the chain rule, $$\Pr[F_i, N_i] = \Pr[F_i \mid N_i]\,\Pr[N_i].$$ Obviously $\Pr[N_1] = 1$; for $i > 1$,

\begin{align} \Pr[N_i] &= \Pr[\lnot F_{i-1}, N_{i-1}] = \Pr[\lnot F_{i-1} \mid N_{i-1}] \, \Pr[N_{i-1}] \\ &= \bigl(1 - \Pr[F_{i-1} \mid N_{i-1}]\bigr) \, \Pr[N_{i-1}]. \end{align}

Let's now find $\Pr[F_i \mid N_i]$: in this event, given $N_i$, there are $i - 1$ possible values of $\pi(x_i)$ ruled out among the $2^b$ strings of $b$ bits, because they have already been covered by $\pi(x_1), \dots, \pi(x_{i-1})$. So the conditional probability that $x_i$ is a fixed point of $\pi$ given that none of the previous queries were is $$\Pr[F_i \mid N_i] = \frac{1}{2^b - (i - 1)}.$$ Thus we can write

\begin{equation} \Pr[N_i] = \prod_{j=1}^{i-1} \bigl(1 - \Pr[F_j \mid N_j]\bigr) = \prod_{j=1}^{i-1} \biggl(1 - \frac{1}{2^b - (j - 1)}\biggr), \end{equation}

and so

\begin{align} \Pr[F] &= \sum_{i=1}^q \Pr[F_i, N_i] \\ &= \sum_{i=1}^q \Pr[F_i \mid N_i] \, \Pr[N_i] \\ &= \sum_{i=1}^q \frac{1}{2^b - (i - 1)} \prod_{j=1}^{i-1} \biggl(1 - \frac{1}{2^b - (j - 1)}\biggr). \end{align}

We can stop here, and set the bound $\Pr[F] \leq q/(2^b - (q - 1))$, since $\Pr[N_i] \leq 1$ so replacing it by $1$ can't make a wrong upper bound. As long as $q \leq 2^{b - 1}$, we thus have $$\lvert\Pr[A(\pi)] - \Pr[A(\delta)]\rvert \leq \Pr[F] \leq \frac{2 q}{2^b}$$ which is enough to give high confidence—if I didn't make any mistakes in the math above—that substituting a uniform random derangement for a uniform random permutation can't reduce the security by much.

What is $\Pr[F]$, the probability of stumbling upon a fixed point in $q$ queries to a uniform random permutation? Let's suppose they are all distinct—obviously repeating a query can only reduce $\Pr[F]$, and we are looking for an upper bound. Let $F_i$ be the event that the $i^{\mathit{th}}$ query is a fixed point: $\pi(x_i) = x_i$. Let $N_i$ be the event that none of the first $i - 1$ queries are fixed points: $\pi(x_1) \ne x_1, \dots, \pi(x_{i-1}) \ne x_{i-1}$. For a single input the output is uniformly distributed, so we have $$\Pr[F_i] = \Pr[\pi(x_i) = x_i] = 1/2^b.$$ The event $F$ can be written as: either $N_1$ and $F_1$, or $N_2$ and $F_2$, or $N_3$ and $F_3$, etc. By the chain rule, $$\Pr[F_i, N_i] = \Pr[F_i \mid N_i]\,\Pr[N_i].$$ Let's now find $\Pr[F_i \mid N_i]$: in this event, given $N_i$, there are $i - 1$ possible values of $\pi(x_i)$ ruled out among the $2^b$ strings of $b$ bits, because they have already been covered by $\pi(x_1), \dots, \pi(x_{i-1})$. So the conditional probability that $x_i$ is a fixed point of $\pi$ given that none of the previous queries were is $$\Pr[F_i \mid N_i] = \frac{1}{2^b - (i - 1)},$$ and thus

\begin{align} \Pr[F] &= \sum_{i=1}^q \Pr[F_i, N_i] \\ &= \sum_{i=1}^q \Pr[F_i \mid N_i] \, \Pr[N_i] \\ &\leq \sum_{i=1}^q \Pr[F_i \mid N_i] &&\text{(since $0 \leq \Pr[N_i] \leq 1$)} \\ &= \sum_{i=1}^q \frac{1}{2^b - (i - 1)}. \end{align}

Hence as long as $q \leq 2^{b - 1}$, we have $$\lvert\Pr[A(\pi)] - \Pr[A(\delta)]\rvert \leq \Pr[F] \leq \frac{2 q}{2^b}$$ which is enough to give high confidence—if I didn't make any mistakes in the math above—that substituting a uniform random derangement for a uniform random permutation can't reduce the security by more than a small factor that is linear in the number of the queries to the permutation.

Since it is difficult to know whether $\operatorname{AES}_k$ is a derangement for any $k$—such a result, affirmative or negative, would be a remarkable theoretical development on AES whether or not it led to an attack—it seems intuitively that an attack on a system with a large random derangement can't do much better than an attack on a system with a large random permutation; if it could, then we could tell whether the input is any old permutation or a derangement. We can formalize this intuition, and quantify it. And it turns out substituting a derangement for a permutation can't hurt security much, unless the security was already extremely low like the Enigma—it hurts security much less than substituting a permutation for a function like we do all the time when we instantiate protocols with block ciphers like AES.

Thus, $\Pr[A(\pi)] - \Pr[A(\delta)] \leq \Pr[F]$. Conversely, $B = \lnot A$ is also an arbitrary random algorithm making $q$ queries, with $\Pr[B(\mathcal O)] = 1 - \Pr[A(\mathcal O)]$ for any oracle $\mathcal O$, so the bound applies to $B$ too, and thus $$|\Pr[A(\pi)] - \Pr[A(\delta)]| \leq \Pr[F].$$

We can stop here, and set the bound $\Pr[F] \leq q/(2^b - (q - 1))$, since $\Pr[N_i] \leq 1$ so replacing it by $1$ can't make a wrong upper bound. As long as $q \leq 2^{b - 1}$, we thus have $$|\Pr[A(\pi)] - \Pr[A(\delta)]| \leq \Pr[F] \leq \frac{2 q}{2^b}$$ which is enough to give high confidence—if I didn't make any mistakes in the math above—that substituting a uniform random derangement for a uniform random permutation can't reduce the security by much.

To put this in perspective, we regularly use AES—a permutation family—to instantiate protocols designed for uniform random functions not restricted to be permutations. There's a standard theorem that $$|\Pr[A(\pi)] - \Pr[A(f)]| \leq \frac{q^2}{2^b},$$ where $f$ is a uniform random function, yet we tolerate that much larger quadratic bound in standard applications like the AES-CCM and AES-GCM authenticated ciphers. In other words, using a derangement instead of a permutation is much less of a flaw than using a permutation instead of a function.

It is difficult to know whether $\operatorname{AES}_k$ is a derangement for any $k$—in the ideal cipher model, it is essentially guaranteed that there exists some $k$ such that $\operatorname{AES}_k$ is a derangement, since about $1/e$ of all permutations are derangements; but a way to determine whether $\operatorname{AES}_k$ is a derangement for any particular $k$ would be a remarkable theoretical development on AES even if it didn't lead to an attack.

Since it is difficult to tell whether $\operatorname{AES}_k$ is a derangement for any particular key $k$, it seems intuitively that an attack on a system with a large random derangement can't do much better than an attack on a system with a large random permutation; if it could, then we could tell whether the input is any old permutation or a derangement. We can formalize this intuition, and quantify it. And it turns out substituting a derangement for a permutation can't hurt security much, unless the security was already extremely low like the Enigma—it hurts security much less than substituting a permutation for a function like we do all the time when we instantiate protocols with block ciphers like AES.

Thus, $\Pr[A(\pi)] - \Pr[A(\delta)] \leq \Pr[F]$. Conversely, $B = \lnot A$ is also an arbitrary random algorithm making $q$ queries, with $\Pr[B(\mathcal O)] = 1 - \Pr[A(\mathcal O)]$ for any oracle $\mathcal O$, so the bound applies to $B$ too, and thus $$\lvert\Pr[A(\pi)] - \Pr[A(\delta)]\rvert \leq \Pr[F].$$

We can stop here, and set the bound $\Pr[F] \leq q/(2^b - (q - 1))$, since $\Pr[N_i] \leq 1$ so replacing it by $1$ can't make a wrong upper bound. As long as $q \leq 2^{b - 1}$, we thus have $$\lvert\Pr[A(\pi)] - \Pr[A(\delta)]\rvert \leq \Pr[F] \leq \frac{2 q}{2^b}$$ which is enough to give high confidence—if I didn't make any mistakes in the math above—that substituting a uniform random derangement for a uniform random permutation can't reduce the security by much.

To put this in perspective, we regularly use AES—a permutation family—to instantiate protocols designed for uniform random functions not restricted to be permutations. There's a standard theorem that $$\lvert\Pr[A(\pi)] - \Pr[A(f)]\rvert \leq \frac{q^2}{2^b},$$ where $f$ is a uniform random function, yet we tolerate that much larger quadratic bound in standard applications like the AES-CCM and AES-GCM authenticated ciphers. In other words, using a derangement instead of a permutation is much less of a flaw than using a permutation instead of a function.

Consider the following cipher: Let $k_0$ be a key for AES-256, and let $k_1$ be a key for a hypothetical Advanced Derangement Standard, ADS. To encrypt the $n^{\mathit{th}}$ message $m$, the ciphertext is $$c = m \oplus \bigl[\operatorname{ADS256}_{k_1}(\operatorname{AES256}_{k_0}(n \mathbin\| 0)) \mathbin\| \operatorname{ADS256}_{k_1}(\operatorname{AES256}_{k_0}(n \mathbin\| 1)) \mathbin\| \cdots\bigr].$$ That is, we encrypt $m$ with AES256-CTR, but we also permute every block of the CTR mode pad first with ADS.

If we advertise a 128-bit security level for this cipher, as I would advertise for AES256-CTR, meaning that the expected cost of an attack to break one of any number of targets is at least $2^{128}$ bit operations, then clearly this attains that security level as long as AES256-CTR does: the fact that we also permute every block again with an independent derangement can't reduce the attack cost.

The fact that the key is longer than 128 bits isn't the important thing—like any block cipher with 128-bit keys, AES-128 doesn't provide a 128-bit security level itself, because the cost of a generic attack on a block cipher with 128-bit keys is substantially less than $2^{128}$ as long as you have more than one target, which is why I recommend that, if you must use AES, you use AES-256 to get a 128-bit security level. What's relevant is the security claim, not the key size.

Since it is difficult to know whether $\operatorname{AES}_k$ is a derangement for any $k$—such a result, affirmative or negative, would be a remarkable theoretical development on AES whether or not it led to an attack—it seems intuitively that an attack on a system with a large random derangement can't do much better than an attack on a system with a large random permutation; if it could, then we could tell whether the input is any old permutation or a derangement. We can formalize this intuition, and quantify it.  And it turns out substituting a derangement for a permutation can't hurt security much, unless the security was already extremely low like the Enigma.

Let $\pi$ be a uniform random permutation, and $\delta$ a uniform random derangement, of $b$-bit strings. Can we set a bound on $\Pr[A(\delta)]$ in terms of $\Pr[A(\pi)]$ for all random decision algorithms $A$—attacks on a cryptosystem involving a permutation or derangement—that make a limited number $q$ of queries to an oracle?

We can stop here, and set the bound $\Pr[F] \leq q/(2^b - (q - 1))$, since $\Pr[N_i] \leq 1$ so replacing it by $1$ can't make a wrong upper bound. As long as $q \leq 2^{b - 1}$, we thus have $$|\Pr[A(\pi)] - \Pr[A(\delta)]| \leq \Pr[F] \leq \frac{2 q}{2^b}$$ which is enough to give high confidence—if I didn't make any mistakes in the math above—that substituting a uniform random derangement for a uniform random permutation can't reduce the security by much.

Of course, if $b = 5$ like you might use to permute up to 32 letters in a Latinoid alphabet, this bound doesn't give high confidence, or any confidence if there's more than sixteen queries—and the table you showed has thirty-one!

Consider the following cipher: Let $k_0$ be a key for AES-256, and let $k_1$ be a key for a hypothetical Advanced Derangement Standard, ADS-256. To encrypt the $n^{\mathit{th}}$ message $m$, the ciphertext is $$c = m \oplus \bigl[\operatorname{ADS}_{k_1}(\operatorname{AES}_{k_0}(n \mathbin\| 0)) \mathbin\| \operatorname{ADS}_{k_1}(\operatorname{AES}_{k_0}(n \mathbin\| 1)) \mathbin\| \cdots\bigr].$$ That is, we encrypt $m$ with AES256-CTR, but we also permute every block of the CTR mode pad first with ADS.

If we advertise a 128-bit security level for this cipher, as I would advertise for AES256-CTR, meaning that the expected cost of an attack to break one of any number of targets is at least $2^{128}$ bit operations,^* then clearly this attains that security level as long as AES256-CTR does: the fact that we also permute every block again with an independent derangement can't reduce the attack cost.

Since it is difficult to know whether $\operatorname{AES}_k$ is a derangement for any $k$—such a result, affirmative or negative, would be a remarkable theoretical development on AES whether or not it led to an attack—it seems intuitively that an attack on a system with a large random derangement can't do much better than an attack on a system with a large random permutation; if it could, then we could tell whether the input is any old permutation or a derangement. We can formalize this intuition, and quantify it. And it turns out substituting a derangement for a permutation can't hurt security much, unless the security was already extremely low like the Enigma—it hurts security much less than substituting a permutation for a function like we do all the time when we instantiate protocols with block ciphers like AES.

Quantifying the impact on security. Let $\pi$ be a uniform random permutation, and $\delta$ a uniform random derangement, of $b$-bit strings. Can we set a bound on $\Pr[A(\delta)]$ in terms of $\Pr[A(\pi)]$ for all random decision algorithms $A$—attacks on a cryptosystem involving a permutation or derangement—that make a limited number $q$ of queries to an oracle?

We can stop here, and set the bound $\Pr[F] \leq q/(2^b - (q - 1))$, since $\Pr[N_i] \leq 1$ so replacing it by $1$ can't make a wrong upper bound. As long as $q \leq 2^{b - 1}$, we thus have $$|\Pr[A(\pi)] - \Pr[A(\delta)]| \leq \Pr[F] \leq \frac{2 q}{2^b}$$ which is enough to give high confidence—if I didn't make any mistakes in the math above—that substituting a uniform random derangement for a uniform random permutation can't reduce the security by much.

Of course, for block size $b = 5$ like you might use to permute up to 32 letters in a Latinoid alphabet, this bound doesn't give high confidence, or any confidence if there's more than sixteen queries—and the table you showed has thirty-one!

_{^* The fact that the key is longer than 128 bits isn't the important thing—like any block cipher with 128-bit keys, AES-128 doesn't provide a 128-bit security level itself, because the cost of a generic attack on a block cipher with 128-bit keys is substantially less than $2^{128}$ as long as you have more than one target, which is why I recommend that, if you must use AES, you use AES-256 to get a 128-bit security level. What's relevant is the security claim, not the key size.}