×

Blockcipher-based authenticated encryption: how small can we go? (English) Zbl 1457.94107

Summary: This paper presents a lightweight blockcipher-based authenticated encryption mode mainly focusing on minimizing the implementation size, i.e., hardware gates or working memory on software. The mode is called \(\mathsf{COFB}\), for COmbined FeedBack. \(\mathsf{COFB}\) uses an \(n\)-bit blockcipher as the underlying primitive and relies on the use of a nonce for security. In addition to the state required for executing the underlying blockcipher, \(\mathsf{COFB}\) needs only \(n / 2\) bits state as a mask. Till date, for all existing constructions in which masks have been applied, at least \(n\) bit masks have been used. Thus, we have shown the possibility of reducing the size of a mask without degrading the security level much. Moreover, it requires one blockcipher call to process one input block. We show \(\mathsf{COFB}\) is provably secure up to \(O(2^{n/2}/n)\) queries which is almost up to the standard birthday bound. We first present an idealized mode \(\mathsf{iCOFB}\) along with the details of its provable security analysis. Next, we extend the construction to the practical mode \(\mathsf{COFB}\). We instantiate \(\mathsf{COFB}\) with two 128-bit blockciphers, \(\mathsf{AES}\)-\(\mathsf{128}\) and \(\mathsf{GIFT}\)-\(\mathsf{128}\), and present their implementation results on FPGAs. We present two implementations, with and without CAESAR hardware API. When instantiated with \(\mathsf{AES}\)-\(\mathsf{128}\) and implemented without CAESAR hardware API, \(\mathsf{COFB}\) achieves only a few more than 1000 Look-Up-Tables (LUTs) while maintaining almost the same level of provable security as standard \(\mathsf{AES}\)-based AE, such as GCM. When instantiated with \(\mathsf{GIFT}\)-\(\mathsf{128}\), \(\mathsf{COFB}\) performs much better in hardware area. It consumes less than 1000 LUTs while maintaining the same security level. However, when implemented with CAESAR hardware API, there are significant overheads both in hardware area and in throughput. \(\mathsf{COFB}\) with \(\mathsf{AES}\)-\(\mathsf{128}\) achieves about 1475 LUTs. \(\mathsf{COFB}\) with \(\mathsf{GIFT}\)-\(\mathsf{128}\) achieves a few more than 1000 LUTs. Though there are overheads, still both these figures show competitive implementation results compared to other authenticated encryption constructions.

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI

References:

[1] ATHENa: Automated Tool for Hardware Evaluation. https://cryptography.gmu.edu/athena/.
[2] Authenticated Encryption FPGA Ranking. https://cryptography.gmu.edu/athenadb/fpga_auth_cipher/rankings_view.
[3] CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness. http://competitions.cr.yp.to/caesar.html/.
[4] Recommendation for Block Cipher Modes of Operation: Methods and Techniques. NIST Special Publication 800-38A, 2001. National Institute of Standards and Technology.
[5] Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality . NIST Special Publication 800-38C, 2004. National Institute of Standards and Technology.
[6] Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication. NIST Special Publication 800-38B, 2005. National Institute of Standards and Technology.
[7] CAESAR Development Package. 2016. https://cryptography.gmu.edu/athena/index.php?id=download.
[8] NIST FIPS 197. Advanced Encryption Standard (AES). Federal Information Processing Standards Publication, 197, 2001.
[9] Elena Andreeva, Begül Bilgin, Andrey Bogdanov, Atul Luykx, Florian Mendel, Bart Mennink, Nicky Mouha, Qingju Wang, and Kan Yasuda. PRIMATEs v1.02. Submission to CAESAR. 2016. https://competitions.cr.yp.to/round2/primatesv102.pdf.
[10] Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Elmar Tischhauser, and Kan Yasuda. Parallelizable and authenticated online ciphers. In ASIACRYPT (1), volume 8269 of LNCS, pages 424-443. Springer, 2013. · Zbl 1327.94026
[11] Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Elmar Tischhauser, and Kan Yasuda. AES-COPA v.2. Submission to CAESAR, 2015. https://competitions.cr.yp.to/round2/aescopav2.pdf.
[12] Jean-Philippe Aumasson, Philipp Jovanovic, and Samuel Neves. NORX v3.0. Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/norxv30.pdf.
[13] Subhadeep Banik, Andrey Bogdanov, and Kazuhiko Minematsu. Low-Area Hardware Implementations of CLOC, SILC and AES-OTR. DIAC, 2015.
[14] Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB v1.0. https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/GIFT-COFB-spec.pdf.
[15] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present—towards reaching the limit of lightweight encryption. In Fischer and Homma [33], pages 321-345. · Zbl 1450.94026
[16] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Siang Meng Sim, Yosuke Todo, and Yu Sasaki. GIFT: A small present. IACR Cryptol ePrint Arch., 2017:622, 2017.
[17] Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, and Louis Wingers. The SIMON and SPECK lightweight block ciphers. In Proceedings of the 52nd Annual Design Automation Conference, San Francisco, CA, USA, June 7-11, 2015, pages 175:1-175:6. ACM, 2015. · Zbl 1382.94059
[18] Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY family of block ciphers and its low-latency variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology—CRYPTO 2016—-36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 123-153. Springer, 2016. · Zbl 1372.94412
[19] Bellare, Mihir; Kilian, Joe; Rogaway, Phillip, The security of the cipher block chaining message authentication code, J. Comput. Syst. Sci., 61, 3, 362-399 (2000) · Zbl 0970.68054 · doi:10.1006/jcss.1999.1694
[20] Guido Bertoni, Michaël Peeters Joan Daemen, Gilles Van Assche, and Ronny Van Keer. Ketje v2. Submission to CAESAR. 2016. https://competitions.cr.yp.to/round3/ketjev2.pdf.
[21] Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. PRESENT: an ultra-lightweight block cipher. In CHES 2007, pages 450-466, 2007. · Zbl 1142.94334
[22] Andrey Bogdanov, Florian Mendel, Francesco Regazzoni, Vincent Rijmen, and Elmar Tischhauser. ALE: AES-based lightweight authenticated encryption. In FSE 2013, pages 447-466, 2013. · Zbl 1321.94042
[23] Julia Borghoff, Anne Canteaut, Tim Güneysu, Elif Bilge Kavun, Miroslav Knezevic, Lars R. Knudsen, Gregor Leander, Ventzislav Nikov, Christof Paar, Christian Rechberger, Peter Rombouts, Søren S. Thomsen, and Tolga Yalçin. PRINCE—a low-latency block cipher for pervasive computing applications—extended abstract. In ASIACRYPT 2012, pages 208-225, 2012. · Zbl 1292.94035
[24] Christophe De Cannière, Orr Dunkelman, and Miroslav Knezevic. KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers. In Christophe Clavier and Kris Gaj, editors, Cryptographic Hardware and Embedded Systems - CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6-9, 2009, Proceedings, volume 5747 of Lecture Notes in Computer Science, pages 272-288. Springer, 2009. · Zbl 1290.94060
[25] Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based authenticated encryption: how small can we go? In Fischer and Homma [33], pages 277-298. · Zbl 1450.94050
[26] Chakraborti, Avik; Iwata, Tetsu; Minematsu, Kazuhiko; Nandi, Mridul, Blockcipher-based authenticated encryption: how small can we go?, IACR Cryptol. ePrint Arch., 2017, 649 (2017)
[27] Avik Chakraborti and Mridul Nandi. TriviA-ck-v2. Submission to CAESAR. 2015. https://competitions.cr.yp.to/round2/triviackv2.pdf.
[28] Nilanjan Datta and Mridul Nandi. Proposal of ELmD v2.1. Submission to CAESAR, 2015. https://competitions.cr.yp.to/round2/elmdv21.pdf.
[29] Dey, Prakash; Rohit, Raghvendra Singh; Adhikari, Avishek, Full key recovery of ACORN with a single fault, J. Inf. Sec. Appl., 29, 57-64 (2016)
[30] Christoph Dobraunig, Maria Eichlseder, Florian Mendel, and Martin Schläffer. Ascon v1.2. Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/asconv12.pdf. · Zbl 1382.94096
[31] Morris Dworkin. Recommendation for block cipher modes of operation: Galois/counter mode (GCM) and GMAC. NIST Special Publication 800-38D, 2011. csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf.
[32] Farahmand, Farnoud; Diehl, William; Abdulgadir, Abubakr; Kaps, Jens-Peter; Gaj, Kris, Improved lightweight implementations of CAESAR authenticated ciphers, IACR Cryptol. ePrint Arch., 2018, 573 (2018)
[33] Wieland Fischer and Naofumi Homma, editors. Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science. Springer, 2017. · Zbl 1371.68007
[34] Ewan Fleischmann, Christian Forler, and Stefan Lucks. McOE: a family of almost foolproof on-line authenticated encryption schemes. In FSE 2012, pages 196-215, 2012. · Zbl 1312.94113
[35] Vincent Grosso, Gaëtan Leurent, Francois-Xavier Standaert, Kerem Varici, Anthony Journault, Francois Durvaux, Lubos Gaspar, and Stéphanie Kerckhof. SCREAM Side-Channel Resistant Authenticated Encryption with Masking. Submission to CAESAR, 2015. https://competitions.cr.yp.to/round2/screamv3.pdf.
[36] Jian Guo, Thomas Peyrin, Axel Poschmann, and Matthew J. B. Robshaw. The LED block cipher. In CHES 2011, pages 326-341, 2011. · Zbl 1291.94092
[37] Viet Tung Hoang, Ted Krovetz, and Philip Rogaway. AEZ v4.2: Authenticated Encryption by Enciphering. Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/aezv42.pdf.
[38] Tetsu Iwata and Kaoru Kurosawa. OMAC: One-key CBC MAC. In FSE, pages 129-153, 2003. · Zbl 1254.94033
[39] Tetsu Iwata, Kazuhiko Minematsu, Jian Guo, and Sumio Morioka. CLOC: authenticated encryption for short input. In FSE 2014, pages 149-167, 2014. · Zbl 1382.94121
[40] Tetsu Iwata, Kazuhiko Minematsu, Jian Guo, Sumio Morioka, and Eita Kobayashi. CLOC and SILC. Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/clocsilcv3.pdf.
[41] Jérémy Jean, Ivica Nikolić, and Thomas Peyrin. Joltik v1.3. Submission to CAESAR, 2015. https://competitions.cr.yp.to/round2/joltikv13.pdf.
[42] Jérémy Jean, Ivica Nikolić, and Thomas Peyrin. Deoxys v1.41. Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/deoxysv141.pdf.
[43] Ted Krovetz and Phillip Rogaway. The software performance of authenticated-encryption modes. In FSE, pages 306-327, 2011. · Zbl 1307.94119
[44] Ted Krovetz and Phillip Rogaway. OCB(v1.1). Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/ocbv11.pdf.
[45] Kumar, Sachin; Haj-Yihia, Jawad; Khairallah, Mustafa; Chattopadhyay, Anupam, A comprehensive performance analysis of hardware implementations of CAESAR candidates, IACR Cryptol. ePrint Arch., 2017, 1261 (2017)
[46] Lafitte, Frédéric; Lerman, Liran; Markowitch, Olivier; Van Heule, Dirk, SAT-based cryptanalysis of ACORN, IACR Cryptol. ePrint Arch., 2016, 521 (2016)
[47] Moses Liskov, Ronald L. Rivest, and David A. Wagner. Tweakable block ciphers. In Moti Yung, editor, Advances in Cryptology—CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 31-46. Springer, 2002. · Zbl 1026.94533
[48] Kerry A. McKay, Larry Bassham, Meltem Snmez Turan, and Nicky Mouha. Report on Lightweight Cryptography, 2017. http://nvlpubs.nist.gov/nistpubs/ir/2017/NIST.IR.8114.pdf.
[49] Kazuhiko Minematsu. Parallelizable rate-1 authenticated encryption from pseudorandom functions. In EUROCRYPT, volume 8441 of LNCS, pages 275-292. Springer, 2014. · Zbl 1332.94091
[50] Kazuhiko Minematsu. AES-OTR v3.1. Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/aesotrv31.pdf.
[51] Amir Moradi, Axel Poschmann, San Ling, Christof Paar, and Huaxiong Wang. Pushing the limits: a very compact and a threshold implementation of AES. In EUROCRYPT 2011, pages 69-88, 2011. · Zbl 1281.94044
[52] Ivica Nikolić. Tiaoxin - 346. Submission to CAESAR. 2016. https://competitions.cr.yp.to/round3/tiaoxinv21.pdf.
[53] J. Patarin. Etude des Générateurs de Permutations Basés sur le Schéma du D.E.S. Ph.d. Thèsis de Doctorat de l’Université de Paris 6, 1991. · Zbl 0925.94085
[54] Thomas Peyrin, Siang Meng Sim, Lei Wang, and Guoyan Zhang. Cryptanalysis of JAMBU. In FSE 2015, pages 264-281, 2015. · Zbl 1382.94154
[55] Phillip Rogaway. Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science, pages 16-31. Springer, 2004. · Zbl 1094.94035
[56] Rogaway, Phillip; Bellare, Mihir; Black, John, OCB: A block-cipher mode of operation for efficient authenticated encryption, ACM Trans. Inf. Syst. Secur., 6, 3, 365-403 (2003) · doi:10.1145/937527.937529
[57] Phillip Rogaway and Thomas Shrimpton. A provable-security treatment of the key-wrap problem. In EUROCRYPT, pages 373-390, 2006. · Zbl 1140.94369
[58] Md. Iftekhar Salam, Harry Bartlett, Ed Dawson, Josef Pieprzyk, Leonie Simpson, and Kenneth Koon-Ho Wong. Investigating cube attacks on the authenticated encryption stream cipher ACORN. In ATIS 2016, pages 15-26, 2016.
[59] Md. Iftekhar Salam, Kenneth Koon-Ho Wong, Harry Bartlett, Leonie Ruth Simpson, Ed Dawson, and Josef Pieprzyk. Finding state collisions in the authenticated encryption stream cipher ACORN. In Proceedings of the Australasian Computer Science Week Multiconference, page 36, 2016.
[60] Yu Sasaki, Yosuke Todo, Kazumaro Aoki, Yusuke Naito, Takeshi Sugawara, Yumiko Murakami, Mitsuru Matsui, and Shoichi Hirose. Minalpher v1.1. Submission to CAESAR, 2015. https://competitions.cr.yp.to/round2/minalpherv11.pdf.
[61] Willem Schroé, Bart Mennink, Elena Andreeva, and Bart Preneel. Forgery and Subkey recovery on CAESAR candidate iFeed. In SAC, volume 9566 of LNCS, pages 197-204. Springer, 2015. · Zbl 1396.94099
[62] Kyoji Shibutani, Takanori Isobe, Harunaga Hiwatari, Atsushi Mitsuda, Toru Akishita, and Taizo Shirai. Piccolo: an ultra-lightweight blockcipher. In CHES 2011, pages 342-357, 2011. · Zbl 1291.94154
[63] Tomoyasu Suzaki, Kazuhiko Minematsu, Sumio Morioka, and Eita Kobayashi. TWINE: a lightweight block cipher for multiple platforms. In SAC 2012, pages 339-354, 2012. · Zbl 1327.94075
[64] Vaudenay, Serge, Decorrelation: a theory for block cipher security, J. Cryptol., 16, 4, 249-286 (2003) · Zbl 1070.94009 · doi:10.1007/s00145-003-0220-6
[65] Hongjun Wu. ACORN: A Lightweight Authenticated Cipher (v3). Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/acornv3.pdf.
[66] Hongjun Wu and Tao Huang. The JAMBU Lightweight Authentication Encryption Mode (v2.1). Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/jambuv21.pdf.
[67] Hongjun Wu and Bart Preneel. AEGIS: A Fast Authenticated Encryption Algorithm (v1.1). Submission to CAESAR, 2016. https://competitions.cr.yp.to/round3/aegisv11.pdf. · Zbl 1339.94083
[68] Panasayya Yalla and Jens-Peter Kaps. Evaluation of the CAESAR hardware API for lightweight implementations. In International Conference on ReConFigurable Computing and FPGAs, ReConFig 2017, Cancun, Mexico, December 4-6, 2017, pages 1-6. IEEE, 2017.
[69] Liting Zhang, Wenling Wu, Han Sui, and Peng Wang. iFeed[AES] v1. Submission to CAESAR, 2014. https://competitions.cr.yp.to/round1/ifeedaesv1.pdf.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.