Rotational Cryptanalysis From a Differential-linear Perspective: Practical Distinguishers for Round-reduced FRIET, Xoodoo, and Alzette

Yunwen Liu, Siwei Sun, and Chao Li

Abstract

The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was proposed by Langford and Hellman at CRYPTO 1994. From the exact formula for evaluating the bias of a differential-linear distinguisher (JoC 2017), to the differential-linear connectivity table (DLCT) technique for dealing with the dependencies in the switch between the differential and linear parts (EUROCRYPT 2019), and to the improvements in the context of cryptanalysis of ARX primitives (CRYPTO 2020), we have seen significant development of the differential-linear attack during the last four years. In this work, we further extend this framework by replacing the differential part of the attack by rotational-xor differentials. Along the way, we establish the theoretical link between the rotational-xor differential and linear approximations, revealing that it is nontrivial to directly apply the closed formula for the bias of ordinary differential- linear attack to rotational differential-linear cryptanalysis. We then revisit the rotational cryptanalysis from the perspective of differential- linear cryptanalysis and generalize Morawiecki et al.’s technique for analyzing Keccak, which leads to a practical method for estimating the bias of a (rotational) differential-linear distinguisher in the special case where the output linear mask is a unit vector. Finally, we apply the rotational differential-linear technique to the permutations involved in FRIET, Xoodoo, Alzette, and SipHash. This gives significant improvements over existing cryptanalytic results or offers explanations for previous experimental distinguishers without a theoretical foundation. To confirm the validity of our analysis, all distinguishers with practical complexities are verified experimentally.

Available format(s)
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in Eurocrypt 2021
Keywords
Differential-linear CryptanalysisRotational CryptanalysisARXFRIETXoodooAlzetteSipHash
Contact author(s)
univerlyw @ hotmail com
siweisun isaac @ gmail com
History
2021-02-21: revised
See all versions
Short URL
https://ia.cr/2021/189

CC BY

BibTeX

@misc{cryptoeprint:2021/189,
author = {Yunwen Liu and Siwei Sun and Chao Li},
title = {Rotational Cryptanalysis From a Differential-linear Perspective: Practical Distinguishers for Round-reduced FRIET, Xoodoo, and Alzette},
howpublished = {Cryptology ePrint Archive, Paper 2021/189},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/189}},
url = {https://eprint.iacr.org/2021/189}
}

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