A New Cryptographic Analysis of 4-bit S-Boxes

Ling Cheng¹⁶,
Wentao Zhang¹⁶ &
Zejun Xiang¹⁶

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 9589))

Included in the following conference series:

International Conference on Information Security and Cryptology

1022 Accesses

Abstract

An exhaustive search of all 16! bijective 4-bit S-boxes has been conducted by Markku-Juhani et al. (SAC 2011). In this paper, we present an improved exhaustive search over all permutation-xor equivalence classes. We put forward some optimizing strategies and make some improvements on the basis of their work. For our program, it only takes about one-sixth of the time of the experiment by Markku-Juhani et al. to get the same results. Furthermore, we classify all those permutation-xor equivalence classes in terms of a new classification criterion, which has been come up with by Wentao Zhang et al. (FSE 2015). For some special cases, we calculate the distributions of permutation-xor equivalence classes with respect to their differential bound and linear bound. It turns out that only in three special cases, there exist S-boxes having a minimal differential bound $p=1/4$ and a minimal linear bound $\epsilon =1/4$, which imply the optimal S-boxes.

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

Access this chapter

Subscribe and save

Springer+ Basic

$34.99 /Month

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Buy Now

Chapter: USD 29.95; Price excludes VAT (USA)

eBook: USD 39.99; Price excludes VAT (USA)

Softcover Book: USD 54.99; Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

A New Classification of 4-bit Optimal S-boxes and Its Application to PRESENT, RECTANGLE and SPONGENT

On the Evolution of Boomerang Uniformity in Cryptographic S-boxes

An STP-based model toward designing S-boxes with good cryptographic properties

Article 02 April 2022

References

Feistel, H.: Block Cipher Cryptographic System. U.S. Patent 3,798,359, Filed 30 June 1971
Google Scholar
Ben-Aroya, I., Biham, E.: Differential cryptanalysis of lucifer. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 187–199. Springer, Heidelberg (1994)
Chapter Google Scholar
National Bureau of Standards: Data Encryption Standard. FIPS PUB 46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., 15 January 1977
Google Scholar
Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991)
Google Scholar
Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002)
Book MATH Google Scholar
Yamamoto, D., Hospodar, G., Maes, R., Verbauwhede, I.: Performance and security evaluation of AES S-box-based glitch PUFs on FPGAs. In: Bogdanov, A., Sanadhya, S. (eds.) SPACE 2012. LNCS, vol. 7644, pp. 45–62. Springer, Heidelberg (2012)
Chapter Google Scholar
Moradi, A., Poschmann, A., Ling, S., Paar, C., Wang, H.: Pushing the limits: a very compact and a threshold implementation of AES. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 69–88. Springer, Heidelberg (2011)
Chapter Google Scholar
Engels, D., Fan, X., Gong, G., Hu, H., Smith, E.M.: Hummingbird: ultra-lightweight cryptography for resource-constrained devices. In: Sion, R., Curtmola, R., Dietrich, S., Kiayias, A., Miret, J.M., Sako, K., Sebé, F. (eds.) FC 2010 Workshops. LNCS, vol. 6054, pp. 3–18. Springer, Heidelberg (2010)
Chapter Google Scholar
Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007)
Chapter Google Scholar
Bogdanov, A., Knežević, M., Leander, G., Toz, D., Varıcı, K., Verbauwhede, I.: spongent: a lightweight hash function. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 312–325. Springer, Heidelberg (2011)
Chapter Google Scholar
Zhang, W., Bao, Z., Lin, D., Rijmen, V., Yang, B., Verbauwhede, I.: RECTANGLE: A Bit-slice Ultra-Lightweight Block Cipher Suitable for Multiple Platforms. Cryptology ePrint Archive: Report 2014/084. http://eprint.iacr.org/2014/084
Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED block cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011)
Chapter Google Scholar
Wu, W., Zhang, L.: LBlock: a lightweight block cipher. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 327–344. Springer, Heidelberg (2011)
Chapter Google Scholar
Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222–239. Springer, Heidelberg (2011)
Chapter Google Scholar
Borghoff, J., et al.: PRINCE – a low-latency block cipher for pervasive computing applications. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 208–225. Springer, Heidelberg (2012)
Chapter Google Scholar
Albrecht, M.R., Driessen, B., Kavun, E.B., Leander, G., Paar, C., Yalçın, T.: Block ciphers – focus on the linear layer (feat. PRIDE). In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 57–76. Springer, Heidelberg (2014)
Chapter Google Scholar
Leander, G., Poschmann, A.: On the classification of 4 bit S-boxes. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 159–176. Springer, Heidelberg (2007)
Chapter Google Scholar
Saarinen, M.-J.O.: Cryptographic analysis of all 4 $\times $ 4-bit S-boxes. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 118–133. Springer, Heidelberg (2012)
Google Scholar
Zhang, W., Bao, Z., Rijmen, V., Liu, M.: A new classification of 4-bit optimal S-boxes and its application to PRESENT, RECTANGLE and SPONGENT. In: FSE 2015. Cryptology ePrint Archive: Report 2015/433 (2015)
Google Scholar
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Chapter Google Scholar
Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. In: Carlet, C., Charpin, P., Zinoviev, V. (eds.) Designs, Codes and Cryptography, vol. 15, pp. 125–156. Springer, Heidelberg (1998)
Google Scholar
Nyberg, K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)
Chapter Google Scholar

Download references

Acknowledgements

The research presented in this paper is supported by the National Natural Science Foundation of China (No. 61379138), and the “Strategic Priority Research Program” of the Chinese Academy of Sciences (No. XDA06010701).

Author information

Authors and Affiliations

State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
Ling Cheng, Wentao Zhang & Zejun Xiang

Authors

Ling Cheng
View author publications
You can also search for this author in PubMed Google Scholar
Wentao Zhang
View author publications
You can also search for this author in PubMed Google Scholar
Zejun Xiang
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ling Cheng .

Editor information

Editors and Affiliations

Chinese Academy of Sciences, SKLOIS Institute of Engineering, Beijing, China
Dongdai Lin
Center for Security Informatics, Indiana University at Bloomington, Indiana, USA
XiaoFeng Wang
Computer Science, Columbia University, New York, New York, USA
Moti Yung

Appendix A

See Tables 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and 14

Table 4. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =0 , \mathop {\mathrm {CarL1_S}}\nolimits =2$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 5. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =0 , \mathop {\mathrm {CarL1_S}}\nolimits =3$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 6. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =0 , \mathop {\mathrm {CarL1_S}}\nolimits =4$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 7. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =1 , \mathop {\mathrm {CarL1_S}}\nolimits =1$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 8. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =1 , \mathop {\mathrm {CarL1_S}}\nolimits =2$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 9. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =1 , \mathop {\mathrm {CarL1_S}}\nolimits =3$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 10. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =2 , \mathop {\mathrm {CarL1_S}}\nolimits =0$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 11. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =2 , \mathop {\mathrm {CarL1_S}}\nolimits =1$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 12. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =2 , \mathop {\mathrm {CarL1_S}}\nolimits =2$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 13. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =3 , \mathop {\mathrm {CarL1_S}}\nolimits =1$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Table 14. Distribution of S-boxes with $\mathop {\mathrm {CarD1_S}}\nolimits =4 , \mathop {\mathrm {CarL1_S}}\nolimits =0$ in relation to differential bound p and linear bound $\epsilon $

Full size table

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper

Cheng, L., Zhang, W., Xiang, Z. (2016). A New Cryptographic Analysis of 4-bit S-Boxes. In: Lin, D., Wang, X., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2015. Lecture Notes in Computer Science(), vol 9589. Springer, Cham. https://doi.org/10.1007/978-3-319-38898-4_9

Download citation

DOI: https://doi.org/10.1007/978-3-319-38898-4_9
Published: 07 May 2016
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-38897-7
Online ISBN: 978-3-319-38898-4
eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

A New Cryptographic Analysis of 4-bit S-Boxes

Abstract

Access this chapter

Subscribe and save

Buy Now

Similar content being viewed by others

A New Classification of 4-bit Optimal S-boxes and Its Application to PRESENT, RECTANGLE and SPONGENT

On the Evolution of Boomerang Uniformity in Cryptographic S-boxes

An STP-based model toward designing S-boxes with good cryptographic properties

References

Acknowledgements

Author information

Authors and Affiliations

Corresponding author

Editor information

Editors and Affiliations

Appendix A

Appendix A

Rights and permissions

Copyright information

About this paper

Cite this paper

Download citation

Share this paper

Publish with us