New Analysis Methods on Strict Avalanche Criterion of S-Boxes

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.

Authors:

• Phyu Phyu Mar
• Khin Maung Latt

Keywords:

• S-boxes
• cryptosystems
• strict avalanche criterion
• function
• analysis methods.

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.