SAGE can't process component functions for huge csv file - SBOX Look up table

[smitadas95]

Hi. Sage is unable to generate algebraic normal form(ANF) results for a huge csv file containing S-Box LUT list and it kills the terminal. S-Box size is 5X5 bit. How to overcome this issue?

CC: @slel

Component: cryptography

Keywords: pbori

Issue created by migration from https://trac.sagemath.org/ticket/34513

[sheerluck]

comment:1

Probably you are out of memory.

Show us your code and csv file or debug it using python -m pudb your_script.sage.py

[smitadas95]

comment:2

There's enough memory available.
I am reading each line from the csv file which contains 5X5 bit s-box LUT. There are around 1.2 Crores of such s-box LUT's in each line in the csv file. But the code kills the terminal after printing maximum of around 500 LUT line count followed by system shut down!
However, I am able to print Nonlinearity of each LUT for entire csv file..

Each line of the csv file contains s-box LUT shown below:

0 8 4 12 2 10 6 15 1 9 5 13 3 11 23 14 16 24 20 30 18 26 22 28 17 29 21 25 27 19 7 31

The code to print algebraic normal form (ANF) equation is given below:

from sage.crypto.sbox import SBox
import csv

count=0

with open('filepath/filename.csv') as f:
for line in f:

	count+=1
	
	line1=line.replace('"','')
	
    line2=line1.replace("\n","")
	
    line3=line2.replace(' ',',')
	
    int_list= list(map(int, line3.split(',')))
	
    S=SBox(int_list)
	
    print("Line{}".format(count))
    
    print(S.component_function([1]).algebraic_normal_form())

[sheerluck]

comment:3

well, I got x0*x1*x2*x4 + x0*x1*x2 + x3 for your line, so attach whole csv file here. There's a bad line in that csv file, we need to find it.

[smitadas95]

comment:4

https://drive.google.com/file/d/10ZZMhm9ygPUvpqfP5ubtYX4c1SFw26UA/view?usp=sharing

Please find the link attached for the huge csv file s-box LUT list.

[sheerluck]

comment:5

Problem was with memory, here:

https://github.com/sagemath/sage-prod/blob/develop/src/sage/crypto/boolean_function.pyx#L488-L509

R = BooleanPolynomialRing(self._nvariables,"x") allocates a lof of memory.

I thought what if we stop recreating BooleanPolynomialRing every time we call algebraic_normal_form, like this:

--- a/sage/crypto/boolean_function.pyx
+++ b/sage/crypto/boolean_function.pyx
@@ -485,7 +485,7 @@
         return res
 
 
-    def algebraic_normal_form(self):
+    def algebraic_normal_form(self, R=None):
         """
         Return the :class:`sage.rings.polynomial.pbori.BooleanPolynomial`
         corresponding to the algebraic normal form.
@@ -505,8 +505,9 @@
         bitset_init(anf, <mp_bitcnt_t> (1<<self._nvariables))
         bitset_copy(anf, self._truth_table)
         reed_muller(anf.bits, ZZ(anf.limbs).exact_log(2))
-        from sage.rings.polynomial.pbori.pbori import BooleanPolynomialRing
-        R = BooleanPolynomialRing(self._nvariables,"x")
+        if R is None:
+            from sage.rings.polynomial.pbori.pbori import BooleanPolynomialRing
+            R = BooleanPolynomialRing(self._nvariables,"x")
         G = R.gens()
         P = R(0)
 

After rebuilding sage I use this code:

sage: import numpy as np
sage: from sage.crypto.sbox import SBox
sage: from sage.rings.polynomial.pbori.pbori import BooleanPolynomialRing
sage: count = 0
sage: rings = {}
sage: with open("/tmp/sboxdataremote.csv") as f:
....:     for line in f:
....:         count += 1
....:         int_list = list(arr := np.fromstring(line, dtype=int, sep=" "))
....:         print(f"{count:>10} {arr}")
....:         S = SBox(int_list)
....:         cf = S.component_function([1])
....:         nv = cf.nvariables()
....:         R = rings.get(nv, None)
....:         if R is None:
....:             R = rings[nv] = BooleanPolynomialRing(nv, "x")
....:         anf = cf.algebraic_normal_form(R)
....:         print(f"{count:>10} {anf}")

Since nv = cf.nvariables() is 5, there is one BooleanPolynomialRing created, no memory is wasted and we can get millions of anf = cf.algebraic_normal_form(R) without fail:

   1000446 [ 0 14  7 12 19 22  6 18 25 26 11 29  3 15  9  4 28 24 13  5 21 27 30  8 17 10 23 16 20  1  2 31]
   1000446 x0*x1*x4 + x0*x1 + x0*x2*x4 + x0*x2 + x0*x3 + x1*x3 + x1 + x2*x3*x4 + x2*x3 + x2 + x3
   1000447 [ 0 14  7 12 19 22  6 20 25 26 11 29  3 15 10  1 28 24 13  9 21 27 30  2 17 18 23  4  5  8 16 31]
   1000447 x0*x1*x4 + x0*x1 + x0*x2*x4 + x0*x2 + x0*x3 + x1*x2*x3 + x1*x3 + x1 + x2*x3 + x2 + x3

[sheerluck]

comment:8

or even better to save R = BooleanPolynomialRing(self._nvariables,"x") to self._rings

[smitadas95]

comment:9

Here also, we call algebraic_normal_form() everytime. Even after using the above modified code, it kills the terminal after printing around 700 lines.

[sheerluck]

comment:10

It is not enough to patch sage/crypto/boolean_function.pyx, sage should be properly rebuilt so sage/crypto/boolean_function.cpython-310-x86_64-linux-gnu.so would be updated. And it must be algebraic_normal_form(R) not algebraic_normal_form()

[sheerluck]

comment:11

--- a/src/sage/crypto/boolean_function.pyx
+++ b/src/sage/crypto/boolean_function.pyx
@@ -485,7 +485,7 @@
         return res
 
 
-    def algebraic_normal_form(self):
+    def algebraic_normal_form(self, R=None):
         """
         Return the :class:`sage.rings.polynomial.pbori.BooleanPolynomial`
         corresponding to the algebraic normal form.
@@ -506,7 +506,11 @@
         bitset_copy(anf, self._truth_table)
         reed_muller(anf.bits, ZZ(anf.limbs).exact_log(2))
         from sage.rings.polynomial.pbori.pbori import BooleanPolynomialRing
-        R = BooleanPolynomialRing(self._nvariables,"x")
+        if R is None:
+            R = BooleanPolynomialRing(self._nvariables,"x")
+        else:
+            assert isinstance(R, BooleanPolynomialRing)
+            assert R.ngens() == self._nvariables
         G = R.gens()
         P = R(0)

[smitadas95]

Attachment: Screenshot from 2022-09-20 13-05-56.png

Attachment: Screenshot from 2022-09-20 13-01-37.png

[smitadas95]

Attachment: Screenshot from 2022-09-20 13-04-58.png