New Analysis Methods on Strict Avalanche Criterion of S-Boxes

Authors: Phyu Phyu Mar, Khin Maung Latt

Abstract:

S-boxes (Substitution boxes) are keystones of modern symmetric cryptosystems (block ciphers, as well as stream ciphers). S-boxes bring nonlinearity to cryptosystems and strengthen their cryptographic security. They are used for confusion in data security An S-box satisfies the strict avalanche criterion (SAC), if and only if for any single input bit of the S-box, the inversion of it changes each output bit with probability one half. If a function (cryptographic transformation) is complete, then each output bit depends on all of the input bits. Thus, if it were possible to find the simplest Boolean expression for each output bit in terms of the input bits, each of these expressions would have to contain all of the input bits if the function is complete. From some important properties of S-box, the most interesting property SAC (Strict Avalanche Criterion) is presented and to analyze this property three analysis methods are proposed.

Keywords: S-boxes, cryptosystems, strict avalanche criterion, function, analysis methods.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072660

References:

[1] C. Adams, S. Tavares, "The Structured Design of Cryptographically Good S-boxes", To appear in J. of Cryptology, 1990.
[2] F. Ayoub, "Probabilistic Completeness of Substitution-Permutation Encryption Network", IEEE, Vol.129, E, 5, pp195-199, Sep., 1982.
[3] E.F. Brickell, J.H. Moore, M.R. Purtill,"Structures in the S-boxes of the DES", Proc. of CRYPTO'86, Springer-Verlag, pp. 3-8, 1986.
[4] J. Daemen, V. Rijmen, "AES Proposal: Rijndael", Document version 2, 03-09-99, http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijn dael.pdf.
[5] H. Feistel, "Cryptography and Computer Privacy", Scientific American, Vol.228, No.5, pp 15-23, 1973.
[6] J.B. Kam, G.I. Davida, "Structured Design of Substitution-Permutation Encryption Network", IEEE Trans. on Compute. Vol.C-28, No.10, pp.747-753, Oct., 1979.
[7] Kwangjo KIM, "A Study on the Construction and Analysis of Substitution Boxes for Symmetric Cryptosystems", Dissertation submitted to the Division of Electrical and Computer Engineering for the Degree of Doctor of Philosophy, December 25, 1990, http://citeseer.ist.psu.edu/336097.html.