# Construction of key recovery attack in O(2^(n/2))

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.

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

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?