Abstract
We present cryptanalytic results of an exhaustive search of all 16! bijective 4-bit S-Boxes. Previously affine equivalence classes have been exhaustively analyzed in 2007 work by Leander and Poschmann. We extend on this work by giving further properties of the optimal S-Box linear equivalence classes. In our main analysis we consider two S-Boxes to be cryptanalytically equivalent if they are isomorphic up to the permutation of input and output bits and a XOR of a constant in the input and output. We have enumerated all such equivalence classes with respect to their differential and linear properties. These equivalence classes are equivalent not only in their differential and linear bounds but also have equivalent algebraic properties, branch number and circuit complexity. We describe a “golden” set of S-boxes that have ideal cryptographic properties. We also present a comparison table of S-Boxes from a dozen published cryptographic algorithms.
Chapter PDF
Similar content being viewed by others
References
Anderson, R., Biham, E., Knudsen, L.: Serpent: A Proposal for the Advanced Encryption Standard (1999), http://www.cl.cam.ac.uk/~rja14/Papers/serpent.pdf
Adams, C., Tavares, S.: The Structured Design of Cryptographically Good S-Boxes. Journal of Cryptology 3(1), 27–41 (1990)
Biham, E.: A Fast New DES Implementation in Software. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 260–272. Springer, Heidelberg (1997)
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)
Biham, E., Shamir, A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, Heidelberg (1993)
Biryukov, A., De Cannière, C., Braeken, A., Preneel, B.: A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 33–50. Springer, Heidelberg (2003)
Biryukov, A., De Cannière, C., Quisquater, M.: On Multiple Linear Approximations. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 1–22. Springer, Heidelberg (2004)
Blondeau, C., Gérard, B.: Multiple Differential Cryptanalysis: Theory and Practice. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 35–54. Springer, Heidelberg (2011)
Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., 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)
Branstad, D.K., Gait, J., Katzke, S.: Report of the Workshop on Cryptography in Support of Computer Security. Tech. Rep. NBSIR 77-1291, National Bureau of Standards (September 1976)
Coppersmith, D.: The Data Encryption Standard (DES) and its strength against attacks. IBM Journal of Research and Development Archive 38(3) (May 1994)
Daemen, J., Peeters, M., Van Assche, G., Rijmen, V.: Nessie Proposal: NOEKEON. NESSIE Proposal (October 27, 2000)
Denning, D.: The Data Encryption Standard – Fifteen Years of Public Scrutiny. In: Distinguished Lecture in Computer Security, Sixth Annual Computer Security Applications Conference, Tucson, December 3-7 (1990)
Dolmatov, V. (ed.): GOST 28147-89: Encryption, Decryption, and Message Authentication Code (MAC) Algorithms. Internet Engineering Task Force RFC 5830 (March 2010)
De Cannière, C., Sato, H., Watanabe, D.: Hash Function Luffa - Specification Ver. 2.0.1. NIST SHA-3 Submission, Round 2 document (October 2, 2009)
Courtois, N.T., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Dinur, I., Shamir, A.: Cube Attacks on Tweakable Black Box Polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer, Heidelberg (2009)
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.) RLCPS, WECSR, and WLC 2010. LNCS, vol. 6054, pp. 3–18. Springer, Heidelberg (2010)
Engels, D., Saarinen, M.-J.O., Schweitzer, P., Smith, E.M.: The Hummingbird-2 Lightweight Authenticated Encryption Algorithm. In: RFIDSec 2011, The 7th Workshop on RFID Security and Privacy, Amherst, Massachusetts, USA, June 26-28 (2011)
Feistel, H.: Block Cipher Cryptographic System. U.S.Patent 3,798,359 (Filed June 30, 1971)
Hermelin, M., Nyberg, K.: Dependent Linear Approximations: The Algorithm of Biryukov and Others Revisited. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 318–333. Springer, Heidelberg (2010)
Golomb, S.: On the classification of Boolean functions. IEEE Transactions on Information Theory 5(5), 176–186 (1959)
Government Committee of the USSR for Standards. Cryptographic Protection for Data Processing System. GOST 28147-89, Gosudarstvennyi Standard of USSR (1989) (in Russian)
Government Committee of the Russia for Standards. Information technology. Cryptographic Data Security. Hashing function. GOST R 34.11-94, Gosudarstvennyi Standard of Russian Federation (1994) (in Russian)
Hiltgen, A.P.: Constructions of Feebly-One-Way Families of Permutations. In: Zheng, Y., Seberry, J. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 422–434. Springer, Heidelberg (1993)
Hiltgen, A.P.: Towards a Better Understanding of One-Wayness: Facing Linear Permutations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 319–333. Springer, Heidelberg (1998)
Hirsch, E.A., Nikolenko, S.I.: A Feebly Secure Trapdoor Function. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) CSR 2009. LNCS, vol. 5675, pp. 129–142. Springer, Heidelberg (2009)
Intel: Intel Advanced Vector Extensions Programming Reference. Publication 319433-010, Intel (April 2011)
Kaliski Jr., B.S., Robshaw, M.J.B.: Linear Cryptanalysis Using Multiple Approximations. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 26–39. Springer, Heidelberg (1994)
Küçük, Ö.: The Hash Function Hamsi. NIST SHA-3 Submission, Round 2 document (September 14, 2009)
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)
Matsui, M.: Linear Cryptanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
National Bureau of Standards: Data Encryption Standard. FIPS PUB 46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C. (January 15, 1977)
Poschmann, A.: Lightweight Cryptography - Cryptographic Engineering for a Pervasive World. Doktor-Ingenieur Thesis, Ruhr-University Bochum, Germany. Also available as Cryptology ePrint Report 2009/516 (2009)
Saarinen, M.-J.O.: Chosen-IV Statistical Attacks Against eSTREAM CIPHERS. In: Proc. SECRYPT 2006, International Conference on Security and Cryptography, Setubal, Portugal, August 7-10 (2006)
Shannon, C.E.: Communication Theory of Secrecy Systems. Bell System Technical Journal 28, 656–717 (1949)
Sorkin, A.: Lucifer: A cryptographic algorithm. Cryptologia 8(1), 22–42 (1984)
Standaert, F.-X., Piret, G., Rouvroy, G., Quisquater, J.-J., Legat, J.-D.: ICEBERG: An Involutional Cipher Efficient for Block Encryption in Reconfigurable Hardware. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 279–299. Springer, Heidelberg (2004)
Ullrich, M., De Cannière, C., Indesteege, S., Kü¸, Ö., Mouha, N., Preneel, B.: Finding Optimal Bitsliced Implementations of 4 ×4-bit S-Boxes. In: SKEW 2011 Symmetric Key Encryption Workshop, Copenhagen, Denmark, February 16-17 (2011)
Wegener, I.: The complexity of Boolean functions. WileyTeubner series in computer science. Wiley, Teubner (1987)
Wu, H.: The Hash Function JH. NIST SHA-3 Submission, Round 3 document (January 16, 2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saarinen, MJ.O. (2012). Cryptographic Analysis of All 4 × 4-Bit S-Boxes. In: Miri, A., Vaudenay, S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28496-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-28496-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28495-3
Online ISBN: 978-3-642-28496-0
eBook Packages: Computer ScienceComputer Science (R0)