0
$\begingroup$

How many possible 16 bit S-boxes exist? (AES uses 8 bit substitution boxes) I first taught of calculating 128(keysize in bits)/8(bits) =16, but I believe it's wrong.

|improve this question
$\endgroup$
2
$\begingroup$

An s-box is a bijective function $f: \{0,1\}^b\rightarrow\{0,1\}^b$. This reduces the question to "how many of those $f$ exist".

To see this easily, imagine domain and image of this function as two boxes with $2^b$ elements. How many different sets of arrows can you imagine between those two sets?

For the first arrow, you have $2^b$ choices. For the second arrow, you have $2^b -1$ choices. For the third, $2^b-2$, and so forth to the last arrow, where there's one choice left.

Multiplying those together, you would get $2^b(2^b-1)(2^b-2)\dots 1=2^b!$ possible s-boxes, so in your 16-bit case that makes $2^{16}!$ possibilities.

To put this more mathematically, an s-box is a permutation of $2^b$ elements, and there are $2^b!$ such permutations.

|improve this answer
$\endgroup$
  • $\begingroup$ Seems correct to me, thank you very much for your answer and for all the details, it's so much clearer now! $\endgroup$ – Esma Tuzovic Mar 14 '18 at 10:05
  • 1
    $\begingroup$ Just a comment, since $2^b$ factorial is much larger than $2^b$, this also demonstrates that a $b-$bit key for a $b\times b$ cipher [after alll a block cipher has to be invertible for each key, thus be a permutation] can only sample a small subset of possible permutations. One can use Stirling's approximation to approximate the factorial for clarity. $\endgroup$ – kodlu Mar 15 '18 at 23:22
  • $\begingroup$ Yes. It always bothers me that we use a keyspace of $2^b$ elements, where there are $2^b!$ permutation functions for a block cipher... $\endgroup$ – Ruben De Smet Mar 16 '18 at 8:30

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.