Acta Informatica Pragensia 2017, 6(2), 162-173 | DOI: 10.18267/j.aip.1072258

Vliv nelinearity na vybraná kryptografická kritéria 8x8 S-boxů

Petr Tesař
Department of Computer Science and Mathematics, Faculty of Economic Studies, University of Finance and Administration, Estonská 500, 101 00 Prague 10, Czech Republic

V článku jsou definována standardně používaná kritéria charakterizující kryptografickou kvalitu S boxu: regulárnost, nelinearita, autokorelace, propagace změny a imunita proti diferenční kryptoanalýze. Jsou porovnány hodnoty autokorelace, propagace změny a imunity proti diferenční kryptoanalýze pro regulární 8x8 S boxy s nelinearitou 98, a regulárních 8x8 S boxů s nelinearitou 104. Je statisticky ověřeno, že vyšší nelinearita zlepšuje, v kryptograficky výhodném smyslu, hodnoty těchto kritérií.

Keywords: Kryptografie, regulární 8x8 S-box, kritérium nelinearity, vliv nelinearity na ostatní kryptografická kritéria

Influence of Non-Linearity on Selected Cryptographic Criteria of 8x8 S-Boxes

The article defines standard criteria used to characterize the cryptographic quality of the S box: regularity, non linearity, autocorrelation, avalanche and immunity against differential cryptanalysis. The values of autocorrelation, avalanche and immunity against differential cryptanalysis for regular 8x8 S-boxes with non-linearity 98 and regular 8x8 S-boxes with non linearity 104 are compared. It is statistically verified that higher non-linearity improves the values of these criteria in a cryptographically advantageous sense.

Keywords: Cryptography, Regular 8x8 S-box, Non-linearity criterion, Effect of non-linearity on other cryptographic criteria

Received: March 30, 2017; Revised: September 5, 2017; Accepted: September 17, 2017; Published: December 31, 2017  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Tesař, P. (2017). Influence of Non-Linearity on Selected Cryptographic Criteria of 8x8 S-Boxes. Acta Informatica Pragensia, 6(2), 162-173. doi: 10.18267/j.aip.107
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. Anděl, J. (1978). Matematická statistika. Praha: SNTL.
    2. Biryukov, A. & Perrin, L. (2015). On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure. In CRYPTO 2015 (pp. 116-140). Berlin: Springer. doi: 10.1007/978-3-662-47989-6_6 Go to original source...
    3. Borissov, Y., Boyvalenkov, P. & Tsenkov, R. (2016). On a Linear Cryptanalysis of a Family of Modified DES Ciphers with Even weight S-boxes. Cybernetics and Information Technologies, 16(4), 3-12. doi: 10.1515/cait-2016-0063 Go to original source...
    4. Canright, D. & Batina, L. (2009, January 14). A Very Compact "Perfectly Masked" S-Box for AES (corrected). Retrieved from https://eprint.iacr.org/2009/011.pdf
    5. Canteaut, A., Duval, S. & Leurent, G. (2015). Construction of Lightweight S-Boxes Using Feistel and MISTY Structures. In International Conference on Selected Areas in Cryptography - SAC 2015 (pp. 373-393). Berlin: Springer. doi: 10.1007/978-3-319-31301-6_22 Go to original source...
    6. Carlet, C. & Ding, C. (2007). Nonlinearities of S-boxes. Finite Fields and Their Applications, 13(1), 121-135. doi: 10.1016/j.ffa.2005.07.003 Go to original source...
    7. Carlet, C. (2005). On highly nonlinear S-boxes and their inability to thwart DPA attacks. In International Conference on Cryptology - INDOCRYPT 2005 (pp. 49-62). Berlin: Springer. doi: 10.1007/11596219_5 Go to original source...
    8. Carlet, C. & Ding, C. (2004). Highly nonlinear mappings. Journal of Complexity, 20(2-3), 205-244. doi: 10.1016/j.jco.2003.08.008 Go to original source...
    9. Clark, J. A., Jacob, J. L. & Stepney, S. (2005). The design of S-Boxes by simulated annealing. New Generation Computing, 23(3), 219-231. doi: 10.1007/BF03037656 Go to original source...
    10. Courtois, N.T., Debraize, B. & Garrido, E. (2006). On Exact Algebraic [Non-]Immunity of S-boxes Based on Power Functions. In Australasian Conference on Information Security and Privacy - ACISP 2006 (pp. 76-86). Berlin: Springer. doi: 10.1007/11780656_7 Go to original source...
    11. Cui, L. & Cao, Y. (2007). A New S-Box Structure Named Affine-Power-Affine. International Journal of Innovative Computing, Information and Control, 3(3), 751-759. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.129.8337
    12. Das, S. (2014, January 7). Ultra-lightweight 8-bit Multiplicative Inverse Based S-box Using LFSR. Retrieved from https://eprint.iacr.org/2014/22.pdf
    13. Dawson, M. H. & Tavares, S. E. (1991). An Expanded Set of S-box Design Criteria Based on Information Theory and its Relation to Differential-Like Attacks. In EUROCRYPT '91 (p. 352-367). Berlin: Springer. doi: 10.1007/3-540-46416-6_30 Go to original source...
    14. Farwa, S., Shah, T. & Idrees, L. (2016). A highly nonlinear S-box based on a fractional linear transformation. SpringerPlus, 5, 1658. doi: 10.1186/s40064-016-3298-7 Go to original source...
    15. Ghosal, R. (2017, June 13). Analysing Relations involving small number of Monomials in AES S-Box. Retrieved from https://eprint.iacr.org/2017/580.pdf
    16. Gilbert, H. & Peyrin, T. (2010). Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations. In International Workshop on Fast Software Encryption - FSE 2010 (pp. 365-383). Berlin: Springer. doi: 10.1007/978-3-642-13858-4_21 Go to original source...
    17. Gologlu, F., Rijmen, V. & Wang, Q. (2016, February 23). On the division property of S-boxes. Retrieved from https://eprint.iacr.org/2016/188.pdf
    18. Goudarzi, D., Rivain, M., Vergnaud, D. & Vivek, S. (2017, June 27). Generalized Polynomial Decomposition for S-boxes with Application to Side-Channel Countermeasures. Retrieved from https://eprint.iacr.org/2017/632.pdf
    19. Guo, J., Jean, J., Nikolić, I., Qiao, K., Sasaki, Y. & Sim, S.M. (2016). Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs. IACR Transactions on Symmetric Cryptology, 2016(1), doi: 10.13154/tosc.v2016.i1.33-56 Go to original source...
    20. Guo, X., Xu, K., Sun, T. & Fan, X. (2012). Analysis of Minimum Numbers of Linearly Active S-Boxes of a Class of Generalized Feistel Block Ciphers. Journal of Systems Science and Complexity, 25(5), 1014-1031. doi: 10.1007/s11424-012-0238-7 Go to original source...
    21. Ivanov, G., Nikolov, N. & Nikova, S. (2016). Reversed Genetic Algorithms for Generation of Bijective S-boxes with Good Cryptographic Properties. Cryptography and Communications, 8(2), 247-276. doi: 10.1007/s12095-015-0170-5 Go to original source...
    22. Kazymyrov, O., Kazymyrova, V. & Oliynykov, R. (2014). A Method For Generation Of High-Nonlinear S-Boxes Based On Gradient Descent. Mathematical Aspects of Cryptography, 5(2), 71-78. Go to original source...
    23. Khanoki, H.A., Sadeghiyan, B. & Pieprzyk, J. (2017, January 8). Algebraic Attack Efficiency versus S-box Representation. Retrieved from https://eprint.iacr.org/2017/007.pdf
    24. Leventi-Peetz, A.M. & Peetz, J.V. (2015, July 13). Generating S-Box Multivariate Quadratic Equation Systems And Estimating Algebraic Attack Resistance Aided By SageMath. Retrieved from https://eprint.iacr.org/2015/589.pdf
    25. Mazumdar, B., Mukhopadhyay, D. & Sengupta, I. (2013). Constrained Search for a Class of Good S-Boxes with Improved DPA Resistivity. IEEE Transactions on Information Forensics and Security, 8(12), 2154-2183. doi: 10.1109/TIFS.2013.2285522 Go to original source...
    26. McCluskey, E. J. (1986). Logic design principles. New Jersey: Prentice-Hall
    27. Meloun, M. & Militký, J. (1998). Statistické zpracování experimentálních dat. Praha: East Publishing.
    28. Mishra, P.R., Sarkar,S. & Gupta, I. (2017, April 4). Determining the Minimum Degree of an S-box. Retrieved from https://eprint.iacr.org/2017/376.pdf
    29. Nawaz, Y., Gupta, K.C. & Gong, G. (2009). Algebraic Immunity of S-boxes Based on Power Mappings: Analysis and Construction. IEEE Transactions on Information Theory, 55(9), 4263-4273. doi: 10.1109/TIT.2009.2025534 Go to original source...
    30. Nyberg, K. (1992). On the Construction of Highly Nonlinear Permutations. In EUROCRYPT '92, (pp. 92-98). Berlin: Springer. doi: 10.1007/3-540-47555-9_8 Go to original source...
    31. Parker, M.G. (2003). Generalised S-Box Nonlinearity. Retrieved from http://www.ii.uib.no/~matthew/SBoxLin.pdf
    32. Pieprzyk, J. (1989). Error propagation property and application in cryptography. IEE Proceedings E - Computers and Digital Techniques, 136(4), 262-270. Go to original source...
    33. Rostovtsev, A. (2013, March 12). AES-like ciphers: are special S-boxes better then random ones?. Retrieved from https://eprint.iacr.org/2013/148.pdf
    34. Sakalauskas, E. & Luksys, K. (2007, June 5). Matrix Power S-Box Construction. Retrieved from https://eprint.iacr.org/2007/214.pdf
    35. Selvam, R., Shanmugam, D., Annadurai, S. & Rangasamy, J. (2016). Decomposed S-Boxes and DPA Attacks: A Quantitative Case Study using PRINCE. In International Conference on Security, Privacy, and Applied Cryptography Engineering - SPACE 2016 (pp. 179-193). Berlin: Springer. doi: 10.1007/978-3-319-49445-6_10 Go to original source...
    36. Spain, M. & Varia, M. (2016, October 18). Evolving S-Boxes with Reduced Differential Power Analysis Susceptibility. Retrieved from https://eprint.iacr.org/2016/1145.pdf
    37. Stoffelen, K. (2016). Optimizing S-box Implementations for Several Criteria using SAT Solvers. In International Conference on Fast Software Encryption - FSE 2016 (pp. 140-160). Berlin: Springer. doi: 10.1007/978-3-662-52993-5_8 Go to original source...
    38. Tesař, P. (2010). A New Method for Generating High Non-linearity S-Boxes. Radioengineering, 19(1), 23-26. Retrieved from https://www.radioeng.cz/fulltexts/2010/10_01_023_026.pdf
    39. Tran, M.T., Bui, D.K. & Duong A.D. (2008). Gray S-Box for Advanced Encryption Standard. In International Conference on Computational Intelligence and Security 2008 - CIS ´08 (pp. 253-258). New York: IEEE. doi: 10.1109/CIS.2008.205 Go to original source...
    40. Webster, A. F. (1986) Plaintext/Ciphertext Bit Dependencies in Cryptographic Systems. Master's thesis, Department of Electrical Engineering, Queen's University.
    41. Youssef, A.M., Tavares, S.E. & Gong, G. (2006). On some probabilistic approximations for AES-like S-boxes. Discrete Mathematics, 306(16), 2016-2020. doi: 10.1016/j.disc.2006.03.055 Go to original source...
    42. Zhang, W., Bao, Z., Rijmen, V. & Liu, M. (2015). A New Classification of 4-bit Optimal S-boxes and its Application to PRESENT, RECTANGLE and SONGENT. In International Workshop on Fast Software Encryption (pp. 494-515). Berlin: Springer. doi: 10.1007/978-3-662-48116-5_24 Go to original source...
    43. Zhang, W., Li, L. & Pasalic., E. (2017). Construction of resilient S-boxes with higher-dimensional vectorial outputs and strictly almost optimal nonlinearity. IET Information Security, 11(4), 199-203. doi: 10.1049/iet-ifs.2016.0168 Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content