A question about the optimal tree of F_delta of rectangle sbox

[zzy32677]

In your paper "Generic Framework for Key-Guessing Improvements", an example of optimal tree is given in appendix F.1. I tried to calculate F_4(y) = S^(-1)(S(y)+4)+y in this example, and found that the F_4 is different from the tree in this paper. After reading the code
trees_rectangle_f_delta.cc in this repository, I find that the tree in appendix F.1 is constructed by funtion S(S^(-1)(y)+4)+y instead of S^(-1)(S(y)+4). I wonder if I misunderstand the example, in other words, F_4(y) = S(S^(-1)(y)+4)+y but not S^(-1)(S(y)+4)+y in this example.

There may be a typo in appendix F.1, x + x' = F_delta(x + k).

[MarkusSuperbus]

Hello Zhangzhi,

Thank you very much for letting us know! I think you are exactly right, we swapped the roles of S and S^{-1} by accident; we are looking at a fixed output difference, so we should first use S, change the output by \Delta, then use S^{-1} [therefore your first point is valid], and then add y to get a difference [so you are also right with the mistake you pointed out].
(Also, there is another typo, we first defined \Delta = 2 and then changed to \Delta = 4; If there are other problems, do not hesitate to tell us, it is helpful.)

Cheers
Marek

[zzy32677]

Hi Marek,
Thanks a lot for your detailed explanation. Your work is exciting and I am trying to apply the technique on some other attacks.
I am reading the applications of your technique now, and I find some typos. In section 5.3 property of F_2, it seems that F_2(x)=6 when x_0=x_3=0. In appendix E.1 the output difference is wrong.

I have some problems when calculating the equation in the last line at page 23,
1/8 (3 (1/2 * 2 + 1/2 * 2) + 3 (1/2 * 2) + 2(1/2 * 2 + 1/2 * 1)) = 1.5 .
This equation shows that for a compatible input pair of sbox0 in round 3, we can get 1.5 pairs from L_1 and L_2 on average. The 1/8 is because of the 8 cases of x0, x2, and x3 of the input of sbox0 in round 3, where 3, 3, and 2 are the three conditions of the difference \Delta_x1 of the input of sbox0 in round 3. This paper does not explain how to get the equation. I try to figure out that in the following picture.

I am not sure that is same to your idea. If I misunderstand the equatoin, could you help me fix that?

Another problem is that in page 25, the computation of P has some typos.

Best Regards,
Zhangzhi