Tight Security of TNT and Beyond
(2024) 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14651 LNCS. p.249-279- Abstract
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(2n/2)... (More)
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(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.
(Less)
- author
- Jha, Ashwin ; Khairallah, Mustafa LU ; Nandi, Mridul and Saha, Abishanka
- organization
- publishing date
- 2024
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- 4-LRW1, birthday-bound attack, CLRW2, LRW1, TNT
- host publication
- Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Joye, Marc and Leander, Gregor
- volume
- 14651 LNCS
- pages
- 31 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024
- conference location
- Zurich, Switzerland
- conference dates
- 2024-05-26 - 2024-05-30
- external identifiers
-
- scopus:85193632436
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 9783031587153
- DOI
- 10.1007/978-3-031-58716-0_9
- language
- English
- LU publication?
- yes
- id
- 6d119e1a-aa24-411e-9507-fe46413dc46d
- date added to LUP
- 2024-06-17 13:39:45
- date last changed
- 2024-06-19 13:38:23
@inproceedings{6d119e1a-aa24-411e-9507-fe46413dc46d,
abstract = {{<p>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<sup>n/2</sup>) 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 2<sup>3n/4</sup> 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.</p>}},
author = {{Jha, Ashwin and Khairallah, Mustafa and Nandi, Mridul and Saha, Abishanka}},
booktitle = {{Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings}},
editor = {{Joye, Marc and Leander, Gregor}},
isbn = {{9783031587153}},
issn = {{0302-9743}},
keywords = {{4-LRW1; birthday-bound attack; CLRW2; LRW1; TNT}},
language = {{eng}},
pages = {{249--279}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{Tight Security of TNT and Beyond}},
url = {{http://dx.doi.org/10.1007/978-3-031-58716-0_9}},
doi = {{10.1007/978-3-031-58716-0_9}},
volume = {{14651 LNCS}},
year = {{2024}},
}