16
$\begingroup$

As I understand s box properties, they primarily need high non linearity and low auto correlation. But most importantly for this question, they're not secret.

There are many questions on this site asking for help in generating them. And new ciphers always seem to have new s boxes. Why? There are proven numerical optimisation techniques such as tree search and hill climbing to optimise a function. Could we not just devote an hour of a large computer cluster to generate optimum (say) 3, 4, 5, 6, 7 and 8 bit wide s boxes? Universities have access to such resources. They could then be published in a book rather like they used to publish random numbers.

Note: By static s box, I mean one of those that isn't related to a key like Blowfish's.

| improve this question | |
$\endgroup$
  • $\begingroup$ I'd guess the reason being performance and / or (efficient) computability without a table and / or in constant-time. $\endgroup$ – SEJPM♦ Aug 2 '17 at 14:35
  • $\begingroup$ "devote an hour of a large computer cluster" is not even close enough for 8-bit s-boxes, change hour to FOREVER (there are $2^{1684}$ possible 8-bit permutations) $\endgroup$ – Richie Frame Aug 3 '17 at 0:20
  • 1
    $\begingroup$ @RichieFrame I was implicitly referring to the progress made in www-users.cs.york.ac.uk/~jac/PublishedPapers/CEC-04/paper5.pdf and that they used a Pentium PC. The search space shouldn't be a distraction as that's the point of annealed hill climbing, rather than brute force random generation. $\endgroup$ – Paul Uszak Aug 3 '17 at 0:42
  • $\begingroup$ I know, but the hill to climb is still very large for an 8-bit s-box. The workload to brute force is impossible, for genetic algorithms or simulated annealing it is massively less, but still massive in its own right. I noticed that paper had no test for differential uniformity $\endgroup$ – Richie Frame Aug 3 '17 at 4:40
  • $\begingroup$ @RichieFrame Yes . I've just done an overnight run on generating random 8 bit s boxes and didn't generate a single one with hamming = 3. I can get hamming = 2, but not 3. Never mind 4. Sad face. $\endgroup$ – Paul Uszak Aug 21 '17 at 14:01
11
$\begingroup$

There are simply a long list of properties for S-boxes that are relevant, see for example these questions:

In addition people have been trying to design S-boxes that are fast to implement in hardware or in software or which can be masked efficiently. For example the Midori S-box is designed to be especially energy efficient.

The search space for S-boxes is actually quite big as well; for 4-bit S-boxes (pretty small) there are $16! \approx 2^{44}$ possibilities.

This might be a nice read: Cryptographic Analysis of All 4×4-Bit S-Boxes

| improve this answer | |
$\endgroup$
  • $\begingroup$ It's just that in the optimisation papers I've reviewed, the value /cost function doesn't include things like gate equivalency. Numerical techniques seem to focus principally on non linearity. Is Midori an edge case? $\endgroup$ – Paul Uszak Aug 2 '17 at 16:08
  • 2
    $\begingroup$ But that's my point. They all optimize for different properties depending on their use-case. $\endgroup$ – Elias Aug 2 '17 at 19:19
  • 3
    $\begingroup$ Depending on how much you want to optimize it will at some point even make a difference if you optimize for power or for energy, i.e. smartcards vs wearables. $\endgroup$ – Elias Aug 2 '17 at 19:20
  • $\begingroup$ @PaulUszak Pretty much no one seems look at these from the hardware side. I have an implementation for the AES S-Box that calculates out everything. I have another 8-bit S-Box based on an irreducible polynomial that uses 1/2 the transistors. It's also worth noting that you can have a faster circuit, that uses less power, with more transistors. Mirror architectures give you a NAND with 8 transistors instead of 4 transistors, but it's lower power due to the balanced drain conditions. $\endgroup$ – b degnan Aug 3 '17 at 1:47
  • $\begingroup$ @bdegnan You should write this as an answer $\endgroup$ – pipe Aug 3 '17 at 9:01
7
$\begingroup$

Why?

There are many factors besides basic linear/differential properties. For example, as mentioned by Elias, there are other considerations such as "How does the mapping facilitate masking countermeasures?".

Arguably the most important factor, besides optimal linear/differential properties, is the implementation cost.

Could we not just devote an hour of a large computer cluster to generate optimum (say) 3, 4, 5, 6, 7 and 8 bit wide s boxes?

Probably not for the larger ones, but not only can we, people have already done so. The linked paper presents not just 4x4 s-boxes with optimal cryptanalysis stats, but also organizes the results by the number of instructions required to implement the function in a bit-sliced representation.

As a result of this, they are able to present what is arguably objectively the "best possible" 4x4 s-box, as it has both ideal cryptanalytic properties along with the minimal implementation cost for achieving said properties.

The equivalent for the linear layer

Just for the sake of completeness, there exists similar work for linear diffusion layers here:

we obtain not only the MDS matrices with the least XOR gates requirement for dimensions from $3×3$ to $8×8$ in $GF(2^4)$ and $GF(2^8)$...

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The important point in these papers about 4x4 S-boxes is that all classes of "affine equivalent" 4 bit S-boxes are known. This is not the case for larger S-boxes. $\endgroup$ – Aleph Aug 2 '17 at 16:34
  • 1
    $\begingroup$ It has been done for 5 bit as well: tosc.iacr.org/index.php/ToSC/article/view/601 $\endgroup$ – Elias Aug 2 '17 at 19:18
  • 1
    $\begingroup$ @Elias Not really, only for 5 bit quadratics. $\endgroup$ – Aleph Aug 2 '17 at 20:00
  • $\begingroup$ Good point, overlooked that. $\endgroup$ – Elias Aug 2 '17 at 20:02

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.