# Block cipher fixed points (plaintext equal to ciphertext)

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.

-
On algebra and block ciphers, you should separate that out into a separate question: post a separate question with that. (It might be a bit too broad or open-ended to get good answers, but you can try.) Are you familiar with, for instance, the results that DES encryption is not a group (does not generate a small subgroup)? –  D.W. Jun 6 '13 at 19:27
Thanks for your help and wisdom. I found the paper: link.springer.com/content/pdf/10.1007%2F3-540-48071-4_36.pdf –  user7139 Jun 6 '13 at 19:50

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

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.

-
I suppose the results about probability of fixed points are specifically about block ciphers with key length longer than block length. When they are equal can I say that ONE fixed point must exist? –  user7139 Jun 7 '13 at 8:30
@Truthserum: Odds of existence of fixed point of a particular "bijective map from the set of possible plaintexts to the set of ciphertexts" (your definition) as approximated by a block cipher is about $1-e^{-1}$ regardless of the (assumed good) block cipher's key size. Odds that for at least one key, there is a fixed point, do increase with the key size, and is overwhelming for any mildly secure keyspace (it is about $1-e^{-2^k}$). –  fgrieu Jun 7 '13 at 10:43

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.

-
So you are saying that just because you managed to find one of several keys that correctly decrypt a message, there is only one key that will decrypt ALL messages encrypted under that key? –  user7139 Jun 7 '13 at 8:32
@Truthserum: no, instead it's "just because you managed to find one of several keys that correctly decrypt one block of the message, there is (likely) only one key that will decrypt the entire message". This statement is likely to hold if the message is strictly longer than the key (and the cipher acts approximately like an ideal cipher). –  poncho Jun 7 '13 at 12:56

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