[Resource Topic] 2023/1272: Tight Security of TNT and Beyond: Attacks, Proofs and Possibilities for the Cascaded LRW Paradigm

Welcome to the resource topic for 2023/1272

Tight Security of TNT and Beyond: Attacks, Proofs and Possibilities for the Cascaded LRW Paradigm

Authors: Ashwin Jha, Mustafa Khairallah, Mridul Nandi, Abishanka Saha


Liskov, Rivest and Wagner laid the theoretical foundations for tweakable block ciphers (TBC). In a seminal paper, they proposed two (up to) birthday-bound secure design strategies — LRW1 and LRW2 — to convert any block cipher into a TBC. Several of the follow-up works consider cascading of LRW-type TBCs to construct beyond-the-birthday bound (BBB) secure TBCs. Landecker et al. demonstrated that just two-round cascading of LRW2 can already give a BBB security. Bao et al. undertook a similar exercise in context of LRW1 with TNT — a three-round cascading of LRW1 — that has been shown to achieve BBB security as well. In this paper, we present a CCA distinguisher on TNT that achieves a non-negligible advantage with O(2^{n/2}) queries, directly contradicting the security claims made by the designers. We provide a rigorous and complete advantage calculation coupled with experimental verifications that further support our claim. Next, we provide new and simple proofs of birthday-bound CCA security for both TNT and its single-key variant, which confirm the tightness of our attack. Furthering on to a more positive note, we show that adding just one more block cipher call, referred as 4-LRW1, does not just reestablish the BBB security, but also amplifies it up to 2^{3n/4} queries. As a side-effect of this endeavour, we propose a new abstraction of the cascaded LRW-design philosophy, referred to as the LRW+ paradigm, comprising two block cipher calls sandwiched between a pair of tweakable universal hashes. This helps us to provide a modular proof approach covering all cascaded LRW constructions with at least 2 rounds, including 4-LRW1, and its more established relative, the well-known CLRW2, or more aptly, 2-LRW2.

ePrint: https://eprint.iacr.org/2023/1272

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .