[en] We propose a tool for automated truncation of differential trails in ciphers using modular addition, bitwise rotation, and XOR (ARX). The tool takes as input a differential trail and produces as output a set of truncated differential trails. The set represents all possible truncations of the input trail according to certain predefined rules. A linear-time algorithm for the exact computation of the differential probability of a truncated trail that follows the truncation rules is proposed. We further describe a method to merge the set of truncated trails into a compact set of non-overlapping truncated trails with associated probability and we demonstrate the application of the tool on block cipher Speck64. We have also investigated the effect of clustering of differential trails around a fixed input trail. The best cluster that we have found for 15 rounds has probability 2^−55.03 (consisting of 389 unique output differences) which allows us to build a distinguisher using 128 times less data than the one based on just the single best trail, which has probability 2^−62. Moreover, we show examples for Speck64 where a cluster of trails around a suboptimal (in terms of probability) input trail results in higher overall probability compared to a cluster obtained around the best differential trail.
Centre de recherche :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > CryptoLUX – Cryptography
Disciplines :
Sciences informatiques
Auteur, co-auteur :
BIRYUKOV, Alexei ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
CARDOSO DOS SANTOS, Luan ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
FEHER, Daniel ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Cryptolux
Velichkov, Vesselin; University of Edinburgh
VITTO, Giuseppe ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Automated Truncation of Differential Trails and Trail Clustering in ARX
Date de publication/diffusion :
2022
Nom de la manifestation :
Selected Areas in Cryptography - 28th International Conference
Lieu de la manifestation :
Canada
Date de la manifestation :
September 29 - October 1, 2021
Manifestation à portée :
International
Titre de l'ouvrage principal :
Selected Areas in Cryptography - 28th International Conference, Revised Selected Papers
Maison d'édition :
Springer
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
Projet FnR :
FNR11684537 - Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts, 2017 (01/08/2018-31/07/2021) - Alex Biryukov
Intitulé du projet de recherche :
R-AGR-3125 - PRIDE15/1062187/SPsquared (01/01/2017 - 30/06/2023) - MAUW Sjouke FNR11684537 - Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts, 2017 (01/08/2018-31/07/2021) - Alex Biryukov
YAARX: Yet Another Toolkit for Analysis of ARX Cryptographic Algorithms (2012–2018). Source code: https://github.com/vesselinux/yaarx. Documentation: https://vesselinux.github.io/yaarx/index.html
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., Jr. (eds.) Selected Areas in Cryptography-SAC 2018. LNCS, vol. 11349, pp. 163–190. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7 8
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK Families of Lightweight Block Ciphers. Cryptology ePrint Archive, Report 2013/404
Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4, 3–72 (1991)
Biryukov, A., Roy, A., Velichkov, V.: Differential analysis of block ciphers SIMON and SPECK. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 546–570. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0 28
Biryukov, A., Velichkov, V.: Automatic search for differential trails in ARX ciphers. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 227–250. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04852-9 12
Biryukov, A., Velichkov, V., Le Corre, Y.: Automatic search for the best trails in ARX: application to block cipher Speck. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 289–310. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5 15
De Cannière, C., Rechberger, C.: Finding SHA-1 characteristics: general results and applications. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 1–20. Springer, Heidelberg (2006). https://doi.org/10.1007/11935230 1
Fu, K., Wang, M., Guo, Y., Sun, S., Hu, L.: MILP-based automatic search algorithms for differential and linear trails for speck. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 268–288. Springer, Heidelberg (2016). https://doi.org/10. 1007/978-3-662-52993-5 14
Huang, M., Wang, L.: Automatic tool for searching for differential characteristics in ARX ciphers and applications. In: Hao, F., Ruj, S., Sen Gupta, S. (eds.) INDOCRYPT 2019. LNCS, vol. 11898, pp. 115–138. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35423-7 6
Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60590-8 16
Leurent, G.: Analysis of differential attacks in ARX constructions. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 226–243. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4 15
Leurent, G.: Construction of differential characteristics in ARX designs-application to skein. IACR Cryptol. ePrint Arch. 2012, 668 (2012)
Leurent, G.: Construction of differential characteristics in ARX designs application to skein. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 241–258. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4 14
Leurent, G., Peyrin, T.: SHA-1 is a shambles: first chosen-prefix collision on SHA-1 and application to the PGP web of trust. In: USENIX (2020)
Lipmaa, H., Moriai, S.: Efficient algorithms for computing differential properties of addition. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 336–350. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45473-X 28
Liu, Z., Li, Y., Jiao, L., Wang, M.: A new method for searching optimal differential and linear trails in ARX ciphers. Cryptology ePrint Archive, Report 2019/1438
Mendel, F., Nad, T., Schläffer, M.: Finding SHA-2 characteristics: searching through a minefield of contradictions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 288–307. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0 16
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
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.) ACISP 2016. LNCS, vol. 9723, pp. 379–394. Springer, Cham (2016). https://doi.org/10. 1007/978-3-319-40367-0 24
Stevens, M.: New collision attacks on SHA-1 based on optimal joint local-collision analysis. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 245–261. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9 15
Sun, S., et al.: Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties. Cryptology ePrint Archive, Report 2014/747
Sun, S., Hu, L., Wang, M., Yang, Q., Qiao, K., Ma, X., Song, L., Shan, J.: Extending the applicability of the mixed-integer programming technique in automatic differential cryptanalysis. In: Lopez, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 141–157. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23318-5 8
