Skip to main content
placeholder image

Pitfalls in designing substitution boxes

Chapter


Abstract


  • Two significant recent advances in cryptanalysis, namely the differential attack put forward by Biham and Shamir [3] and the linear attack by Matsui [7, 8] have had devastating impact on data encryption algorithms. An eminent problem that researchers are facing is to design S-boxes or substitution boxes so that an encryption algorithm that employs the S-boxes is immune to the attacks. In this paper we present evidence indicating that there are many pitfalls on the road to achieve the goal. In particular, we show that certain types of S-boxes which are seemly very appealing do not exist. We also show that, contrary to previous perception, techniques such as chopping or repeating permutations do not yield cryptographically strong S-boxes. In addition, we reveal an important combinatorial structure associated with certain quadratic permutations, namely, the dfference distribution table of each differentially 2-uniform quadratic permutation embodies a Hadamard matrix. As an application of this result, we show that chopping a differentially 2-uniform quadratic permutation results in an S-box that is very prone to the differential cryptanalytic attack.

Publication Date


  • 1994

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1994). Pitfalls in designing substitution boxes. In Unknown Book (Vol. 839 LNCS, pp. 383-396). doi:10.1007/3-540-48658-5_35

International Standard Book Number (isbn) 13


  • 9783540583332

Scopus Eid


  • 2-s2.0-85025579661

Web Of Science Accession Number


Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 383

End Page


  • 396

Abstract


  • Two significant recent advances in cryptanalysis, namely the differential attack put forward by Biham and Shamir [3] and the linear attack by Matsui [7, 8] have had devastating impact on data encryption algorithms. An eminent problem that researchers are facing is to design S-boxes or substitution boxes so that an encryption algorithm that employs the S-boxes is immune to the attacks. In this paper we present evidence indicating that there are many pitfalls on the road to achieve the goal. In particular, we show that certain types of S-boxes which are seemly very appealing do not exist. We also show that, contrary to previous perception, techniques such as chopping or repeating permutations do not yield cryptographically strong S-boxes. In addition, we reveal an important combinatorial structure associated with certain quadratic permutations, namely, the dfference distribution table of each differentially 2-uniform quadratic permutation embodies a Hadamard matrix. As an application of this result, we show that chopping a differentially 2-uniform quadratic permutation results in an S-box that is very prone to the differential cryptanalytic attack.

Publication Date


  • 1994

Citation


  • Seberry, J., Zhang, X. M., & Zheng, Y. (1994). Pitfalls in designing substitution boxes. In Unknown Book (Vol. 839 LNCS, pp. 383-396). doi:10.1007/3-540-48658-5_35

International Standard Book Number (isbn) 13


  • 9783540583332

Scopus Eid


  • 2-s2.0-85025579661

Web Of Science Accession Number


Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 383

End Page


  • 396