Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck

Biryukov, Alex; Velichkov, Vesselin; Le Corre, Yann

Download

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck

Biryukov, Alex; Velichkov, Vesselin; Le Corre, Yann

2016 • In Fast Software Encryption - FSE 2016

Peer reviewed

Permalink
https://hdl.handle.net/10993/29482

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

409.pdf

Author postprint (296.98 kB)

Cryptology ePrint Archive: Report 2016/409

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

symmetric-key; cryptanalysis; ARX; Speck

Abstract :

[en] We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any heuristics and returns optimal results. The practical application of the new algorithm is demonstrated on reduced round variants of block ciphers from the Speck family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds of Speck32, Speck48, Speck64, Speck96 and Speck128 respectively, together with the exact number of differential trails that have the best probability. The new results are used to compute bounds, under the Markov assumption, on the security of Speck against single-trail differential cryptanalysis. Finally, we propose two new ARX primitives with provable bounds against single-trail differential and linear cryptanalysis -- a long standing open problem in the area of ARX design.

Disciplines :

Computer science

Author, co-author :

Biryukov, Alex ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

Velichkov, Vesselin ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Computer Science and Communications Research Unit (CSC)

Le Corre, Yann ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

External co-authors :

Language :

English

Title :

Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck

Publication date :

2016

Event name :

Fast Software Encryption - 23rd International Workshop (2016)

Event date :

from 20-03-2016 to 23-03-2016

Main work title :

Fast Software Encryption - FSE 2016

Peer reviewed :

Peer reviewed

Focus Area :

Security, Reliability and Trust

Additional URL :

http://eprint.iacr.org/2016/409

Name of the research project :

R-AGR-0526 - CAESAREA (20150415-20181231) - BIRYUKOV Alexei

Funders :

UL Internal Research Project (reference I2R-DIR-PUL-15CAES)

Available on ORBilu :

since 23 January 2017

Statistics

Number of views

216 (21 by Unilu)

Number of downloads

401 (4 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

Aumasson, J.-P., Jovanovic, P., Neves, S.: NORX: parallel and scalable AEAD. In: Kutyłowski, M., Vaidya, J. (eds.) ICAIS 2014, Part II. LNCS, vol. 8713, pp. 19-36. Springer, Heidelberg (2014)
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 (2013). http://eprint.iacr.org/
Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. J. Crypt. 4(1), 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)
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)
CryptoLUX.: FELICS - Fair Evaluation of Lightweight Cryptographic Systems (2015). https://www.cryptolux.org/index.php/FELICS
Daemen, J., Rijmen, V.: AES and the wide trail design strategy. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 108-109. Springer, Heidelberg (2002)
Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg (2002)
Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. IACR Cryptology ePrint Archive 2005, 212 (2005)
Dehnavi, S.M., Rishakani, A.M., Shamsabad, M.R.M.: A More explicit formula for linear probabilities of modular addition modulo a power of two. Cryptology ePrint Archive, report 2015/026 (2015). http://eprint.iacr.org/
Dobraunig, C., Eichlseder, M., Mendel, F.: Heuristic tool for linear cryptanalysis with applications to CAESAR candidates. In: Iwata, T., et al. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 490-509. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48800-3_20
Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The skein hash function family. Submission to the NIST SHA-3 Competition (Round 2) (2009)
Fu, K., Wang, M., Guo, Y., Sun, S., Hu, L.: MILP-based automatic search algorithms for differential and linear trails for speck. In: 23rd International Workshop on Fast Software Encryption, FSE 2016, Bochum, Germany, 20-23 March (2016, to appear)
Lai, X., Massey, J.L.: Markov ciphers and differential cryptanalysis. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 17-38. Springer, Heidelberg (1991)
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)
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)
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)
Matsui, M.: On correlation between the order of s-boxes and the strength of DES. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 366-375. Springer, Heidelberg (1995)
Matsui, M., Yamagishi, A.: A new method for known plaintext attack of FEAL cipher. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 81-91. Springer, Heidelberg (1993)
McKay, K.A., Vora, P.L.: Analysis of ARX functions: pseudo-linear methods for approximation, differentials, and evaluating diffusion. Cryptology ePrint Archive, report 2014/895 (2014). http://eprint.iacr.org/
Mouha, N., Preneel, B.: Towards finding optimal differential characteristics for ARX: application to Salsa20. Cryptology ePrint Archive, report 2013/328 (2013). http://eprint.iacr.org/
Mouha, N., Velichkov, V., De Cannière, C., Preneel, B.: The differential analysis of S-functions. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 36-56. Springer, Heidelberg (2011)
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)
National Institute of Standards, U.S. Department of Commerce. FIPS 47: Data Encryption Standard (1977)
NIST: Lightweight Cryptography Workshop (2015). http://www.nist.gov/itl/csd/ct/lwcworkshop2015.cfm, July 2015
Nyberg, K., Wallén, J.: Improved linear distinguishers for SNOW2.0. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 144-162. Springer, Heidelberg (2006)
Schulte-Geers, E.: On CCZ-equivalence of addition mod 2n. Des. Codes Crypt. 66(1-3), 111-127 (2013)
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)
Varrette, S., Bouvry, P., Cartiaux, H., Georgatos, F.: Management of an academic HPC cluster: the UL experience. In: Proceedings of the 2014 International Conference on High Performance Computing & Simulation (HPCS 2014), pp. 959-967. IEEE, Bologna, Italy, July 2014
Velichkov, V.: YAARX: Yet another toolkit for the analysis of ARX cryptographic algorithms. Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, 2013-2016. https://github.com/vesselinux/yaarx
Velichkov, V., Corre, Y.L.: Tool for searching for optimal trails in ARX. Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg (2016). https://www.cryptolux.org
Wallén, J.: Linear approximations of addition modulo 2n. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 261-273. Springer, Heidelberg (2003)
Wallén, J.: On the differential and linear properties of addition. Master’s thesis, Helsinki University of Technology (2003)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 1-18. Springer, Heidelberg (2005)
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17-36. Springer, Heidelberg (2005)
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19-35. Springer, Heidelberg (2005)
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)