Decrypting the Same Cipher Text With Different Keys (AES)

Question

Lets say I have a key - k, and plain text P. I then encrypt P with AES using key k:

C = AES_k(P)

Now lets say I have another plain text that I chose - P*.This plain text has nothing to do with P, I choose it to be whatever I want it to be.

Is it possible to find a key - k*, so that when I decrypt C with k* I will get P* ?

Meaning: D_k*( AES_k(P) ) = P*

Answer 1

I don't think the key will necessarily exist. A key defines a permutation over all possible values of a block. With a 128-bit block size, there are (2^128)! possible permutations. With a 256-bit key, there are 2^256 possible keys. That's considerably less than the number of permutations, and so not every permutation can be specified. I think - although I certainly cannot prove, or even argue - that this means that there may not be a specifiable permutation which maps your chosen second plaintext to the ciphertext.

If such a permutation does exist, I think it would be very hard to find. If it was easy, known plaintext attacks on the cipher would be trivial.

Answer 2

I assume here that your plaintexts and ciphertexts P, P* and C are all 128-bit blocks.

If your keys k and k* have 128-bit length (i.e. you are using AES-128), then, with probability about 36.8%, there is no solution: more formally, if you consider the set of all possible values for C and P* (2²⁵⁶ combinations), then for about e^-1 of them there is no k* such that AES_k*(P*) = C.

This follows from the idea that, for a given value of P*, the function which transforms k* into AES_k*(P*) should behave as a random function, and a random function from a set of size N to a set of identical size N has average coverage of 1-e^-1 of the destination set. Here, for a given P*, there are about 63.2% of 128-bit words which are possible outputs of AES encryption of P* with a 128-bit key.

On the other hand, if you allow k* to be wider (AES also accepts 192-bit and 256-bit keys) then there should be a great many solutions k* to your equation.

Anyway, actually finding k* (even a 192-bit or 256-bit k*) should be infeasible, with work factor close to 2¹²⁸ operations. Being able to find k* with less work than that could be viewed as a structural flaw in AES. Knowledge of P and k helps in no way: for the given 128-bit ciphertext C, it is easy to find matching pairs (P, k).

Note: if you take AES and swap the roles of the plaintext and the key, then you get a crude emulation of a hash function with limited input, and 128-bit output. What you are asking for is the feasibility of a preimage attack on that hash function.