For simplicity, I’m skipping some of the details here… but the main criteria of a good s-box are:
- It should have balanced component functions,
- The non-linearity of its component functions should be high,
- The non-zero linear combinations of its component functions should be balanced and
- It should satisfy SAC (strict avalanche criterion),
- It should have a high algebraic degree.
S-Boxes Are Not Random
You have to realize that the most important thing an s-box adds to a block cipher is “non-linearity“. And you can trust in the fact that the chances that you’ll manage to create a good s-box randomly by using your current criteria are very minimal… very, very minimal!
See, an s-box is not just a randomly permuted set of values (may it be bits, words, integers, or whatever) with some equalized bits to make it look somewhat balanced. Creating s-boxes can be seen as a mathematical design step. It involves working with and checking on things like boolean functions, truth tables, hamming weights, the distance between the function and the set of all affine functions, etc.
In short: an s-box is not something you quickly wrap up in an afternoon, and it’s certainly not something you can create “randomly” or with the specifics you’ve defined. The reason is simple: your whole block cipher depends on the non-linearity and other characteristics of that s-box. Such s-boxes are rare, while the rest of potential combinations is either linear or completely distinguishable from randomness. As you might have read here and there: if an adversary can pinpoint one or more distinguishers, the adversary gains knowledge that can potentially be used to successfully break a way into your ciphertext. Cipher algorithms using s-boxes rely on s-box non-linearity to be secure. If you replace the s-box(es) without knowing what you’re doing, you’re risking to break a once perfectly secure cipher by removing its heart.
Please, do not simply create a random s-box that fits your listed criteria and throw it into some cipher algorithm. The chance that you introduce a wide-open door for attackers is too big to even consider it.
To be sure you get the right idea about what an s-box is and how s-boxes are created, I would like to point you to the following papers:
Personally, I’ld like to advise you to start reading “The Design Of S-Boxes” by Cheung, as that will most probably make it easier for you to grasp the whole concept… while getting a clear picture on what you might already know and what you might still need to do some research on. After all, there are dozens of papers out there that handle s-box design. Depending on your personal knowledge level, you’ll surely find yourself reading additional papers that handle certain specifics of s-box design and analysis.
Get The Picture
If you want to dive in head-first and quickly see what I’m talking about, visit YouTube at “Mod-01 Lec-17 Overview on S-Box Design Principles” where Prof. Mukhopadhyay (Department of Computer Science and Engineering, IIT Kharagpur) roughly explains it. Even if you can’t follow him, it’ll surely give you a good, first impression why s-box design is a bit more complicated than randomly shuffling an array.