sbox linear approximation matrix scaling #24819

pfasante · 2018-02-22T13:44:07Z

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

The text was updated successfully, but these errors were encountered:

pfasante · 2018-02-22T14:53:43Z

Branch: u/asante/sbox_linear_approximation_matrix_scaling

pfasante · 2018-02-22T14:54:21Z

Commit: 1f2942b

pfasante · 2018-02-22T14:54:21Z

New commits:

`1f2942b`	`add scale argument to linear approximation matrix method`

sagetrac-git · 2018-02-22T14:58:35Z

Changed commit from 1f2942b to ec8284c

sagetrac-git · 2018-02-22T14:58:35Z

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

`ec8284c`	`fix docstring enumeration`

rusydi · 2018-02-23T21:42:25Z

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 · 2018-02-23T22:57:35Z

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 · 2018-02-23T23:01:01Z

Reviewer: Rusydi H. Makarim

sagetrac-git · 2018-02-25T18:13:19Z

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

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

sagetrac-git · 2018-02-25T18:13:19Z

Changed commit from ec8284c to dd927aa

pfasante · 2018-02-25T18:20:50Z

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 · 2018-02-25T21:59:05Z

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 · 2018-02-25T22:08:08Z

comment:11

More comments :

Starts the docstring with r""". In this way you can remove all the double backslash in latex notation (e.g. \\alpha becomes \alpha)
You forget the backslash in the definition A[alpha, beta] and put them in between backtick
Existing notation used for dot product is \cdot (e.g, see the description of autocorrelation_matrix() and component function() )
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").

sagetrac-git · 2018-02-26T14:06:25Z

Changed commit from dd927aa to e72aae4

sagetrac-git · 2018-02-26T14:06:25Z

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

`e72aae4`	`update docstring for linear_approximation_matrix`

rusydi · 2018-02-28T23:06:29Z

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 · 2018-03-05T14:40:25Z

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

sagetrac-git · 2018-03-08T09:16:55Z

Changed commit from e72aae4 to dbc821d

sagetrac-git · 2018-03-08T09:16:55Z

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

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

pfasante · 2018-03-08T09:21:00Z

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 · 2018-03-08T13:19:05Z

comment:19

Okay, all good

vbraun · 2018-03-19T07:57:49Z

Changed branch from u/asante/sbox_linear_approximation_matrix_scaling to dbc821d

pfasante added this to the sage-8.2 milestone Feb 22, 2018

pfasante added c: cryptography labels Feb 22, 2018

pfasante self-assigned this Feb 22, 2018

pfasante added the s: needs review label Feb 22, 2018

rusydi added s: needs work and removed s: needs review labels Feb 23, 2018

pfasante added s: needs review and removed s: needs work labels Feb 26, 2018

rusydi added s: needs work and removed s: needs review labels Feb 28, 2018

pfasante added s: needs review and removed s: needs work labels Mar 8, 2018

rusydi added s: positive review and removed s: needs review labels Mar 8, 2018

vbraun removed the s: positive review label Mar 19, 2018

vbraun closed this as completed in ace16ce Mar 19, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

sbox linear approximation matrix scaling #24819

sbox linear approximation matrix scaling #24819

pfasante commented Feb 22, 2018

pfasante commented Feb 22, 2018

pfasante commented Feb 22, 2018

pfasante commented Feb 22, 2018

sagetrac-git mannequin commented Feb 22, 2018

sagetrac-git mannequin commented Feb 22, 2018

rusydi commented Feb 23, 2018

rusydi commented Feb 23, 2018

rusydi commented Feb 23, 2018

sagetrac-git mannequin commented Feb 25, 2018

sagetrac-git mannequin commented Feb 25, 2018

pfasante commented Feb 25, 2018

rusydi commented Feb 25, 2018

rusydi commented Feb 25, 2018

sagetrac-git mannequin commented Feb 26, 2018

sagetrac-git mannequin commented Feb 26, 2018

rusydi commented Feb 28, 2018

rusydi commented Mar 5, 2018

sagetrac-git mannequin commented Mar 8, 2018

sagetrac-git mannequin commented Mar 8, 2018

pfasante commented Mar 8, 2018

rusydi commented Mar 8, 2018

vbraun commented Mar 19, 2018

sbox linear approximation matrix scaling #24819

sbox linear approximation matrix scaling #24819

Comments

pfasante commented Feb 22, 2018

pfasante commented Feb 22, 2018

pfasante commented Feb 22, 2018

pfasante commented Feb 22, 2018

sagetrac-git mannequin commented Feb 22, 2018

sagetrac-git mannequin commented Feb 22, 2018

rusydi commented Feb 23, 2018

rusydi commented Feb 23, 2018

rusydi commented Feb 23, 2018

sagetrac-git mannequin commented Feb 25, 2018

sagetrac-git mannequin commented Feb 25, 2018

pfasante commented Feb 25, 2018

rusydi commented Feb 25, 2018

rusydi commented Feb 25, 2018

sagetrac-git mannequin commented Feb 26, 2018

sagetrac-git mannequin commented Feb 26, 2018

rusydi commented Feb 28, 2018

rusydi commented Mar 5, 2018

sagetrac-git mannequin commented Mar 8, 2018

sagetrac-git mannequin commented Mar 8, 2018

pfasante commented Mar 8, 2018

rusydi commented Mar 8, 2018

vbraun commented Mar 19, 2018