17
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Are you asking whether this can hold for a single fixed input or rather all inputs? $\endgroup$ – Artjom B. Feb 23 '16 at 14:10
  • 6
    $\begingroup$ Please clarify what you are asking. Are you asking whether there exists a key k and a plaintext x such that E_k(x)=x? Or are you asking whether there exists a key k such that E_k(x)=x for all x? $\endgroup$ – D.W. Apr 12 '16 at 20:46
44
$\begingroup$

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 2128 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 128! possible permutations, a number waaaay larger than the 2256+2192+2128 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.

$\endgroup$
  • 4
    $\begingroup$ I suspect one could create a handwaving 'proof' for the last para. Let's suppose AES key X had a fixed point with plaintext Y (where Y is at least as large as the key size). If any given bit of Y is altered, then for X to be an identity key, exactly the same bit (but no others) of Y must be changed. But by looking at how AES's 'stirring' works, it cannot be true that changing any one bit of the input changes exactly the same bit (and only that bit) of the output. Therefore X cannot be an identity key. $\endgroup$ – abligh Apr 13 '16 at 8:13
  • $\begingroup$ @abligh Sounds like a reasonable answer to the question. $\endgroup$ – a CVn Apr 13 '16 at 14:45
  • $\begingroup$ @MichaelKjörling I've converted it into an answer. Thomas did most of the work though! $\endgroup$ – abligh Apr 13 '16 at 16:36
  • $\begingroup$ @abligh: that's not a proof that there's no key that makes AES an identity; one can prove that after 2 rounds, AES isn't an identity, but AES has 10-14 rounds; what happens when you get to the third round is hard to model. Now, it's quite unlikely that there's an AES key, but that's basically what Thomas said... $\endgroup$ – poncho Apr 13 '16 at 19:37
9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ OK, this answer is just waiting to be obliterated by a more mathematically inclined one, but I hope it at least provides a "plain English" Jip and Janneke answer (Louis van Gaal at least would call it that, the English translation is of course an explanation in plain/simple language). $\endgroup$ – Maarten Bodewes Feb 23 '16 at 14:41
  • 5
    $\begingroup$ "A modern block cipher would be considered broken if it had a key that would result in the identity function." Why ? O.o $\endgroup$ – Biv Feb 23 '16 at 14:47
  • 1
    $\begingroup$ There are almost an infinite number of possible permutations. Choosing one that is the exact identity function would mean that the copher would be constructed for that purpose. Functionally you would certainly have an issue of the cipher was used to construct other primitives like hash functions, DRBGs etc. Besides of course the obvoious question whty a certain plaintext was not actually encrypted. $\endgroup$ – Maarten Bodewes Feb 23 '16 at 15:01
  • $\begingroup$ That just seems like a case of "don't pick that key". We don't consider RSA broken just because some numbskull can set the public exponent to 1. $\endgroup$ – user2357112 Feb 23 '16 at 19:38
  • 1
    $\begingroup$ That would be an invalid key pair. AES doesn't have any invalid values besides the key size of course. So you would not consider that kind of stupidity. You could still use an all zero key of course but you wouldn't see it when looking at the the ciphertext. $\endgroup$ – Maarten Bodewes Feb 23 '16 at 19:46
0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I do not think that you can rigorously infer "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 true for a single round, but I fail to see how that extends to many rounds. In fact, it seems unlikely that this property holds. $\endgroup$ – fgrieu Apr 13 '16 at 17:14
  • $\begingroup$ @fgrieu if it affects multiple bits on the first round, how can it not also affect multiple bits on subsequent rounds? $\endgroup$ – abligh Apr 13 '16 at 17:36
  • 3
    $\begingroup$ @abligh, subsequent rounds may undo changes of previous rounds. So you have no guarantee. $\endgroup$ – mikeazo Apr 13 '16 at 17:46
  • $\begingroup$ @mikeazo in theory, but as I say "This proof ... relies on AES meeting its design criteria", one of which is minimization of correlation of input and output bits of the Rijndael S-Boxes, and non-linearity of each step in the round. So whilst it's possible a round may undo a previous round (exactly) it should be fantastically unlikely (as I attempt to estimate) - it only needs one bit to differ for the key not to be an identity key. If a key had properties that each round reversed the previous round, it would mean AES has some very weak keys - contrary to the assumption re design criteria. $\endgroup$ – abligh Apr 13 '16 at 17:59
  • 1
    $\begingroup$ This is not a proof, rigorous or otherwise. $\endgroup$ – kodlu Apr 18 '16 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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