Block cipher fixed points (plaintext equal to ciphertext)

Question

A block cipher is a bijective map from the set of possible plaintexts to the set of ciphertexts, which are the same size and might as well be considered the same thing: $\theta: S\to S$. In this there must exist a fixed point m $\in S$ such that $\theta(m) = m$ (alternatively you could consider encryption to be a binary operator acting on the set $S$ then you could write encryption under key $k$ as $m \odot k = m$, with $m,k \in S$. Unfortunately this cannot form a group since there is no unit $e$ that makes $e \odot k = e$ for all $k \in S$).

It is clear that when the block size is equal to the key size a single fixed point will exist when you hold the plaintext message constant and permute the key. The key allows you to select one of all the possible possible unique mappings, of which one must surely be a fixed point (am I right about my use of the word unique here?).

What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, or equivalently many different keys that will decrypt a ciphertext.

Note: I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions.

Answer 1

The question makes a number of statements that are incorrect. It is not correct that a fixed point is guaranteed to exist. It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist. Moreover, the existence of fixed points has only an extremely tenuous connection to security.

Assume $E$ is a secure block cipher. A reminder of standard notation: $E_k(x)$ denotes the encryption of plaintext $x$ under key $k$ using this block cipher.

Here are some results on the number of fixed points, for different mappings derived from the block cipher $E$:

• If we fix a key $k$ and look at the mapping $x \mapsto E_k(x)$, then we expect this to look like a random permutation. The expected number of fixed points in a random permutation is 1, but this number varies from permutation to permutation. The probability that a random permutation has no fixed points is $1/e \approx 0.37$. For more facts on fixed points of a random permutation, see Random permutation statistics.

• If we fix a plaintext $x$ and look at the mapping $k \mapsto E_k(x)$, then for most modern block ciphers we'd expect this to look like a random function. If the key has the same size as the ciphertext, then the expected number of fixed points (treating it as a random function) is again 1. The probability that a random function has no fixed points is again $1/e \approx 0.37$.

See also Does AES have any fixed-points?, and also The Ideal Cipher Model (wonky) on Matt Green's excellent blog.

The reason a longer key provides extra security has nothing to do with fixed points. It has to do with the fact that a longer key provides better resistance against certain other attacks (e.g., brute-force keysearch).

In short: I think you are laboring under some misconceptions about the existence of fixed points in block ciphers, and their relevance to security.

Answer 2

Your first two paragraphs made a series of statements; these statements were less than perfectly accurate, and D.W. attempted to address those.

You then went on and asked

What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, or equivalently many different keys that will decrypt a ciphertext.

I shall attempt to address this question.

As you know, a block cipher is an invertible transform that takes a plaintext $P$ and a key $k$ and produces ciphertext $C = E_k(P)$.

Now, if $k$ is larger than $P$ or $C$, there must be (in general) lots of values $k$ for which $C = E_k(P)$ for any fixed $P$ and $C$. So, if there lots of $k$'s that act equivalently, why does having a larger $k$ value help?

Well, that's because they're not really equivalent. When we use a block cipher to encrypt a message, this message is (in general) also larger than the block size. We make this work with a block cipher by using a Mode of Operation. This works by somehow converting the message into a series of plaintext blocks $P_1, P_2, ..., P_n$, sending those blocks through the block cipher, and then taking those ciphertext blocks $C_1, C_2, ..., C_n$ into the actual ciphertext (different modes vary in the details).

Two different keys would encrypt a message in the same way only if they both had $C_i = E_k(P_i)$ for all the $(P_i, C_i)$ pairs in the message; this is unlikely to happen.

That is, in general, if the keys were $n$ bits, then a block cipher might be able to decrypt a specific message in $2^n$ different ways, even if $n$ is much larger than the block size; all $n$ needs to be in no larger than the message size.

As for fixed points, you should listen to D.W.; as long as the cipher acts like a random permutation, the existence or nonexistence of fixed points is not particularly relevent.

Answer 3

You also asked

I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions.

One nontrivial result is here; what this result states is that a composition of the DES round functions (with each round function in tne composition keyed independently) generates the alternating group over $Z/2^{64}$; that is, all $(2^{64})! / 2$ permutations within that group can be creating by tacking on enough DES rounds (and keying each round correctly).

This result rather implies that, at least for DES (and 3DES), it appears unlikely to be any possible result based on the fact that it consists of iterated round functions; of course, a result that relies on the fact that the rounds aren't actually keyed independently for DES/3DES, or that there is a fixed number, is still possible).