sbox linear approximation matrix scaling

[pfasante]

as discussed here https://groups.google.com/forum/#!topic/sage-devel/l8N2wQl9WsY I would like to introduce an (optional) argument to the linear_approximation_matrix method on S-boxes, that allows to scale the output to the four typical use cases: biases, correlations, absolute biases, and fourier coefficients.

The current implementation returns absolute biases, which would thus be the default value to the scale argument.

Component: cryptography

Keywords: sbox, lat, linear approximation matrix

Author: Friedrich Wiemer

Branch/Commit: dbc821d

Reviewer: Rusydi H. Makarim

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

[pfasante]

Branch: u/asante/sbox_linear_approximation_matrix_scaling

[pfasante]

Commit: 1f2942b

[pfasante]

New commits:

1f2942b

add scale argument to linear approximation matrix method

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1f2942b to ec8284c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

ec8284c

fix docstring enumeration

[rusydi]

comment:5

Hi Friedrich,

You can remove "B" and the nested for-loop. The list "L" can be constructed as

L = [ self.component_function(i).walsh_hadamard_transform() for i in range(ncols) ]

Regards, Rusydi

[rusydi]

comment:6

Running make doc-html produces the following error in my machine

[dochtml] [cryptogra] loading pickled environment... not yet created
[dochtml] [cryptogra] building [mo]: targets for 0 po files that are out of date
[dochtml] [cryptogra] building [inventory]: targets for 19 source files that are out of date
[dochtml] [cryptogra] updating environment: 19 added, 0 changed, 0 removed
[dochtml] [cryptogra] reading sources... [  5%] index
[dochtml] [cryptogra] reading sources... [ 10%] sage/crypto/block_cipher/miniaes
[dochtml] [cryptogra] reading sources... [ 15%] sage/crypto/block_cipher/sdes
[dochtml] [cryptogra] reading sources... [ 21%] sage/crypto/boolean_function
[dochtml] [cryptogra] reading sources... [ 26%] sage/crypto/cipher
[dochtml] [cryptogra] reading sources... [ 31%] sage/crypto/classical
[dochtml] [cryptogra] reading sources... [ 36%] sage/crypto/classical_cipher
[dochtml] [cryptogra] reading sources... [ 42%] sage/crypto/cryptosystem
[dochtml] [cryptogra] reading sources... [ 47%] sage/crypto/lattice
[dochtml] [cryptogra] reading sources... [ 52%] sage/crypto/lfsr
[dochtml] [cryptogra] reading sources... [ 57%] sage/crypto/lwe
[dochtml] [cryptogra] reading sources... [ 63%] sage/crypto/mq/mpolynomialsystemgenerator
[dochtml] [cryptogra] reading sources... [ 68%] sage/crypto/mq/rijndael_gf
[dochtml] [cryptogra] reading sources... [ 73%] sage/crypto/mq/sr
[dochtml] [cryptogra] reading sources... [ 78%] sage/crypto/public_key/blum_goldwasser
[dochtml] [cryptogra] reading sources... [ 84%] sage/crypto/sbox
[dochtml] [cryptogra] reading sources... [ 89%] sage/crypto/stream
[dochtml] [cryptogra] reading sources... [ 94%] sage/crypto/stream_cipher
[dochtml] [cryptogra] reading sources... [100%] sage/crypto/util
[dochtml] [cryptogra] /home/makarim/sage/local/lib/python2.7/site-packages/sage/crypto/sbox.py:docstring of sage.crypto.sbox.SBox.linear_approximation_matrix:7: WARNING: Unexpected indentation.
[dochtml] Error building the documentation.
[dochtml] Traceback (most recent call last):
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main
[dochtml]     "__main__", fname, loader, pkg_name)
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/runpy.py", line 72, in _run_code
[dochtml]     exec code in run_globals
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml]     main()
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1675, in main
[dochtml]     builder()
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 310, in _wrapper
[dochtml]     getattr(get_builder(document), 'inventory')(*args, **kwds)
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 505, in _wrapper
[dochtml]     build_many(build_ref_doc, L)
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 246, in build_many
[dochtml]     ret = x.get(99999)
[dochtml]   File "/home/makarim/sage/local/lib/python2.7/multiprocessing/pool.py", line 572, in get
[dochtml]     raise self._value
[dochtml] OSError: [cryptogra] /home/makarim/sage/local/lib/python2.7/site-packages/sage/crypto/sbox.py:docstring of sage.crypto.sbox.SBox.linear_approximation_matrix:7: WARNING: Unexpected indentation.
[dochtml] 
Makefile:1002: recipe for target 'doc-html' failed
make[1]: *** [doc-html] Error 1
make[1]: Leaving directory '/home/makarim/sage/build/make'

real    4m16.422s
user    12m7.154s
sys 0m24.788s
***************************************************************

[rusydi]

Reviewer: Rusydi H. Makarim

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

abd73ad	simplify linear approximation matrix computation
dd927aa	fix doc-html build error

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ec8284c to dd927aa

[pfasante]

comment:9

Good catch with the nested for loops, now its much more clearer I think.

I fixed the doc build error, but did not find a syntactic correct way to break the now-too-long lines:

    There are three typical notations for this probability used in
    the literature:

    - `Pr[<\\alpha, x> = <\\beta, S(x)>] = 1/2 + e(\\alpha, \\beta)`, where `e(\\alpha, \\beta)` is called the bias,
    - `2\cdot Pr[<\\alpha, x> = <\\beta, S(x)>] = 1 + c(\\alpha, \\beta)`, where `c(\\alpha, \\beta) = 2\cdot e(\\alpha, \\beta)` is the correlation, and
    - `2^{(n+1)}\cdot Pr[<\\alpha, x> = <\\beta, S(x)>] = 2^n + \hat{S}(\\alpha, \\beta)`, where `\hat{S}(\\alpha, \\beta)` is the Fourier coefficient of S.

How do I correctly break these last three lines?

[rusydi]

comment:10

Replying to @pfasante:

Good catch with the nested for loops, now its much more clearer I think.

I fixed the doc build error, but did not find a syntactic correct way to break the now-too-long lines:

    There are three typical notations for this probability used in
    the literature:

    - `Pr[<\\alpha, x> = <\\beta, S(x)>] = 1/2 + e(\\alpha, \\beta)`, where `e(\\alpha, \\beta)` is called the bias,
    - `2\cdot Pr[<\\alpha, x> = <\\beta, S(x)>] = 1 + c(\\alpha, \\beta)`, where `c(\\alpha, \\beta) = 2\cdot e(\\alpha, \\beta)` is the correlation, and
    - `2^{(n+1)}\cdot Pr[<\\alpha, x> = <\\beta, S(x)>] = 2^n + \hat{S}(\\alpha, \\beta)`, where `\hat{S}(\\alpha, \\beta)` is the Fourier coefficient of S.

How do I correctly break these last three lines?

You can break it like this :

      There are three typical notations for this probability used in
      the literature:

      - `Pr[<\\alpha, x> = <\\beta, S(x)>] = 1/2 + e(\\alpha, \\beta)`,
        where `e(\\alpha, \\beta)` is called the bias,
      - `2\cdot Pr[<\\alpha, x> = <\\beta, S(x)>] = 1 + c(\\alpha, \\beta)`,
        where `c(\\alpha, \\beta) = 2\cdot e(\\alpha, \\beta)` is the correlation, and
      - `2^{(n+1)}\cdot Pr[<\\alpha, x> = <\\beta, S(x)>] = 2^n + \hat{S}(\\alpha, \\beta)`,
        where `\hat{S}(\\alpha, \\beta)` is the Fourier coefficient of S.

[rusydi]

comment:11

More comments :

1. Starts the docstring with r""". In this way you can remove all the double backslash in latex notation (e.g. \\alpha becomes \alpha)
2. You forget the backslash in the definition A[alpha, beta] and put them in between backtick
3. Existing notation used for dot product is \cdot (e.g, see the description of autocorrelation_matrix() and component function() )
4. Abbreviation LAT does not match with the function's name. I used LAM instead (e.g., see the description of linear_branch_number() ). Although this is somewhat different from standard terminology in literature, this matches the existing function's name to avoid confusion. But I do think in the future we should replace the word "matrix" to "table" in functions' name (initial committer for this module already used the terminology "matrix").

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dd927aa to e72aae4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e72aae4

update docstring for linear_approximation_matrix

[rusydi]

comment:14

Hi Friedrich,

Please make it clear in the documentation that m and n refers to the input and output size of the S-Box respectively.

[rusydi]

comment:16

Hi Friedrich,

This is just an opinion, so feel free to disagree. Instead of passing a string to parameter scale, why don't we let it to take the scaling factor directly. For instance, instead of calling S.linear_approximation_matrix(scale="absolute_bias"), one may call it with S.linear_approximation_matrix(scale=2). There are two advantages for this : it gives a far more flexibility and at the same time we free ourselves from explaining new terminologies associated with whatever scaling factor available in the literature.

In that case, the argument scale can be replaced to something like scale_factor

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e72aae4 to dbc821d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

dbc821d

small bugfix in docstring, add 'n' and 'm' value explanation

[pfasante]

comment:18

I disagree with using a custom scaling factor.

If you actually need to change the factor, you can also easily scale it afterwards anyway.

Additional, having this scaling argument allows for a much clearer docstring, as we can use the common terms from literature to explain the function. I think its important to precisely say what the function returns and for this choosing from the common scalings used in the literature is the best way, I think.

It should also be quite unlikely that there will be a new scaling factor introduced.

---

New commits:

dbc821d

small bugfix in docstring, add 'n' and 'm' value explanation

[rusydi]

comment:19

Okay, all good

[vbraun]

Changed branch from u/asante/sbox_linear_approximation_matrix_scaling to dbc821d