0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "reverse block"? Is it putting the bits into the opposite order? $\endgroup$
    – poncho
    Oct 30 '20 at 14:08
  • $\begingroup$ Also, it is not specified the width of the S-box, and if there's one repeated, or several different ones. That makes it difficult to figure out the construction. Most importantly, that construction has no key (as pointed in that answer), which makes common security objectives inapplicable. $\endgroup$
    – fgrieu
    Oct 30 '20 at 14:46
  • $\begingroup$ Poncho - yes, that's what I mean. For example 1011 go into 1101. $\endgroup$
    – Tom
    Oct 30 '20 at 20:49
  • $\begingroup$ Frieu - these s-boxes are just some functions. Similar like here (these simpler kind of cipher got the same issues): crypto.stackexchange.com/questions/84420/lehmer-random-number-generator-cipher-looking-for-differentials/ $\endgroup$
    – Tom
    Oct 30 '20 at 21:07
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Ok, so maybe it will be better to call it encryption functions. They just take input and a key and gives output with such properties as I described. I don't know if it change and clarify the problem, but I will change it. $\endgroup$
    – Tom
    Oct 30 '20 at 21:14
  • $\begingroup$ @Tom can you please revert your question to the original version and post a new question instead, since it is a completely different question comparing to that one already answered, editing the question was done after a substantial reply. Your initial question was about the sboxes, while the new question is about keys. The sboxes and the keys are completely different matter. After your substantial edits, my reply becomes irrelevant, although, it covers the topic of sboxes thoroughly. $\endgroup$ Oct 30 '20 at 21:51
  • 1
    $\begingroup$ Maxim - ok, I will do it. $\endgroup$
    – Tom
    Oct 31 '20 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.