Can “collisions” occur with encryption algorithms?

Question

For a given Key $K$ and two messages $m_1, m_2$ is it possible for an encryption algorithm (say AES-256) to produce this: $AES(K, m_1)$ = $AES(K, m_2)$?

I understand that the output has to be unique (aka every input has to be mapped to a different output) so that it can be decrypted, but it just seems so bizarre to me that it is possible for an algorithm to consistently map every single bit of input to a different output such that $AES(K, m_i) \ne AES(K, m_j)$ where $m_i$ and $m_j$ are numbers $<2^{256}$.

Do I just have to dive deep into the maths?

Answer 1

For a given Key K and two messages $m_1$, $m_2$ is it possible for an encryption algorithm (say AES256) to produce this: $AES(K, m_1) = AES(K, m_2)$.

Not if $m_1$ is different than $m_2$. Assuming you are talking about AES as a block cipher, and $m_1$ and $m_2$ as input blocks, this is not possible. Every different input block will have a unique output block. Take this cropped image as an example of a 4-bit block cipher with a fixed key, with 16 plaintexts and 16 ciphertexts:

As you can see, 11 encrypts into 12, and thus 12 decrypts to 11. If, as per your example, 13 also encrypted to 12, how would you correctly decrypt 12? Also, how would you decrypt 9?

Well, you couldn't, because a block cipher is a bijection, that is the amount of plaintexts and ciphertexts are composed of sets of equal size, and there is a one-to-one mapping between them, with all of them being paired.

The following behaviors of a block cipher are possible:

$AES(K_1, m_1) = AES(K_2, m_1)$
$AES(K_1, m_1) = AES(K_2, m_2)$
$AES(K_1, m_1) = m_1$

As fgrieu pointed out, a mode of operation with a third input (such as an IV or a prior block) may cause this to happen within a group of blocks, but since the decryption process depends on that third input as well, it will decrypt properly.

Answer 2

Encryption algorithms do not produce collisions for the same key. Ever. AES is a block cipher and is built as permutation, The structure of AES is built to ensure that it is indeed a permutation and collision free. Should it not have been a permutation we would have no chance of decrypting AES even with the secret key. but it is and we can.

You can read about the structure of AES and convince yourself it is indeed a permutation and decryption always works.

If you interestes in block ciphers in general? it may be simpler to explain how this can be achieved with a https://en.m.wikipedia.org/wiki/Feistel_cipher Where understanding why the cipher is invertable is trivial IMHO.

Answer 3

No, that isn't possible. It is because of the nature of how encryption should have a corresponding decryption associated with it, otherwise encryption would make no sense if we cannot decrypt the ciphertext.

If we have that Enc$(k,m_1)$ = Enc$(k,m_2)$ = $c$, then this means that if we try to decrypt $c$ we won't have a determined decryption because both of $m_1$ and $m_2$ are correct decryptions.
This means that the encryption function should be invertible meaning that it cannot be just surjective and not bijective.

You might also want to know that we essentially want our encryption functions to be pseudo-random permutations (falsifying your hypothesis) if input and output sets are of equal cardinality.

Answer 4

The answer depends on if the question is about AES the block cipher (as considered by these two answers); or about a cipher based on the block cipher AES, such as AES-CTR.

For the later, knowing the key it is trivial to exhibit different messages enciphering to the same ciphertext, as long as the Initialization Vectors are known when choosing the messages, and the IVs are not considered part of the ciphertext. Just pick any ciphertext (all-zero will do) and decipher it with the two IVs to obtain the two messages. If padding goes in the way, or one wants to choose a messages, encipher a messages with one IV and decipher with the other IV, an acceptable byte padding will likely be found in less than 300 attempts. Making both messages sensible is harder, but doable for lenient definitions of sensible (e.g. letters-or-digits).