Abstract
We propose an efficient technique called coefficient grouping to evaluate the algebraic degree of the FHE-friendly cipher Chaghri, which has been accepted for ACM CCS 2022. It is found that the algebraic degree increases linearly rather than exponentially. As a consequence, we can construct a 13-round distinguisher with time and data complexity of \(2^{63}\) and mount a 13.5-round key-recovery attack. In particular, a higher-order differential attack on 8 rounds of Chaghri can be achieved with time and data complexity of \(2^{38}\). Hence, it indicates that the full 8 rounds are far from being secure. Furthermore, we also demonstrate the application of our coefficient grouping technique to the design of secure cryptographic components. As a result, a countermeasure is found for Chaghri and it has little overhead compared with the original design. Since more and more symmetric primitives defined over a large finite field are emerging, we believe our new technique can have more applications in the future research.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The designers of Chaghri have revised their design based on our countermeasures.
- 2.
From the perspective of attackers, \(D_r\) can be defined as \({\text {min}}\{D_{r,1},D_{r,2},D_{r,3}\}\) to reduce the time complexity of the attacks. However, due to the strong diffusion of the MDS matrix, using \(D_r={\text {max}}\{D_{r,1},D_{r,2},D_{r,3}\}\) is reasonable and can greatly simplify the attack. This can also be observed from our later analysis of the evolution of the polynomials through the step function of Chaghri, i.e. using \(D_r={\text {max}}\{D_{r,1},D_{r,2},D_{r,3}\}\) is indeed tight according to the experiments.
- 3.
Motivated by this work, an ad-hoc algorithm [28] has been developed to solve the above optimization problem in time \(\mathcal {O}(n)\). However, in this following, there still remain some other optimization problems which cannot be handled by that \(\mathcal {O}(n)\) algorithm [28]. Hence, we only consider the general-purpose solvers for the optimization problems in this paper.
- 4.
Indeed, this problem can also be solved in \(\mathcal {O}(n)\) time with the algorithm in [28].
References
Albrecht, M.R., et al.: Algebraic cryptanalysis of STARK-friendly designs: application to MARVELlous and MiMC. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11923, pp. 371–397. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_13
Albrecht, M., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 191–219. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_7
Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_17
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). https://doi.org/10.13154/tosc.v2020.i3.1-45
Ashur, T., Dhooghe, S.: MARVELlous: a STARK-friendly family of cryptographic primitives. IACR Cryptol. ePrint Arch., p. 1098 (2018). https://eprint.iacr.org/2018/1098
Ashur, T., Mahzoun, M., Toprakhisar, D.: Chaghri – an FHE-friendly block cipher. Cryptology ePrint Archive, Paper 2022/592 (2022). https://eprint.iacr.org/2022/592
Beyne, T., et al.: Out of oddity – new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 299–328. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_11
Boura, C., Canteaut, A., De Cannière, C.: Higher-order differential properties of Keccak and Luffa. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 252–269. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_15
Bouvier, C., Canteaut, A., Perrin, L.: On the algebraic degree of iterated power functions. IACR Cryptol. ePrint Arch., p. 366 (2022). https://eprint.iacr.org/2022/366
Canteaut, A., et al.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 313–333. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_16
Cid, C., Grassi, L., Gunsing, A., Lüftenegger, R., Rechberger, C., Schofnegger, M.: Influence of the linear layer on the algebraic degree in SP-networks. IACR Trans. Symmetric Cryptol. 2022(1), 110–137 (2022). https://doi.org/10.46586/tosc.v2022.i1.110-137
Cid, C., Indrøy, J.P., Raddum, H.: FASTA – a stream cipher for fast FHE evaluation. In: Galbraith, S.D. (ed.) CT-RSA 2022. LNCS, vol. 13161, pp. 451–483. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-95312-6_19
Cui, J., Hu, K., Wang, M., Wei, P.: On the field-based division property: applications to MiMC, Feistel MiMC and GMiMC. In: ASIACRYPT (3). Lecture Notes in Computer Science, vol. 13793, pp. 241–270. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22969-5_9
Dinur, I.: Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2). In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 374–403. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_14
Dobraunig, C., et al.: Rasta: a cipher with low ANDdepth and few ANDs per bit. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 662–692. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_22
Dobraunig, C., Grassi, L., Guinet, A., Kuijsters, D.: Ciminion: symmetric encryption based on toffoli-gates over large finite fields. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 3–34. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_1
Dobraunig, C., Grassi, L., Helminger, L., Rechberger, C., Schofnegger, M., Walch, R.: Pasta: a case for hybrid homomorphic encryption. IACR Cryptol. ePrint Arch., p. 731 (2021). https://eprint.iacr.org/2021/731
Duval, S., Lallemand, V., Rotella, Y.: Cryptanalysis of the FLIP family of stream ciphers. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 457–475. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_17
Eichlseder, M., et al.: An algebraic attack on ciphers with low-degree round functions: application to full MiMC. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 477–506. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_16
Grassi, L., Lüftenegger, R., Rechberger, C., Rotaru, D., Schofnegger, M.: On a generalization of substitution-permutation networks: the HADES design strategy. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 674–704. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_23
Ma, H., et al.: Masta: an HE-friendly cipher using modular arithmetic. IEEE Access 8, 194741–194751 (2020). https://doi.org/10.1109/ACCESS.2020.3033564
Hao, Y., Leander, G., Meier, W., Todo, Y., Wang, Q.: Modeling for three-subset division property without unknown subset. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 466–495. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_17
Hebborn, P., Leander, G.: Dasta - alternative linear layer for Rasta. IACR Trans. Symmetric Cryptol. 2020(3), 46–86 (2020). https://doi.org/10.13154/tosc.v2020.i3.46-86
Hu, K., Sun, S., Wang, M., Wang, Q.: An algebraic formulation of the division property: revisiting degree evaluations, cube attacks, and key-independent sums. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 446–476. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_15
Liu, F., Isobe, T., Meier, W.: Cryptanalysis of full LowMC and LowMC-M with algebraic techniques. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 368–401. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_13
Liu, F., Sarkar, S., Meier, W., Isobe, T.: Algebraic attacks on rasta and dasta using low-degree equations. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13090, pp. 214–240. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_8
Liu, F., Sarkar, S., Wang, G., Meier, W., Isobe, T.: Algebraic meet-in-the-middle attack on LowMC. In: ASIACRYPT (1). Lecture Notes in Computer Science, vol. 13791, pp. 225–255. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22963-3_8
Liu, F., Wang, L.: An \(\cal{O} (n)\) algorithm for coefficient grouping. Cryptology ePrint Archive, Paper 2022/992 (2022). https://eprint.iacr.org/2022/992
Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_13
Rechberger, C., Soleimany, H., Tiessen, T.: Cryptanalysis of low-data instances of full LowMCv2. IACR Trans. Symmetric Cryptol. 2018(3), 163–181 (2018). https://doi.org/10.13154/tosc.v2018.i3.163-181
Todo, Y., Morii, M.: Bit-based division property and application to Simon family. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 357–377. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_18
Xiang, Z., Zhang, W., Bao, Z., Lin, D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 648–678. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_24
Acknowledgement
We thank Mohammad Mahzoun and Tomer Ashur for carefully checking our results. We also thank the reviewers of EUROCRYPT 2023 for providing many insightful comments. Fukang Liu is supported by Grant-in-Aid for Research Activity Start-up (Grant No. 22K21282). Takanori Isobe is supported by JST, PRESTO Grant Number JPMJPR2031. These research results were also obtained from the commissioned research (No.05801) by National Institute of Information and Communications Technology (NICT), Japan. Libo Wang is supported by the National Natural Science Foundation of China under Grants 62102167, 62032025, and by the Guangdong Basic and Applied Basic Research Foundation under Grants 2022A1515010299, 2020A1515110364.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Liu, F., Anand, R., Wang, L., Meier, W., Isobe, T. (2023). Coefficient Grouping: Breaking Chaghri and More. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14007. Springer, Cham. https://doi.org/10.1007/978-3-031-30634-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-30634-1_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30633-4
Online ISBN: 978-3-031-30634-1
eBook Packages: Computer ScienceComputer Science (R0)
