Sboxes provide confusion in cipher. Non Linearity measures the strength of sbox layer. In order to measure non linearity of sbox, a table is computed to measure distances with its affine functions. If the dimensions of sbox are huge say eg 64 bits input to 64 bit output, how to determine it's non linearity as table construction is not computationally possible?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ If it is made by finite field inversion, like the AES s-box, then yes it is possible, as the nonlinearity follows a simple rule. I think it is $2^{n-1}$ - $2n$ $\endgroup$– Richie FrameMar 16, 2018 at 11:22
-
$\begingroup$ The sample sbox is based on mixed mode modular arithmetic like IDEA cipher. Is this rule applicable to mixed mode modular arithmetic based sbox? $\endgroup$– R. SamMar 16, 2018 at 20:46
-
$\begingroup$ No. And the correct formula for a finite field inversion s-box should be $2^{n-1}$ - $2^{n/2}$ $\endgroup$– Richie FrameMar 19, 2018 at 3:44
-
$\begingroup$ @RichieFrame For an n bit sbox which is designed by finite field inversion the nonlinearity always $2^{n-1}-2n$? $\endgroup$– RadiumNov 24, 2020 at 10:40
-
$\begingroup$ @Radium as long as $n$ is even, I believe the answer is yes, not sure when it is odd, still might be, but see my corrected equation in the comments $\endgroup$– Richie FrameNov 24, 2020 at 15:55
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
Table construction would require 148 Exabytes of RAM, so it would be hard to store all at once. This also means that you can't have a predefined S box that you might have developed either to be a random permutation, or used some sort of hill climbing technique to be better than random. You can however have a computed S box function. So it would not be a simple look up table, but rather the 64 bit output would be calculated piecemeal (byte by byte) based upon the 64 bit input. As long as the function was bijective and not surjective, you'd have S box behaviour.
So instead of a large table, you'd have a mathematical function. Without resorting to finite fields, the function could be a simple non cryptographic hash of the 64 bits /8 bytes. One implementation would be a Pearson hash of the 8 bytes, with a unique 256 byte permutation table for each byte position. That means you require 2048 bytes of RAM instead. Less than perfect non linearity could be compensated for with additional rounds, as is done in some current lightweight algoriths.
Note. You'd need a similar function for the permutation layer of your cipher as you wouldn't be able to store that easily either.
answered Mar 16, 2018 at 11:41
-
$\begingroup$ My sample sbox is based on mixed mode modular arithmetic just like IDEA. So, i have a function for computing sbox output instead of look up table. Can you explain how to determine it's non linearity. Size is 64 x 64 bit. $\endgroup$– R. SamMar 16, 2018 at 20:50
-
1$\begingroup$ I would imagine using something like a 64-bit block cipher with a fixed key would make a fine 64-bit s-box $\endgroup$ Mar 17, 2018 at 0:45