Let $\pi : \{0,1\}^n \rightarrow \{0,1\}^n$ be a permutation.

Let $E(k, x) = \pi(x \oplus k)$ where $x,k \in \{0,1\}^n$.

Why isn't $E$ a secure block cipher?

My idea: Suppose $E$ is a secure block cipher.

If one let $k = 0^n$ and let $\pi(s) = s$ for any $s \in \{0,1\}^n$, then one can build an adversary that could guess, for example, that for $x_0 = 0^{n/2}1^{n/2}, \; x_1 = 1^{n/2}0^{n/2}$, the first half of $E(k, x_0)$ would be equal to the second half of $E(k, x_1)$ and the second half of $E(k, x_0)$ would be equal to the first half of $E(k, x_1)$. Such an adversary should have a considerable advantage and then $E$ couldn't be secure.

  • 3
    $\begingroup$ Hint: if the permutation $\pi$ is known to the adversary, how could he use that? What if the adversary can compute $\pi^{-1}$? $\endgroup$ – poncho Apr 24 '18 at 3:37
  • $\begingroup$ @poncho if he knows $\pi(x)$, he could guess $k$ with only one query (if the query gives output $y$, then one just needs to search the value $v$ whose $\pi(v) = y$, and $v = x \oplus k$). Am I allowed to suppose that $\pi$ is known in order to prove insecurity? $\endgroup$ – Daniel Apr 24 '18 at 4:01
  • 3
    $\begingroup$ @Daniel Since in your design $\pi$ is part of your algorithm and not your key, it is known to the adversary. $\endgroup$ – dionyziz Apr 24 '18 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.