Example of S-Box truth table in AES

Question

I'm trying to understand some cryptographic properties of the s-box so I can have my own code. Example of balanced properties I read in this document that they say

A boolean function S : $ GF(2^n) $ $ \to $ $ GF(2) $ is called balanced if the output set contains equal number of ones and zeros in the corresponding truth table.

Example 2.2.3 We provide a comparison of balanced and unbalanced functions. Consider two boolean functions, XOR and AND defined as:

                                                           $ S_1 = \oplus : GF(2^n) \to GF(2) $

                                                           $ S_2 = \cdot : GF(2^n) \to GF(2) $

They define following truth table for two variables $x_1$ and $x_2$.

                                 

                                         Table 2.12: Truth Table of XOR, AND functions

Third column has equal number of zeros and ones representing “XOR” function which is balanced while fourth column presents “AND” function which is not balanced.

With the above example, I can easily understand. But for the S-box in AES I still can't imagine how it will be represented. Could you please help me get an example of S-Box truth table in AES?

Answer 1

how is the S-box in AES represented ?

FIPS 197 Figure 7 is the truth table of the AES S-box, stated in hexadecimal for compactness. That's the most usual and arguably most convenient representation. For example, for input $\mathtt{53_h}$, the output is determined by the intersection of the row with index ‘5’ and the column with index ‘3’. This results in the output having value $\mathtt{ed_h}$.

If we wanted a representation more similar to the representation in the question, that is in binary rather than hexadecimal, that would be a table with 8 input columns on the left (thus $2^8=256$ lines to cover all the cases, e.g. by increasing value per big-endian binary), and 8 output columns (obtained by converting to binary per same convention the content of table 7 in reading order) on the right. That could go $$\begin{array}{cccccccc|cccccccc} i_7&i_6&i_5&i_4&i_3&i_2&i_1&i_0&o_7&o_6&o_5&o_4&o_3&o_2&o_1&o_0\\ \hline 0&0&0&0&0&0&0&0&0&1&1&0&0&0&1&1\\ 0&0&0&0&0&0&0&1&0&1&1&1&1&1&0&0\\ 0&0&0&0&0&0&1&0&0&1&1&1&0&1&1&1\\ 0&0&0&0&0&0&1&1&0&1&1&1&1&0&1&1\\ 0&0&0&0&0&1&0&0&1&1&1&1&0&0&1&0\\ .&.&.&.&.&.&.&.&.&.&.&.&.&.&.&.\\ 1&1&1&1&1&1&1&0&1&0&1&1&1&0&1&1\\ 1&1&1&1&1&1&1&1&0&0&0&1&0&1&1&0\\ \end{array}$$

---

How to make the truth table of S-box?

If we want to build table 7 or it's binary equivalent above from scratch (rather than using the values in table 7 given in the standard), we can apply the definition of the S-box as stated in FIPS 197 section 5.1.1. We can merely apply for each of the $2^8=256$ entries:

1. inversion in $\operatorname{GF}(2^8)$ per the stated convention/reduction polynomial, except for input $\mathtt{00_h}$ left unchanged
2. apply a linear transformation where each of 8 output bits $i$ is computed as $b_i\oplus b_{i+4\bmod8}\oplus b_{i+5\bmod8}\oplus b_{i+6\bmod8}\oplus b_{i+7\bmod8}$
3. XOR with the constant $\mathtt{63_h}$

Optimizations are possible, including using that for all $k$, the inverse of $\mathtt{02_h}^k$ is $\mathtt{8d_h}^k$, which allows to compute the inverses simply.