19
$\begingroup$

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?

$\endgroup$
1
  • 5
    $\begingroup$ Just a note, purposefully avoiding fixed points is probably the major reason the enigma machine was cracked. Avoiding fixed points is a big weakness in a cipher. $\endgroup$ Dec 15, 2014 at 21:00

2 Answers 2

21
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ 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? $\endgroup$
    – Fixee
    Oct 15, 2011 at 2:16
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2011 at 2:23
  • 1
    $\begingroup$ How could it be "made to have fewer fixed points than expected" without introducing some exploitable structure? You had an idea in mind? $\endgroup$
    – ByteCoin
    Oct 15, 2011 at 2:27
  • $\begingroup$ Probability Distributions Related to Random Mappings by Bernard Harris from 1960 might be useful. $\endgroup$
    – ByteCoin
    Oct 15, 2011 at 2:32
  • $\begingroup$ @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.) $\endgroup$ Oct 15, 2011 at 2:37
10
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Do you consider the proof that all AES permutations are even to be "suspicious" as well then? $\endgroup$
    – Fixee
    Oct 15, 2011 at 16:55
  • 3
    $\begingroup$ @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. $\endgroup$ Oct 15, 2011 at 19:38
  • $\begingroup$ 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. $\endgroup$
    – Fixee
    Oct 17, 2011 at 4:27
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Apr 30, 2012 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.