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

Department of Applied Mathematics and Computer Science

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

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
Title of host publication	Progress in Cryptology – INDOCRYPT 2015 : Proceedings of the 16th International Conference on Cryptology in India
Editors	Alex Biryukov, Vipul Goyal
Publisher	Springer
Publication date	2015
Pages	153-179
ISBN (Print)	978-3-319-26616-9
ISBN (Electronic)	978-3-319-26617-6
DOIs	https://doi.org/10.1007/978-3-319-26617-6_9
Publication status	Published - 2015
Event	16th International Conference on Cryptology in India - Bangalore, India Duration: 6 Dec 2015 → 9 Dec 2015 Conference number: 16 http://www.indocrypt2015.org/

Conference

Conference	16th International Conference on Cryptology in India
Number	16
Country/Territory	India
City	Bangalore
Period	06/12/2015 → 09/12/2015
Internet address	http://www.indocrypt2015.org/

Series	Lecture Notes in Computer Science
Volume	9462
ISSN	0302-9743

Keywords

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

Access to Document

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

OpenUrl availability

Full text

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: Proceedings of the 16th International Conference on Cryptology in India (pp. 153-179). Springer. https://doi.org/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: Proceedings of the 16th International Conference on Cryptology in India. editor / Alex Biryukov ; Vipul Goyal. Springer, 2015. pp. 153-179 (Lecture Notes in Computer Science, Vol. 9462).

@inproceedings{112f454a2e3a4b57add7de0220f86e4f,

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 = "SIMON, Linear cryptanalysis, Linear hull, Correlation matrix, Mixed Integer Programming (MIP), MIP",

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

year = "2015",

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

language = "English",

isbn = "978-3-319-26616-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "153--179",

editor = "Biryukov, {Alex } and Goyal, {Vipul }",

booktitle = "Progress in Cryptology – INDOCRYPT 2015",

note = "16th International Conference on Cryptology in India, INDOCRYPT 2015 ; Conference date: 06-12-2015 Through 09-12-2015",

url = "http://www.indocrypt2015.org/",

}

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: Proceedings of the 16th International Conference on Cryptology in India. Springer, Lecture Notes in Computer Science, vol. 9462, pp. 153-179, 16th International Conference on Cryptology in India, Bangalore, India, 06/12/2015. 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: Proceedings of the 16th International Conference on Cryptology in India. ed. / Alex Biryukov; Vipul Goyal. Springer, 2015. p. 153-179 (Lecture Notes in Computer Science, Vol. 9462).

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

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 - Conference code: 16

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 - SIMON

KW - Linear cryptanalysis

KW - Linear hull

KW - Correlation matrix

KW - Mixed Integer Programming (MIP)

KW - MIP

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

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

M3 - Article in proceedings

SN - 978-3-319-26616-9

T3 - Lecture Notes in Computer Science

SP - 153

EP - 179

BT - Progress in Cryptology – INDOCRYPT 2015

A2 - Biryukov, Alex

A2 - Goyal, Vipul

PB - Springer

T2 - 16th International Conference on Cryptology in India

Y2 - 6 December 2015 through 9 December 2015

ER -

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: Proceedings of the 16th International Conference on Cryptology in India. Springer. 2015. p. 153-179. (Lecture Notes in Computer Science, Vol. 9462). doi: 10.1007/978-3-319-26617-6_9

Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this