A Toolboxfor Cryptanalysis: Linear and A-ne Equivalence Algorithms ?

Thispaperpresentstwoalgorithmsforsolvingthelinearand thea-neequivalenceproblemforarbitrarypermutations(S-boxes).For apairof n£ n-bitpermutationsthecomplexityofthelinearequivalence algorithm (LE) is O(n 3 2 n ). The a-ne equivalence algorithm (AE) has complexity O(n 3 2 2n ).Thealgorithmsaree-cientandallowtostudylin- ear and a-ne equivalences for bijective S-boxes of all popular sizes (LE is e-cient up to n • 32). Using these tools new equivalent representa- tionsarefoundforavarietyofciphers:Rijndael,DES,Camellia,Serpent, Misty, Kasumi, Khazad, etc. The algorithms are furthermore extended for the case of non-bijective n to m-bit S-boxes with a small value of jni mj and for the case of almost equivalent S-boxes. The algorithms alsoprovidenewattacksonageneralizedEven-Mansourscheme.Finally, thepaperdeflnesanewproblemofS-boxdecompositionintermsofSub-