Vjylku

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?

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.

2. 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. To encrypt the $n^{mathit{th}}$ message $m$, the ciphertext is $$c = m oplus (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).$$ 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.

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?

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?

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 $$|Pr[A(pi)] - Pr[A(delta)]| 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].$$ 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 $$|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!

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;

• according to Kaliski et. al DES acts like a set of randomly chosen permutations.


• according to Bogdanov et. al: Biclique Cryptanalysis of the Full AES.

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.

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.