1
$\begingroup$

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) ?

Thanks for your answers.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage May 21 '19 at 19:49
  • $\begingroup$ 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 $\endgroup$ – Richie Frame May 22 '19 at 0:21