1
$\begingroup$

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$.

                                 enter image description here

                                         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?

$\endgroup$
2
  • $\begingroup$ The AES S-box table is represented in FIPS 197, figure 7 on bottom of page marked 6, with explanation above. If anything is unclear, what? $\endgroup$
    – fgrieu
    May 8, 2023 at 8:52
  • $\begingroup$ @fgrieu I know s-box is a mapping of boolean function. So how to make the truth table of s-box? $\endgroup$
    – Cat Dragon
    May 8, 2023 at 8:59

1 Answer 1

0
$\begingroup$

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}$.

FIPS 197 Figure 7

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer that "8 input columns on the left and 8 output columns". I seem to have understood what that means. $\endgroup$
    – Cat Dragon
    May 8, 2023 at 10:45

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.