Skip to main content
SpringerLink
Log in

Literature survey on nonlinear components and chaotic nonlinear components of block ciphers

  • Review
  • Published:
Nonlinear Dynamics Aims and scope Submit manuscript

Abstract

In the modern era of secure communication, it is important to create uncertainty in the original data in order to avoid unauthorized entities to extract or manipulate information. From simple methods such as permutations of original data to different mapping algorithms, the security of the ciphers rely on the substitution process. There are many types of components proposed in literature that are evolved by different methodologies and ideas. The prevailing ciphers use substitution boxes (S-boxes) to do this transformation process. In this work, we present a literature review of the design, construction, and analysis of the S-boxes used in block ciphers.

The performance of S-boxes depends on the design and algebraic structure used for the construction and is contingent upon its ability to resist against cryptanalysis. We present the details of the S-box synthesis process and issues pertaining to creating resistance against various types of attacks, and highlight the consequences of a particular design methodology.

In the infancy of the development of modern block ciphers, Shannon (Bell Syst. Tech. J. 28(4):656–715, 1949) presented the idea of encryption with the implementation of substitution-permutation network (SPN). In this process, the data is initially transformed by the substation process and then permuted that ends the first round supported by the secret key for this step. This substitution-permutation process is repeated several times to ensure reliability of encrypted data. The objective of using the substitution-permutation network is to create confusion between cipher text and secret key, and add diffusion in the plaintext.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Carlet, C.: On the coset weight divisibility and nonlinearity of resilient and correlation immune functions. In: Sequences and Their Applications-SETA, 01. Discrete Mathematics and Theoretical Computer Science, pp. 131–144. Springer, Berlin (2000)

    Google Scholar 

  2. Meier, W., Stafelbach, O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1(3), 159–176 (1989)

    Article  MATH  Google Scholar 

  3. Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. Elsevier, Amsterdam (1997)

    MATH  Google Scholar 

  4. Millan, W.L.: Analysis and design of Boolean functions for cryptographic applications. Ph.D. thesis, Queensland University of Technology (1997)

  5. Feistel, H.: Cryptography and computer privacy. Sci. Am. 228(5), 15–23 (1973)

    Article  Google Scholar 

  6. Lai, X.: Higher Order Derivative and Differential Cryptanalysis. Communications and Cryptography: Two Sides of One Tapestry, pp. 227–233. Kluwer Academic, Dordrecht (1994)

    Google Scholar 

  7. Zhang, X.M., Zheng, Y.: GAC-the criterion for global avalanche characteristics of cryptographic functions. J. Univers. Comput. Sci. 1(5), 316–333 (1995)

    Google Scholar 

  8. Webster, A.F., Tavares, S.E.: On the design of S-boxes. In: Advances in Cryptology CRYPTO 85. Lecture Notes in Computer Science, vol. 218, pp. 523–534. Springer, Berlin (1986)

    Google Scholar 

  9. Preneel, B., Leekwijck, W.V., Linden, L.V., Govaerts, R., Vandewalle, J.: Propagation characteristics of Boolean functions. In: Advances in Cryptology—EUROCRYPT 90. Lecture Notes in Computer Science, vol. 473, pp. 161–173. Springer, Berlin (1991)

    Google Scholar 

  10. Kurosawa, K.: Almost security of cryptographic Boolean functions. IEEE Trans. Inf. Theory IT-50(11), 2752–2761 (2004)

    Article  MathSciNet  Google Scholar 

  11. Zhen, X.G., Massey, J.L.: A spectral characterization of correlation immune combining functions. IEEE Trans. Inf. Theory 34(3), 569–571 (1988)

    Article  MATH  Google Scholar 

  12. Siegenthaler, T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inf. Theory IT-30(5), 776–780 (1984)

    Article  MathSciNet  Google Scholar 

  13. Sarkar, P., Maitra, S.: New directions in design of resilient functions. In: Cryptology ePrint Archive (2000). http://eprint.iacr.org/2000/009

    Google Scholar 

  14. Kurosawa, K., Johansson, T., Stinson, D.: Almost k-wise independent sample spaces and their cryptological applications. J. Cryptol. 14(4), 434–449 (2001)

    MathSciNet  Google Scholar 

  15. Seberry, J., Zhang, X.M., Zheng, Y.: The relationship between propagation characteristics and nonlinearity of cryptographic functions. J. Univers. Comput. Sci. 1(2), 136–150 (1995)

    MathSciNet  MATH  Google Scholar 

  16. Zheng, Y., Zhang, X.M.: Connections among nonlinearity, avalanche and correlation immunity. Theor. Comput. Sci. 292(3), 697–710 (2003)

    Article  MATH  Google Scholar 

  17. Zhang, X.M., Zheng, Y.: Auto-correlations and new bounds on the nonlinearity of Boolean functions. In: Advances in Cryptology-EU-ROCRYPT 96. Lecture Notes in Computer Science, vol. 1070, pp. 294–306. Springer, Berlin (1996)

    Google Scholar 

  18. Daemen, J., Rijmen, V.: The Design of Rijndael-AES: The Advanced Encryption Standard. Springer, Berlin (2002). Printed in Germany

    Book  Google Scholar 

  19. Elsayed, A.E.H.: Correlation coefficients based on mean absolute deviation about median. Int. J. Stat. Syst. 6(4), 413–428 (2011)

    Google Scholar 

  20. Carlet, C., Sarkar, P.: Spectral domain analysis of correlation immune and resilient Boolean functions. Finite Fields Appl. 8(1), 120–130 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  21. Zheng, Y., Zhang, X.M.: Improved upper bound on the nonlinearity of high order correlation immune functions. In: Selected Areas in Cryptography, SAC 2000. Lecture Notes in Computer Science, vol. 2012, pp. 262–274. Springer, Berlin (2001)

    Chapter  Google Scholar 

  22. Tarannikov, Y.: On resilient Boolean functions with maximal possible nonlinearity. In: Progress in Cryptology-INDOCRYPT 2000. Lecture Notes in Computer Science, vol. 1977, pp. 30–79. Springer, Berlin (2000)

    Google Scholar 

  23. Tarannikov, Y., Kirienko, D.: Spectral analysis of high order correlation immune functions. In: Cryptology ePrint Archive (2000). http://eprint.iacr.org/2000/050

    Google Scholar 

  24. Sarkar, P., Maitra, S.: Nonlinearity bounds and constructions of resilient Boolean functions. In: Advances in Cryptology-CRYPTO 2000. Lecture Notes in Computer Science, vol. 1880, pp. 515–532. Springer, Berlin (2000)

    Chapter  Google Scholar 

  25. Zheng, Y., Zhang, X.M.: New results on correlation immunity. In: Information Security and Cryptology—ICISC 2000. Lecture Notes in Computer Science, vol. 2015, pp. 49–63. Springer, Berlin (2001)

    Chapter  Google Scholar 

  26. Rothaus, O.S.: On bent functions. J. Comb. Theory 20(3), 300–305 (1967)

    Article  MathSciNet  Google Scholar 

  27. Meier, W., Stafelbach, O.: Nonlinearity criteria for cryptographic functions. In: Advances in Cryptology—EUROCRYPT 89. Lecture Notes in Computer Science, vol. 434, pp. 549–562. Springer, Berlin (1990)

    Google Scholar 

  28. McFarland, R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory 15, 1–10 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  29. Nyberg, K.: Constructions of bent functions and difference sets. In: Advances in Cryptology EUROCRYPT 90. Lecture Notes in Computer Science, vol. 473, pp. 151–160. Springer, Berlin (1991)

    Google Scholar 

  30. Seberry, J., Zhang, X.M.: Constructions of bent functions from two known bent functions. Australas. J. Comb. 9, 21–35 (1994)

    MathSciNet  MATH  Google Scholar 

  31. Dobbertin, H.: Construction of bent functions and balanced Boolean functions with high nonlinearity. In: Fast Software Encryption, FSE 94. Lecture Notes in Computer Science, vol. 1008, pp. 61–74. Springer, Berlin (1994)

    Chapter  Google Scholar 

  32. Carlet, C.: A construction of bent functions. Finite Fields Appl. 233, 47–58 (1996)

    Article  MathSciNet  Google Scholar 

  33. Chee, S., Lee, S., Kim, K.: Semi-bent functions. In: Advances in Cryptology—ASI-ACRYPT 94. Lecture Notes in Computer Science, vol. 917, pp. 107–118. Springer, Berlin (1995)

    Google Scholar 

  34. Zheng, Y., Zhang, X.M.: Plateaued functions. In: Information and Communication Security—ICICS 99. Lecture Notes in Computer Science, vol. 1726, pp. 284–300. Springer, Berlin (1999)

    Chapter  Google Scholar 

  35. Carlet, C.: Partially-bent functions. Des. Codes Cryptogr. 3, 135–145 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  36. Carlet, C., Prouf, E.: On plateaued functions and their constructions. In: Fast Software Encryption, FSE 2003. Lecture Notes in Computer Science, vol. 2887, pp. 54–73. Springer, Berlin (2003)

    Chapter  Google Scholar 

  37. Shannon, C.E.: Communications theory of secrecy systems. Bell Syst. Tech. J. 28(4), 656–715 (1949)

    Article  MathSciNet  MATH  Google Scholar 

  38. Millan, W.: Low order approximation of cipher functions. In: Cryptography: Policy and Algorithms. Lecture Notes in Computer Science, vol. 1029, pp. 144–155. Springer, Berlin (1996)

    Chapter  Google Scholar 

  39. Golic, J.D.: Fast low order approximation of cryptographic functions. In: Advances in Cryptology—EUROCRYPT 96. Lecture Notes in Computer Science, vol. 1070, pp. 268–282. Springer, Berlin (1996)

    Google Scholar 

  40. Kam, J., Davida, G.: Structured design of substitution-permutation encryption networks. IEEE Trans. Comput. C-28(10), 747–753 (1979)

    Article  MathSciNet  Google Scholar 

  41. Gordon, J., Retkin, H.: Are big S-boxes best? In: Proc. of the Workshop on Cryptography. Lecture Notes in Computer Science, pp. 257–262. Springer, Berlin (1982)

    Google Scholar 

  42. Ayoub, F.: Probabilistic completeness of substitution-permutation encryption networks. IEE Proc. E 129(5), 195–199 (1982)

    Google Scholar 

  43. Pieprzyk, J., Finkelstein, G.: Towards effective nonlinear cryptosystem design. IEE Proc., Part E 135(6), 325–335 (1988)

    Google Scholar 

  44. Forre, R.: The strict avalanche criterion: spectral properties of Boolean functions and an extended definition. In: Advances in Cryptology—CRYPTO ’88, pp. 450–468 (1988)

    Google Scholar 

  45. Meier, W., Staffelbach, O.: Nonlinearity criteria for cryptographic functions. In: Advances in Cryptology—EUROCRYPT ’89, pp. 549–562 (1989)

    Google Scholar 

  46. Pieprzyk, J.: Error propagation property and application in cryptography. IEEE Proc., Part E 136(4), 262–270 (1989)

    Google Scholar 

  47. Pieprzyk, J., Finkelstein, G.: Permutations that maximize non-linearity and their cryptographic significance. In: Computer Security in the Age of Information, pp. 63–74 (1989)

    Google Scholar 

  48. Pieprzyk, J.: Non-linearity of exponent permutations. In: Advances in Cryptology—EUROCRYPT ’89, pp. 80–92 (1989)

    Google Scholar 

  49. Lloyd, S.: Properties of binary functions. In: Advances in Cryptology—EUROCRYPT ’90, pp. 124–139 (1990)

    Google Scholar 

  50. Nyberg, K.: Perfect nonlinear S-boxes. In: Advances in Cryptology—EUROCRYPT ’91, pp. 378–386 (1991)

    Google Scholar 

  51. Dawson, M., Tavares, S.: An expanded set of S-box design criteria based on information theory and its relation to differential-like attacks. In: Advances in Cryptology—EUROCRYPT ’91, pp. 353–367 (1991)

    Google Scholar 

  52. Sivabalan, M., Tavares, S., Peppard, L.: On the design of SP networks from an information theoretic point of view. In: Advances in Cryptology—CRYPTO ’92, pp. 260–279 (1992)

    Google Scholar 

  53. Adams, C.: On immunity against Biham and Shamir’s “differential cryptanalysis”. Inf. Process. Lett. 41, 77–80 (1992)

    Article  MATH  Google Scholar 

  54. Cusick, T.: Boolean functions satisfying a higher order strict avalanche criterion. In: Advances in Cryptology—EUROCRYPT ’93, pp. 102–117 (1993)

    Google Scholar 

  55. O’Connor, L.: On the distribution of characteristics in bijective mappings. In: Advances in Cryptology—EUROCRYPT 93, pp. 360–370 (1993)

    Google Scholar 

  56. Daemen, J., Govaerts, R., Vandewalle, J.: Correlation Matrices. Fast Software Encryption. Lecture Notes in Computer Science (LNCS), vol. 1008, pp. 275–285. Springer, Berlin (1994)

    Book  Google Scholar 

  57. Youssef, A., Tavares, S., Mister, S., Adams, C.: Linear approximation of injective S-boxes. IEE Electron. Lett. 31(25), 2168–2169 (1995)

    Article  Google Scholar 

  58. Youssef, A., Tavares, S.: Resistance of balanced S-boxes to linear and differential cryptanalysis. Inf. Process. Lett. 56, 249–252 (1995)

    Article  MATH  Google Scholar 

  59. Vaudenay, S.: An experiment on DES statistical cryptanalysis. In: 3rd ACM Conference on Computer and Communications Security, pp. 139–147. ACM, New York (1996)

    Google Scholar 

  60. Xu, J., Heys, H.M.: A new criterion for the design of 8∗8 S-boxes in private-key ciphers, 0-7803-3716-6/97 IEEE (1997)

  61. Biham, E.: Cryptanalysis of Patarin’s 2 Round public key system with S-boxes. Technical report CS-2000-01-2000, Technion, Computer science department

  62. Tang, G., Liao, X., Chen, Y.: A novel method for designing S-boxes based on chaotic maps. Chaos Solitons Fractals 23, 413–419 (2005)

    Article  MATH  Google Scholar 

  63. Liu, J., Wei, B., Cheng, X., Wang, X.: An AES S-box to increase complexity and cryptographic analysis. In: Proceedings of the 19th International Conference on Advanced Information Networking and Applications (AINA’05), 1550-445X/05 (2005)

    Google Scholar 

  64. Sakalauskas, E., Luksys, K.: Matrix power S-box construction. Cryptology ePrint Archive: Report, no. 214 (2007). http://eprint.iacr.org/2007/214

  65. Aslan, B., Sakallı, M.T., Bulu¸s, E.: Classifying 8-bit to 8-bit S-boxes based on power mappings from the point of DDT and LAT distributions. In: International Workshop on the Arithmetic of Finite Fields, WAIFI 2008. Lecture Notes in Computer Science, vol. 5130, pp. 123–133. Springer, Siena (2008)

    Chapter  Google Scholar 

  66. Chen, H., Feng, D.: An effective genetic algorithm for self-inverse S-boxes. Int. Conf. Comput. Intell. Secur. (2007). doi:10.1109/CIS.2007.51

    Google Scholar 

  67. Cui, L., Cao, Y.: A new S-box structure named affine-power-affine. Int. J. Innov. Comput., Inf. Control 3(3), 751–759 (2007)

    Google Scholar 

  68. Nalini, C., Anandmohan, P.V., Poornaiah, D.V., Kulkarni, V.D.: Optimized S-box design for AES core. In: IET UK International Conference on Information and Communication Technology in Electrical Sciences, pp. 843–849 (2007)

    Google Scholar 

  69. Ghosh, S., Alam, M., Kumar, K., Mukhopadhyay, D., Chowdhury, D.R.: Preventing the side-channel leakage of masked AES S-box. In: 15th International Conference on Advanced Computing and Communications (2007). doi:10.1109/ADCOM.2007.63

    Google Scholar 

  70. Chen, G., Chen, Y., Liao, X.: An extended method for obtaining S-boxes based on three-dimensional chaotic Baker maps. Chaos Solitons Fractals 31, 571–579 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  71. Qiu, J., Liao, X., Wang, P.: A method to construct dynamic S-box based on chaotic map. In: Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing. IEEE Press, New York (2007). doi:10.1109/SNPD.2007.317

    Google Scholar 

  72. Nawaz, Y., Gupta, K.C., Gong, G.: Algebraic immunity of S-boxes based on power mappings, analysis and construction. IEEE Trans. Inf. Theory 55(9), 4263–4273 (2009)

    Article  MathSciNet  Google Scholar 

  73. Chen, J.H., Huang, S.J., Lin, W.C., Lu, Y.K., Shieh, M.D.: Exploration of low-cost configurable S-box designs for AES applications. In: Proc. the Fifth International Conference on Embedded Software and Systems, pp. 422–428 (2008)

    Google Scholar 

  74. Tran, M.T., Bui, D.K., Duong, A.D.: S-box for advanced encryption standard. In: Proc. of International Conference on Computational Intelligence and Security, vol. 1, pp. 253–258 (2008)

    Google Scholar 

  75. Zarina, S., Naziri, M., Idris, N.: The memory-less method of generating multiplicative inverse values for S-box in AES algorithm. In: International Conference on Electronic Design, Malaysia, pp. 1–3 (2008)

    Google Scholar 

  76. Zhang, R., Chen, L.: A block cipher using key-dependent S-box and P-boxes. In: Industrial Electronics, ISIE 2008. IEEE International Symposium, pp. 1463–1468 (2008)

    Chapter  Google Scholar 

  77. Szaban, M., Seredynski, F.: Cryptographically strong S-boxes based on cellular automata. Lecture Notes on Computer Science, vol. 5191, pp. 478–485. Springer, Berlin (2008)

    Book  Google Scholar 

  78. Lineham, A., Gulliver, T.A.: Heuristic S-box design. Contemp. Eng. Sci. 1(4), 147–168 (2008)

    Google Scholar 

  79. Wang, Y., Xie, Q.: A software for S-box performance analysis and test. In: International Conference on Electronic Commerce and Business Intelligence, pp. 125–128 (2009)

    Chapter  Google Scholar 

  80. Maingot, V., Leveugle, R.: Influence of error detecting or correcting codes on the sensitivity to DPA of an AES S-box. In: International Conference on Signals, Circuits and Systems, pp. 1–5 (2009)

    Google Scholar 

  81. Kermani, M.M., Masoleh, A.R.: A low-cost S-box for the advanced encryption standard using normal basis. In: International Conference on Electro/Information Technology, pp. 52–55 (2009)

    Google Scholar 

  82. Tran, B.N., Nguyen, T.D., Tran, T.D.: A new S-box structure to increase complexity of algebraic expression for block cipher cryptosystems. In: International Conference on Computer Technology and Development, pp. 212–216 (2009)

    Google Scholar 

  83. Tran, B.N., Nguyen, T.D., Tran, T.D.: A new S-box structure based on graph isomorphism. In: International Conference on Computational Intelligence and Security, pp. 463–467 (2009)

    Google Scholar 

  84. Xiangyang, X.U.: A new genetic algorithm and tabu search for S-box optimization. International Conf. Comput. Des. Appl. (ICCDA) 26(9), 2169–2171 (2010)

    Google Scholar 

  85. Yuan, H., Luo, L., Wang, Y.: An S-Box Construction Algorithm Based on Spatiotemporal Chaos. In: International Conference on Communications and Mobile Computing. IEEE Press, New York (2010). doi:10.1109/CMC.2010.48

    Google Scholar 

  86. Yang, M., Wang, Z., Meng, Q., Han, L.: Evolutionary design of S-box with cryptographic properties. In: Ninth IEEE International Symposium on Parallel and Distributed Processing with Applications Workshops, pp. 12–15 (2011)

    Google Scholar 

  87. Wong, M.M., Wong, M.L.D., Hijazin, I., Nandi, A.K.: Composite field GF(((22)2)2) AES S-box with direct computation in GF(24) inversion. In: 7th International Conference on IT in Asia (CITA), pp. 1–6 (2011)

    Google Scholar 

  88. Shi, H., Deng, Y., Guan, Y.: Analysis of the avalanche effect of the AES S-box. In: Ninth IEEE International Symposium on Parallel and Distributed Processing with Applications Workshops, pp. 5425–5428 (2011)

    Google Scholar 

  89. Peng, J., Zhang, D., Liao, X.: A method for designing dynamical S-boxes based on hyperchaotic Lorenz system. In: Proc. 10th IEEE I.C. on Cognitive Informatics & Cognitive Computing (ICCI CC 11), pp. 304–309 (2011)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Quaid-i-Azam University, Islamabad, Pakistan

    Iqtadar Hussain & Tariq Shah

Authors
  1. Iqtadar Hussain
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tariq Shah
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Iqtadar Hussain.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hussain, I., Shah, T. Literature survey on nonlinear components and chaotic nonlinear components of block ciphers. Nonlinear Dyn 74, 869–904 (2013). https://doi.org/10.1007/s11071-013-1011-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11071-013-1011-8

Keywords

Search

Navigation