2
$\begingroup$

I am trying to understand the paper The Boomerang Attack from David Wagner. On page 162 about complexity of boomerang attack the paper says that:

The attack requires $8 \cdot 2 \cdot 32 \cdot 2^{32} = 2^{41}$ offline computations of the $F$ function.

I think I understand the attack but I cannot understand the value of these complexity constants. From what do $8$ and $2$ originate?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The answer that you are looking for is on page 161.

  • Each round key is guessed and checked in the divide and conquer approach, so $2^{32}$ is the cost of guessing a single key. We need to find the number of $F$ calls in each stage, multiply them and finally sum the cost of each stage.

  • The first and the last (8th) stages require the same 16 quartets and that makes $16\cdot 4\cdot 2$ calls to the $F$ function of the Feistel Network.

    Note that a quartet contains $4$ ciphertext-plaintext pairs.

  • The second and the seventh stages require $8$ quartets and that makes $8\cdot 4\cdot 2$

  • The third and the sixth stage requires $4$ quartets and that makes $4\cdot 4\cdot 2$

  • ...

    The attack halves the number of quartets when it goes inner and inner.

Let's sum them all

\begin{align} time &= 2^{32}(16\cdot 4\cdot 2) + 2^{32}(8\cdot 4\cdot 2) + 2^{32}(4\cdot 4\cdot 2) + 2^{32}(2\cdot 4\cdot 2) + 2^{32}(1\cdot 4\cdot 2)\\ &= 2^{32}(16\cdot 4\cdot 2 + 8\cdot 4\cdot 2 + 4\cdot 4\cdot 2 + 2\cdot 4\cdot 2 + 1\cdot 4\cdot 2)\\ & = 2^{32}\cdot 8 \cdot (16+8+4+2+1)\\ & \approx 2^{32}\cdot 8 \cdot 32 \end{align}

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't see any reason for 2. Me or the Wagner may missed a point there. $\endgroup$
    – kelalaka
    Commented Jun 1, 2021 at 1:47
  • $\begingroup$ The two may be the pre-calculation of the 16 quartets, however, that doesn't add too $2^32 \cdot8 \cdot 32$ because $16*950$ trials can make $16*950*8*4$ F calls. $\endgroup$
    – kelalaka
    Commented Jun 1, 2021 at 13:31
  • $\begingroup$ what ı don't understand is this: Lets think attack on key 1 . We had 16 quartet. For first quartet we guess 2^32 key value and found 2^30 correct key candidate. Then for second quartet we will try these 2^30 key candidate not all 2^32 again. $\endgroup$
    – user738585
    Commented Jun 2, 2021 at 18:19
  • $\begingroup$ Nope, did you check the key schedule of the Coconut98? $\endgroup$
    – kelalaka
    Commented Jun 2, 2021 at 20:04
  • $\begingroup$ yes I checked the key schedule of COCOUNUT98 it consist of xored values of 4 different subkey. But first one is just k1.There is no xor operation for first subkey. $\endgroup$
    – user738585
    Commented Jun 2, 2021 at 20:10

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.