Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48

Mohamed Ahmed Abdelraheem; Javad Alizadeh; Hoda A. Alkhzaimi; Mohammad Reza Aref; Nasour Bagheri; Praveen Gauravaram

doi:10.1007/978-3-319-26617-6_9

Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48

Mohamed Ahmed Abdelraheem, Javad Alizadeh, Hoda A. Alkhzaimi, Mohammad Reza Aref, Nasour Bagheri, Praveen Gauravaram

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

Abstract

In this paper we analyse two variants of SIMON family of light-weight block ciphers against variants of linear cryptanalysis and present the best linear cryptanalytic results on these variants of reducedround SIMON to date. We propose a time-memory trade-off method that finds differential/ linear trails for any permutation allowing low Hamming weight differential/ linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32. The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

Original language	English (US)
Title of host publication	Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings
Editors	Alex Biryukov, Vipul Goyal
Publisher	Springer Verlag
Pages	153-179
Number of pages	27
ISBN (Print)	9783319266169
DOIs	https://doi.org/10.1007/978-3-319-26617-6_9
State	Published - 2015
Event	16th International Conference on Cryptology in India, INDOCRYPT 2015 - Bangalore, India Duration: Dec 6 2015 → Dec 9 2015

Publication series

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

Other

Other	16th International Conference on Cryptology in India, INDOCRYPT 2015
Country/Territory	India
City	Bangalore
Period	12/6/15 → 12/9/15

Keywords

Correlation matrix
Linear cryptanalysis
Linear hull
Mixed Integer Programming (MIP)
SIMON

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-26617-6_9

Cite this

Abdelraheem, M. A., Alizadeh, J., Alkhzaimi, H. A., Aref, M. R., Bagheri, N., & Gauravaram, P. (2015). Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48. In A. Biryukov, & V. Goyal (Eds.), Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings (pp. 153-179). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9462). Springer Verlag. https://doi.org/10.1007/978-3-319-26617-6_9

Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48. / Abdelraheem, Mohamed Ahmed; Alizadeh, Javad; Alkhzaimi, Hoda A. et al.
Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings. ed. / Alex Biryukov; Vipul Goyal. Springer Verlag, 2015. p. 153-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9462).

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

Abdelraheem, MA, Alizadeh, J, Alkhzaimi, HA, Aref, MR, Bagheri, N & Gauravaram, P 2015, Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48. in A Biryukov & V Goyal (eds), Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9462, Springer Verlag, pp. 153-179, 16th International Conference on Cryptology in India, INDOCRYPT 2015, Bangalore, India, 12/6/15. https://doi.org/10.1007/978-3-319-26617-6_9

Abdelraheem MA, Alizadeh J, Alkhzaimi HA, Aref MR, Bagheri N, Gauravaram P. Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48. In Biryukov A, Goyal V, editors, Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings. Springer Verlag. 2015. p. 153-179. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-26617-6_9

Abdelraheem, Mohamed Ahmed ; Alizadeh, Javad ; Alkhzaimi, Hoda A. et al. / Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48. Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings. editor / Alex Biryukov ; Vipul Goyal. Springer Verlag, 2015. pp. 153-179 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b60bc36ca68741a69438784dc52115fe,

title = "Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48",

abstract = "In this paper we analyse two variants of SIMON family of light-weight block ciphers against variants of linear cryptanalysis and present the best linear cryptanalytic results on these variants of reducedround SIMON to date. We propose a time-memory trade-off method that finds differential/ linear trails for any permutation allowing low Hamming weight differential/ linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32. The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.",

keywords = "Correlation matrix, Linear cryptanalysis, Linear hull, Mixed Integer Programming (MIP), SIMON",

author = "Abdelraheem, {Mohamed Ahmed} and Javad Alizadeh and Alkhzaimi, {Hoda A.} and Aref, {Mohammad Reza} and Nasour Bagheri and Praveen Gauravaram",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 16th International Conference on Cryptology in India, INDOCRYPT 2015 ; Conference date: 06-12-2015 Through 09-12-2015",

year = "2015",

doi = "10.1007/978-3-319-26617-6_9",

language = "English (US)",

isbn = "9783319266169",

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

publisher = "Springer Verlag",

pages = "153--179",

editor = "Alex Biryukov and Vipul Goyal",

booktitle = "Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings",

}

TY - GEN

T1 - Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48

AU - Abdelraheem, Mohamed Ahmed

AU - Alizadeh, Javad

AU - Alkhzaimi, Hoda A.

AU - Aref, Mohammad Reza

AU - Bagheri, Nasour

AU - Gauravaram, Praveen

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - In this paper we analyse two variants of SIMON family of light-weight block ciphers against variants of linear cryptanalysis and present the best linear cryptanalytic results on these variants of reducedround SIMON to date. We propose a time-memory trade-off method that finds differential/ linear trails for any permutation allowing low Hamming weight differential/ linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32. The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

AB - In this paper we analyse two variants of SIMON family of light-weight block ciphers against variants of linear cryptanalysis and present the best linear cryptanalytic results on these variants of reducedround SIMON to date. We propose a time-memory trade-off method that finds differential/ linear trails for any permutation allowing low Hamming weight differential/ linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32. The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

KW - Correlation matrix

KW - Linear cryptanalysis

KW - Linear hull

KW - Mixed Integer Programming (MIP)

KW - SIMON

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

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

U2 - 10.1007/978-3-319-26617-6_9

DO - 10.1007/978-3-319-26617-6_9

M3 - Conference contribution

AN - SCOPUS:84951870245

SN - 9783319266169

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

SP - 153

EP - 179

BT - Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings

A2 - Biryukov, Alex

A2 - Goyal, Vipul

PB - Springer Verlag

T2 - 16th International Conference on Cryptology in India, INDOCRYPT 2015

Y2 - 6 December 2015 through 9 December 2015

ER -

Improved linear cryptanalysis of reduced-round SIMON-32 and SIMON-48

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this