0
$\begingroup$

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:

Toy cipher mixer

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?

$\endgroup$
  • $\begingroup$ How many bits are you rotating by? $\endgroup$ – kodlu Apr 2 '15 at 0:40
  • $\begingroup$ 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. $\endgroup$ – Aleph Apr 2 '15 at 19:31
  • $\begingroup$ @kodlu 2, on an 8-bit input. Sorry, should've said. $\endgroup$ – Polynomial Apr 2 '15 at 22:46
  • $\begingroup$ @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? $\endgroup$ – Polynomial Apr 2 '15 at 22:51
  • $\begingroup$ 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. $\endgroup$ – Maarten - reinstate Monica Apr 3 '15 at 20:25
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Polynomial Apr 6 '15 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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