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?


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}

  • $\begingroup$ I don't see any reason for 2. Me or the Wagner may missed a point there. $\endgroup$ – kelalaka Jun 1 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 Jun 1 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 Jun 2 at 18:19
  • $\begingroup$ Nope, did you check the key schedule of the Coconut98? $\endgroup$ – kelalaka Jun 2 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 Jun 2 at 20:10

Your Answer

