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.


1 Answer 1


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.

  • $\begingroup$ Seems correct to me, thank you very much for your answer and for all the details, it's so much clearer now! $\endgroup$ Commented Mar 14, 2018 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
    Commented Mar 15, 2018 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$ Commented Mar 16, 2018 at 8:30

Your Answer

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

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