3
$\begingroup$

i read about linear cryptanalysis and about S-Box that there is not any ideal S-Box (ideal S-Box is a random S-Box in another words S-Box that bias of input and output bits is zero) then i read about implementation of S-Box in this post and understand that S-Box is implementing with Lookup tables,then read this post (e-sushi's answer) about non-linearity and randomness aspects of S-Box:

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!

but i don't understand that why is not there any random(ideal) S-Box? why can't lookup tables implement a random S-box? what is restriction(limitation) for it?

Improve this question
$\endgroup$
1
  • $\begingroup$ I thought the whole point of DES's choice of S-Box was that "a random S-Box" is unlikely to have zero "bias of input and output bits". ​ ​ $\endgroup$
    – user991
    Mar 5, 2016 at 21:24

1 Answer 1

Reset to default
3
$\begingroup$

It is important to understand that although a very large random function will only have linear biases with very low probability, this is simply not true of small random functions. If you choose a small random function, then it is unlikely that you will get one that is suitable for block cipher constructions. In addition, it is not enough to construct an S-box with low linear biases; one must also take into account differential cryptanalysis, and more.

Having said all of the above, this does raise an interesting question. Can we even define an ideal S-box? This doesn't necessarily mean we could find one; for example, the AES S-box has an 8-bit input and 8-bit output. This means that there are $2^{128}$ possible functions of this type, and this cannot be enumerated. Nevertheless, I would be interested to know if an "ideal" construction even exists, in terms of our best cryptanalysis knowledge.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I am a layman and hence not sure at all whether the following paper could eventually have some relevance in the present context or not: K. Nyberg, Perfect nonlinear S-boxes, EUROCRYPT'91, pp 378-386. $\endgroup$
    – Mok-Kong Shen
    Mar 6, 2016 at 13:14
  • $\begingroup$ Indeed, it seems like this is very relevant. By the abstract, they prove that to construct such an S-box the number of input bits must be at least twice the number of output-bits. This means that it can be relevant for a Feistel construction but not for an SPN construction. In addition, note that this just covers linear cryptanalysis. There is also differential cryptanalysis and other techniques that must be taken into account. $\endgroup$
    – Yehuda Lindell
    Mar 6, 2016 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.