FEDT: Forkcipher-based Leakage-resilient Beyond-birthday-secure AE
Authors
Nilanjan Datta, Avijit Dutta, Eik List, Sougata Mandal
Nilanjan Datta
Institute for Advancing Intelligence, TCG CREST, Kolkata, India
nilanjan dot datta at tcgcrest dot org
nilanjan dot datta at tcgcrest dot org
Eik List
Independent Researcher, Singapore, Singapore
elist at posteo dot de
elist at posteo dot de
Abstract
There has been a notable surge of research on leakage-resilient authenticated encryption (AE) schemes, in the bounded as well as the unbounded leakage model. The latter has garnered significant attention due to its detailed and practical orientation. Designers have commonly utilized (tweakable) block ciphers, exemplified by the TEDT scheme, achieving $\mathcal{O}(n-\log(n^2))$-bit integrity under leakage and comparable AE security in the black-box setting. However, the privacy of TEDT was limited by $n/2$-bits under leakage; TEDT2 sought to overcome these limitations by achieving improved security with $\mathcal{O}(n-\log n)$-bit integrity and privacy under leakage.
This work introduces FEDT, an efficient leakage-resilient authenticated encryption (AE) scheme based on fork-cipher. Compared to the state-of-the-art schemes TEDT and TEDT2, which process messages with a rate of $1/2$ block per primitive call for encryption and one for authentication, FEDT doubles their rates at the price of a different primitive. FEDT employs a more parallelizable tree-based encryption compared to its predecessors while maintaining $\mathcal{O}(n-\log n)$-bit security for both privacy and integrity under leakage. FEDT prioritizes high throughput at the cost of increased latency. For settings where latency is important, we propose FEDT*, which combines the authentication part of FEDT with a CTR-based encryption. FEDT* offers security equivalent to FEDT while increasing the encryption rate of $4/3$ and reducing the latency.
References
[ABL+14]
Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, and Kan Yasuda. How to Securely Release Unverified Plaintext in Authenticated Encryption. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT I, volume 8873 of Lecture Notes in Computer Science, pages 105–125. 2014. Springer. DOI: 10.1007/978-3-662-45611-8_6
[ALP+19]
Elena Andreeva, Virginie Lallemand, Antoon Purnal, Reza Reyhanitabar, Arnab Roy, and Damian Vizár. Forkcipher: A New Primitive for Authenticated Encryption of Very Short Messages. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT II, volume 11922 of Lecture Notes in Computer Science, pages 153–182. 2019. Springer. DOI: 10.1007/978-3-030-34621-8_6
[BBC+20]
Davide Bellizia, Olivier Bronchain, Gaëtan Cassiers, Vincent Grosso, Chun Guo, Charles Momin, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Mode-Level vs. Implementation-Level Physical Security in Symmetric Cryptography - A Practical Guide Through the Leakage-Resistance Jungle. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO I, volume 12170 of Lecture Notes in Computer Science, pages 369–400. 2020. Springer. DOI: 10.1007/978-3-030-56784-2_13
[BBKN01]
Mihir Bellare, Alexandra Boldyreva, Lars R. Knudsen, and Chanathip Namprempre. Online Ciphers and the Hash-CBC Construction. In Joe Kilian, editor, CRYPTO, volume 2139 of Lecture Notes in Computer Science, pages 292–309. 2001. Springer. DOI: 10.1007/3-540-44647-8_18
[Ber14]
Daniel J. Bernstein. CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness. last update 20 Feb 2019, last accessed 18 July 2023. 2014.
[BGP+19]
Francesco Berti, Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Strong Authenticity with Leakage Under Weak and Falsifiable Physical Assumptions. In Zhe Liu and Moti Yung, editors, Inscrypt, volume 12020 of Lecture Notes in Computer Science, pages 517–532. 2019. Springer. DOI: 10.1007/978-3-030-42921-8_31
[BGP+20]
Francesco Berti, Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. TEDT, a Leakage-Resistant AEAD Mode for High Physical Security Applications. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(1):256–320, 2020. DOI: 10.13154/tches.v2020.i1.256-320
[BGPS21]
Francesco Berti, Chun Guo, Thomas Peters, and François-Xavier Standaert. Efficient Leakage-Resilient MACs Without Idealized Assumptions. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT II, volume 13091 of Lecture Notes in Computer Science, pages 95–123. 2021. Springer. DOI: 10.1007/978-3-030-92075-3_4
[BKP+18]
Francesco Berti, François Koeune, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Ciphertext Integrity with Misuse and Leakage: Definition and Efficient Constructions with Symmetric Primitives. In Jong Kim, Gail-Joon Ahn, Seungjoo Kim, Yongdae Kim, Javier López, and Taesoo Kim, editors, AsiaCCS, pages 37–50. 2018. ACM. DOI: 10.1145/3196494.3196525
[BMOS17]
Guy Barwell, Daniel P. Martin, Elisabeth Oswald, and Martijn Stam. Authenticated Encryption in the Face of Protocol and Side Channel Leakage. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT I, volume 10624 of Lecture Notes in Computer Science, pages 693–723. 2017. Springer. DOI: 10.1007/978-3-319-70694-8_24
[BN00]
Mihir Bellare and Chanathip Namprempre. Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm. In Tatsuaki Okamoto, editor, ASIACRYPT, volume 1976 of Lecture Notes in Computer Science, pages 531–545. 2000. Springer. DOI: 10.1007/3-540-44448-3_41
[BPPS17]
Francesco Berti, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. On Leakage-Resilient Authenticated Encryption with Decryption Leakages. IACR Transactions on Symmetric Cryptology, 2017(3):271–293, 2017. DOI: 10.13154/tosc.v2017.i3.271-293
[BPS19]
Francesco Berti, Olivier Pereira, and François-Xavier Standaert. Reducing the Cost of Authenticity with Leakages: a CIML2-Secure AE Scheme with One Call to a Strongly Protected Tweakable Block Cipher. In Johannes Buchmann, Abderrahmane Nitaj, and Tajje-eddine Rachidi, editors, AFRICACRYPT, volume 11627 of Lecture Notes in Computer Science, pages 229–249. 2019. Springer. DOI: 10.1007/978-3-030-23696-0_12
[BY03]
Mihir Bellare and Bennet S. Yee. Forward-Security in Private-Key Cryptography. In Marc Joye, editor, CT-RSA, volume 2612 of Lecture Notes in Computer Science, pages 1–18. 2003. Springer. DOI: 10.1007/3-540-36563-X_1
[CDD+19]
Donghoon Chang, Nilanjan Datta, Avijit Dutta, Bart Mennink, Mridul Nandi, Somitra Sanadhya, and Ferdinand Sibleyras. Release of Unverified Plaintext: Tight Unified Model and Application to ANYDAE. IACR Transactions on Symmetric Cryptology, 2019(4):119–146, 2019. DOI: 10.13154/tosc.v2019.i4.119-146
[CJRR99]
Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards Sound Approaches to Counteract Power-Analysis Attacks. In Michael J. Wiener, editor, CRYPTO, volume 1666 of Lecture Notes in Computer Science, pages 398–412. 1999. Springer. DOI: 10.1007/3-540-48405-1_26
[DDLM23]
Nilanjan Datta, Avijit Dutta, Eik List, and Sougata Mandal. On the Security of Triplex- and Multiplex-Type Constructions with Smaller Tweaks. In Anupam Chattopadhyay, Shivam Bhasin, Stjepan Picek, and Chester Rebeiro, editors, INDOCRYPT I, volume 14459 of Lecture Notes in Computer Science, pages 25–47. 2023. Springer. DOI: 10.1007/978-3-031-56232-7_2
[DEM+17]
Christoph Dobraunig, Maria Eichlseder, Stefan Mangard, Florian Mendel, and Thomas Unterluggauer. ISAP – Towards Side-Channel Secure Authenticated Encryption. IACR Transactions on Symmetric Cryptology, 2017(1):80–105, 2017. DOI: 10.13154/tosc.v2017.i1.80-105
[DEM+20]
Christoph Dobraunig, Maria Eichlseder, Stefan Mangard, Florian Mendel, Bart Mennink, Robert Primas, and Thomas Unterluggauer. Isap v2.0. IACR Transactions on Symmetric Cryptology, 2020(S1):390–416, 2020. DOI: 10.13154/tosc.v2020.iS1.390-416
[DNT19]
Avijit Dutta, Mridul Nandi, and Suprita Talnikar. Beyond Birthday Bound Secure MAC in Faulty Nonce Model. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT I, volume 11476 of Lecture Notes in Computer Science, pages 437–466. 2019. Springer. DOI: 10.1007/978-3-030-17653-2_15
[Dwo04]
Morris Dworkin. NIST Special Publication 800-38C – Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality [including updates through 7/20/2007]. Technical report, U.S. National Institute of Standards and Technology. 2004.
[Dwo07]
Morris Dworkin. NIST Special Publication 800-38D – Recommendation for block cipher modes of operation: Galois/Counter Mode (GCM) and GMAC. Technical report, U.S. National Institute of Standards and Technology. 2007.
[GKP20]
Chun Guo, Mustafa Khairallah, and Thomas Peyrin. AET-LR: Rate-1 Leakage-Resilient AEAD based on the Romulus Family. In NIST LWC Workshop. 2020. last accessed 24 June 2024
[GP99]
Louis Goubin and Jacques Patarin. DES and Differential Power Analysis (The "Duplication" Method). In Çetin Kaya Koç and Christof Paar, editors, CHES, volume 1717 of Lecture Notes in Computer Science, pages 158–172. 1999. Springer. DOI: 10.1007/3-540-48059-5_15
[GPPS18]
Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Authenticated Encryption with Nonce Misuse and Physical Leakages: Definitions, Separation Results, and Leveled Constructions. Cryptology ePrint Archive, Paper 2018/484. 2018.
[GPPS19]
Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Authenticated Encryption with Nonce Misuse and Physical Leakage: Definitions, Separation Results and First Construction - (Extended Abstract). In Peter Schwabe and Nicolas Thériault, editors, LATINCRYPT, volume 11774 of Lecture Notes in Computer Science, pages 150–172. 2019. Springer. DOI: 10.1007/978-3-030-30530-7_8
[GPPS20]
Chun Guo, Olivier Pereira, Thomas Peters, and François-Xavier Standaert. Towards Low-Energy Leakage-Resistant Authenticated Encryption from the Duplex Sponge Construction. IACR Transactions on Symmetric Cryptology, 2020(1):6–42, 2020. DOI: 10.13154/tosc.v2020.i1.6-42
[GSF13]
Vincent Grosso, François-Xavier Standaert, and Sebastian Faust. Masking vs. Multiparty Computation: How Large Is the Gap for AES?. In Guido Bertoni and Jean-Sébastien Coron, editors, CHES, volume 8086 of Lecture Notes in Computer Science, pages 400–416. 2013. Springer. DOI: 10.1007/978-3-642-40349-1_23
[Hir06]
Shoichi Hirose. Some Plausible Constructions of Double-Block-Length Hash Functions. In Matthew J. B. Robshaw, editor, FSE, volume 4047 of Lecture Notes in Computer Science, pages 210–225. 2006. Springer. DOI: 10.1007/11799313_14
[HOM06]
Christoph Herbst, Elisabeth Oswald, and Stefan Mangard. An AES Smart Card Implementation Resistant to Power Analysis Attacks. In Jianying Zhou, Moti Yung, and Feng Bao, editors, ACNS, volume 3989 of Lecture Notes in Computer Science, pages 239–252. 2006. DOI: 10.1007/11767480_16
[HPY07]
Shoichi Hirose, Je Hong Park, and Aaram Yun. A Simple Variant of the Merkle-Damgård Scheme with a Permutation. In Kaoru Kurosawa, editor, ASIACRYPT, volume 4833 of Lecture Notes in Computer Science, pages 113–129. 2007. Springer. DOI: 10.1007/978-3-540-76900-2_7
[HRRV15]
Viet Tung Hoang, Reza Reyhanitabar, Phillip Rogaway, and Damian Vizár. Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance. In Rosario Gennaro and Matthew Robshaw, editors, CRYPTO I, volume 9215 of Lecture Notes in Computer Science, pages 493–517. 2015. Springer. DOI: 10.1007/978-3-662-47989-6_24
[KJJ99]
Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential Power Analysis. In Michael J. Wiener, editor, CRYPTO, volume 1666 of Lecture Notes in Computer Science, pages 388–397. 1999. Springer. DOI: 10.1007/3-540-48405-1_25
[KR16]
Ted Krovetz and Phillip Rogaway. OCB (v1.1). 2016.
[Lis21]
Eik List. TEDT2 – Highly Secure Leakage-Resilient TBC-Based Authenticated Encryption. In Patrick Longa and Carla Ràfols, editors, LATINCRYPT, volume 12912 of Lecture Notes in Computer Science, pages 275–295. 2021. Springer. DOI: 10.1007/978-3-030-88238-9_14
[MV04]
David A. McGrew and John Viega. The Security and Performance of the Galois/Counter Mode (GCM) of Operation. In Anne Canteaut and Kapalee Viswanathan, editors, INDOCRYPT, volume 3348 of Lecture Notes in Computer Science, pages 343–355. 2004. Springer. DOI: 10.1007/978-3-540-30556-9_27
[Nai19]
Yusuke Naito. Optimally Indifferentiable Double-Block-Length Hashing Without Post-processing and with Support for Longer Key Than Single Block. In Peter Schwabe and Nicolas Thériault, editors, LATINCRYPT, volume 11774 of Lecture Notes in Computer Science, pages 65–85. 2019. Springer. DOI: 10.1007/978-3-030-30530-7_4
[Ost90]
Rafail Ostrovsky. Efficient Computation on Oblivious RAMs. In Harriet Ortiz, editor, STOC, pages 514–523. 1990. ACM. DOI: 10.1145/100216.100289
[PSV15]
Olivier Pereira, François-Xavier Standaert, and Srinivas Vivek. Leakage-Resilient Authentication and Encryption from Symmetric Cryptographic Primitives. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, CCS, pages 96–108. 2015. ACM. DOI: 10.1145/2810103.2813626
[RBBK01]
Phillip Rogaway, Mihir Bellare, John Black, and Ted Krovetz. OCB: a block-cipher mode of operation for efficient authenticated encryption. In Michael K. Reiter and Pierangela Samarati, editors, CCS, pages 196–205. 2001. ACM. DOI: 10.1145/501983.502011
[Rog02]
Phillip Rogaway. Authenticated-encryption with associated-data. In Vijayalakshmi Atluri, editor, CCS, pages 98–107. 2002. ACM. DOI: 10.1145/586110.586125
[RS06]
Phillip Rogaway and Thomas Shrimpton. A Provable-Security Treatment of the Key-Wrap Problem. In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 373–390. 2006. Springer. DOI: 10.1007/11761679_23
[SPS+22]
Yaobin Shen, Thomas Peters, François-Xavier Standaert, Gaëtan Cassiers, and Corentin Verhamme. Triplex: an Efficient and One-Pass Leakage-Resistant Mode of Operation. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(4):135–162, 2022. DOI: 10.46586/tches.v2022.i4.135-162
[SPS24]
Yaobin Shen, Thomas Peters, and François-Xavier Standaert. Multiplex: TBC-Based Authenticated Encryption with Sponge-Like Rate. IACR Transactions on Symmetric Cryptology, 2024(2):1–34, Jun. 2024. DOI: 10.46586/tosc.v2024.i2.1-34
[TMC+23]
Meltem Sönmez Turan, Kerry McKay, Donghoon Chang, and Lawrence E. Bassham, Jinkeon Kang, Noah D. Wallerand John M. Kelsey, and Deukjo Hong. NIST IR 8454 – Status Report on the Final Round of the NIST Lightweight Cryptography Standardization Process. Technical report, US National Institute of Standards and Technology. June 2023.
[VMKS12]
Nicolas Veyrat-Charvillon, Marcel Medwed, Stéphanie Kerckhof, and François-Xavier Standaert. Shuffling against Side-Channel Attacks: A Comprehensive Study with Cautionary Note. In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT, volume 7658 of Lecture Notes in Computer Science, pages 740–757. 2012. Springer. DOI: 10.1007/978-3-642-34961-4_44
PDF
History
Submitted: 2024-04-09
Accepted: 2024-06-03
Published: 2024-07-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite
Nilanjan Datta, Avijit Dutta, Eik List, and Sougata Mandal, FEDT: Forkcipher-based Leakage-resilient Beyond-birthday-secure AE. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/akgyl86bm.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.