Paper 2023/1212

CLRW1$^{3}$ is not Secure Beyond the Birthday Bound: Breaking TNT with ${O(2^{n/2})}$ queries

Abstract

In this paper, we present a new distinguisher for the Tweak-aNd-Tweak (TNT) tweakable block cipher with $O(2^{n/2})$ complexity. The distinguisher is an adaptive chosen ciphertext distinguisher, unlike previous attacks that are only non-adaptive chosen plaintext attacks. However, the attack contradicts the security claims made by the designers. Given TNT can be seen as the three-round CLRW1 tweakable block cipher, our attack matches its more conservative bound. We provide the distinguisher description, a probabilistic analysis of its behaviour, experimental verification and an analysis of why the proof fails to capture the security of TNT. In summary, the distinguisher is based on collision counting and exploits non-uniformity in the statistical behaviour of random permutations. It reduces the goal of finding the collision to solving a difference equation defined over a random permutation. Due to this relation, the number of collisions observed by the distinguisher is twice as expected from an ideal tweakable block cipher.

Note: See [Cryptology ePrint Archive: Report 2023/1272] that appeared on August 24, 2023, which combines and extends the findings of [Cryptology ePrint Archive: Report 2023/1233] (by Jha, Nandi and Saha), and this report.