I have to construct a key recovery attack on symmetric key encryption using a publicly known permutation $\Pi$ in $O(2^\frac{n}{2})$ time using $2^\frac{n}{2}$ queries to an encryption oracle.

The encryption is done as $ \Pi ( m \oplus K) \oplus K $, where $K$ is the key. Both $m$ and $K$ belong to ${0, 1}^{n}$

I do not know how I can use the queries to do the key recovery attack in that time. I can check my guesses against the output of the queries for $2^\frac{n}{2}$ of them. But how will I recover the key successfully ?

Really need some help here.

  • 1
    $\begingroup$ Is this homework? $\endgroup$
    – poncho
    Commented Jul 15, 2021 at 23:28
  • $\begingroup$ @poncho One of the practice problems. Not exactly homework. $\endgroup$
    – Itsy
    Commented Jul 15, 2021 at 23:34

1 Answer 1


Well, you said that this was a "practice problem"; hence you're supposed to learn from it, so I won't give you the answer.

I will give you a hint: you have $E_k(M) = \Pi(M \oplus K) \oplus K$; suppose you defined $F_k(M) = E_k(M) \oplus E_k(M \oplus 1)$, and further defined $G$ such that $F_k(M) = G( M \oplus K )$ (and yes, such a $G$ exists independent of $K$). How could you use that to do key recovery?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.