# Can $AES_{k1}(m)$ be equal to $AES_{k2}(m)$? [duplicate]

Context:

We have a generic bloc cipher composed of an encryption function $$E_k$$ and a decryption function $$D_k$$ operating on blocs of $$n$$ bits.

For a key $$k$$ fixed, we can see $$E_k$$ as a pseudo-random permutation from $$\{0,1\}^n$$ to $$\{0,1\}^n$$ (I am wrong ?). $$D_k$$ is the inverse permutation.

If we have a plain/ciphertext pair $$(m, c)$$, a common bruteforce attack consists in enumerating all possibles $$k$$ and testing if $$E_{k}(m) = c$$.

Question

1) Considering that $$E_k$$ is a random permutation, can we have two keys, $$k1$$ and $$k2$$ such as $$E_{k1}(m) = E_{k2}(m) = c$$ ?

2) If the answer is yes (and I think it is), how many $$(c,m)$$ do we need to uniquely determine the right key ?

3) And do we have the same problem for common bloc ciphers like AES or DES (i.e getting more than one $$(c,m)$$ to uniquely determine the right key) ?

• A note on terminology: The family of functions $E_k\colon \{0,1\}^n \to \{0,1\}^n$ is a pseudorandom permutation family, or PRP for short, if it is hard to distinguish $E_k$ from $\pi$, where $k$ is a uniform random key and $\pi$ is a uniform random permutation. For any particular $k$, $E_k$ is just a permutation; it is the family that is pseudorandom, not any particular permutation. – Squeamish Ossifrage May 21 '19 at 19:49
• if you follow simple logic, consider a key size larger than the block size. Therefore there MUST be some $m$ where the ciphertext for 2 different keys is the same. This can be seen easily with a toy cipher, use a 4-bit key and 3-bit block, and try to generate some combination of ciphertext blocks where this does not hold true – Richie Frame May 22 '19 at 0:21