1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you want to recover $x'$, why doesn't $x-2^n=x'$ work? $\endgroup$ – SEJPM Aug 11 '17 at 13:54
  • $\begingroup$ 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 :( $\endgroup$ – Donut Aug 11 '17 at 13:57
  • 1
    $\begingroup$ @Donut Maybe you could post the actual question from wherever you are relaying it from. $\endgroup$ – Elias Aug 11 '17 at 14:27
  • $\begingroup$ These are all information I received. There is no more. Sorry. If I had more information, I would have added it. $\endgroup$ – Donut Aug 11 '17 at 14:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Donut Aug 11 '17 at 15:24
2
$\begingroup$

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...

$\endgroup$

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.