# How to use sagemath to find nonlinear invariants of S-box?

I read a paper about a nonlinear invariant attack that is "Nonlinear Invariant Attack: Practical Attack on Full SCREAM, iSCREAM, and Midori64"

And I've found a website of sagemath : https://trac.sagemath.org/ticket/21252 where they have a code to find nonlinear invariant for any S-box. But it's not official so it's not included in sagemath. Does anyone know how to do it? I want to write a code in C++ to find nonlinear invariant, but I don't get the idea of the author. Thank you

• I don't think you can get it from Sage.
– hola
May 28, 2021 at 18:20
• @hola can you explain how to do it? I dont get the idea of the author. Thank you. May 28, 2021 at 19:00

Generally, the idea is simple. Compute the cycle decomposition of the S-box. If there are $$t$$ cycles, there are $$2^t$$ nonlinear invariants, that can be obtained by assigning 0 or 1 to each cycle. For switching invariants ($$f(S(x)) = f(x) + 1$$), they may occur only if length of all cycles are even. Then assign 010101... or 101010... to each cycle, getting $$2^t$$ more invariants.