Related-key differential cryptanalysis of GMiMC used in post-quantum signatures. (English) Zbl 07730570
Seo, Seung-Hyun (ed.) et al., Information security and cryptology – ICISC 2022. 25th international conference, ICISC 2022, Seoul, South Korea, November 30 – December 2, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13849, 41-60 (2023).
Summary: With the urgency of the threat imposed by quantum computers, there is a strong interest in making the signature schemes quantum resistant. As the promising candidates to ensure post-quantum security, symmetric-key primitives, in particular the recent MPC/FHE/ZK-friendly hash functions or block ciphers, are providing another choice to build efficient and secure signature schemes that do not rely on any assumed hard problems. However, considering the intended use cases, many of these novel ciphers for advanced cryptographic protocols do not claim the related-key security.
In this paper, we initiate the study of the ignored related-key security of GMiMC proposed by Albrecht et al. at ESORICS 2019, some versions of which are optimized and designed to be used in post-quantum secure signatures. By investigating the potential threats of related-key attacks for GMiMC intended to be deployed as the underlying building block in post-quantum signature schemes, we then construct two kinds of iterative related-key differentials, from which not only do we explore its security margin against related-key attacks, but also collision attacks on its key space can be performed. For example, for GMiMC instance that beats the smallest signature size obtainable using LowMC, we can find its key collision using only about \(2^{10}\) key pairs. It worths noting that our current key collision attack is only applicable when the adversarial power is sufficiently strong (e.g., in the so-called multi-user setting), and it does not threaten the one-wayness of GMiMC. Furthermore, from the experiments of our related-key differentials, it can be observed that the differential clustering effect of GMiMC differs in both aspects: the choice of the finite field \(\mathbb{F}\) being \(\mathbb{F}_p\) or \(\mathbb{F}_2^n\), and the size of the finite field \(\mathbb{F} \).
For the entire collection see [Zbl 1517.68028].
In this paper, we initiate the study of the ignored related-key security of GMiMC proposed by Albrecht et al. at ESORICS 2019, some versions of which are optimized and designed to be used in post-quantum secure signatures. By investigating the potential threats of related-key attacks for GMiMC intended to be deployed as the underlying building block in post-quantum signature schemes, we then construct two kinds of iterative related-key differentials, from which not only do we explore its security margin against related-key attacks, but also collision attacks on its key space can be performed. For example, for GMiMC instance that beats the smallest signature size obtainable using LowMC, we can find its key collision using only about \(2^{10}\) key pairs. It worths noting that our current key collision attack is only applicable when the adversarial power is sufficiently strong (e.g., in the so-called multi-user setting), and it does not threaten the one-wayness of GMiMC. Furthermore, from the experiments of our related-key differentials, it can be observed that the differential clustering effect of GMiMC differs in both aspects: the choice of the finite field \(\mathbb{F}\) being \(\mathbb{F}_p\) or \(\mathbb{F}_2^n\), and the size of the finite field \(\mathbb{F} \).
For the entire collection see [Zbl 1517.68028].
References:
| [1] | Albrecht, MR; Sako, K.; Schneider, S.; Ryan, PYA, Feistel structures for MPC, and more, Computer Security - ESORICS 2019, 151-171 (2019), Cham: Springer, Cham · Zbl 1500.94015 · doi:10.1007/978-3-030-29962-0_8 |
| [2] | Albrecht, M.R., et al.: Feistel structures for MPC, and more. IACR Cryptol. ePrint Arch, p. 397 (2019). https://eprint.iacr.org/2019/397 |
| [3] | Albrecht, M.; Grassi, L.; Rechberger, C.; Roy, A.; Tiessen, T.; Cheon, JH; Takagi, T., MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity, Advances in Cryptology - ASIACRYPT 2016, 191-219 (2016), Heidelberg: Springer, Heidelberg · Zbl 1404.94035 · doi:10.1007/978-3-662-53887-6_7 |
| [4] | Albrecht, MR; Rechberger, C.; Schneider, T.; Tiessen, T.; Zohner, M.; Oswald, E.; Fischlin, M., Ciphers for MPC and FHE, Advances in Cryptology - EUROCRYPT 2015, 430-454 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94477 · doi:10.1007/978-3-662-46800-5_17 |
| [5] | Aly, A.; Ashur, T.; Ben-Sasson, E.; Dhooghe, S.; Szepieniec, A., Design of symmetric-key primitives for advanced cryptographic protocols, IACR Trans. Symmetric Cryptol., 2020, 3, 1-45 (2020) · doi:10.13154/tosc.v2020.i3.1-45 |
| [6] | Aumasson, J.P., et al.: \( \text{SPHINCS}^+\). In: Submission to NIST Post-Quantum Cryptography project (2020). https://sphincs.org/data/sphincs+-round3-specification.pdf |
| [7] | Beyne, T.; Micciancio, D.; Ristenpart, T., Out of oddity – new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems, Advances in Cryptology - CRYPTO 2020, 299-328 (2020), Cham: Springer, Cham · Zbl 1504.94105 · doi:10.1007/978-3-030-56877-1_11 |
| [8] | Biham, E., New types of cryptanalytic attacks using related keys, J. Crypt., 7, 4, 229-246 (1994) · Zbl 0812.94012 · doi:10.1007/BF00203965 |
| [9] | Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, J. Crypt., 4, 1, 3-72 (1991) · Zbl 0729.68017 · doi:10.1007/BF00630563 |
| [10] | Boneh, D.; Eskandarian, S.; Fisch, B.; Matsui, M., Post-quantum EPID signatures from symmetric primitives, Topics in Cryptology - CT-RSA 2019, 251-271 (2019), Cham: Springer, Cham · Zbl 1509.94152 · doi:10.1007/978-3-030-12612-4_13 |
| [11] | Chase, M., et al.: The picnic signature scheme. In: Submission to NIST Post-Quantum Cryptography Project (2020). https://github.com/microsoft/Picnic/blob/master/spec/design-v2.2.pdf |
| [12] | Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, pp. 1825-1842 (2017). doi:10.1145/3133956.3133997 |
| [13] | Chen, L., Report on post-quantum cryptography (2016), National Institute of Standards and Technology: US Department of Commerce, National Institute of Standards and Technology · doi:10.6028/NIST.IR.8105 |
| [14] | Derler, D.; Ramacher, S.; Slamanig, D.; Lange, T.; Steinwandt, R., Post-quantum zero-knowledge proofs for accumulators with applications to ring signatures from symmetric-key primitives, Post-Quantum Cryptography, 419-440 (2018), Cham: Springer, Cham · Zbl 1406.94043 · doi:10.1007/978-3-319-79063-3_20 |
| [15] | Eichlseder, M.; Kales, D., Clustering related-tweak characteristics: application to MANTIS-6, IACR Trans. Symmetric Cryptol., 2018, 2, 111-132 (2018) · doi:10.13154/tosc.v2018.i2.111-132 |
| [16] | Ganesh, V., Dill, D.L.: A decision procedure for bit-vectors and arrays. In: Computer Aided Verification, 19th International Conference, CAV 2007, pp. 519-531 (2007). doi:10.1007/978-3-540-73368-3_52 · Zbl 1135.68472 |
| [17] | Kaplan, M.; Leurent, G.; Leverrier, A.; Naya-Plasencia, M.; Robshaw, M.; Katz, J., Breaking symmetric cryptosystems using quantum period finding, Advances in Cryptology - CRYPTO 2016, 207-237 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94766 · doi:10.1007/978-3-662-53008-5_8 |
| [18] | Knudsen, LR; Imai, H.; Rivest, RL; Matsumoto, T., Cryptanalysis of LOKI, Advances in Cryptology — ASIACRYPT ’91, 22-35 (1993), Heidelberg: Springer, Heidelberg · Zbl 0809.94013 · doi:10.1007/3-540-57332-1_2 |
| [19] | Knudsen, LR; Kohno, T.; Johansson, T., Analysis of RMAC, Fast Software Encryption, 182-191 (2003), Heidelberg: Springer, Heidelberg · Zbl 1254.94037 · doi:10.1007/978-3-540-39887-5_14 |
| [20] | Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, October 28-31(2012), pp. 312-316, 2012. https://ieeexplore.ieee.org/document/6400943/ |
| [21] | Leander, G.; May, A.; Takagi, T.; Peyrin, T., Grover meets Simon – quantumly attacking the FX-construction, Advances in Cryptology - ASIACRYPT 2017, 161-178 (2017), Cham: Springer, Cham · Zbl 1380.94109 · doi:10.1007/978-3-319-70697-9_6 |
| [22] | Leurent, G.; Pernot, C.; Schrottenloher, A.; Tibouchi, M.; Wang, H., Clustering effect in Simon and Simeck, Advances in Cryptology - ASIACRYPT 2021, 272-302 (2021), Cham: Springer, Cham · Zbl 1514.94113 · doi:10.1007/978-3-030-92062-3_10 |
| [23] | Nyberg, K.; Knudsen, LR; Brickell, EF, Provable security against differential cryptanalysis, Advances in Cryptology — CRYPTO’ 92, 566-574 (1993), Heidelberg: Springer, Heidelberg · Zbl 0824.68037 · doi:10.1007/3-540-48071-4_41 |
| [24] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pp. 124-134 (1994). doi:10.1109/SFCS.1994.365700 |
| [25] | Simon, D.R.: On the power of quantum computation. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pp. 116-123 (1994). doi:10.1109/SFCS.1994.365701 |
| [26] | The Sage Developers: SageMath, the Sage mathematics software system (Version 8.8). https://www.sagemath.org |
| [27] | Wang, M.; Sun, Y.; Tischhauser, E.; Preneel, B.; Canteaut, A., A model for structure attacks, with applications to PRESENT and serpent, Fast Software Encryption, 49-68 (2012), Heidelberg: Springer, Heidelberg · Zbl 1312.94098 · doi:10.1007/978-3-642-34047-5_4 |
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.
