12
$\begingroup$

Given an SBox, how can I generate its component equations (in ANF)?

For example, let's say I have this SBox:

6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11

Then, the equations are:

$y_0 = x_1 \oplus x_0x_1 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_0x_2x_3 \oplus x_1x_2x_3$

$y_1 = 1 \oplus x_0 \oplus x_2 \oplus x_0x_2 \oplus x_1x_2 \oplus x_0x_3 \oplus x_1x_3$

$y_2 = 1 \oplus x_0x_1 \oplus x_2 \oplus x_0x_2 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_2x_3 \oplus x_1x_2x_3$

$y_3 = x_0x_1 \oplus x_3 \oplus x_0x_3 \oplus x_0x_1x_3 \oplus x_0x_2x_3$

The same question is asked in cs.stackexchange

$\endgroup$
10
$\begingroup$

From TRUTH TABLE to ANF

First write [6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11] in that way: the columns of matrix are those numbers in $\mathbb{F_2^4}$. $$ \begin{bmatrix} 0&0&1&0&0&1&0&0&0&1&1&1&0&1&1&1\\ 1&0&1&0&0&0&1&1&1&1&0&0&0&1&0&1\\ 1&1&1&0&0&1&0&0&1&0&1&0&1&1&0&0\\ 0&0&0&1&0&0&0&1&1&0&1&0&1&1&1&1 \end{bmatrix} $$ Then multiply it with Moebius transformation matrix :

$$ M_1 = \begin{bmatrix} 1 \end{bmatrix}, M_2 = \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix}, \cdots, M_{2^k} = M_2 \otimes M_{2^{k-1}} = \begin{bmatrix} M_{2^{k-1}}&M_{2^{k-1}}\\ 0&M_{2^{k-1}} \end{bmatrix}. $$ So for $k=4$, the matrix is: $$ \begin{bmatrix} 1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 \\ 0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\\ 0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &1 &1 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &1 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &1 \end{bmatrix} $$ Then you have this matrix: $$ \begin{bmatrix} 0&0&1&1&0&1&1&0&0&1&0&0&0&1&1&0\\ 1&1&0&0&1&1&1&0&0&1&1&0&0&0&0&0\\ 1&0&0&1&1&1&0&0&0&1&0&1&1&0&1&0\\ 0&0&0&1&0&0&0&0&1&1&0&1&0&1&0&0 \end{bmatrix} $$ Each row gives the coordinate function $S_1,S_2,S_3$and $S_4$ resp. The entries of each row are the coefficients of $1, x_0, x_1, x_0x_1, x_2, x_0x_2, x_1x_2, x_0x_1x_2, x_3, x_0x_3, x_1x_3, x_0x_1x_3, x_2x_3, x_0x_2x_3, x_1x_2x_3, x_0x_1x_2x_3$.

From ANF to TRUTH TABLE (TT)

Exactly the inverse of operations. Note that $M_{2^k}^{-1}=M_{2^k}$ for any $k$.


i.e. [TT] * $[M]$ = [ANF] and [TT] = [ANF] * $[M]$.


Note: The arithmetics are taken modulo 2.

| improve this answer | |
$\endgroup$
  • $\begingroup$ can the same be extended to 8-bit sbox? like AES sbox? $\endgroup$ – abraza Sep 29 at 16:34
  • $\begingroup$ @abraza Yes, it'll work for any sbox $\endgroup$ – hola Sep 30 at 1:18
  • 1
    $\begingroup$ I would also note that applying $M_2$ recursively leads to complexity $k2^k$. That is, xor the right half to the left half, then recurse to each half. $\endgroup$ – Fractalic Sep 30 at 17:39
13
$\begingroup$

This is useful to know in general.

Given the Sbox map, generate the truth tables for the bits of the map. From the truth tables, obtain the algebraic normal form, via the Mobius transform.

So, given an $n-$bit truth table, say $$T=[f(x): x \in \mathbb{F}_2^n]$$

where $$x=(x_1,\ldots,x_n)$$ ranges over the vector space $\mathbb{F}_2^n$ in standard order, the function has an anf representation given by $$ f(x)=\sum_{y \in \mathbb{F}_2^n} a_y \prod_{1\leq i\leq n~:~y_i=1} x_i $$ which means the variable $x_i$ is included in the monomial product corresponding to the coefficient $a_y$ if and only if $i$ is in the support of the vector $y.$

So if we had $y=(y_1,y_2,y_3,y_4)=(1,0,1,0),$ for $n=4,$ the coefficient $a_y$ multiplies the monomial $x_1 x_3$.

The transform computes the coefficients $a_y$ by the sum $$ a_y=\sum_{x\preccurlyeq y} f(x) ~(mod~2), $$ where $x \preccurlyeq y$ means the support of $x$ is a subset of the support of $y.$

The complexity is $N \log N$ where $N=2^n,$ so this is a fast transform.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think the tag is well written $\endgroup$ – kodlu Oct 1 at 3:03
4
$\begingroup$

It is possible to use the SageMath, too.

from sage.crypto.sbox import SBox

S = SBox(6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11);

f1 = S.component_function(1)
f2 = S.component_function(2)
f3 = S.component_function(3)
f4 = S.component_function(4)

print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())
print ( "y4 = ", f4.algebraic_normal_form())

Providing the output

y1 =  x0*x1 + x0*x2*x3 + x0*x2 + x0*x3 + x1*x2*x3 + x1*x2 + x1
y2 =  x0*x2 + x0*x3 + x0 + x1*x2 + x1*x3 + x2 + 1
y3 =  x0*x1 + x0*x2*x3 + x0 + x1*x2*x3 + x1*x3 + x1 + x2 + 1
y4 =  x0*x1*x3 + x0*x1 + x0*x2 + x0*x3 + x1*x2*x3 + x2*x3 + x2 + 1

The Sbox package of Sage has lots of other tools, too. Some are;

  • autocorrelation table
  • boomerang connectivity table (BCT)
  • Conjunctive Normal Form (CNF)
  • fixed points
  • has a linear structure
  • Linearity
  • Non-Linearity
  • inverse
  • almost perfect nonlinear (APN) function.
  • Balanced
  • Bent
  • Involution
  • Permutation
  • Max Degree
  • Min Degree
  • polynomials satisfying the S-box.
| improve this answer | |
$\endgroup$
2
$\begingroup$

There is a simple way based on repeated linear interpolation, known as the Shannon-expansion.

With this you can extract the ANF expression from any black-box map function (for example, an S-Box) using on the order of $2^n$ evaluations for an $n$-bit Boolean function. It's slow but remarkably simple. I will demonstrate using $2$-bit function.

$$f(x_0,x_1)$$

can be expanded in the first bit

$$\small{f(x_0,x_1) = f(0,x_1)(1-x_0) \; + \; f(1,x_1){x_0}}$$

and then again in the second bit

$$\small{f(x_0,x_1) = f(0,0)(1-x_0)(1-x_1) \; + \; f(0,1)(1-x_0)x_1 \; + \; f(1,0){x_0}(1-x_1) \; + \; f(1,1){x_0}{x_1}}$$

Repeating this with larger functions, the pattern becomes clear. The $k$th term in this expression simply multiplies $\small{f(x)}$ with either a $x_i$ or $\small(1-x_i)$, depending on the setting of the bit in the input to the map function.

So for a larger Boolean function, the first term would be

$$\small{f(0,0,0,0,\ldots,0)(1-x_0)(1-x_1)(1-x_2)(1-x_3)\ldots(1-x_n)}$$

and the final term would be

$$\small{f(1,1,1,1,\ldots,1)x_0 x_1 x_2 x_3\ldots x_n}$$

The ANF can then be derived from this expression by multiplying out the parenthesis. This is laborious by hand, but a small amount of code in a computer program.

Here is the idea implemented in C++

#include <iostream>
#include <vector>

/* black-box map function to extract ANF */
int map(int x) {
  int sbox[] = {6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11};
  return sbox[x % 16];
}

int num_input_bits = 4; /* number of map input bits to consider */
int num_output_bits = 4; /* number of map output bits to consider */

/* (1-x_0)(1-x1)x_2 = x_2*(1 + x_0 + x_1 + x_0*x_1) */

int main() {
  /* step 1) calculate ANF of the map function */
  int num_input_states = 1 << num_input_bits;
  for (int i = 0; i < num_output_bits; ++i) {
    std::vector<int> anf(num_input_states); /* accumulate ANF here */
    for (int j = 0; j < num_input_states; ++j) {
      int bit = (map(j) >> i) & 1; /* extract map output bit */
      if (bit == 1) {
        for (int k = 0; k < num_input_states; ++k) { /* "broadcast" result to ANF terms */
          if ((j & k) == j) { /* does this bit contribute to this ANF term? */
            anf[k] = (anf[k] + 1) % 2;
          }
        }
      }
    }
    /* step 2) print the ANF expression */
    std::cout << "y_" << i << " = ";
    int term_count = 0;
    for (int j = 0; j < anf.size(); ++j) {
      if (anf[j]) {
        std::cout << (term_count++ != 0 ? " + " : "");
        size_t factor_count = 0;
        for (int k = 0; k < num_input_bits; ++k) {
          if ((j >> k) & 1) {
            std::cout << (factor_count++ != 0 ? "*" : "");
            std::cout << "x_" << k;
          }
        }
        if (factor_count == 0) {
          std::cout << "1"; /* empty product */
        }
      }
    }
    if (term_count == 0) {
      std::cout << "0"; /* empty sum */
    }
    std::cout << std::endl;
  }
  return 0;
}

Which outputs the ANF representation of your S-Box:

y_0 = x_1 + x_0*x_1 + x_0*x_2 + x_1*x_2 + x_0*x_3 + x_0*x_2*x_3 + x_1*x_2*x_3
y_1 = 1 + x_0 + x_2 + x_0*x_2 + x_1*x_2 + x_0*x_3 + x_1*x_3
y_2 = 1 + x_0*x_1 + x_2 + x_0*x_2 + x_0*x_3 + x_0*x_1*x_3 + x_2*x_3 + x_1*x_2*x_3
y_3 = x_0*x_1 + x_3 + x_0*x_3 + x_0*x_1*x_3 + x_0*x_2*x_3
| improve this answer | |
$\endgroup$
  • $\begingroup$ That is great. It explains why the Mobious transform works. $\endgroup$ – hola Oct 2 at 2:47
  • $\begingroup$ I think this answer will be much great if you bring the Shannon-expansion and Mobius transform relation. $\endgroup$ – kelalaka Oct 2 at 8:38
  • $\begingroup$ The last two equations of $f$ confusingly changed notation: $f(1,\ldots,1)$ somehow now means the coefficient of $x_0x_1\ldots,x_{n-1}$ instead of the value fo $f$ on the input $(1,1,\ldots,1)$. Maybe simply remove the = sign. $\endgroup$ – Fractalic Oct 5 at 12:03
  • $\begingroup$ Thanks & Fixed @Fractalic $\endgroup$ – conchild Oct 5 at 17:49

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.