Rotational-Linear Attack: A New Framework of Cryptanalysis on ARX ciphers with Applications to Chaskey

Yaqi Xu, Baofeng Wu, and Dongdai Lin

Abstract

In this paper, we formulate a new framework of cryptanalysis called rotational-linear attack on ARX ciphers. We firstly build an efficient distinguisher for the cipher $E$ consisted of the rotational attack and the linear attack together with some intermediate variables. Then a key recovery technique is introduced with which we can recover some bits of the last whitening key in the related-key scenario. To decrease data complexity of our attack, we also apply a new method, called bit flipping, in the rotational cryptanalysis for the first time and the effective partitioning technique to the key-recovery part. Applying the new framework of attack to the MAC algorithm Chaskey, we build a full-round distinguisher over it. Besides, we have recovered $21$ bits of information of the key in the related-key scenario, for keys belonging to a large weak-key class based on 6-round distinguisher. The data complexity is $2^{38.8}$ and the time complexity is $2^{46.8}$. Before our work, the rotational distinguisher can only be used to reveal key information by checking weak-key conditions. This is the first time it is applied in a last-rounds key-recovery attack. We build a 17-round rotational-linear distinguisher for ChaCha permutation as an improvement compared to single rotational cryptanalysis over it.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. ICICS 2021
DOI
10.1007/978-3-030-88052-1_12
Keywords
Contact author(s)
xuyaqi @ iie ac cn
wubaofeng @ iie ac cn
History
Short URL
https://ia.cr/2021/1690

CC BY

BibTeX

@misc{cryptoeprint:2021/1690,
author = {Yaqi Xu and Baofeng Wu and Dongdai Lin},
title = {Rotational-Linear Attack: A New Framework of Cryptanalysis on ARX ciphers with Applications to Chaskey},
howpublished = {Cryptology ePrint Archive, Paper 2021/1690},
year = {2021},
doi = {10.1007/978-3-030-88052-1_12},
note = {\url{https://eprint.iacr.org/2021/1690}},
url = {https://eprint.iacr.org/2021/1690}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.