×

Linear redundancy in S-boxes. (English) Zbl 1242.94025

Johansson, Thomas (ed.), Fast software encryption. 10th international workshop, FSE 2003, Lund, Sweden, February 24–26, 2003. Revised papers. Berlin: Springer (ISBN 3-540-20449-0/pbk). Lect. Notes Comput. Sci. 2887, 74-86 (2003).
Summary: This paper reports the discovery of linear redundancy in the S-boxes of many ciphers recently proposed for standardisation (including Rijndael, the new AES). We introduce a new method to efficiently detect affine equivalence of Boolean functions, and hence we study the variety of equivalence classes existing in random and published S-boxes. This leads us to propose a new randomness criterion for these components. We present experimental data supporting the notion that linear redundancy is very rare in S-boxes with more than six inputs. Finally we discuss the impact this property may have on implementations, review the potential for new cryptanalytic attacks, and propose a new tweak for block ciphers that removes the redundancy. We also provide details of a highly nonlinear 8*8 non-redundant bijective S-box, which is suitable as a plug-in replacement where required.
For the entire collection see [Zbl 1029.00054].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI