Is there an AES identity key?

Question

The following questions are of pure theoretical nature. I don't have an application in mind.

1. Is there a key that makes AES the identity function?

2. Is there a key that makes AES the identity function for certain inputs?

3. Is it known whether such keys might exist?

4. Are such keys known for other ciphers?

For example, I want to encrypt "Hello StackExchg" with AES with said key and the ciphertext should be again "Hello StackExchg".

When I encrypt "Hello StackExchg" with the perfect cipher one-time-pad, there is a possibility that the resulting ciphertext is again "Hello StackExchg". This possibility must exist (though it is unrealistically small), otherwise, the ciphertext would not be perfectly random but depending on the plaintext. The corresponding key for one-time-pad would be all zeros.

Answer 1

In the "ideal cipher" model, the block cipher is a permutation of the space of input blocks, chosen uniformly among all such permutations. A plaintext that gets encrypted to itself is a fixed point for the permutation; it is expected that about 63.21% of all permutations have at least one fixed point (a permutation with no fixed point is called a derangement).

Thus, assuming that AES is an ideal cipher, then it is expected that for about two thirds of possible keys, there will be at least one plaintext block that is encrypted to itself.

Now, finding that fixed point is quite another thing; we in fact expect not to be able to easily find that fixed point or even ascertain whether it exists or not -- the "moral" reason is that finding a fixed point on a random permutation requires hitting it exactly, which is akin to a brute force on the whole input space, of size 2¹²⁸ in the case of AES. In other words, if we could find fixed points or even prove (non-constructively) their existence or non-existence for any specific key, then this would mean that we could differentiate AES from the ideal cipher model, and that would be worrying.

(See also that answer on crypto.SE.)

Note: while a majority of AES keys should have at least one fixed point, it is strongly expected that there is no key that turns AES into an identity function (i.e. all plaintexts being fixed points): there are 2¹²⁸! ≈ 2²¹³⁵ possible permutations, a number waaaay larger than the 2²⁵⁶+2¹⁹²+2¹²⁸ possible AES keys, thus the identity permutation is very unlikely to correspond to a key. But then again, we don't expect to be able to prove it.

Answer 2

Is there a key that makes AES the identity function?

No, probably not. That would mean that exactly the right permutation would be chosen out of the almost infinite set of permutations that are possible.

Is there a key that makes AES the identity function for certain inputs?

That's more likely, but it won't be easy to find it.

Is it known whether such keys might exist?

Not to my knowledge. I cannot answer for the rest of earths population though.

Are such keys known for other ciphers?

What you are probably looking for is the notion of weak keys.

The Enigma already had specific methods of avoiding to encrypt the plaintext to the same ciphertext. A modern block cipher would be considered broken if it had a key that would result in the identity function; a modern block cipher isn't supposed to have weak keys. The output would be clearly distinguishable from random, even if just for that key.

Now the chance that a single plaintext would result in the same ciphertext is of course related to the size that is being encrypted. For block ciphers such as AES that would be the block size. It's easy to see that the chance that a particular plaintext encrypts to itself with a certainty of $1/{2^{n}}$ given a specific key.

There are however also $2^{n}$ possible plaintext and of course $2^{k}$ keys (where $n$ is the block size and $k$ the key size). This means that it is extremely likely that there is a key / plaintext combination that would result in the permutation having one relation between plaintext and ciphertext where both are the same.

The trouble is that block ciphers are generally constructed in such a way that this combination would be extremely hard to find. Of course, with DES having a certain kind of weak keys, double DES would be a prime candidate for creating a block cipher acting like a identity function. You just double encrypt with a known weak key and presto: identity function.

The AES competition however required the candidates to have fully random keys and - of course - no weak keys [citation needed]. Combine that with a relatively high block size / key size and it may take quite a bit of a search to even find one key with a single "identity relationship".

Answer 3

I've converted my comment into an answer.

Thomas Pornin accurately sets out why there are likely to be fixed points in AES (where for a given key K, there is a plaintext which equals the ciphertext).

Let me explain why there is no key K where the plain text equals the ciphertext for all plaintext inputs (i.e. there is no identity key). This is not a completely rigorous proof, but the comment got some upvotes so I am putting it in as an answer, to be read in conjunction with Thomas's answer.

Let's suppose you find a given K where there is a plaintext P which equals the ciphertext C. If K is an identity key, then you must be able to modify any given bit of P, and it it must modify the ciphertext C in the same way (else K would not be an identity key as P and C would differ). However, a known property of AES is that modifying the plain text by one bit will affect the ciphertext by more than one bit. This is essentially a property of the Rijndael S-Boxes from which AES is built, and the fact that there are multiple rounds. A design criterion is that a single bit change in the plain text potentially affects every bit in the crypt text; for all them to be unaffected has a probability of 1 in 2^(number of bits in crypt text). Provided the number of bits in the crypt text is significant (i.e. much larger than the number of bits in the key), this means that it is very unlikely indeed that there will be an identity mapping that works for a given length of crypt text. As a true identity key would have to work for arbitrary (infinite) length plain and crypt text, in practice this means there is not an identity key.

This proof is not entirely rigorous as it relies on AES meeting its design criteria, but it "should do".

In short: if AES does what AES is supposed to do, then it is fantastically unlikely an identity key exists. If AES does not do what it's supposed to do, then we have more to worry about than there (potentially) being identity keys.