Decrypting the Same Cipher Text With Different Keys (AES)

Lets say I have a key开发者_JAVA百科 - 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*

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.

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.

This should not be possible for any plaintext that you choose. Being able to decrypt a ciphertext to arbitrary plaintext would imply something known as perfect security (or perfect secrecy).

For example, if I have cipher ADGWTX and I know that it is encrypted using simple XOR and a 6 letter key, I still cannot break this without more informaion about the key. Because one key will give me ESCAPE while another key will give me ATTACK.

Perfect security is a feature of the "one-time pad" (http://en.wikipedia.org/wiki/One-time_pad), but not AES.

It is possible to get k* and decrypt C to get plaintext P*, but only by decrypting it with another type of cipher, like perhaps vernam cipher.

you can get k* such that D_k*( AES_k(P) ) produces your P*.

you just do: P* ^ C to get your k* then if you decrypt: k* ^ C you get P* (assuming both C and P* are of equal size)

but if the size of your P* is smaller than C, then it will produce a repetitive P*

^ : bitwise XOR

Im not sure if that's what you want, you didn't mention you want to decrypt it using AES also.