Paper 2021/1690

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

Yaqi Xu, Baofeng Wu, and Dongdai Lin


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)
Secret-key cryptography
Publication info
Published elsewhere. ICICS 2021
Rotational-linear attackARX cipherpartitioningkey recoveryChaskeyChaCha permutation
Contact author(s)
xuyaqi @ iie ac cn
wubaofeng @ iie ac cn
2021-12-30: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.