Is it possible to construct a specific AES collision?

Question

Suppose I have a plaintext message P, and I encrypt it using key K to get ciphertext C.

It's trivial to find a different plaintext message P' and a key K' so that the encryption results in C: just decrypt C using K' to get P'.

But suppose that I have a specific P' that I'd like to encrypt, using any key, so that P' encrypted with the key will result in C. Is this feasible?

Answer 1

No. Not with the key alone.

If you have a known plaintext and a known cipher text then the problem of getting the key from that is known as a "known plaintext attack".

And any modern crypto system, including AES, is hardened against this. Several terabytes of plaintext/cipher text pairs will still not allow you to get at the key within reasonable time.

Further reading

• https://en.wikipedia.org/wiki/Known-plaintext_attack
• https://stackoverflow.com/questions/11716468/can-aes-be-cracked-with-enough-decrypted-data-why-or-why-not
• https://crypto.stackexchange.com/questions/1512/why-is-aes-resistant-to-known-plaintext-attacks
• Compute the AES-encryption key given the plaintext and its ciphertext?

However...

If you go beyond simply choosing an AES key and also allow choosing an AES Initialization Vector (IV) for an AES block mode, then, yes, you can do this. Easily. If your message is short enough. You only get one IV's length worth.

It's something of a hobby for one Ange Albertini. He likes to create "polyglot files" that can decoded/interpreted in more than one way.

He gave a talk about this in 2014:

• Ange Albertini. 31c3. 2014-12-29, Funky File Formats

Answer 2

There was a time when some cryptographers considered it infeasible for an attacker to find a P and K so as to produce a given C through AES, and there were attempts to build hash functions from AES based on this assumption. But, hash functions based on AES did not turn out to be as secure as other hashing algorithms (see Why AES is not used for secure hashing, instead of SHA-x?).

What you are asking is: given P is it possible for an attacker to find a K so as to produce a given C. This is at least as challenging as the above case, because in this case the attacker is given a particular P, whereas in the above case both P and K can be chosen by the attacker.

So, the answer is: it depends on the resources available to the attacker. If the attacker has sufficient resources, it may be possible to find a key K that produces a given C from given P (or P'). But, it's going to require a LOT of resources.