Related-key rectangle attack on round-reduced khudra block cipher

Xiaoshuang Ma; Kexin Qiao

doi:10.1007/978-3-319-25645-0_22

Related-key rectangle attack on round-reduced khudra block cipher

Xiaoshuang Ma, Kexin Qiao^*

^*Corresponding author for this work

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

9 Citations (Scopus)

Abstract

Khudra is a block cipher proposed in the SPACE’2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active F-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of Khudra against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability 2⁻⁴⁸ for the 14-round Khudra, which is better than the highest probability related-key boomerang quartet of the 14-round Khudra of probability at most 2⁻⁷² claimed by the designers. Then we propose a related-key rectangle attack on the 16-round Khudra without whitening key by constructing a related-key rectangle distinguisher for 12-round Khudra with a probability of 2^−23.82. The attack has time complexity of 278.68 memory accesses and data complexity of 257.82 chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced Khudra.

Original language	English
Title of host publication	Network and System Security - 9th International Conference, NSS 2015, Proceedings
Editors	Shouhuai Xu, Meikang Qiu, Haibo Zhang, Moti Yung
Publisher	Springer Verlag
Pages	331-344
Number of pages	14
ISBN (Print)	9783319256443
DOIs	https://doi.org/10.1007/978-3-319-25645-0_22
Publication status	Published - 2015
Externally published	Yes
Event	9th International Conference on Network and System Security, NSS 2015 - New York, United States Duration: 3 Nov 2015 → 5 Nov 2015

Publication series

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

Conference

Conference	9th International Conference on Network and System Security, NSS 2015
Country/Territory	United States
City	New York
Period	3/11/15 → 5/11/15

Keywords

Khudra block cipher
Rectangle attack
Related-key attack

Access to Document

10.1007/978-3-319-25645-0_22

Cite this

Ma, X., & Qiao, K. (2015). Related-key rectangle attack on round-reduced khudra block cipher. In S. Xu, M. Qiu, H. Zhang, & M. Yung (Eds.), Network and System Security - 9th International Conference, NSS 2015, Proceedings (pp. 331-344). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9408). Springer Verlag. https://doi.org/10.1007/978-3-319-25645-0_22

Ma, Xiaoshuang ; Qiao, Kexin. / Related-key rectangle attack on round-reduced khudra block cipher. Network and System Security - 9th International Conference, NSS 2015, Proceedings. editor / Shouhuai Xu ; Meikang Qiu ; Haibo Zhang ; Moti Yung. Springer Verlag, 2015. pp. 331-344 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{aafb062a6073459ab0cc96310fda5b0f,

title = "Related-key rectangle attack on round-reduced khudra block cipher",

abstract = "Khudra is a block cipher proposed in the SPACE{\textquoteright}2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active F-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of Khudra against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability 2−48 for the 14-round Khudra, which is better than the highest probability related-key boomerang quartet of the 14-round Khudra of probability at most 2−72 claimed by the designers. Then we propose a related-key rectangle attack on the 16-round Khudra without whitening key by constructing a related-key rectangle distinguisher for 12-round Khudra with a probability of 2−23.82. The attack has time complexity of 278.68 memory accesses and data complexity of 257.82 chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced Khudra.",

keywords = "Khudra block cipher, Rectangle attack, Related-key attack",

author = "Xiaoshuang Ma and Kexin Qiao",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 9th International Conference on Network and System Security, NSS 2015 ; Conference date: 03-11-2015 Through 05-11-2015",

year = "2015",

doi = "10.1007/978-3-319-25645-0_22",

language = "English",

isbn = "9783319256443",

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

publisher = "Springer Verlag",

pages = "331--344",

editor = "Shouhuai Xu and Meikang Qiu and Haibo Zhang and Moti Yung",

booktitle = "Network and System Security - 9th International Conference, NSS 2015, Proceedings",

address = "Germany",

}

Ma, X & Qiao, K 2015, Related-key rectangle attack on round-reduced khudra block cipher. in S Xu, M Qiu, H Zhang & M Yung (eds), Network and System Security - 9th International Conference, NSS 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9408, Springer Verlag, pp. 331-344, 9th International Conference on Network and System Security, NSS 2015, New York, United States, 3/11/15. https://doi.org/10.1007/978-3-319-25645-0_22

Related-key rectangle attack on round-reduced khudra block cipher. / Ma, Xiaoshuang; Qiao, Kexin.
Network and System Security - 9th International Conference, NSS 2015, Proceedings. ed. / Shouhuai Xu; Meikang Qiu; Haibo Zhang; Moti Yung. Springer Verlag, 2015. p. 331-344 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9408).

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

TY - GEN

T1 - Related-key rectangle attack on round-reduced khudra block cipher

AU - Ma, Xiaoshuang

AU - Qiao, Kexin

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

PY - 2015

Y1 - 2015

N2 - Khudra is a block cipher proposed in the SPACE’2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active F-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of Khudra against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability 2−48 for the 14-round Khudra, which is better than the highest probability related-key boomerang quartet of the 14-round Khudra of probability at most 2−72 claimed by the designers. Then we propose a related-key rectangle attack on the 16-round Khudra without whitening key by constructing a related-key rectangle distinguisher for 12-round Khudra with a probability of 2−23.82. The attack has time complexity of 278.68 memory accesses and data complexity of 257.82 chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced Khudra.

AB - Khudra is a block cipher proposed in the SPACE’2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active F-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of Khudra against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability 2−48 for the 14-round Khudra, which is better than the highest probability related-key boomerang quartet of the 14-round Khudra of probability at most 2−72 claimed by the designers. Then we propose a related-key rectangle attack on the 16-round Khudra without whitening key by constructing a related-key rectangle distinguisher for 12-round Khudra with a probability of 2−23.82. The attack has time complexity of 278.68 memory accesses and data complexity of 257.82 chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced Khudra.

KW - Khudra block cipher

KW - Rectangle attack

KW - Related-key attack

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

U2 - 10.1007/978-3-319-25645-0_22

DO - 10.1007/978-3-319-25645-0_22

M3 - Conference contribution

AN - SCOPUS:84952359731

SN - 9783319256443

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

SP - 331

EP - 344

BT - Network and System Security - 9th International Conference, NSS 2015, Proceedings

A2 - Xu, Shouhuai

A2 - Qiu, Meikang

A2 - Zhang, Haibo

A2 - Yung, Moti

PB - Springer Verlag

T2 - 9th International Conference on Network and System Security, NSS 2015

Y2 - 3 November 2015 through 5 November 2015

ER -

Ma X, Qiao K. Related-key rectangle attack on round-reduced khudra block cipher. In Xu S, Qiu M, Zhang H, Yung M, editors, Network and System Security - 9th International Conference, NSS 2015, Proceedings. Springer Verlag. 2015. p. 331-344. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-25645-0_22

Related-key rectangle attack on round-reduced khudra block cipher

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this