2023-1272.pdf (710.92 kB)

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

Download (710.92 kB)
posted on 2024-05-22, 07:00 authored by 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 tworound cascading of LRW2 can already give a BBB security. Bao et al. undertook a similar exercise in context of LRW1 with TNT — a threeround 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(2n/2 ) queries, directly contradicting the security claims made by the designers. We provide a rigorous and complete advantage calculation coupled with experimental verification 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 re-establish the BBB security, but also amplifies it up to 23n/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 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


Primary Research Area

  • Algorithmic Foundations and Cryptography


@misc{Jha:Khairallah:Nandi:Saha:2023, title = "Tight Security of TNT and Beyond: Attacks, Proofs and Possibilities for the Cascaded LRW Paradigm.", author = "Jha, Ashwin" AND "Khairallah, Mustafa" AND "Nandi, Mridul" AND "Saha, Abishanka", year = 2023, month = 8 }

Usage metrics


    No categories selected



    Ref. manager