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
    Jul 15, 2021 at 23:28
  • $\begingroup$ @poncho One of the practice problems. Not exactly homework. $\endgroup$
    – Swagata
    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, privacy policy and cookie policy

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