Are the weaknesses of my s-boxes attackable?

Question

I got specific problem with my s-boxes in $128$-bit block cipher. One round of encryption is like that:

input - sbox - reverse block - $sbox^{-1}$ - output

Every s-box got specific $128$-bit key. $sbox^{-1}$ means that we are looking for such input to s-box that will give us such reversed block.

First problem is with numbers divisible by $2$. Every input block in s-box of the form 000...0001... also will give us the same first zeros and one. Fore example:

000001...0111101...

go into:

000001...1111001...

All the rest of the block depends on key and there is no know way to guess it without the key. It also means that block 000...0001 always gives the same block 000...0001 and block of only zeros goes into the same block. It also means that every block with $1$ as the first bit will also go into block with $1$ as the first bit. I think it can be solve, by xoring with some key before every round, let's ignore that problem for now.

Second problem is that every $input + 2^{n}\cdot l$ will give output block with the same first $n$ bits in s-box.

Can you find a way to attack it? Main idea is to avoid problems by reversing blocks and then looking for such input to s-box, that will give us such reversed block - it destroys patterns which we have in that s-boxes. Let's say we want to encrypt block 000...0001. We know what block will gives us first s-box (exactly the same), but without the key of the second s-box we can't tell which number is giving 1000...000 block in that second s-box.

Answer 1

The strengths and weaknesses of an S-Box can be determined by analysis of the commonly agreed within the cryptanalytic community S-Box properties.

The following list of properties have been described in a 2014 paper "Study of S-box properties in block cipher" by Kamsiah Mohamed and colleagues: Robustness, Balancing, Strict Avalance Criterion, Nonlinearity, Differential Uniformity, Linear Approximation, Algebraic Complexity, Fp/OFp, Bit Independence criterion. There may be other important properties as well.

Practical aspects of strong S-Box generation, considering these properties, have been described by Waqar Ahmad Khan and colleagues in a 2011 article "Construction of Cryptographically Strong 8x8 S-boxes".

A toolbox for S-Box analysis have been described by Stjepan Picek and colleagues in a 2016 paper.

Your question was whether we can find a way to attack the encryption scheme based on your S-Boxes, but from the description that you gave, on how you use them, they are not actually S-Boxes, but the keys. In cryptography, the S-box (substitution box) is the basic component of the symmetric key algorithm that performs replacement. In block ciphers, S-Boxes are usually applied to conceal the relationship between the key and the ciphertext to satisfy the Shannon's property of confusion. This property refers to making the relationship between ciphertext and symmetric key as complicated and involved as possible. S-boxes need to be strong, in terms of the properties above mentioned, but they are not necessarily need to be secret. To the contrary, in a Russian GOST 28147-89 (RFC 5830), developed in the 1970s, S-Boxes are secret, and are called "long-term" keys, in addition to "session" keys, so both "long-term" and "session" keys comprise the key. This approach has its drawbacks because the "long-term" key, i.e. the S-Box should be thoroughly analyzed to comply to the properties above mentioned. What you call "S-Box" in your algorithm is actually a key. If what you call "S-Box" is actually a one-time pad, i.e. a truly random key used only once, then it is a completely different matter. The one-time pad was first described by Frank Miller in 1882 and was reinvented in 1917 by Gilbert Vernam who in 1919 was granted an US Patent 1,310,719 for the encrypted XOR operation of one-time pads. So, if what you call "S-Boxes" fit the definition of one-time pads, than you've got the perfect secrecy. But this is unlikely that you meant that. Thus, I would recommend to analyze your S-Boxes according to the properties above described.