Communications in Cryptology IACR CiC

CCA Security with Short AEAD Tags

Authors

Mustafa Khairallah
Mustafa Khairallah ORCID
Seagate Research Group, Singapore, Singapore
Department of Electrical and Information Technology, Lund University, Lund, Sweden
mustafa dot khairallah dot 1608 at eit dot lth dot se
Keywords: Chosen Ciphertext Attacks IND-CCA AEAD SIV Authentication Rugged PRP

Abstract

The size of the authentication tag represents a significant overhead for applications that are limited by bandwidth or memory. Hence, some authenticated encryption designs have a smaller tag than the required privacy level, which was also suggested by the NIST lightweight cryptography standardization project. In the ToSC 2022, two papers have raised questions about the IND-CCA security of AEAD schemes in this situation. These papers show that (a) online AE cannot provide IND-CCA security beyond the tag length, and (b) it is possible to have IND-CCA security beyond the tag length in a restricted Encode-then-Encipher framework. In this paper, we address some of the remaining gaps in this area. Our main result is to show that, for a fixed stretch, Pseudo-Random Injection security implies IND-CCA security as long as the minimum ciphertext size is at least as large as the required IND-CCA security level. We also show that this bound is tight and that any AEAD scheme that allows empty plaintexts with a fixed stretch cannot achieve IND-CCA security beyond the tag length. Next, we look at the weaker notion of MRAE security, and show that two-pass schemes that achieve MRAE security do not achieve IND-CCA security beyond the tag size. This includes SIV and rugged PRPs.

References

[AFL+16]
Farzaneh Abed, Christian Forler, Eik List, Stefan Lucks, and Jakob Wenzel. RIV for robust authenticated encryption. In Fast Software Encryption: 23rd International Conference, FSE 2016, 23–42. Springer, 2016. https://doi.org/https://doi.org/10.1007/978-3-662-52993-5_2.
Google Scholar ePrint
[BN00]
Mihir Bellare and Chanathip Namprempre. Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In Tatsuaki Okamoto, editor, Advances in Cryptology — ASIACRYPT 2000, 531–545. Springer Berlin Heidelberg, 2000. https://doi.org/https://doi.org/10.1007/3-540-44448-3_41.
Google Scholar ePrint
[CG16]
Colin Chaigneau and Henri Gilbert. Is AEZ v4. 1 sufficiently resilient against key-recovery attacks? IACR Transactions on Symmetric Cryptology, 1:654–682, 2016. https://doi.org/https://doi.org/10.13154/tosc.v2016.i1.114-133.
Google Scholar ePrint
[CIMN20]
Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based Authenticated Encryption: How Small Can We Go? Journal of Cryptology, 33(3):703–741, 2020. https://doi.org/https://doi.org/10.1007/978-3-319-66787-4_14.
Google Scholar ePrint
[com19]
Crypto competitions. Caesar: competition for authenticated encryption: security, applicability, and robustness. Feb 2019.
Google Scholar ePrint
[DK22]
Jean Paul Degabriele and Vukašin Karadžić. Overloading the nonce: rugged PRPs, nonce-set AEAD, and order-resilient channels. In Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV, 264–295. Springer, 2022. https://doi.org/https://doi.org/10.1007/978-3-031-15985-5_10.
Google Scholar ePrint
[HII+22]
Akinori Hosoyamada, Akiko Inoue, Ryoma Ito, Tetsu Iwata, Kazuhiko Mimematsu, Ferdinand Sibleyras, and Yosuke Todo. Cryptanalysis of Rocca and Feasibility of Its Security Claim. IACR Transactions on Symmetric Cryptology, 2022(3):123–151, Sep. 2022. https://doi.org/10.46586/tosc.v2022.i3.123-151.
Google Scholar ePrint
[HKR15]
Viet Tung Hoang, Ted Krovetz, and Phillip Rogaway. Robust Authenticated-Encryption AEZ and the Problem That It Solves. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, 15–44. Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. https://doi.org/https://doi.org/10.1007/978-3-662-46800-5_2.
Google Scholar ePrint
[IKMP20]
Tetsu Iwata, Mustafa Khairallah, Kazuhiko Minematsu, and Thomas Peyrin. Duel of the Titans: the Romulus and Remus Families of Lightweight AEAD Algorithms. IACR Transactions on Symmetric Cryptology, pages 43–120, 2020. https://doi.org/https://doi.org/10.13154/tosc.v2020.i1.43-120.
Google Scholar ePrint
[Kha22]
Mustafa Khairallah. Security of COFB against chosen ciphertext attacks. IACR Transactions on Symmetric Cryptology, pages 138–157, 2022. https://doi.org/https://doi.org/10.46586/tosc.v2022.i1.138-157.
Google Scholar ePrint
[oST19]
National Institute of Standardization and Technology. Lightweight cryptography. 2019.
Google Scholar ePrint
[PS16]
Thomas Peyrin and Yannick Seurin. Counter-in-Tweak: Authenticated Encryption Modes for Tweakable Block Ciphers. In Advances in Cryptology–CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, 33–63. Springer, 2016. https://doi.org/https://doi.org/10.1007/978-3-662-53018-4_2.
Google Scholar ePrint
[Rog02]
Phillip Rogaway. Authenticated-Encryption with Associated Data. In Proceedings of the 9th ACM Conference on Computer and Communications Security, 98–107. 2002. https://doi.org/https://doi.org/10.1145/586110.586125.
Google Scholar ePrint
[RS06]
Phillip Rogaway and Thomas Shrimpton. A Provable-Security Treatment of the Key-Wrap Problem. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 373–390. Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. https://doi.org/https://doi.org/10.1007/11761679_23.
Google Scholar ePrint
[Sho04]
Victor Shoup. Sequences of games: a tool for taming complexity in security proofs. 2004.
Google Scholar ePrint
[SLN+21]
Kosei Sakamoto, Fukang Liu, Yuto Nakano, Shinsaku Kiyomoto, and Takanori Isobe. Rocca: an efficient AES-based encryption scheme for beyond 5G. IACR Transactions on Symmetric Cryptology, pages 1–30, 2021. https://doi.org/https://doi.org/10.46586/tosc.v2021.i2.1-30.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/aevua69p1
History
Submitted: 2024-01-07
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Mustafa Khairallah, CCA Security with Short AEAD Tags. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/aevua69p1.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.