Opened 5 years ago

Last modified 2 months ago

#21252 needs_review enhancement

Computing nonlinear invariants in mq.SBox

Reported by: ruhm Owned by:
Priority: major Milestone: sage-9.5
Component: cryptography Keywords: sbox
Cc: malb, jpflori, asante Merged in:
Authors: Rusydi H. Makarim, Friedrich Wiemer Reviewers:
Report Upstream: N/A Work issues:
Branch: u/asante/computing_nonlinear_invariants_in_mq_sbox (Commits, GitHub, GitLab) Commit: a6ab3c7b88a3af0e62e2b6295067fbf7b4dc9aac
Dependencies: Stopgaps:

Status badges

Description (last modified by ruhm)

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.

Change History (19)

comment:1 Changed 5 years ago by ruhm

  • Branch set to u/ruhm/computing_nonlinear_invariants_in_mq_sbox

comment:2 Changed 5 years ago by ruhm

  • Authors set to Rusydi H. Makarim
  • Cc malb added
  • Commit set to 15d947b8472f0d266c75dd379a8dc7325a8440ce
  • Component changed from PLEASE CHANGE to cryptography
  • Description modified (diff)
  • Keywords sbox added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

New commits:

15d947binitial commit for ticket #21252

comment:3 Changed 5 years ago by git

  • Commit changed from 15d947b8472f0d266c75dd379a8dc7325a8440ce to 6e9ac9d8ebdc91349327de1ec3c0411c787e95be

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

6e9ac9dfix to include nonlinear invariants that yields constant function 1

comment:4 Changed 5 years ago by ylchapuy

  • Status changed from needs_review to needs_work

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...)

comment:5 Changed 5 years ago by ruhm

  • Milestone changed from sage-7.4 to sage-7.5

comment:6 Changed 4 years ago by jpflori

  • Cc jpflori added

comment:7 Changed 4 years ago by asante

  • Branch changed from u/ruhm/computing_nonlinear_invariants_in_mq_sbox to u/asante/computing_nonlinear_invariants_in_mq_sbox

comment:8 Changed 4 years ago by git

  • Commit changed from 6e9ac9d8ebdc91349327de1ec3c0411c787e95be to c422ac6575b721e0af538f0fa817784341ba7b50

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

5a860b1doctest: do not rely on set order
c422ac6implement the version suggested by ylchapuy

comment:9 Changed 4 years ago by asante

  • Authors changed from Rusydi H. Makarim to Rusydi H. Makarim, Friedrich Wiemer
  • Cc asante added
  • Status changed from needs_work to needs_review

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

comment:10 Changed 2 years ago by git

  • Commit changed from c422ac6575b721e0af538f0fa817784341ba7b50 to a6ab3c7b88a3af0e62e2b6295067fbf7b4dc9aac

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

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

comment:11 Changed 2 years ago by asante

  • Milestone changed from sage-7.5 to sage-8.8

comment:12 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

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).

comment:13 Changed 2 years ago by gh-hellman

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.
  1. Instead of doing the linear algebra, we can look at the cycle structure (or, in general, the functional graph). This should be more efficient.
  1. 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.
  1. 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.

comment:14 Changed 2 years ago by gh-TimBeyne

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.

Last edited 2 years ago by gh-TimBeyne (previous) (diff)

comment:15 Changed 21 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:16 Changed 17 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

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.

comment:17 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:18 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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

comment:19 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

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

Note: See TracTickets for help on using tickets.