# Complexity of Boomerang Attack on COCONUT98

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}

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