International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 4, No. 10, 8 Sep. 2012
Cover page and Table of Contents: PDF (size: 589KB)
Importance of S-Blocks in Modern Block Ciphers
Full Text (PDF, 589KB), PP.1-12
Views: 0 Downloads: 0
Author(s)
Index Terms
Substitution, iterative cipher, the maximum differential probability, the maximum linear probability
Abstract
There is a new approach to determine the degree of cryptographic S-boxes suitability. This approach is based on estimating the number of transformation cycles required for a cipher to achieve differential and linear nature of the state typical for random substitution of the appropriate degree. The paper presents the results of experiments to determine the differential and linear indicators of the Heys cipher (a cipher with a weak linear transformation) and a reduced model of the Rijndael cipher (the cipher with a strong linear transformation), using nibble S-boxes with different values of the XOR table differences maxima and linear approximations table displacements. It is demonstrated that, contrary to widely-known approach that links cipher performance indicators with strength indicators of substitutions that they use, the resistance to cipher attacks by means of linear and differential cryptanalysis (maximum differential and linear probabilities) does not depend on S-boxes used. It is concluded that random substitutions can be used as the S-block designs without compromising the performance of cryptographic ciphers. It means that the search for S-boxes with high encryption performance (at least for ciphers with strong linear transformations) is an unpromising task. At the same time it is shown that a good cipher can not be built without a nonlinear transformation. S-boxes (non-trivial type) are essential and necessary elements of an effective cryptographic transformation, ensuring the operation of the nonlinear mixing of input data blocks bit segments.
Cite This Paper
Lisitskaya I.V., Melnychuk E.D., Lisitskiy K.E., "Importance of S-Blocks in Modern Block Ciphers", International Journal of Computer Network and Information Security(IJCNIS), vol.4, no.10, pp.1-12, 2012. DOI:10.5815/ijcnis.2012.10.01
Reference
[1]С. М. Adams. A formal and practical design procedure for Substitution-Permutation network cryptosystem. PhD thesis, Department of Electrical Engineering, Queen's University at Kingston, 1990.
[2]С. M. Adams. And S.E. Tavares. The Structured design of cryptographically good S-boxes. Journal of Cryptology, 3(1): 27-41, 1990.
[3]R. Forré. Methods and instruments for designing S-boxes. Journal of Cryptology, 2(3): 115-130,1990.
[4]K. Nyberg. Perfect nonlinear S-boxes. In Advances in cryptology - EUROCRYPT91, volume 547, Lecture Notes in Computer Science, pp. 378-386. Springer-Verlag, Berlin, Heidelberg, New York, 1991.
[5]E.F. Brickell, J.H. Moore, and M.R. Purtill. Structure in the S-boxes DES. Advances in cryptology, CRYPTOZb, Lecture Notes in Computer Science, vol. 263.A.M. Odlyzko ed., Springer-Verlag, pages 3-8, 1987.
[6]M. H. Dawson. A unified framework for substitution box design based on information theory. Vaster's thesis, Queen's University, Kingston, Ontario, Canada, 1991.
[7]E. Biham, A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology, Vol. 4 No.l, 1991, pp. 3-72.
[8]K. Nyberg and L.R. Knudsen. Provable security against differential cryptanalysis. In Advances in cryptology - EUROCRYPT'92, volume Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, 1992, pp. 566-574.
[9]T. Beth and C. Ding. On permutations against differential cryptanalysis. In Advances in cryptology - EUROCRYPT'93. Springer-Verlag, Berlin, Heidelberg, New York, 1993.
[10]K. Nyberg. Differentially uniform mappings for cryptography. In Advances in cryptology - Proceedings of EUROCRYPT'93 (1994) vol. 765, Lecture Notes in Computer Science Springer-Verlag, Berlin, Heidelberg, New York, pp. 55-65.
[11]Seberry J., Zhang X.M., Zheng Y. "Pitfalls in Designing Boxes (Extended Abstract)"//, Copyright © Springer-Verlag, 1998, pp. 383-396.
[12]Seberry J., Zhang X.M., Zheng Y.: Relationships among nonlinearity criteria. Presented at EUROCRYPTV4, 1994.
[13]F. Sano, K. Ohkuma, H. Shimizu, S. Kawamura. On the Security of Nested SPN Cipher against the Differential and Linear Cryptanalysis/ IEICE Trans. Fundamentals, vol. E86-a, NO.1 January 2003, pp. 37-46.
[14]S. Hong, S. Lee, J. Lim, J. Sung, D. Cheon and I. Cho. Provable Security against Differential and Linear cryptanalysis for SPN Structure. B. Schneier (Ed.): FSE 2000, LNCS 1978, pp. 273-283, 2001.
[15]L. Keliher, H. Meijer, and S. Tavares, "New method for upper bounding the maximum average linear hull probability for SPNs," Advances in Cryptology, Proceedings of Eurocrypt '01, LNCS 2045, B. Pfitzmann, Ed., Springer-Verlag, 2001, pp. 420-436.
[16]L. Keliher, H. Meijer, and S. Tavares, "Improving the upper bound on the maximum average linear hull probability for Rijndael", Advances in Cryptology, Selected Areas in Cryptography '01, LNCS 2259, S. Vaudenay, A.M. Youssef, Eds., Springer-Verlag, 2001, pp. 112-128.
[17]Thomas Baignoires and Serge Vaudenay. Proving the Security of AES Substitution-Permutation Network. http://lasecwww.epfl.ch. 2004. p. 16.
[18]Aleksiychuk A.N. Assessing the stability of a block cipher Kalina on the methods of the difference, with respect to linear cryptanalysis and algebraic attacks based on homomorphisms. / A.N. Aleksiychuk, L.V. Kovalchuk, E.V. Skrypnyk, A.S. Shevtsov // Applied electronics. 2008. vol.7. № 3. pp. 203-209.
[19]Lisitskaya I.V. On Participation of S-boxes in the formation of maximum differential probability of block symmetric ciphers. / I.V. Lisitskaya, A.V. Kazimirov // Proceedings International Conference SAIT 2011, Kyiv, Ukraine, May 23-28. – 2011, p. 459.
[20]Kuznetsov A.A. Linear properties of block symmetric ciphers submitted to the Ukrainian competition. / A.A. Kuznetsov, I.V. Lisitskaya, S.А. Isaev, Applied electronics, 2011. Vol.10, № 2, pp. 135-140.
[21]Lisitskaya I.V. Participation of S-boxes in the formation of maximum linear probability of block symmetric ciphers. / I.V. Lisitskaya, V.V. Kovtyn //Radio Technical Collection 2011. no. 166, pp. 17-25.
[22]Lisitskaya I.V. A new assessment of the ideology of resistance block symmetric ciphers to attacks of the differential and linear cryptanalysis, Krasnoyarsk, 2011. Proceedings of the 1st All-Russian scientific and practical forum of young scientists and specialists "Modern Russian science through the eyes of young researchers", Krasnoyarsk, 2011, pp. 18-120.
[23]Lisitskaya I.V. Methodology for assessing stability of block symmetric ciphers, Automated control systems and automation devices, 2011, № 163, pp. 123-133.
[24]Alexey Shirokov. Methods of formation of S-type random block designs with improved cryptographic performance (for block symmetric ciphers with provable security): Thesis. 05.13.21. Shirokov Alexey, Kharkov, 2010. 265. Bibliography, pp. 215-232.
[25]K. Nyberg Differentially uniform mappings for cryptography. In Advances in cryptology - Proceedings of EUROCRYPT93 (1994) vol. 765, Lecture Notes in Computer Science Springer-Verlag, Berlin, Heidelberg, New York, pp. 55-65.
[26]Markku-Juhani O. Saarinen Cryptographic Analysis of All 4×4-Bit S-Boxes. IACR Cryptology ePrint Archive Vol. 2011 (2011), p. 218.
[27]N. Tokareva Quadratic approximation of a special form for the four substitutions in the S-boxes, Applied discrete mathematics, 2008. Vol. 1, № 1, pp. 50-54.
[28]Oleynikov R.V., Oleshko O.I., Lisitsky K.E., Tevyashev A.D. Differential properties of substitutions, Applied electronics, 2010. Vol.9, Number 3, pp. 326-333.
[29]V. Dolgov Properties of linear approximation tables of random permutations, Applied electronics, Kharkov: KNURE. - 2010. Vol. 9, № 3, pp. 334-340.
[30]Lisitskaya I.V. Comparative analysis of the mechanisms of avalanche effect in the DES algorithm and GOST 28147-89, Іnformatsіyno-keruyuchi systemy na zalіznichnomu transportі, № 3. pp.24-30.
[31]Joan Daemen, Vincent Rijmen Probability distributions of Correlation and Differentials in Block Ciphers. / Joan Daemen, Vincent Rijmen, April 13, 2006, pp. 1-38.
[32]H. M. Heys. A Tutorial on Linear and Differential Cryptanalysis, CRYPTOLOGIA, v 26, N 3, 2002, p 189-221.
[33]Dolgov V.I. Variations on the theme of the cipher Rijndael, / V.I. Dolgov, I.V. Lisitskaya, A.V. Kazimirov // Applied electronics 2010, Vol.9, № 3, pp. 321-325.
[34]Rostovtsev A., Introduction to the theory of iterated, St. Petersburg: NGO Peace and the Family, 2003.
[35]Schneier B. Applied Cryptography. Protocols, algorithms, source code in C, Moscow: Triumph, 2002.
[36]Kim K., Park S., Lee S. Reconstruction of s2DES S-Boxes and their Immunity to Differential Cryptanalysis // Korea - Japan Workshop on Information Security and Cryptography. (Seoul, Korea. October 24–26, 1993) Proc., pp. 282-291.
[37]Lisitskaya I.V. The large ciphers - random substitution, Interdepartmental Scientific. Radio Technical Collection, 2011, no. 166, pp. 50-55.
[38]Lisitskaya I.V. Differential properties of the cipher FOX. / I.V. Lisitskaya, D.S. Kaidalov // Applied electronics, 2011, Vol.10, № 2. pp. 122-126.