What's happens if we use the weakest S-BOX for AES?

Question

I'm in research of generating Dynamic Secret S-BOX for AES based on 2 Keys (Encryption Key and *I Called S-BOX key). If (worst scenario) I randomly generate the worst S-BOX in an encryption. What would happen? How much it affect to the security of the encryption? I need a reference about this issue. Thanks

Answer 1

See: How can one construct the weakest S-box ever?
and How do I choose the best 3*3 s-boxes?

I believe that user Hend's question is not "how to design the worst possible S-box" but about "having generated an S-box randomly how do we know it is bad, how is that measured?".

A construction of S-boxes that was a trifle, insignificant, a minimis non curat would simply encode during half the rounds and decode during the other half, producing output equal to the input. If the number of rounds were odd the algorithm could leave the output in a state that was equivalent to a single round.

Obviously such poor design is trivial to discover. Where the problem lies is "when presented with an S-box construction that appears complex how do we disprove that". That is the question that I touch upon with this answer.

There are different cryptanalysis techniques and different ways to measure security. Some are published and some are secret. It's not particularly useful to measure an algorithm's security by a published method if a secret method exists for easily cracking the code.

For example: If it were though that there were only 10 ways to approach the cryptanalysis, the first 9 taking a little over a month each to execute but without any certainty of success and the 10th method providing absolute certainty of success but taking a year to produce the result, it makes sense to try the first 9 methods; you don't know which one will be successful but the worst case is it would take as long as simply applying only the 10th algorithm alone.

Similarly, if there were an 11th method, unknown to almost all cryptanalysists, one can not say that any S-box construction is opaque; that it does not reveal itself, and most importantly the original input. This answer can not speculate on what we don't know and will be limited to published measurements of complexity.

Some of the measurements are resistance to:

• Algebraic attacks (RAA) (e.g., XL attack, XSL attack and Gröbner basis attack)

  "Cryptanalysis of block ciphers with overdefined systems of equations" by Nicolas T. Courtois and Josef Pieprzyk.

• Differential cryptanalysis

• Linear cryptanalysis

• Distance to the Strict Avalanche Criterion (DSAC)

In "An improved AES S-box and its performance analysis" by Jie Cui, Hong Zhong, Wei Yang they provide the formula for calculating the above metrics, and offer a list of papers they referenced; unfortunately the first four that I searched for are paywall only. The referenced papers are probably not necessary to understand their paper or this answer.

"The cryptanalysis of the cryptographic strength of Rijndael has not stopped after the announcement and official publication of the AES $[11-16,19]$. Biryukov et al. $[10]$ proposed a distinguisher and related-key attack on the full AES-256. Wang $[5]$ noted that AES S-box affine transformation period is 4, and it does not achieve the most 16. Wang et al. $[6,17,18]$ studied AES S-box structure and pointed out that the iterative period of AES S-box has short-period phenomenon, and all the periods are less than 88. Murphy and Robshaw $[3]$ analyzed AES S-box algebraic expression and indicated that the algebraic expression of AES S-box is very simple and only 9 terms are involved. Much work has concentrated on AES S-box, such as the latest significant progress $[7]$ which illustrated the reason why AES S-box algebraic expression is so simple and proposed an improved S-box, and the algebraic expression of the S-box involves 255 terms, so the complexity of the S-box has been increased. However, the algebraic expression of the inverse S-box becomes very simple and only 9 terms are involved.

In view of the shortcomings of AES S-box and the S-box $[7]$, in this paper, the cryptographic properties of AES S-box are analyzed, and an improved scheme to increase the complexity and security of AES S-box is proposed. Simulation results show that the improved AES S-box is better than AES S-box and S-box $[7]$ in cryptographic properties.

In their paper they offer this table on page 2301:

$[3]$ "Essential algebraic structure within the AES" by S. Murphy and M. J. B. Robshaw, Proc. of the 22nd Annual International Cryptology Conference on Advances in Cryptology, London, pp.1-16, 2002.

$[5]$ "Property of affine transformation in S-box of AES" by Y. B. Wang, Journal of PLA University: Science and Technology, vol.4, no.2, pp.5-9, 2002.

$[6]$ "Analysis of structure of AES and its S-box" by Y. B. Wang, Journal of PLA University: Science and Technology, vol.3, no.3, pp.13-17, 2002.

$[7]$ "An AES S-box to increase complexity and cryptographic analysis" by J. M. Liu, B. D. Wei and X. M. Wang, Journal of Systems Engineering and Electronics, vol.18, no.2, pp.427-433, 2007

$[10]$ A. Biryukov, D. Khovratovich and I. Nikoli´c, "Distinguisher and related-key attack on the full AES-256", Fast Software Encryption, Advances in Cryptology – CRYPTO 2009, pp.231-249, 2009.

$[11]$ W. Phan, "Impossible differential cryptanalysis of 7-round advanced encryption standard (AES)", Information Processing Letters, vol.91, no.1, pp.33-38, 2004.

$[12]$ E. Biham, O. Dunkelman and N. Keller, "Related-key boomerang and rectangle attacks", EURO-CRYPT ’05, LNCS, vol.3494, pp.507-525, 2005.

$[13]$ J. Kim, S. Hong and B. Preneel, "Related-key rectangle attacks on reduced AES-192 and AES-256", FSE 2007, LNCS, vol.4593, pp.225-241, 2007.

$[14]$ W. Zhang, W. Wun, L. Zhang and D. Feng, "Improved related-key impossible differential attacks on reduced round AES-192", SAC 2006, LNCS, vol.4356, pp.15-27, 2007.

$[15]$ S. Galice and M. Minier, "Improving integral attacks against rijndael-256 up to 9 rounds", LNCS, vol.5023, no.3, pp.1-15, 2008.

$[16]$ C.-C. Chang, Y.-W. Lai and J.-H. Yang, "An efficient authenticated encryption scheme based on elliptic curve cryptosystem for broadcast environments", ICIC Express Letters, vol.4, no.1, pp.95-100, 2010.

$[17]$ J. Liu, B. Wei and X. Wang, "Affine transformation observation on rijndael S-box", Journal of Xidian University, vol.32, no.1, pp.94-97, 2005.

$[18]$ L.-G. Cui, "A new S-box structure named affine-power-affine", International Journal of Innovative Computing, Information and Control, vol.3, no.3, pp.751-759, 2007.

$[19]$ Y.-S. Yeh, C.-Y. Lee, T.-Y. Huang and C.-H. Lin, "A transpositional advanced encryption standard (AES) resists 3-round square attack", International Journal of Innovative Computing, Information and Control, vol.5, no.5, pp.1253-1264, 2009.

As you can see the weakest, even stronger S-boxes, are suspicious. Belief that no one anywhere has a means to break the algorithm is probably misplaced. Some S-boxes would be more susceptible to one kind of an attack over another, so there's not one particularly strong or weak one without improvements to the original algorithm. The authors offer an improved version and their analysis of that, in addition to the original.

---

In the thesis "The Design of S-boxes" (direct .PDF link) (2010), by Jennifer Miuling Cheung and the paper "The Structured Design of Cryptographically Good S-Boxes" (1990) by Carlisle M. Adams and Stafford E Tavares, J. Cryptology. 3. 27-41. 10.1007/BF00203967 and "Modification in Designing of Substitution Technique Using 4x32 S-Box in Data Encryption Standard" (direct .PDF link, or 2nd source), (2018), by Sumit Chaudhary, N. K. Joshi, and Foram Suthar - the general consensus has improved over the years but is currently:

Five design factors that must be meet for Boolean functions to construct a cryptographically good S-box:

1. Bijection: If the S-box is of ‘n x n’ bit then from input vectors a one-to-one and onto mapping to output vectors will be there. This can be explained later that how we can achieve this criterion when the S-box will be n x m bits.

2. Strict avalanche criteria: Here, there will be the change in output bit with the probability of one-half only if a strict avalanche criterion of one input bit has changed. In Strict avalanche criteria, output vector will be significantly changed with a small/slight amount of change in the input vector. So, a function is needed that has a 50% dependency on each of its n input bits inorder to achieve this effect.

3. Bit independence criterion or correlation-immunity: Here, there is a requirement that output bits should have different statistical patterns or no statistical dependencies compare to the output vectors.

4. Nonlinearity: The cryptosystem is susceptible to various attacks so nonlinearity requires S-box which should not be a linear mapping from input to output. If the nonlinearity gives a bad result by linear functions and makes a cryptosystem more complex to crack so S-box will be constructed by using maximally nonlinear Boolean functions.

5. Balance: if each Boolean vector has the S-box with an equal number of 0’s and 1’s then it is known as balance. This should meet most of the standards set by the NIST. Sometimes, it can be impossible to achieve all criteria to their full potential. Sometimes criteria can be compromised due to their conflicting nature. For example, maximum nonlinearity also conflicts with balance as well as correlation immunity conflicts with high nonlinearity.

The newest criteria is balance, essentially a test of the output compared to a true random number.

Possibly of interest: "Small Scale Variants of the AES (SR) Polynomial System Generator".

Answer 2

The worst case S box would be linear. Making the entire cipher linear and breaking it would be trivial.

Answer 3

Wouldn't the worst S-box just return whatever was input? Then you'd just have the keys to contend with, which a plaintext of all zeros would return.