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

Alex Biryukov; Vesselin Velichkov; Yann Le Corre

doi:10.1007/978-3-662-52993-5_15

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

Alex Biryukov, Vesselin Velichkov, Yann Le Corre

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

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.

Original language	English
Title of host publication	Fast Software Encryption
Subtitle of host publication	23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers
Editors	Thomas Peyrin
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	289-310
Number of pages	22
ISBN (Electronic)	978-3-662-52993-5
ISBN (Print)	978-3-662-52992-8
DOIs	https://doi.org/10.1007/978-3-662-52993-5_15
Publication status	E-pub ahead of print - 20 Jul 2016
Event	24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering - Seattle, United States Duration: 13 Nov 2016 → 18 Nov 2016 http://www.cs.ucdavis.edu/fse2016/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Berlin, Heidelberg
Volume	9783
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Security and Cryptology
Volume	9783

Conference

Conference	24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering
Abbreviated title	FSE 2016
Country/Territory	United States
City	Seattle
Period	13/11/16 → 18/11/16
Internet address	http://www.cs.ucdavis.edu/fse2016/

Access to Document

10.1007/978-3-662-52993-5_15

Vesselin Velichkov
- School of Informatics - UoE Honorary staff
Person: Affiliated Independent Researcher

Cite this

Biryukov, A., Velichkov, V., & Le Corre, Y. (2016). Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck. In T. Peyrin (Ed.), Fast Software Encryption: 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers (pp. 289-310). (Lecture Notes in Computer Science; Vol. 9783), (Security and Cryptology; Vol. 9783). Springer. Advance online publication. https://doi.org/10.1007/978-3-662-52993-5_15

Biryukov, Alex ; Velichkov, Vesselin ; Le Corre, Yann. / Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck. Fast Software Encryption: 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers. editor / Thomas Peyrin. Berlin, Heidelberg : Springer, 2016. pp. 289-310 (Lecture Notes in Computer Science). (Security and Cryptology).

@inproceedings{626ef1be09f54794a3973201e6704614,

title = "Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck",

abstract = "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.",

author = "Alex Biryukov and Vesselin Velichkov and {Le Corre}, Yann",

year = "2016",

month = jul,

day = "20",

doi = "10.1007/978-3-662-52993-5_15",

language = "English",

isbn = "978-3-662-52992-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "289--310",

editor = "Thomas Peyrin",

booktitle = "Fast Software Encryption",

address = "United Kingdom",

note = "24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering, FSE 2016 ; Conference date: 13-11-2016 Through 18-11-2016",

url = "http://www.cs.ucdavis.edu/fse2016/",

}

Biryukov, A, Velichkov, V & Le Corre, Y 2016, Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck. in T Peyrin (ed.), Fast Software Encryption: 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9783, Security and Cryptology, vol. 9783, Springer, Berlin, Heidelberg, pp. 289-310, 24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering, Seattle, Washington, United States, 13/11/16. https://doi.org/10.1007/978-3-662-52993-5_15

Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck. / Biryukov, Alex; Velichkov, Vesselin; Le Corre, Yann.
Fast Software Encryption: 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers. ed. / Thomas Peyrin. Berlin, Heidelberg: Springer, 2016. p. 289-310 (Lecture Notes in Computer Science; Vol. 9783), (Security and Cryptology; Vol. 9783).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Biryukov, Alex

AU - Velichkov, Vesselin

AU - Le Corre, Yann

PY - 2016/7/20

Y1 - 2016/7/20

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-52993-5_15

DO - 10.1007/978-3-662-52993-5_15

M3 - Conference contribution

SN - 978-3-662-52992-8

T3 - Lecture Notes in Computer Science

SP - 289

EP - 310

BT - Fast Software Encryption

A2 - Peyrin, Thomas

PB - Springer

CY - Berlin, Heidelberg

T2 - 24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering

Y2 - 13 November 2016 through 18 November 2016

ER -

Biryukov A, Velichkov V, Le Corre Y. Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck. In Peyrin T, editor, Fast Software Encryption: 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers. Berlin, Heidelberg: Springer. 2016. p. 289-310. (Lecture Notes in Computer Science). (Security and Cryptology). Epub 2016 Jul 20. doi: 10.1007/978-3-662-52993-5_15

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

Abstract / Description of output

Publication series

Conference

Access to Document

Fingerprint

Profiles

Vesselin Velichkov

Cite this