Computing nonlinear invariants in mq.SBox

[rusydi]

This patch is based on recent results of "Nonlinear Invariants Attack" by Todo, Leander, and Sasaki in http://eprint.iacr.org/2016/732.pdf. For an mxm S-Box S, the attack requires to find m-variables Boolean functions g such that g(x) + g(S(x)) is a constant function. The implementation of this patch is based on the method proposed by authors in Section 3.1 of http://eprint.iacr.org/2016/732.pdf.

CC: @malb @jpflori @pfasante

Component: cryptography

Keywords: sbox

Author: Rusydi H. Makarim, Friedrich Wiemer

Branch/Commit: u/asante/computing_nonlinear_invariants_in_mq_sbox @ a6ab3c7

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

[rusydi]

Branch: u/ruhm/computing_nonlinear_invariants_in_mq_sbox

[rusydi]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+This patch is based on recent results of "Nonlinear Invariants Attack" by Todo, Leander, and Sasaki in http://eprint.iacr.org/2016/732.pdf. For an mxm S-Box S, the attack requires to find m-variables Boolean functions g such that g(x) + g(S(x)) is a constant function. The implementation of this patch is based on the method proposed by authors in Section 3.1 of http://eprint.iacr.org/2016/732.pdf.

[rusydi]

Author: Rusydi H. Makarim

[rusydi]

New commits:

15d947b

initial commit for ticket #21252

[rusydi]

Commit: 15d947b

[rusydi]

Changed keywords from none to sbox

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

Changed commit from 15d947b to 6e9ac9d

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

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

6e9ac9d

fix to include nonlinear invariants that yields constant function 1

[2c00b582-cfe9-43b9-8124-fec470060704]

comment:4

Hi,

my two cents:

• you can't rely on the ordering of a set for a doctest.
• this can be made more efficient with something like that:

def nonlinear_invariants(self):
    m = self.m
    F2 = GF(2)
    one = F2.one()
    zero = F2.zero()
    R = BooleanPolynomialRing(m, 'x')
    def to_bits(i):
        return tuple(ZZ(i).digits(base=2, padto=m))
    def poly_from_coeffs(c):
        return R({to_bits(j): one for j,ci in enumerate(c) if ci})
    L = [[zero if ((v & w) == w) == ((sv & w) == w) else one
          for w in range(1<<m)]
         for v,sv in enumerate(self._S)]
    M = Matrix(F2, L)
    T0 = {poly_from_coeffs(Ai) for Ai in M.right_kernel()}
    M[:,0] = one
    T1 = {poly_from_coeffs(Ai) for Ai in M.right_kernel()}
    return tuple(T0 | T1)

(I'm to lazy to push a real commit...)

[pfasante]

Changed branch from u/ruhm/computing_nonlinear_invariants_in_mq_sbox to u/asante/computing_nonlinear_invariants_in_mq_sbox

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

Changed commit from 6e9ac9d to c422ac6

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

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

5a860b1	doctest: do not rely on set order
c422ac6	implement the version suggested by ylchapuy

[pfasante]

Changed author from Rusydi H. Makarim to Rusydi H. Makarim, Friedrich Wiemer

[pfasante]

comment:9

I updated the code to honor recent changes in the SBox module and added the improvement suggested by ylchapuy.

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

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

a6ab3c7

Merge branch 'develop' of git://trac.sagemath.org/sage into t/21252/computing_nonlinear_invariants_in_mq_sbox

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

Changed commit from c422ac6 to a6ab3c7

[embray]

comment:12

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[hellman]

comment:13

Some comments/suggestions.

1. Wouldn't it make more sense to return truth tables (i.e. crypto.BooleanFunction instances)? The ANF can be obtained by calling the respective method.

2. Instead of doing the linear algebra, we can look at the cycle structure (or, in general, the functional graph). This should be more efficient.

3. Since invariants form a vector space, it may make sense to return a basis, instead of generating all functions (argument option?). Or better, can we make a VectorSpace of BooleanFunctions in Sage? Then it would effectively be a basis and have a straightforward iteration overall all linear combinations.

4. Would be nice to have an option to get invariants g(S(x)) = g(x) separately from those with g(S(x)) = g(x) + 1.

[1a95021f-fda6-4fb5-b75c-68e63dc78f3c]

comment:14

It's nice to see that this functionality is being added.

Having an implementation of suggestion 2 by gh-hellman would be very nice. Maybe this could be a feature to be added in a later version.

That said, I think suggestion 3 above (returning a vector space object rather than all elements individually) is pretty important. Aside from the fact that a VectorSpace is more convenient if you want to find common invariants for several functions, it also helps to avoid potential unpleasant surprises since returning the set of all invariants can sometimes result in very long lists. For example, for the n-bit identity permutation the result will be a list of length 2**(2**n).

If it's not possible/easy to construct subspaces of a BooleanPolynomialRing in sage, I would suggest to return a subspace of VectorSpace(GF(2), 2**n) instead (basically the truth tables as proposed by gh-hellman in suggestion 1). From there, users can easily extract the polynomial representations of all the nonlinear invariants if they really want to.

For some applications (if you want to work with correlation matrices), returning a real vector space (consisting of signed truth tables or their Fourier transformation) is preferable. (Mathematically, returning a subalgebra of GroupAlgebra(VectorSpace(GF(2), 2**n), RR) would be cleaner but from a programming perspective that's probably just annoying.) That would be just another feature, though, so it should probably be postponed to a later version.

[embray]

comment:15

Ticket retargeted after milestone closed

[mkoeppe]

comment:16

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:18

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:19

Setting a new milestone for this ticket based on a cursory review.

[mkoeppe]

comment:20

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[mkoeppe]

Branch has merge conflicts