What makes this mixer function resistant to differential cryptanalysis?

I recently learned how differential cryptanalysis works, and decided to have a play around with testing various designs for resistance against attack.

My testing algorithm is essentially to loop through all $A$ and $B$ values for all potential input differentials ($\Delta A$ or $\Delta B$), and count how many distinct output differentials are seen for each input differential. To ensure its efficacy, I ran it against FEAL's gbox and got the expected value of 1 (0x02) at input differential 0x80.

Testing some other randomly conjured up designs resulted in all sorts of interesting weaknesses, until I stumbled upon this particular construction: Where $S$ is a simple s-box built from fixed 8-bit lookup table. My results from this construction appear to be immaculate: every input differential has a perfect score of 255. I also noticed that removing any single instance of $S$ negates this property.

Am I correct in saying that this is resistant to differential analysis? What is it that produces this apparent resistance? Is there a classification for this kind of mixer construction?

• How many bits are you rotating by? Apr 2 '15 at 0:40
• Probably the fact that $S$ is a good S-box in terms of differential properties. You should compare the DDT of $S$ and the DDT of the entire construction. Apr 2 '15 at 19:31
• @kodlu 2, on an 8-bit input. Sorry, should've said. Apr 2 '15 at 22:46
• @Aleph Sorry, I'm not familiar with the term DDT. The s-box is just a randomly generated preset created by shuffling the numbers 0 to 255 - is it likely that this produced a good S-box in terms of differential properties? Apr 2 '15 at 22:51
• Could you please indicate where you retrieved the mixer function? With this title " ... this mixer function ..." it will not be very easy to find the question and answer. Apr 3 '15 at 20:25

From your picture I deduce that $A$ and $B$ are both 8 bits. So this construction can be seen as a $16 \times 8$ bit S-box (not bijective). The fact that it's not square is probably what is causing confusion. Usually, for SPNs, invertible S-boxes are used. Non-invertible S-boxes are less common, but they certainly have applications.

One of the things we can do to determine the weakness of an S-box with respect to differential cryptanalysis, is to look at the difference distribution table (DDT). That's just a table where each row (column) represents an input (output) difference. The entries are equal to the amount of times the output difference occurs for the input difference. If a certain input difference $\Delta X$ often leads to output difference $\Delta Y$, then this is considered a weakness.

So, how is the value you compute related to the DDT?

My testing algorithm is essentially to loop through all A and B values for all potential input differentials (ΔA or ΔB), and count how many distinct output differentials are seen for each input differential.

For a given input difference $(\Delta A, \Delta B)$ (this corresponds to a row), you compute the amount of columns (output differences) that have a nonzero DDT entry on that row. For S-boxes that are not square, this doesn't really tell us a lot about the strength with respect to differential cryptanalysis. For square S-boxes, it may be some kind of average indicator (which is probably not very useful).

It does explain why you get 255 though. The amount of columns in the DDT equals $2^8 = 256$. The output difference $\Delta Y=0$ only occurs when $\Delta X = 0$. I assume you didn't count those (the result would be 1). This means that there are at most $256 - 1 = 255$ nonzero entries in a row. For common $8 \times 8$ S-boxes that would indeed be theoretically optimal (unfortunately that's not possible, even in theory). But in your case, given that there are $2^{16} = 65536$ (256 times as many) input values, you can indeed get 255 nonzero entries.

(Sorry if the above was not entirely correct, I may have misunderstood the way you compute the "score".)

I computed the DDT for this structure, scaled to an $8 \times 4$ system. With $S$ a very good $4 \times 4$ S-box, the result isn't a very good S-box. Of course it's dangerous to extrapolate to a larger size, but I see no reason why this structure would be particularly good.

• Makes sense! Do you have a reference that explains the part about invertible vs. non-invertible s-boxes for SPNs? It sounds like an interesting topic. Apr 6 '15 at 20:18