Invariant-Attack Resistance for All Keys Under Linear (Tweak)key Schedules, with Applications to SKINNY, GIFT, Midori and MANTIS

Invariant attacks threaten lightweight ciphers whose round keys are closely related. The criterion of Beierle, Canteaut, Leander and Rotella (CRYPTO 2017) proves resistance from the linear layer and the round constants, but it covers only round keys that differ by constants, and it says nothing once it is inconclusive. We extend the criterion to arbitrary linear (tweak)key schedules and decide it for all keys at once: the inconclusive keys form a finite union of affine subspaces, each found by one Gaussian elimination. We then settle inconclusive keys from the S-box, with a one-sided certificate, a plane-quotient theorem and a cell-reduction lemma. Within the model of Beierle et al., the criterion holds for every tweakey of SKINNY-64 from a tight number of rounds on; no tweakey of SKINNY-128-128 admits an invariant; GIFT can never satisfy the criterion, yet the S-box excludes invariants for most GIFT-64 keys, and the two published attacks on Midori-64 are its only invariants. Beyond this model, no key and tweak admits a sum-type trail through MANTISr, 3≤r≤8. For designers, constants and key schedule have to be chosen as one algebraic object, and where constants enter the state matters more than how nonlinear they are.