# Are encryption algorithms with fixed-point free permutations inherently flawed?

### Flaw in Enigma

One of the Enigma machine's flaw was the derangement (fixed-point free permutation) of the produced ciphertext, or simply put: No plaintext-letter can be enciphered to itself. See this example from Wikipedia of how this text (in German) "Keine besonderen Ereignisse" can or can't be encrypted:

More modern encryption algorithms used during WW2, such as the Enigma-alike Typex machine used by the British, eliminated this flaw, meaning that a plaintext-letter sometimes could indeed be encrypted to itself.

And as far as I know most modern encryption algorithms (i.e. AES) also allow for the possibility of plaintext-letters being encrypted to themselves.

### Questions

My questions are:

1. Are all encryption algorithms with fixed-point free permutations inherently flawed?
2. Can it be mathematically proven that all fixed-point free permutation algorithms can be broken with a "faster-than-brute-force" attack?
• A derangement is a permutation of a set, in this case the alphabet shared by plaintext and ciphertext. Any encryption algorithm where this is not the case (e.g. because the output alphabet has a different size) would be hard to classify in this regard. – MSalters Feb 21 '19 at 12:27

1. Are all encryption algorithms with fixed-point free permutations inherently flawed?

Yes - when fixed points, or the lack of them, is knowable and detectable.

This is a violation of multiple modern semantic security definitions. For example, this means that plaintexts with repeating symbols are distinguishable with high probability from plaintexts that has none. It means you with a high probability can determine what a plaintext does not include, especially if you can observe multiple communications.

This violates security notions like chosen plaintext attacks, indistinguishability from random, and more.

1. Can it be mathematically proven that all fixed-point free permutation algorithms can be broken with a "faster-than-brute-force" attack?

It always makes it easier to guess the plaintext (as according to the answer of question 1), but it does not necessarily make it easier to derive the original key (what bruteforce normally refers to). You can often not say with certainty what the original plaintext is without the key, but often you can settle for an educated guess.

1. Are all encryption algorithms with fixed-point free permutations inherently flawed?

No, they are not inherently flawed.

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.

Of course, that doesn't mean using a derangement is an efficient way to design a cryptosystem! Similarly, using a permutation at all like AES256-CTR is not necessarily an efficient way to design a stream cipher: it is much cheaper to use functions that are not permutations, because the inverse direction is not important.

Can substituting a derangement for a permutation make a difference? Obviously yes: as you saw, this directly led to practical attacks on a cryptosystem in the real world with serious consequences, attacks which would not have been applicable had the permutation not been restricted to a derangement. But how much of a difference can it make? The Enigma used a very small alphabet compared to, e.g., AES, whose ‘alphabet’ of 128-bit blocks has $$2^{128}$$ ‘letters’. Will a protocol that uses a 128-bit permutation become insecure if we replace it by a 128-bit derangement?

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.

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?

Consider the event $$F$$ that of the $$q$$ queries, $$\pi$$ has a fixed point. If this doesn't happen, $$\lnot F$$, then it is as if we had submitted all the queries to a derangement, so clearly $$\Pr[A(\pi) \mid \lnot F] = \Pr[A(\delta)]$$. Thus,

\begin{align} \Pr[A(\pi)] &= \Pr[A(\pi) \mid F]\,\Pr[F] + \Pr[A(\pi) \mid \lnot F]\,\Pr[\lnot F] \\ &= \Pr[A(\pi) \mid F]\,\Pr[F] + \Pr[A(\delta)]\,\Pr[\lnot F] \\ &\leq \Pr[F] + \Pr[A(\delta)]. \end{align}

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].$$

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.

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.

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.

• Nice. What is $\mathcal O$ in $\Pr[B(\mathcal O)] = 1 - \Pr[A(\mathcal O)]$ ? – kodlu Feb 20 '19 at 18:57
• @kodlu It is either oracle, whether a uniform random permutation $\pi$ or a uniform random derangement $\delta$. – Squeamish Ossifrage Feb 20 '19 at 19:17
• Actually the expression before "We can stop here..." simplifies to $q/2^{b}$ due to a telescoping product which divides the bound on $Pr[F]$ by a factor of 2. – kodlu Feb 21 '19 at 6:47
• Asymptotically insignificant but still it's something. – kodlu Feb 21 '19 at 6:48

Block ciphers operators from $$\{0,1\}^n \to \{0,1\}^n$$. Each key selects one permutation among all possible permutations $$n!$$ and this is very small one if you compare $$2^{128}$$ to $$128^{128}$$

For block ciphers like AES;

• One of them is identity, which key selects, we don't know. We don't know even it is selectable by one of the key spaces $$2^{128},2^{196},$$ or $$2^{256}$$
• Many of them have very small non-fixed elements. Still, we don't know...
• Many of them have only one fixed point, i.e. the output is the same only one input, which is selectable by the keys, we don't know.

Nobody has found anything similar to above for AES, yet. If you find it is a good article. If you distinguish a good block cipher from random, it is a good article, too. For example;

The designers of Enigma, in that time, may think that it is a weakness to have an identity for letter-based encryption. With other flaws, it is used in Cryptoanalysis. Using only this flaw cannot help you much in brute-force. It is better to ignore the if condition.

The question: How can we use if we know such property? It is hard to carry into an attack. This property is cipher (full rounds) property of the block-cipher. Linear and Differential attacks work on the rounds functions and try to carry the bias into more rounds. So, the opposite way. If someone may use this to execute an attack, this is another article.

• To be fair, no concrete cipher with short key can correctly "model" an ideal cipher in arbitrary theoretical constructions. The Biryukov et. al. paper you link to shows a problem with using AES in Davies-Meyer -- and while the abstract says what you wrote, what they really mean is something like "theoretical constructions used in practice". I would suggest a reference to the (not related key) biclique attack here. (I think that would illustrate your point better. Also, DES doesn't act like a set of randomly chosen permutations.) – Aleph Feb 20 '19 at 23:15
• Thanks. Kaliski at al claim that: Except for the weak key experiment, our results are consistent with the hypothesis that DES acts like a set of randomly chosen permutations. In particular, our results show with overwhelming confidence that DES is not pure. – kelalaka Feb 21 '19 at 9:20
• The Kaliski et. al. paper is from 1985, since then other results have appeared which are not consistent with the hypothesis that DES acts like a set of randomly chosen permutations (think LC). Sure, DES is not a "pure cipher", but that doesn't imply that it "acts like a set of randomly chosen permutations". I don't really understand how the Kaliski et. al. article illustrates what you're trying to say, since they show that DES does not have some specific properties (so you can't use those for distinguishing). – Aleph Feb 21 '19 at 12:04

There are three nice answers here, each supported with well thought out arguments. It seems to me that not only is it difficult to distinguish between fixed point free and non fixed point free encryption mappings, as shown by @SqueamishOssifrage's answer, it is not the pure encryption mapping $$E(k,x)$$ that is used in many situations but offsets like $$E(k,x+a)$$ where $$a$$ is derived from an IV, depends on a mode of operation, etc.

This results in a further randomization and even if the pure map is fixed point free, the derived map may not be (due to nonlinearity).

So a good cipher with sufficient blocklength and keylength is statistically sometimes fixed point free, sometimes not.