# Does AES have any fixed-points?

Is there any pair of 128-bit strings M and K such that AES$_K$(M) = M?

If yes, how do I go about (efficiently) finding such a pair?

-

Short version: It is quite likely that a large proportion of the keys have fixed points, but I don't have any idea on how to find them.

Long version: A stochastic argument

There are $2^{128}!$ permuations of 128-bit blocks, and of these, $!2^{128}$ (this is the subfactorial) are fixpoint-free. It is known that $\lim_{N\to\infty}\frac{!N}{N!} = \frac 1e \approx 0.3679$ (and this limit is approached quite quickly), i.e. slightly more than one third of all permutations are fixpoint-free.

AES-128 selects $2^{128}$ from these $2^{128}!$ permutations. Assuming this selection behaves like a random one, about 63% of all keys have at least one fixed point.

(This argument is valid for any block cipher with sufficiently large blocks, nothing AES-specific here.)

But ...

Of course, AES (and any block cipher usable in practice) is not a random selection of permutations – for example, all permutations selected by AES are even (AES is composed of operations which each leave some bits unchanged, these are even, and compositions of even permutations are even), thus the available space is halved.

There might be some similar property which makes fixpoint-less permutations less or more likely than a random selection, or even make each key (or no key) have fixed points (both the number of fixed-point-free and non-fixed-point-free permutations are much much larger than the number of available AES keys). I don't know anything here (and as Thomas points out, knowing more might indicate a weakness in AES).

Also, this heuristic gives no way of finding these fixed points (other than brute force).

-
But AES is not a random subset of the $2^{128}!$ permutations on 128 bits; for example, it generates only even permutations. How do we know it doesn't select only from the derangements? –  Fixee Oct 15 '11 at 2:16
Good point. I don't know an answer here (and I'm not sure there is one). Actually I would not be too surprised if AES is made to have fewer fixed points than expected, or none at all. –  Paŭlo Ebermann Oct 15 '11 at 2:23
How could it be "made to have fewer fixed points than expected" without introducing some exploitable structure? You had an idea in mind? –  ByteCoin Oct 15 '11 at 2:27
Probability Distributions Related to Random Mappings by Bernard Harris from 1960 might be useful. –  ByteCoin Oct 15 '11 at 2:32
@ByteCoin: No, I have no ideas. Just the space of fixed-point-free permutations is large enough that we can choose only from those without introducing some weakness by this alone. I hope we get some answers from people which know more about AES (did some cryptanalysis or read the corresponding papers). My argument here is a generic one which is valid (or not) for any block cipher of this block and key size, nothing AES-specific. (I'll edit my answer later after I've got some sleep.) –  Paŭlo Ebermann Oct 15 '11 at 2:37

To my knowledge, no such fixed point is known, but it would be considered highly improbable that there is none (as @Paŭlo points out). We can say that the absence of a fixed point would be viewed as suggestive of a weakness: AES is supposed to "look like" a random permutation.

On the other hand, even being able to prove (non constructively) the presence of a fixed point would already be considered as suspicious: such a proof cannot exist on a really random permutation, so the proof itself would have to exploit the internal structure of AES. Consequently, we currently cannot prove the existence of a fixed point.

There is no known efficient algorithm for finding a fixed point; the best currently known algorithm is trying random keys and messages until a fixed point is hit, with average computational cost $2^{128}$ evaluation of AES.

-
Do you consider the proof that all AES permutations are even to be "suspicious" as well then? –  Fixee Oct 15 '11 at 16:55
@Fixee: yes. But that property is also present in Feistel schemes, which have been deployed since the 1970s without implying any actual attack, so I have learned to live with it. –  Thomas Pornin Oct 15 '11 at 19:38
By the way, finding a fixed-point in AES-128 is equivalent to inverting one round of Davies-Meyer built on AES; showing how to do this efficiently would be a startling result. –  Fixee Oct 17 '11 at 4:27
@Fixee: the fact that AES (resp. DES) is an even permutation matters only after $2^{128}-2$ (resp. $2^{64}-2$) plaintext/ciphertext pairs are known; that explains why it is considered a non-issue in practice. –  fgrieu Apr 30 '12 at 21:53