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.
Yet, it’s hardly possible to achieve all those goals 100%. Nevertheless, there is somewhat of a consensus what properties an “Ideal S-Box Properties” would posess…
Ideal S-Box Properties
- All linear combinations of s-box columns are bent.
- All entries in the s-box XOR table are 0 or 2.
- The s-box satisfies MOSAC (aka „Maximum order SAC“).
- The s-box satisfies MOBIC (aka “Maximum order BIC”).
- The set of weights of rows has a binomial distribution with mean $m / 2$.
- The set of weights of all pairs of rows has a binomial distribution with mean $m / 2$.
- The columns each have Hamming weight $2^(n− 1)$.
At least, that would be the expected properties in an ideal world.
Practically, making sure s-boxes satisfy all desired properties is hard already and working towards satisfying all “ideal” properties is definitely a goal, but chances are you might not reach all “ideal” goals to your fullest satisfaction. Especially when cryptography isn’t your day job where you happen to have plenty of R&D resources to back your efforts.
I guess this also explains to you why they call it “designing” s-boxes. Fact is, you can’t just throw some shuffled byte-values into a 2D array and expect s-box creation to be completed. An s-box is a part of the cipher you create it for. An s-box is meant to add security. Depending on the individual cipher algorithm design, a low-quality s-box can break the neck of each and every person that might use the cipher. Therefore, it’s utterly important that you don’t mess things up along the lines of “oh, that 2D array of values looks random enough to me”.
Make No Mistake – 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 of what you might already know and what you 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.