Paper 2019/208

Related-Tweak Statistical Saturation Cryptanalysis and Its Application on QARMA

Muzhou Li, Kai Hu, and Meiqin Wang

Abstract

Statistical saturation attack takes advantage of a set of plaintext with some bits fixed while the others vary randomly, and then track the evolution of a non-uniform plaintext distribution through the cipher. Previous statistical saturation attacks are all implemented under single-key setting, and there is no public attack models under related-key/tweak setting. In this paper, we propose a new cryptanalytic method which can be seen as related-key/tweak statistical saturation attack by revealing the link between the related-key/tweak statistical saturation distinguishers and KDIB (Key Difference Invariant Bias) / TDIB (Tweak Difference Invariant Bias) ones. KDIB cryptanalysis was proposed by Bogdanov \emph{et al.} at ASIACRYPT'13 and utilizes the property that there can exist linear trails such that their biases are deterministically invariant under key difference. And this method can be easily extended to TDIB distinguishers if the tweak is also alternated. The link between them provides a new and more efficient way to find related-key/tweak statistical saturation distinguishers in ciphers. Thereafter, an automatic searching algorithm for KDIB/TDIB distinguishers is also given in this paper, which can be implemented to find word-level KDIB distinguishers for S-box based key-alternating ciphers. We apply this algorithm to \texttt{QARMA}-64 and give related-tweak statistical saturation attack for 10-round \texttt{QARMA}-64 with outer whitening key. Besides, an 11-round attack on \texttt{QARMA}-128 is also given based on the TDIB technique. Compared with previous public attacks on \texttt{QARMA} including outer whitening key, all attacks presented in this paper are the best ones in terms of the number of rounds.