# Meet in the Middle Attack on x=2^n + x'

I encountered today the following equation:

$x = 2^n + x'$, where $0 \le x' < 2^k < 2^n$, $2|k$ and $n, k$ is known.

There seems to be a meet in the middle attack for this, with runtime $O(2^{\frac{k}{2}})$ but I don't see it.

$x$ is known and we want to recover $x'$.

Could anyone give me a hint?

Thanks.

• If you want to recover $x'$, why doesn't $x-2^n=x'$ work? – SEJPM Aug 11 '17 at 13:54
• I agree, this would work but I got asked about a Meet in the Middle Attack and that's what I can't figure out :( – Donut Aug 11 '17 at 13:57
• @Donut Maybe you could post the actual question from wherever you are relaying it from. – Elias Aug 11 '17 at 14:27
• These are all information I received. There is no more. Sorry. If I had more information, I would have added it. – Donut Aug 11 '17 at 14:40
• I totally agree that it can be solved without a meet in the middle attack. We have seen it in an exam today. We discussed it with several people but no one of us has an idea how to perform a mitm attack on that one. I thought I am going to ask here to see if someone has a hint or idea. – Donut Aug 11 '17 at 15:24

Well, if you absolutely had to do a MITM attack, I suppose one could look like:

• Rewrite the equation as:

$$x - x'_{low} = 2^h + 2^{k/2}x'_{high}$$

where $x' = 2^{k/2}x'_{high} + x'_{low}$ and $0 \le x'_{low}, x'_{high} < 2^{k/2}$

• For each $x'_{low}$ value in the range, compute $x - x'_{low}$ and place it in a list.

• For each $x'_{high}$ value in the range, compute $2^h + 2^{k/2}x'_{high}$ and place it in a list.

• Flip the order of the first list (normally, you're supposed to sort them; these are already in sorted order), and then scan through the two lists, and look for a value in common.

Yes, this is a silly way to do it; however it is a Man-in-the-Middle attack of the specified complexity; this might be the answer they're looking for...