Linear Cryptanalysis of Simplified AES Under Change of S-Box

Abstract

The Simplified Advanced Encryption Standard, or S-AES, was introduced by Musa, Schaefer, and Wedig [10], in part, to show how to find linear equations for use in linear cryptanalysis. We review their methods and then consider how the choice of S-box affects the success of a greedy linear cryptanalysis algorithm devised for one-round S-AES. We characterize a class of highly non-linear S-boxes for which our algorithm is always successful; we analyze the strange phenomena that occur when S-boxes with linear features are considered; and we show how to construct S-boxes that foil our linear cryptanalysis algorithm completely.

Keywords:

• linear cryptanalysis
• S-box
• simplified AES

Acknowledgments

This work was part of the Summer 2011 LURE Program and was supported by an NSF grant (#DMS-0636528). The authors would like to thank their mentor; Gary Greenfield.

Notes

¹Phan [11] developed a version of AES called Mini-AES with a key scheduling algorithm that is susceptible to a four-round square attack.

²We are now ignoring opposite points because to quote Daemen and Rijmen, the designers of AES, “we are not aware of any attacks that would exploit the existence of (opposite) fixed points” [1, p. 36].

Additional information

Notes on contributors

Samantha Campbell

Samantha Campbell, Max Grinchenko, and William Smith are students at the University of Richmond in the Department of Mathematics and Computer Science.