An STP-based model toward designing S-boxes with good cryptographic properties. (English) Zbl 1508.94059
Summary: The substitution box (S-box) is an important nonlinear component in most symmetric cryptosystems and thus should have good properties. Its difference distribution table (DDT) and linear approximation table (LAT) affect the security of the cipher against differential and linear cryptanalysis. In most previous work, differential uniformity and linearity of an S-box are two primary cryptographic properties to impact the resistance against differential and linear attacks. In some cases, the branch number and fixed point are also considered. However, other important cryptographic properties such as the frequency of differential uniformity (resp. linearity) and the number of Bad Input and Bad Output (BIBO) patterns in DDT (resp. LAT) are often ignored. These properties substantially affect lightweight cryptography based on substitution bit permutation networks (SbPN) such as PRESENT, GIFT and RECTANGLE. This paper introduces a new method to search for S-boxes satisfying all above criteria simultaneously. In our strategy, we transform the process of searching for S-boxes under certain constraints on cryptographic properties into a satisfiability (SAT) problem. As applications, we use our new approach to search out 4-bit and 5-bit S-boxes with the same or better cryptographic properties compared with the S-boxes from well-known ciphers. Finally, we also utilize our method to verify a conjecture proposed by C. Boura et al. [ibid. 87, No. 2–3, 185–202 (2019; Zbl 1454.94052)] in the case of all 3-bit and 4-bit S-boxes. We propose a proposition and two corollaries to reduce the search space in this verification.
MSC:
| 94A60 | Cryptography |
| 68P25 | Data encryption (aspects in computer science) |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
Keywords:
symmetric cryptography; lightweight cryptography; block cipher; S-box; difference distribution table (DDT); linear approximation table (LAT)Citations:
Zbl 1454.94052References:
| [1] | Ankele R., Kölbl S.: Mind the gap—a closer look at the security of block ciphers against differential cryptanalysis. In: Cid, C., Jacobson, M.J., Jr. (eds.) 25th International Conference on Selected Areas in Cryptography (SAC 2018), Calgary, AB, Canada, 15-17 August 2018. Revised Selected Papers. Lecture Notes in Computer Science, vol. 11349, pp. 163-190. Springer, Berlin (2018). doi:10.1007/978-3-030-10970-7_8. · Zbl 1447.94017 |
| [2] | Aumasson J., Jovanovic P., Neves S.: Analysis of NORX: investigating differential and rotational properties. In: Aranha, D.F., Menezes, A. (eds.) Progress in Cryptology - LATINCRYPT 2014 - Third International Conference on Cryptology and Information Security in Latin America, Florianópolis, Brazil, 17-19 September 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8895, pp. 306-324. Springer, Berlin (2014). doi:10.1007/978-3-319-16295-9_17. · Zbl 1370.94482 |
| [3] | Azimi S.A., Ranea A., Salmasizadeh M., Mohajeri J., Aref M.R., Rijmen V.: A bit-vector differential model for the modular addition by a constant. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology—ASIACRYPT 2020—26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 7-11 December 2020, Proceedings, Part I. Lecture Notes in Computer Science, vol. 12491, pp. 385-414. Springer, Berlin (2020). doi:10.1007/978-3-030-64837-4_13. · Zbl 1511.94046 |
| [4] | Banik S., Bogdanov A., Isobe, T., Shibutani, K., Hiwatari H., Akishita T., Regazzoni F.: Midori: a block cipher for low energy. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 29 November-December 3, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9453, pp. 411-436. Springer, Berlin (2015). doi:10.1007/978-3-662-48800-3_17. · Zbl 1382.94057 |
| [5] | Banik S., Pandey S.K. Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT: A small present—towards reaching the limit of lightweight encryption. In: Fischer, W., Homma, H. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, 25-28 September 2017, Proceedings. Lecture Notes in Computer Science, vol. 10529, pp. 321-345. Springer, Berlin (2017). doi:10.1007/978-3-319-66787-4_16. · Zbl 1450.94026 |
| [6] | Bao Z., Guo J., Ling S., Sasaki Y.: PEIGEN—a platform for evaluation, implementation, and generation of s-boxes. IACR Trans. Symmetric Cryptol. 2019(1), 330-394 (2019). doi:10.13154/tosc.v2019.i1.330-394. |
| [7] | Bar-On, A.; Biham, E.; Dunkelman, O.; Keller, N., Efficient slide attacks, J. Cryptol., 31, 3, 641-670 (2018) · Zbl 1400.94116 · doi:10.1007/s00145-017-9266-8 |
| [8] | Bar-On A., Dunkelman O., Keller N., Weizman A.: DLCT: a new tool for differential-linear cryptanalysis. In: Ishai, Y., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2019—38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, 19-23 May 2019, Proceedings, Part I. Lecture Notes in Computer Science, vol. 11476, pp. 313-342. Springer, Berlin (2019). doi:10.1007/978-3-030-17653-2_11. · Zbl 1470.94078 |
| [9] | Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, 14-18 August 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9815, pp. 123-153. Springer, Berlin (2016). doi:10.1007/978-3-662-53008-5_5. · Zbl 1372.94412 |
| [10] | Bertoni G., Daemen J., Peeters M., Van Assche G.: The keccak sha-3 submission. Submission to NIST (Round 3) 6(7), 16 (2011) |
| [11] | Biham E., Shamir A.: Differential Cryptanalysis of the Data Encryption Standard. Springer, New York (1993). doi:10.1007/978-1-4613-9314-6. · Zbl 0778.94005 |
| [12] | Bilgin B., Meyer L.D., Duval S., Levi I., Standaert F.: Low AND depth and efficient inverses: a guide on s-boxes for low-latency masking. IACR Trans. Symmetric Cryptol. 2020(1), 144-184 (2020). doi:10.13154/tosc.v2020.i1.144-184. |
| [13] | Bogdanov 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.) Cryptographic Hardware and Embedded Systems—CHES 2007, 9th International Workshop, Vienna, Austria, 10-13 September 2007, Proceedings. Lecture Notes in Computer Science, vol. 4727, pp. 450-466. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74735-2_31. · Zbl 1142.94334 |
| [14] | Boura, C.; Canteaut, A.; Jean, J.; Suder, V., Two notions of differential equivalence on sboxes, Des. Codes Cryptogr., 87, 2-3, 185-202 (2019) · Zbl 1454.94052 · doi:10.1007/s10623-018-0496-z |
| [15] | Browning, K.; Dillon, J.; McQuistan, M.; Wolfe, A., An APN permutation in dimension six, Finite Fields Theory Appl., 518, 33-42 (2010) · Zbl 1206.94026 · doi:10.1090/conm/518/10194 |
| [16] | Calderini M., Budaghyan L., Carlet C.: On known constructions of APN and AB functions and their relation to each other. Rad Hrvatske akademije znanosti i umjetnosti Matematicke znanosti 25, 79-105(2020). · Zbl 1484.94043 |
| [17] | Carlet C.: Open questions on nonlinearity and on APN functions. In: Koç, Ç.K., Mesnager, S., Savas, E. (eds.) Arithmetic of Finite Fields—5th International Workshop, WAIFI 2014, Gebze, Turkey, 27-28 September 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 9061, pp. 83-107. Springer, New York (2014). doi:10.1007/978-3-319-16277-5_5. · Zbl 1400.94133 |
| [18] | Chabaud F., Vaudenay S.: Links between differential and linear cryptanalysis. In: Santis, A.D. (ed.) Advances in Cryptology—EUROCRYPT ’94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, 9-12 May 1994, Proceedings. Lecture Notes in Computer Science, vol. 950, pp. 356-365. Springer, New York (1994). doi:10.1007/BFb0053450. · Zbl 0879.94023 |
| [19] | Cid C., Huang T., Peyrin T., Sasaki Y., Song L.: Boomerang connectivity table: a new cryptanalysis tool. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 29 April-3 May 2018 Proceedings, Part II. Lecture Notes in Computer Science, vol. 10821, pp. 683-714. Springer, New York (2018). doi:10.1007/978-3-319-78375-8_22. · Zbl 1428.94065 |
| [20] | Daemen, J.; Rijmen, V., The Design of Rijndael (2002), Berlin: Springer, Berlin · Zbl 1065.94005 · doi:10.1007/978-3-662-04722-4 |
| [21] | De Cannière C.: Analysis and design of symmetric encryption algorithms. Doctoral Dissertaion, KULeuven (2007). |
| [22] | Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Ascon. Submission to the CAESAR competition (2014). http://ascon.iaik.tugraz.at. |
| [23] | Dunkelman O., Huang S.: Reconstructing an s-box from its difference distribution table. IACR Trans. Symmetric Cryptol. 2019(2), 193-217 (2019). doi:10.13154/tosc.v2019.i2.193-217. |
| [24] | Ganesh V., Dill D.L.: http://stp.github.io/ (2007). |
| [25] | Guo J., Jean J., Nikolic I., Qiao K., Sasaki Y., Sim S.M.: Invariant subspace attack against midori64 and the resistance criteria for s-box designs. IACR Trans. Symmetric Cryptol. 2016(1), 33-56 (2016). doi:10.13154/tosc.v2016.i1.33-56. |
| [26] | Isa, H.; Jamil, N.; Z’aba, M., Hybrid heuristic methods in constructing cryptographically strong s-boxes, Int. J. Cryptol. Res., 6, 1, 1-15 (2016) |
| [27] | Ivanov G., Nikolov N., Nikova S.: Cryptographically strong s-boxes generated by modified immune algorithm. In: Pasalic, E., Knudsen, L.R. (eds.) Cryptography and Information Security in the Balkans—Second International Conference, BalkanCryptSec 2015, Koper, Slovenia, 3-4 September 2015, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9540, pp. 31-42. Springer, New York (2015). doi:10.1007/978-3-319-29172-7_3. · Zbl 1336.94055 |
| [28] | Ivanov, G.; Nikolov, N.; Nikova, S., Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties, Cryptogr. Commun., 8, 2, 247-276 (2016) · Zbl 1338.94074 · doi:10.1007/s12095-015-0170-5 |
| [29] | Kim, H.; Jeon, Y.; Kim, G.; Kim, J.; Sim, B.; Han, D.; Seo, H.; Kim, S.; Hong, S.; Sung, J.; Hong, D., A new method for designing lightweight s-boxes with high differential and linear branch numbers, and its application, IACR Cryptol, 2020, 1582 (2020) |
| [30] | Kim, SG; Hong, D.; Sung, J.; Hong, S., Classification of 4-bit s-boxes for BOGI permutation, IEEE Access, 8, 210935-210949 (2020) · doi:10.1109/ACCESS.2020.3039273 |
| [31] | Kölbl S., Leander G., Tiessen T.: Observations on the SIMON block cipher family. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, 16-20 August 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9215, pp. 161-185. Springer, New York (2015). doi:10.1007/978-3-662-47989-6_8. · Zbl 1369.94546 |
| [32] | Leander G., Poschmann A.: On the classification of 4 bit s-boxes. In: Carlet, C., Sunar, B. (eds.) Arithmetic of Finite Fields, First International Workshop, WAIFI 2007, Madrid, Spain, 21-22 June 2007, Proceedings. Lecture Notes in Computer Science, vol. 4547, pp. 159-176. Springer, New York (2007). doi:10.1007/978-3-540-73074-3_13. · Zbl 1184.94239 |
| [33] | Liu Y., Liang H., Li M., Huang L., Hu K., Yang C., Wang M.: STP models of optimal differential and linear trail for s-box based ciphers. IACR Trans Symmetric Cryptol. 2019, 99-129 (2019). https://eprint.iacr.org/2019/025. |
| [34] | Lu Z., Wang W., Hu K., Fan Y., Wu L., Wang M.: Pushing the limits: Searching for implementations with the smallest area for lightweight s-boxes. In: Adhikari, A., Küsters, R., Preneel, B. (eds.) Progress in Cryptology—INDOCRYPT 2021—22nd International Conference on Cryptology in India, Jaipur, India, 12-15 December 2021. Lecture Notes in Computer Science, vol. 13143, pp. 159-178. Springer, New York (2021). doi:10.1007/978-3-030-92518-5_8. · Zbl 1514.94116 |
| [35] | Matsui M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) Advances in Cryptology—EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, 23-27 May 1993, Proceedings. Lecture Notes in Computer Science, vol. 765, pp. 386-397. Springer, New York (1993). doi:10.1007/3-540-48285-7_33. · Zbl 0951.94519 |
| [36] | Nyberg K.: Differentially uniform mappings for cryptography. In: Helleseth, T. (ed.) Advances in Cryptology—EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, 23-27 May 1993, Proceedings. Lecture Notes in Computer Science, vol. 765, pp. 55-64. Springer, New York (1993). doi:10.1007/3-540-48285-7_6. · Zbl 0951.94510 |
| [37] | Perrin, L., Cryptanalysis. Reverse-Engineering and Design of Symmetric Cryptographic Algorithms (2017), Luxembourg: University of Luxembourg, Luxembourg |
| [38] | Ranea, A.; Liu, Y.; Ashur, T., An easy-to-use tool for rotational-xor cryptanalysis of ARX block ciphers, IACR Cryptol., 2020, 727 (2020) |
| [39] | Song L., Huang Z., Yang Q.: Automatic differential analysis of ARX block ciphers with application to SPECK and LEA. In: Liu, J.K., Steinfeld, R. (eds.) Information Security and Privacy—21st Australasian Conference, ACISP 2016, Melbourne, VIC, Australia, 4-6 July 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9723, pp. 379-394. Springer, New York (2016). doi:10.1007/978-3-319-40367-0_24. · Zbl 1346.94124 |
| [40] | Stoffelen K.: Optimizing s-box implementations for several criteria using SAT solvers. In: Peyrin, T. (ed.) Fast Software Encryption—23rd International Conference, FSE 2016, Bochum, Germany, 20-23 March 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9783, pp. 140-160. Springer, New York (2016). doi:10.1007/978-3-662-52993-5_8. · Zbl 1387.94100 |
| [41] | Sun L., Wang W., Wang M.: Accelerating the search of differential and linear characteristics with the SAT method. IACR Trans. Symmetric Cryptol. 2021(1), 269-315 (2021). doi:10.46586/tosc.v2021.i1.269-315. |
| [42] | Wang, Y.; Zhang, Z.; Zhang, LY; Feng, J.; Gao, J.; Lei, P., A genetic algorithm for constructing bijective substitution boxes with high nonlinearity, Inf. Sci., 523, 152-166 (2020) · Zbl 1458.68295 · doi:10.1016/j.ins.2020.03.025 |
| [43] | Zhang, W.; Bao, Z.; Lin, D.; Rijmen, V.; Yang, B.; Verbauwhede, I., RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms, Sci. China Inf. Sci., 58, 12, 1-15 (2015) · doi:10.1007/s11432-015-5459-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
