How exactly to concatenate two differential trails to form a boomerang disguisher in practice?

Question

I've been reading many papers on boomerang/rectangle attacks. The general strategy is to find two trails for a small number of rounds and then concatenate them to form a longer distinguisher. Specifically, they decompose the cipher $E$ to $E = E_1 \circ E_m \circ E_0$, and employ some ladder/sbox switch at the connecting point $E_m$ and/or use the BCT to determine the probability of $E_m$.

I am having trouble understanding how exactly one defines $E_m $ given two short trails $E_0$ and $E_1$. For example, let $S$ denote the S-box layer, $L$ denote the linear layer and $X$ denote the key addition of some toy cipher:

$E_0$ 2 round trail trail:

0 0 0 1 --S--> 0 0 0 6 --L--> 0 0 6 0 --X--> 0 0 6 1 --S--> 0 0 d 6 --L--> 0 6 1 0 --X--> 0 6 1 1

$E_1$ 2 round trail trail:

3 1 1 1 --S--> 1 0 0 0 --L--> 0 0 0 1 --X--> 0 0 0 0 --S--> 0 0 0 0 --L--> 0 0 0 0 --X--> 0 0 0 1

Where/how would one define $E_m$ between these two trails? Assuming the transitions $(0 \rightarrow 3), (1 \rightarrow 1)$ have $pr = 1$ and $(6 \rightarrow 1)$ has $pr = 0.5$ from the BCT

Answer 1

In this case because the trail $E_1$ begins at the stage in the cipher directly after the trail $E_0$ ends you can use $E_m$ as the identity map which preserves all differences with probability one.

Thus to generate data to exploit the distinguisher, start with an arbitrary plaintext, say 0x0123 and call the chosen plaintext resource for both this and its paired $E_0$ input (in our example 0x0122). Both of these will lead to outputs after four rounds, say 0xdead and 0xbeef. Now call the chosen ciphertext resource the paired $E_2$ outputs of these ciphertexts (in our example 0xdeac and 0xbeee). If any we fall off either difference trail these won't produce anything useful, but a positive proportion of the time they should decrypt to a pair with the input difference of $E_0$, say 0xf00d and 0xfooc.

To understand the interaction in the middle, suppose that all difference trails are followed precisely. Suppose also that our initial input 0x0123 reached the state, say 0x3141 after two rounds; by the $E_1$ path our input 0x0122 would have moved to state 0x3750. Now consider the states 0x0050 and 0x0641 after two rounds. The (0x3141, 0x0050) states are a $E_1$ input pair and the (0x3750,0x0641) are another $E_1$ input pair, which would both indeed lead us to an $E_1$ output pair (0xdead,0xdeac) and (0xbeef,0xbeee) respectively. Likewise (0x0050,0x0641) represents an $E_0$ output pair which should back up to a $E_0$ input pair (0xf00d,0xf00c) in our example.

Four difference trails have to be respected for this observation to be causal: 2 copies of $E_0$ and two copies of $E_1$. Thus if the probability that $E_0$ is followed is $p_0$ and the probability that $E_1$ is followed is $p_1$, the probability of the boomerang observation is $p_0^2p_1^2$.

The above contains a subtle assumption of independence. In differential trails we can usually assume independence of the individual steps by assuming that round key has a randomising effect. In boomerangs attacks we are tracking four trails and assuming that they behave more or less independently. The assumption of independence is strongest where the upper and lower trail meet and, say, in our example we assume that the probability that $F(x\oplus\Delta_{0,i})$ equals $F(x)\oplus\Delta_{0,o}$ is independent of the probability that $F(x\oplus\Delta_{1,i}$ equals $F(x)\oplus\Delta_{1,o}$ and also the probability that $F(x\oplus\Delta_{0,i}\oplus\Delta_{1,i})$ equals $F(x)\oplus\Delta_{0,o}\oplus\Delta_{1,o}$ when we're talking about the same input value $x$ for all three probabilities instead of randomising each $x$ with round key. This interdependence can greatly inflate or reduce the probability of observing the boomerang statistic and modern developments such as the Boomerang Connectivity Table try to account for this dependence by generating a single probability to account for all three events. To separate out this interdependent step, we can make it a separate stage of our encryption $E_m$. In our case, linear steps can be passed through with probability 1 and independence and we'll extend to that $E_0$ ends immediately before an $S$-box (as it already does) and $E_1$ starts immediately after an $S$-box (for this we pass back through $X^{-1}$ and $L^{-1}$ and append these to the start of our $E_1$ trail). We can now call $E_m$ the transition through our $S$-box and use the BCT to estimate the interdependent probability of transitioning between $E_0$ and $E_1$.