Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers

Siwei Sun; Lei Hu; Peng Wang; Kexin Qiao; Xiaoshuang Ma; Ling Song

doi:10.1007/978-3-662-45611-8_9

Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers

Siwei Sun^*, Lei Hu, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Ling Song

^*Corresponding author for this work

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

300 Citations (Scopus)

Abstract

We propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry respectively. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-integer Linear Programming (MILP) technique, we propose an automatic method for evaluating the security of bit-oriented block ciphers against the (related-key) differential attack with several techniques for obtaining tighter security bounds, and a new tool for finding (related-key) differential characteristics automatically for bit-oriented block ciphers.

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I
Editors	Palash Sarkar, Tetsu Iwata
Publisher	Springer Verlag
Pages	158-178
Number of pages	21
ISBN (Electronic)	9783662456101
DOIs	https://doi.org/10.1007/978-3-662-45611-8_9
Publication status	Published - 2014
Externally published	Yes
Event	20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014 - Kaoshiung, Taiwan, Province of China Duration: 7 Dec 2014 → 11 Dec 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8873
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014
Country/Territory	Taiwan, Province of China
City	Kaoshiung
Period	7/12/14 → 11/12/14

Keywords

Automatic cryptanalysis
Convex hull
Mixed-integer Linear Programming
Related-key differential attack

Access to Document

10.1007/978-3-662-45611-8_9

Cite this

Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., & Song, L. (2014). Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In P. Sarkar, & T. Iwata (Eds.), Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I (pp. 158-178). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8873). Springer Verlag. https://doi.org/10.1007/978-3-662-45611-8_9

Sun, Siwei ; Hu, Lei ; Wang, Peng et al. / Automatic security evaluation and (related-key) differential characteristic search : Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I. editor / Palash Sarkar ; Tetsu Iwata. Springer Verlag, 2014. pp. 158-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{94fdc7c836364678a8add828430dfe00,

title = "Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers",

abstract = "We propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry respectively. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-integer Linear Programming (MILP) technique, we propose an automatic method for evaluating the security of bit-oriented block ciphers against the (related-key) differential attack with several techniques for obtaining tighter security bounds, and a new tool for finding (related-key) differential characteristics automatically for bit-oriented block ciphers.",

keywords = "Automatic cryptanalysis, Convex hull, Mixed-integer Linear Programming, Related-key differential attack",

author = "Siwei Sun and Lei Hu and Peng Wang and Kexin Qiao and Xiaoshuang Ma and Ling Song",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2014.; 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014 ; Conference date: 07-12-2014 Through 11-12-2014",

year = "2014",

doi = "10.1007/978-3-662-45611-8_9",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "158--178",

editor = "Palash Sarkar and Tetsu Iwata",

booktitle = "Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I",

address = "Germany",

}

Sun, S, Hu, L, Wang, P, Qiao, K, Ma, X & Song, L 2014, Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. in P Sarkar & T Iwata (eds), Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8873, Springer Verlag, pp. 158-178, 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014, Kaoshiung, Taiwan, Province of China, 7/12/14. https://doi.org/10.1007/978-3-662-45611-8_9

Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. / Sun, Siwei; Hu, Lei; Wang, Peng et al.
Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I. ed. / Palash Sarkar; Tetsu Iwata. Springer Verlag, 2014. p. 158-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8873).

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

TY - GEN

T1 - Automatic security evaluation and (related-key) differential characteristic search

T2 - 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2014

AU - Sun, Siwei

AU - Hu, Lei

AU - Wang, Peng

AU - Qiao, Kexin

AU - Ma, Xiaoshuang

AU - Song, Ling

N1 - Publisher Copyright: © International Association for Cryptologic Research 2014.

PY - 2014

Y1 - 2014

N2 - We propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry respectively. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-integer Linear Programming (MILP) technique, we propose an automatic method for evaluating the security of bit-oriented block ciphers against the (related-key) differential attack with several techniques for obtaining tighter security bounds, and a new tool for finding (related-key) differential characteristics automatically for bit-oriented block ciphers.

AB - We propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry respectively. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-integer Linear Programming (MILP) technique, we propose an automatic method for evaluating the security of bit-oriented block ciphers against the (related-key) differential attack with several techniques for obtaining tighter security bounds, and a new tool for finding (related-key) differential characteristics automatically for bit-oriented block ciphers.

KW - Automatic cryptanalysis

KW - Convex hull

KW - Mixed-integer Linear Programming

KW - Related-key differential attack

UR - http://www.scopus.com/inward/record.url?scp=84916603282&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-45611-8_9

DO - 10.1007/978-3-662-45611-8_9

M3 - Conference contribution

AN - SCOPUS:84916603282

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 178

BT - Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I

A2 - Sarkar, Palash

A2 - Iwata, Tetsu

PB - Springer Verlag

Y2 - 7 December 2014 through 11 December 2014

ER -

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, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part I. Springer Verlag. 2014. p. 158-178. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-45611-8_9

Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this