Abstract
As a generalized integral property, the division property can be used to search integral distinguishers of symmetric ciphers by taking the advantage of automatic tools, such as Mixed Integer Linear Programming (MILP) and Boolean Satisfiability Problem (SAT) solvers. In this case, the accuracy of corresponding models will influence the resulting distinguishers. In this paper, we present a new technique to characterize the division property propagation of linear layers. Firstly, we study the impact of a linear layer implementation on its division property propagations. We found that division trails derived from an optimized implementation of a linear layer can be more accurate than the \(\mathcal {S}\) method, and different implementations can eliminate some different invalid division trails. Thus, we can eliminate a large number of invalid division trails by combining different implementations. As an application of our technique, we have searched distinguishers for Midori64, Skinny64 and LED. As a result, we can obtain the same longest distinguishers as the \(\mathcal {ZR}\) method and the \(\mathcal {HW}\) method, which are the exact modeling of linear layers. Moreover, our method can be used with both MILP and SAT, while the \(\mathcal {HW}\) method can only work with SAT. In addition, the number of constraints with the \(\mathcal {HW}\) method increases quadratically, however it increases linearly with our method.
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.
- 2.
Note that these ciphers’ MixColumns are composed of 16-bit matrix. In order to exhibit the universality of our method, we also experimented on AES, and we respectively took about 5 and 10 min to find 4- and 5-round integral distinguishers in the key-dependent scenario. Our distinguishers are consistent with that of the \(\mathcal {HW}\) method, but we took less time. Unfortunately, we can not obtain these results when using the \(\mathcal {S}\) method.
References
Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48285-7_33
Knudsen, L., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 112–127. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45661-9_9
Daemen, J., Knudsen, L., Rijmen, V.: The block cipher Square. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052343
Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 287–314. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_12
Todo, Y.: Integral cryptanalysis on full MISTY1. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 413–432. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_20
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
Sun, L., Wang, W., Wang, M.Q.: MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. IET Inf. Secur. 14, 12–20 (2020). https://doi.org/10.1049/iet-ifs.2018.5283
Sun, L., Wang, W., Liu, R., Wang, M.Q.: Milp-aided bit-based division property for ARX ciphers. Sci. China Inf. Sci. 61, 118102:1-118102:3 (2018). https://doi.org/10.1007/s11432-017-9321-7
Zhang, W.Y., Rijmen, V.: Division cryptanalysis of block ciphers with a binary diffusion layer. IET Inf. Secur. 13, 87–95 (2019). https://doi.org/10.1049/iet-ifs.2018.5151
Hu, K., Wang, Q.J., Wang, M.Q.: Finding bit-based division property for ciphers with complex linear layers. IACR Trans. Symmetric Cryptol. 2020, 396–424 (2020). https://doi.org/10.13154/tosc.v2020.i1.396-424
Elsheikh M., Youssef A.: On MILP-based automatic search for bit-based division property for ciphers with (large) linear layers (Submitted to ACISP 2021) (2021). https://eprint.iacr.org/2021/643
Paar, C.: Optimized arithmetic for reed-solomon encoders. In: Proceedings of IEEE International Symposium on Information Theory 1997, p. 250 (1997). https://doi.org/10.1109/ISIT.1997.613165
Boyar, J., Matthews, P., Peralta, R.: Logic minimization techniques with applications to cryptology. J. Cryptol. 26, 280–312 (2013). https://doi.org/10.1007/s00145-012-9124-7
Xiang, Z.J., Zeng, X.Y., Lin, D., Bao, Z.Z., Zhang, S.S.: Optimizing implementations of linear layers. IACR Trans. Symmetric Cryptol. 2020, 120–145 (2020). https://doi.org/10.13154/tosc.v2020.i2.120-145
Banik, S., et al.: Midori: a block cipher for low energy. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 411–436. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_17
Beierle, C.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5
Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED block cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_22
Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C.-K., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537, pp. 57–76. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34704-7_5
Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_9
Kranz, T., Leander, G., Stoffelen, K., Wiemer, F.: Shorter linear straight-line programs for MDS matrices. IACR Trans. Symmetric Cryptol. 2017, 188–211 (2017). https://doi.org/10.13154/tosc.v2017.i4.188-211
Khoo, K., Peyrin, T., Poschmann, A.Y., Yap, H.: FOAM: searching for hardware-optimal SPN structures and components with a fair comparison. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 433–450. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44709-3_24
Acknowledgements
We would like to thank the anonymous reviewers for their helpful comments. This work was supported by the Application Foundation Frontier Project of Wuhan Science and Technology Bureau (NO. 2020010601012189), the National Natural Science Foundation of China (NO. 61802119) and the Research Foundation of Department of Education of Hubei Province, China (No. D2020104).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Hong, C., Zhang, S., Chen, S., Lin, D., Xiang, Z. (2021). More Accurate Division Property Propagations Based on Optimized Implementations of Linear Layers. In: Yu, Y., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2021. Lecture Notes in Computer Science(), vol 13007. Springer, Cham. https://doi.org/10.1007/978-3-030-88323-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-88323-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-88322-5
Online ISBN: 978-3-030-88323-2
eBook Packages: Computer ScienceComputer Science (R0)