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:  sage9.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: 
Description (last modified by )
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 SBox S, the attack requires to find mvariables 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
 Branch set to u/ruhm/computing_nonlinear_invariants_in_mq_sbox
comment:2 Changed 5 years ago by
 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
comment:3 Changed 5 years ago by
 Commit changed from 15d947b8472f0d266c75dd379a8dc7325a8440ce to 6e9ac9d8ebdc91349327de1ec3c0411c787e95be
Branch pushed to git repo; I updated commit sha1. New commits:
6e9ac9d  fix to include nonlinear invariants that yields constant function 1

comment:4 Changed 5 years ago by
 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
 Milestone changed from sage7.4 to sage7.5
comment:6 Changed 4 years ago by
 Cc jpflori added
comment:7 Changed 4 years ago by
 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
 Commit changed from 6e9ac9d8ebdc91349327de1ec3c0411c787e95be to c422ac6575b721e0af538f0fa817784341ba7b50
comment:9 Changed 4 years ago by
 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
 Commit changed from c422ac6575b721e0af538f0fa817784341ba7b50 to a6ab3c7b88a3af0e62e2b6295067fbf7b4dc9aac
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

comment:11 Changed 2 years ago by
 Milestone changed from sage7.5 to sage8.8
comment:12 Changed 2 years ago by
 Milestone changed from sage8.8 to sage8.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
Some comments/suggestions.
 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.
 Instead of doing the linear algebra, we can look at the cycle structure (or, in general, the functional graph). This should be more efficient.
 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.
 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
It's nice to see that this functionality is being added.
Having an implementation of suggestion 2 by ghhellman 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 nbit 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 ghhellman 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.
comment:15 Changed 21 months ago by
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:16 Changed 17 months ago by
 Milestone changed from sage9.1 to sage9.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
 Milestone changed from sage9.2 to sage9.3
comment:18 Changed 6 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:19 Changed 2 months ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
New commits:
initial commit for ticket #21252