What are the disadvantages of using random s-boxes? In AES, the s-boxes had to obey certain mathematical rules, which? And why? What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Not quite a duplicate, but worth a read: crypto.stackexchange.com/questions/1297/… $\endgroup$– PolynomialCommented Jul 16, 2012 at 8:07
-
$\begingroup$ Thank you for the link, but what I'm asking is how specific s-box generation techniques affect the security of an algorithm, not how to generate secure s-boxes. By the way, what is the reason for the last two criteria in your question? $\endgroup$– Devros ExrixCommented Jul 16, 2012 at 8:42
-
$\begingroup$ I mentioned the reasons in the comments, but you should probably just ignore those to criteria. I didn't really understand the concept properly when I wrote that. $\endgroup$– PolynomialCommented Jul 16, 2012 at 8:45
-
1$\begingroup$ I just want to note that criteria similar to the last two led to the reverse engineering of Enigma. $\endgroup$– Devros ExrixCommented Jul 16, 2012 at 8:56
-
1$\begingroup$ At least in the case of DES, the s-boxes were stronger than random boxes, since the NSA modified them to make them more resistant to differential cryptoanalysis. $\endgroup$– CodesInChaosCommented Sep 7, 2012 at 17:37
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
What are the disadvantages of using random s-boxes?
This relates to the "why" behind some of the rules for s-boxes. AES, for example, requires an invertible s-box. A random s-box will not necessarily be invertible. In an s-box we also want non-linearity to thwart linear and differential cryptanalysis. This might not be the case with a random s-box.
In AES, the s-boxes had to obey certain mathematical rules, which? And why?
According to "The Design of Rijndael" the design criteria was 1) non-linearity, specifically "the maximum input-output correlation amplitude must be as small as possible" and "the maximum difference propagation probability must be as small as possible". This is to prevent linear and differential cryptanalysis. And 2) algebraic complexity. This was to prevent algebraic attacks.
They achieve 1) by choosing an s-box that was studied in Differentially uniform mappings for cryptography. This particular s-box however is algebraically simple. Thus, the AES designers added an affine transformation which would be easy to describe yet algebraically complex.
One additional restriction they placed was that there were no fixed points and no opposite fixed points.
What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?
Full disclosure, I'm not too familiar with these ciphers. From what I saw on wikipedia, the s-box in GOST can but doesn't have to be kept secret. The effect of this is an increase in the key size. Secret s-boxes would have to have properties similar to those of AES's s-box in order to thwart differential and linear cryptanalysis.
Generated s-boxes, I'm assuming must have some algorithm to setup an s-box using keying material that still meets the necessary properties. I'm guessing this is why Khufu has an expensive setup operation.
-
$\begingroup$ How much criteria (LP,DP,Nonlinearity) for AES substitution boxes? $\endgroup$– user4180Commented Oct 31, 2012 at 12:30
-
$\begingroup$ @user4180 For a $n$bit sbox the highest possible nonlinearity is $\it{nl}=2^{(n-1)}-2^{{n}/{2}}$. Ans the linearity is $2^{(n-1)}-\it{nl}$ AES has the highest possible nonlinearity that is 112. So AES linearity is 16. Again DP is the maximum cell value of difference distribution table(DDT). For AES DP value is 4. $\endgroup$– RadiumCommented Nov 25, 2020 at 4:46