A Review of Existing 4-Bit Crypto S-Box Cryptanalysis Techniques and Two New Techniques with 4-Bit Boolean Functions for Cryptanalysis of 4-Bit Crypto S-Boxes* — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
A Review of Existing 4-Bit Crypto S-Box Cryptanalysis Techniques and Two New Techniques with 4-Bit Boolean Functions for Cryptanalysis of 4-Bit Crypto S-Boxes*
Institute of Radio Physics and Electronics, University of Calcutta, Kolkata, India
,
Institute of Radio Physics and Electronics, University of Calcutta, Kolkata, India
1 Institute of Radio Physics and Electronics, University of Calcutta, Kolkata, India
2 Institute of Radio Physics and Electronics, University of Calcutta, Kolkata, India
4-bit linear relations play an important role in cryptanalysis of 4-bit crypto S-boxes. 4-bit finite differences have also been a major part of cryptanalysis of 4-bit S-boxes. Existence of all 4-bit linear relations have been counted for all of 16 input and 16 output 4-bit bit patterns of 4-bit Crypto S-boxes said as S-boxes has been reported in Linear Cryptanalysis of 4-bit S-boxes. Count of existing finite differences from each element of output S-boxes to distant output S-boxes have been noted in Differential Cryptanalysis of S-boxes. In this paper a brief review of these two cryptanalytic methods for 4-bit S-boxes has been introduced in a very lucid and conceptual manner. Two new analysis techniques, one to search for the existing linear approximations among the input vectors (IPVs) and output Boolean functions (BFs) of a particular S-box has also been introduced in this paper. The search is limited to find the existing linear relations or approximations in the contrary to count the number of existent linear relations among all 16, 4-bit input and output bit patterns within all possible linear approximations. Another is to find number of balanced BFs in difference output S-boxes. Better the number of Balanced BFs, Better the security.
Feistel, H. (1971) Block Cipher Cryptographic System. US Patent 3798359.
Carlisle, A. and Stafford, T. (1990) The Structured Design of Cryptographically Good S-Boxes. Journal of Cryptology, 3, 27-41.
Heys, H.M. and Tavares, S.E. (1996) Substitution-Permutation Networks Resistant to Differential and Linear Cryptanalysis. Journal of Cryptology, 9, 1-19.
Heys, H.M. (2002) A Tutorial on Linear and Differential Cryptanlysis. Cryptologia, 26, 189-221.
Menezes A., van Oorschot P. and Vanstone S. (1996) Handbook of Applied Cryptography. CRC Press, Boca Raton, FL.
Schneier, B. (1996) Applied Cryptography. Second Edition, John Wiley and Sons, Hoboken, NJ.
Schaefer, E. (1996) A Simplified Data Encryption Standard Algorithm. Cryptologia, 20, 77-84. https://doi.org/10.1080/0161-119691884799
Schneier, B. (2000) A Self-Study Course in Block-Cipher Cryptanalysis. Cryptologia, 24, 18-34
Schneier, B., et al. (1999) The Twofish Encryption Algorithm. John Wiley and Sons, Hoboken, NJ.
Mirzan, F. (2000) Block Ciphers and Cryptanalysis. Department of Mathematics, Royal Holloway University of London, Egham.
Heys, H.M. (2000) A Tutorial on Linear and Differential Cryptanalysis. Memorial University of Newfoundland, Canada.
Schulzrinne, H. (2000) Network Security: Secret Key Cryptograph. Columbia University, New York.
Pierson, L.G. (2000) Comparing Cryptographic Modes of Operation Using Flow Diagrams. Sandia National Laboratories, Albuquerque, NM; Livermore, CA.
Aoki, K., et al. (2000) Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms. NTT Coporation and Mitsubishi Electric Corporation, Tokyo.
Singh, S. (2001) The Science of Secrecy. Fourth Estate Limited, Sydney.
Landau, S. (2000) Standing the Test of Time: The Data Encryption Standard. Sun Microsystems, Menlo Park, CA.
Garrett, P. (2001) Making, Breaking Codes. Prentice Hall, Upper Saddle River, NJ.
Kilian, J. and Rogaway, P. (2001) How to Protect DES against Exhaustive Key Search. NEC Research Institute, Irving, TX.
Yeun, C.Y. (2000) Design Analysis and Applications of Cryptographic Techniques. Department of Mathematics, Royal Holloway University of London, Egham.
Schneier, B. (2001) Why Cryptography Is Harder than It Looks. Counterpane Internet Security, USA.
Habib, S.N., Awan, R. and Haider, W. (2017) A Modified Simplified Data Encryption Standard Algorithm. International Journal of Computer Science and Software Engineering (IJCSSE), 6, No. 7.
Ooi, K.S. and Vito, B.C. (2002) Cryptanalysis of S-DES. University of Sheffield Center, Taylor College, UK.
Aparna, K., Solomon, J., Harini, M. and Indhumathi, V. (2016) A Study of Twofish Algorithm. IJEDR, 4, No. 2.
Buttayan, L. and Vajda, I. (1995) Searching for Best Linear Approximation on DES-Like Cryptosystems. Electronics Letters, 31, 873-874.
Daemen, J., Govaerts, R. and vandewalle, J. (1995) Correlation Matrices. In: Preneel, B., Ed., Fast Software Encryption, Lecture Notes in Computer Science (LNCS) 1008, Springer, Berlin, 2-21.
Matsui, M. (1994) Linear Cryptanalysis Method for DES Cipher. Eurocrypt, 765, 386-397.
Biham, E. (1994) On Matsui’s Linear Cryptnalysis. Technion, Israel Institute of Technology, Israel.
Harpes, C., Kramer, G. and Massey, J. (1995) A Generation of Linear Cryptanalysis and the Applicability of Matsui’s Pilling-Up Lemma. In: Guillou, L.C. and Quisqater, J.-J., Eds., Advances in Cryptology—Eurocrypt’95, Springer, Berlin, 24-38.
Kaliski, B. and Robshaw, M. (1994) Linear Cryptanalysis Using Multiple Approximations. In: Desmedt, Y.G., Ed., Advances in Cryptology—CRYPTO’94, Springer, Berlin, 26-39.
Matsui, M. (1994) The First Experimental Cryptanalysis of Data Encryption Standard. In: Desmedt, Y.G., Ed., Advances in Cryptology—CRYPTO’94, Springer, Berlin, 1-11.
Junod, P.A. (1998) Linear Cryptanalysis of DES. Eidgenssische Tenhcische Hochsschule, Zurich.
Collard, B., Standaert, F.X. and Quisquater, J.J. (2008) Experiments on the Multiple Linear Cryptanalysis of Reduced Round Serpent. In: Nyberg K., Ed., Fast Software Encryption. FSE 2008. Lecture Notes in Computer Science, Vol. 5086, Springer, Berlin.
Mouha, N., Wang, Q., Gu, D. and Preneel, B. (2012) Differential and Linear Cryptanalysis Using Mixed-Integer Linear Programming. In: Wu, C.K., Yung, M. and Lin, D., Eds., Information Security and Cryptology. Inscrypt 2011. Lecture Notes in Computer Science, Vol. 7537, Springer, Berlin. https://doi.org/10.1007/978-3-642-34704-7_5
Abdelraheem, M.A., Alizadeh, J., AlKhzaimi, H., Aref, M.R., Bagheri, N. and Gauravaram, P. (2015) Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48. Cryptology e-Print Archive, Report-2015/988.
Bagheri, N. (2015) Linear Cryptanalysis of Reduced-Round SIMECK Variants. In: Biryukov, A. and Goyal, V., Eds., Progress in Cryptology—INDOCRYPT 2015. Lecture Notes in Computer Science, Vol. 9462, Springer, Cham. https://doi.org/10.1007/978-3-319-26617-6_8
Yu, X.L., Wu, W.L., Shi, Z.Q., et al. (2015) Zero-Correlation Linear Cryptanalysis of Reduced-Round SIMON. Journal of Computer Science and Technology, 30, 1358. https://doi.org/10.1007/s11390-015-1603-5
Canteaut, A. (1997) Differential Cryptanalysis of Fesitel Ciphers and Differentially D-Uniform Mappings. Domaine de Voluceau, Rocquencourt.
Adams, C. (1992) On Immunity against Biham and Shamir’s Differential Cryptanalysis. Information Processing Letters, 41, 77-80.
Dawson, M. and Tavares, S. (1991) An Expanded Set of S-Box Design Criteria Based on Information Theory and Its Relation to Differential-Like Attacks. Advances in Cryptology—EUROCRYPT’91, Springer, Berlin, 353-367.
Biham, E. and Shamir, A. (1990) Differential Cryptanalysis of DES-Like Cryptosystems. In: Menezes, A.J. and Vanstone, S.A., Eds., Advances in Cryptology—CRYPTO’90, Springer, Berlin, 2-21.
Biham, E. and Shamir, A. (1991) Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. Advances in Cryptology—CRYPTO’91, Springer, Berlin, 156-171.
Biham, E. and Shamir, A. (1992) Differential Cryptanalysis of the Full 16-Round DES. In: Brickell, E.F., Ed., Advances in Cryptology—CRYPTO’92, Springer, Berlin, 487-496.
Nyberg, K. (1991) Perfect Nonlinear S-Boxes. Advances in Cryptology—EUROCRYPT’91, Springer, Berlin, 378-386.
Lai, X.J. and Massey, J.L. (1991) Markov Ciphers and Differential Cryptanalysis. Swiss Federal Institute of Technology, Royal Holloway University of London, Egham.
Murphy, S. and Robshaw, M.J.B. (2000) Differential Cryptanalysis, Key-Dependant, S-Boxes, and Twofish. https://link.springer.com/article/10.1023/A:1019991004496.
Selcuk, A.A. (2008) On Probability of Success in Linear and Differential Cryptanalysis. Journal of Cryptology, 21, 131. https://doi.org/10.1007/s00145-007-9013-7
Albrecht, M. and Cid, C. (2009) Algebraic Techniques in Differential Cryptanalysis. In: Dunkelman O., Ed., Fast Software Encryption. Lecture Notes in Computer Science, Vol. 5665, Springer, Berlin. https://doi.org/10.1007/978-3-642-03317-9_12
Bouillaguet, C., Dunkelman, O., Fouque, P.A., Leurent, G. (2012) New Insights on Impossible Differential Cryptanalysis. In: Miri, A. and Vaudenay, S., Eds., Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, Vol. 7118, Springer, Berlin. https://doi.org/10.1007/978-3-642-28496-0_15
Rajashekarappa, Sunjiv Soyjaudah, K.M. and Sumithra Devi, K.A. (2013) Comparative Study on Data Encryption Standard Using Differential Cryptanalysis and Linear Cryptanalysis. International Journal of Advances in Engineering & Technology, 6, 158-164.
Gerault, D., Minier, M. and Solnon, C. (2016) Constraint Programming Models for Chosen Key Differential Cryptanalysis. In: Rueher M., Ed., Principles and Practice of Constraint Programming. CP 2016. Lecture Notes in Computer Science, Vol. 9892, Springer, Cham. https://doi.org/10.1007/978-3-319-44953-1_37
Hellman, M. and Langford, S. (1994) Differential-Linear Cryptanalysis. In: Desmedt, Y., Ed., Advances in Cryptology: CRYPTO’94, Springer, Berlin, 26-39.
Vaudenay, S. and Moriai, S. (1994) Comparison of the Randomness Provided by Some AES Candidates. EUROCRYPT 1994, 386-397.
Vaudenay, S. (1994) An Experiment on DES Statistical Cryptanalysis. Ecole Normale Supérieure, Paris.
Gorska, A., et al. (2016) New Experimental Results in Differential-Linear Cryptanalysis of Reduced Variant of DES. Polish Academy of Sciences, Warsaw.
Ferguson, N., et al. (2001) Improved Cryptanalysis of Rijndael. Counterpane Internet Security, USA.
Ding, D. (1993) The Differential Cryptanalysis and Design of Natural Stream Ciphers. Fast Software Encryption, Cambridge Security Workshop, LNCS 809.
Golic, J. (1994) Linear Cryptanalysis of Stream Ciphers. Fast Software Encryption, Second International Workshop, LNCS 1008.
Tanaka, M., Hamaide, T., Hisamatsu, K. and Kaneko, T. (1998) Linear Cryptanalysis by Linear Sieve Method. IECE Transactions on Fundamentals of Electronics, Communications and Computer. Science, E81-A(1), 82-87.
Muller, F. (2004) Differential Attacks against the Helix Stream Cipher. In: Roy, B. and Meier, W., Eds., Fast Software Encryption. FSE 2004. Lecture Notes in Computer Science, Vol. 3017, Springer, Berlin. https://doi.org/10.1007/978-3-540-25937-4_7
Wu, H. and Preneel, B. (2007) Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy. In: Naor, M., Ed., Advances in Cryptology—EUROCRYPT 2007. EUROCRYPT 2007. Lecture Notes in Computer Science, Vol. 4515, Springer, Berlin.
Wu, H., Huang, T., Nguyen, P.H., Wang, H. and Ling, S. (2012) Differential Attacks against Stream Cipher ZUC. In: Wang, X. and Sako, K., Eds., Advances in Cryptology—ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, Vol. 7658, Springer, Berlin. https://doi.org/10.1007/978-3-642-34961-4_17
Webster, A.F. and Tavares, S.E. (1985) On the Design of S-Boxes. In: Williams, H.C., Ed., Advances in Cryptology—CRYPTO’85 Proceedings. CRYPTO 1985. Lecture Notes in Computer Science, Vol. 218, Springer, Berlin. https://doi.org/10.1007/3-540-39799-X_41
Adams, C. and Tavares, S. (1990) The Structured Design of Cryptographically Good S-Boxes. Journal of Cryptology, 3, 27. https://doi.org/10.1007/BF00203967
Kim, K., Matsumoto, T. and Imai, H. (1990) A Recursive Construction Method of S-boxes Satisfying Strict Avalanche Criterion. In: Menezes, A.J. and Vanstone, S.A., Eds., Advances in Cryptology—CRYPTO’90. CRYPTO 1990. Lecture Notes in Computer Science, Vol. 537, Springer, Berlin.
Cusick, T.W. (1994) Boolean Functions Satisfying a Higher Order Strict Avalanche Criterion. In: Helleseth, T., Ed., Advances in Cryptology—EUROCRYPT’93. EUROCRYPT 1993. Lecture Notes in Computer Science, Vol. 765, Springer, Berlin. https://doi.org/10.1007/3-540-48285-7_9
Lisiskaya, I.V., Melnychuk, E.D. and Lisitskiy, K.E. (2012) Importance of S-Blocks in Modern Block Ciphers. International Journal of Communication Networks and Information Security, 10, 1-12.
Saarinen, M.J.O. (2012) Cryptographic Analysis of All 4 × 4-Bit S-Boxes. In: Miri, A. and Vaudenay, S., Eds., Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, Vol. 7118, Springer, Berlin.
Alkhzaimi, H.A. and Knudsen, L.R. (2016) Cryptanalysis of Selected Block Ciphers. Kgs. DTU Compute PHD No. 360. Technical University of Denmark (DTU), Lyngby.
Kazlauskas, K., Smailiukas, R. and Vaicekaus, G. (2016) A Novel Method to Design S-Boxes Based on Key-Dependent Permutation Schemes and Its Quality Analysis. International Journal of Advanced Computer Science and Applications, 7, 93-99.
Ahmad, M., Mittal, N., Garg, P. and Khan, M.M. (2016) Efficient Cryptographic Substitution Box Design Using Travelling Salesman Problem and Chaos. Perspectives in Science, 8, 465-468.
Mazurkov, M.I. and Sokolov, A.V. (2016) Algorithm for Synthesis of Efficient S-Boxes Based on Cellular Automata. Radioelectronics and Communications Systems, 59, 212. https://doi.org/10.3103/S0735272716050034
National Bureau of Standards (1977) Data Encryption Standard, Federal Information Processing Standards Publication (FIPS PUB) 46. National Bureau of Standards, Washington, DC.
National Institute of Standards and Technology (1999) Data Encryption Standard (DES), Federal Information Processing Standards Publication (FIPS PUB) 46-3. National Institute of Standards and Technology, Gaithersburg, MD.