15
$\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$
0

4 Answers 4

13
$\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 &0 &0 &0 &0 &1 &1 &1 &1\\ 0 &0 &0 &0 &0 &1 &0 &1 &0 &0 &0 &0 &0 &1 &0 &1\\ 0 &0 &0 &0 &0 &0 &1 &1 &0 &0 &0 &0 &0 &0 &1 &1\\ 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &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.

$\endgroup$
5
  • $\begingroup$ can the same be extended to 8-bit sbox? like AES sbox? $\endgroup$
    – crypt
    Sep 29, 2020 at 16:34
  • $\begingroup$ @abraza Yes, it'll work for any sbox $\endgroup$
    – hola
    Sep 30, 2020 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$
    – Fractalice
    Sep 30, 2020 at 17:39
  • $\begingroup$ @Fractalic Where is this sequence $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,\ldots $ from? That is, how do I generate it for any $k$? $\endgroup$
    – E.Nole
    Dec 17, 2020 at 23:58
  • 2
    $\begingroup$ @E.Nole It is derived from the binary expansion of the index. $x_i$ is included if $i$-th bit in the index is set. $\endgroup$
    – Fractalice
    Dec 18, 2020 at 8:10
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.

$\endgroup$
1
  • 1
    $\begingroup$ I think the tag is well written $\endgroup$
    – kodlu
    Oct 1, 2020 at 3:03
5
$\begingroup$

It is possible to use the SageMath, too. With the help of

SBox package

component_function(b): Return a Boolean function corresponding to the component function $b\cdot S(x)$

and from Boolean funcions package

algebraic_normal_form(): Return the sage.rings.polynomial.pbori.BooleanPolynomial corresponding to the algebraic normal form.

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

f0 = S.component_function(1)
f1 = S.component_function(2)
f2 = S.component_function(4)
f3 = S.component_function(8)

print ( "y0 = ", f0.algebraic_normal_form())
print ( "y1 = ", f1.algebraic_normal_form())
print ( "y2 = ", f2.algebraic_normal_form())
print ( "y3 = ", f3.algebraic_normal_form())

Providing the output

\begin{align} y_0 &= x_{0} x_{1} + x_{0} x_{2} x_{3} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{2} x_{3} + x_{1} x_{2} + x_{1}\\ y_1 &= x_{0} x_{2} + x_{0} x_{3} + x_{0} + x_{1} x_{2} + x_{1} x_{3} + x_{2} + 1\\ y_2 &= x_{0} x_{1} x_{3} + x_{0} x_{1} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{2} x_{3} + x_{2} x_{3} + x_{2} + 1\\ y_3 &= x_{0} x_{1} x_{3} + x_{0} x_{1} + x_{0} x_{2} x_{3} + x_{0} x_{3} + x_{3} \end{align}

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.
$\endgroup$
1
$\begingroup$

Doing it via a simple and short Python snippet based on the Moebius answer.

def s_box_to_anf(s_box, n):
  return [gen_anf(sum((1 if x&(1<<i) else 0)<<j for j, x in enumerate(s_box)), n) for i in range(n)]
def gen_anf(num, n):
  M1, M2 = [1], [[1,1], [0,1]] #Moebius transformation matrix
  Mn = M1 if n == 0 else M2
  for k in range(1, n): 
    Mn = [x+x for i, x in enumerate(Mn)] + [[0]*len(x)+x for i, x in enumerate(Mn)]
  return [sum([y&(1 if num&(1<<i) else 0) for i, y in enumerate(reversed(x))])&1 for x in reversed(Mn)]
print(s_box_to_anf([6,4,7,8,0,5,2,10,14,3,13,1,12,15,9,11], 4))

Outputs the ANF form:

[[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]]

We can extend to human readable form:

def anf_to_formula(bits, n):
  return '⊕'.join(('1' if i==0 else ''.join('x'+str(j) for j in range(n) if i&(1<<j))) for i in range(len(bits)) if bits[i])

Which prints out:

['x1⊕x0x1⊕x0x2⊕x1x2⊕x0x3⊕x0x2x3⊕x1x2x3', '1⊕x0⊕x2⊕x0x2⊕x1x2⊕x0x3⊕x1x3', '1⊕x0x1⊕x2⊕x0x2⊕x0x3⊕x0x1x3⊕x2x3⊕x1x2x3', 'x0x1⊕x3⊕x0x3⊕x0x1x3⊕x0x2x3']
$\endgroup$

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.