3
$\begingroup$

I've been studying many papers on differential cryptanalysis and I see that in the published differential characteristics, such as in the appendices of [1], [2] and [3], some differences are left "unspecified" (usually denoted by ** or -).

Why are these differences left unspecified? Since the differentials pass through an S-box, shouldn't their probability be counted? Additionally, how to determine which differentials can be left unspecified and which cannot? Specifically, I'm asking in the context of boomerang attacks

For a more concrete example, section 3.2 from this paper [1] lists a toy example of computing the probability of a differential characteristic for SKINNY:

Example 1. Figure 3 shows a toy example of boomerang characteristic with two differential characteristics on 3 rounds of SKINNY-64(the upper characteristic is above the lower characteristic). We suppose that we are not adding differences in the key (SK model), so we omit the key from the figure as it will not modify the differences. Lime (for the upper characteristic) and pink (for the lower characteristic) colored cells are non zero differences,and grey cells are unspecified differences. All the differences are given in hexadecimal. We denote the input and output differences by ∆ex= [0,d,d,0,0,0,0,0,0,5,0,0,0,0,0,0] and ∇ex= [0,0,2,0,0,2,0,0,0,0,0,0,0,0,0,0] respectively.

enter image description here

In R1 of the upper characteristic, the cell in position 1 (starting from top left, from left to right) with value "2" passes through the SB layer to the "unspecified" gray cell, thus its probability is not counted. It's not clear to me why these cells in particular do not have their probabilities counted in the total prob. of the distinguisher, and why some cells are seemingly more important than others.

$\endgroup$

1 Answer 1

3
$\begingroup$

In these papers they are trying to search for a strong boomerang trail and are semi-exhaustively searching over families of trails where each family has a higher chance of holding than a trail chosen uniformly at random from all possible trails. In these families the unspecified differentials are what we (semi-)exhaust over and the specified parts of the differential are fixed for the family and improve the probability of a typical member of the family above uniform random.

In your example we are looking at two families of differential trails (one upper and one lower) where the fixed differentials for the upper family are lime and white and the fixed differentials for the lower family are pink and white. The fixed parts of the differentials were likely chosen because they have a very high probability of holding and the maximum probability of differentials on the unspecified parts was not as strong. Greedily choosing likely values of the grey differentials gives a large collection of high probability trails for both the upper and lower families. These can then be efficiently pairwise tested using a meet-in-the-middle approach to calculate the probability of the trails combining to make a strong boomerang trail using e.g. a Boomerang Connectivity Table. Trying enough upper and lower trails will hopefully result in a high probability upper trail that combines well with high probability lower trail and a very strong overall boomerang distinguisher.

Note that if more than one strong trail is found, the probabilities reinforce as the same statistical test will detect any trail that has the same start and end points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.