Automatic search of linear trails in ARX with applications to SPECK and Chaskey. (English) Zbl 1346.94112

Manulis, Mark (ed.) et al., Applied cryptography and network security. 14th international conference, ACNS 2016, Guildford, UK, June 19–22, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-39554-8/pbk; 978-3-319-39555-5/ebook). Lecture Notes in Computer Science 9696, 485-499 (2016).
Summary: In this paper, we study linear cryptanalysis of the ARX structure by means of automatic search. To evaluate the security of ARX designs against linear cryptanalysis, it is crucial to find (round-reduced) linear trails with maximum correlation. We model the problem of finding optimal linear trails by the boolean satisfiability problem (SAT), translate the propagation of masks through ARX operations into bitwise expressions and constraints, and then solve the problem using a SAT solver. We apply the method to find optimal linear trails for round-reduced versions of the block cipher SPECK and the MAC algorithm Chaskey. For SPECK with block size 32/48/64/96/128, we can find optimal linear trails for 22/11/13/9/9 rounds respectively, which largely improves previous results, especially on larger versions. A 3-round optimal linear trail of Chaskey is presented for the first time as far as we know. In addition, our method can be used to enumerate the trails in a linear hull, and we present two linear hulls with the distributions of trails for round-reduced SPECK32. Our work provides designers with more accurate evaluation against linear cryptanalysis on ARX designs, especially for primitives with large block sizes and many rounds.
For the entire collection see [Zbl 1337.94004].


94A60 Cryptography
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI Link


[1] Aumasson, J.-P., Bernstein, D.J.: SipHash: a fast short-input PRF. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 489–508. Springer, Heidelberg (2012) · Zbl 1295.94009
[2] Aumasson, J.-P., Henzen, L., Meier, W., Phan, R.C.W.: SHA-3 proposal BLAKE. Submission to NIST (2008)
[3] Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK lightweight block ciphers. In: Proceedings of the 52nd Annual Design Automation Conference, DAC 2015, pp. 175:1–175:6. ACM (2015) · Zbl 1382.94059
[4] Bernstein, D.J.: ChaCha, a variant of Salsa20. http://cr.yp.to/chacha.html
[5] Bernstein, D.J.: The Salsa20 family of stream ciphers. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 84–97. Springer, Heidelberg (2008) · Zbl 05297172
[6] Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Cryptol. 4(1), 3–72 (1991) · Zbl 0729.68017
[7] 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, Heidelberg (2014) · Zbl 1337.94025
[8] Daemen, J., Govaerts, R., Vandewalle, J.: Correlation matrices. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 275–285. Springer, Heidelberg (1995) · Zbl 0939.94516
[9] Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The Skein hash function family. Submission to NIST (round 3) (2010)
[10] Fu, K., Wang, M., Guo, Y., Sun, S., Hu, L.: MILP-based automatic search algorithms for differential and linear trails for SPECK. In: Fast Software Encryption, FSE 2016. Springer (2016, to appear) · Zbl 1387.94081
[11] Ganesh, V.: STP constraint solver: Simple theorem prover SMT solver. http://stp.github.io
[12] Hong, D., Sung, J., Hong, S.H., Lim, J.-I., Lee, S.-J., Koo, B.-S., Lee, C.-H., Chang, D., Lee, J., Jeong, K., Kim, H., Kim, J.-S., Chee, S.: HIGHT: a new block cipher suitable for low-resource device. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 46–59. Springer, Heidelberg (2006) · Zbl 1307.94058
[13] Kölbl, S., Leander, G., Tiessen, T.: Observations on the SIMON block cipher family. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 161–185. Springer, Heidelberg (2015) · Zbl 1369.94546
[14] Leurent, G.: Construction of differential characteristics in ARX designs application to Skein. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 241–258. Springer, Heidelberg (2013) · Zbl 1310.94160
[15] Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) · Zbl 0951.94519
[16] Mouha, N., Mennink, B., Van Herrewege, A., Watanabe, D., Preneel, B., Verbauwhede, I.: Chaskey: an efficient MAC algorithm for 32-bit microcontrollers. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 306–323. Springer, Heidelberg (2014) · Zbl 1382.94145
[17] 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) · Zbl 1292.94118
[18] Needham, R.M., Wheeler, D.J.: TEA extensions. Technical report (1997)
[19] Nyberg, K.: Linear approximation of block ciphers. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 439–444. Springer, Heidelberg (1995) · Zbl 0885.94023
[20] Nyberg, K., Wallén, J.: Improved linear distinguishers for SNOW 2.0. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 144–162. Springer, Heidelberg (2006) · Zbl 1234.94062
[21] Schulte-Geers, E.: On CCZ-equivalence of addition mod \[ 2^n \] 2 n . Des. Codes Crypt. 66(1–3), 111–127 (2013) · Zbl 1259.94055
[22] Sinz, C.: Towards an optimal CNF encoding of Boolean cardinality constraints. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 827–831. Springer, Heidelberg (2005) · Zbl 1153.68488
[23] Soos, M.: A blog about SAT solving and cryptography. http://www.msoos.org
[24] Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 244–257. Springer, Heidelberg (2009) · Zbl 05576290
[25] 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) · Zbl 1306.94093
[26] Wallén, J.: Linear approximations of addition modulo 2 \[ ^{n} \] n . In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 261–273. Springer, Heidelberg (2003) · Zbl 1254.94046
[27] Wheeler, D.J., Needham, R.M.: TEA, a tiny encryption algorithm. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 363–366. Springer, Heidelberg (1995) · Zbl 0939.94550
[28] Yao, Y., Zhang, B., Wu, W.: Automatic search for linear trails of the SPECK family. In: López, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 158–176. Springer, Heidelberg (2015) · Zbl 1397.94110
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.