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