Paper 2017/649

Blockcipher-based Authenticated Encryption: How Small Can We Go?

Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi

Abstract

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 COFB, for COmbined FeedBack. 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, COFB needs only $n/2$ bits state as a mask. To 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 COFB is provably secure up to $O(2^{n/2}/n)$ queries which are almost up to the standard birthday bound. We first present an idealized mode iCOFB along with the details of its provable security analysis. Next, we extend the construction to the practical mode COFB. We instantiate COFB with two 128-bit blockciphers, AES-128 and GIFT-128, and present their implementation results on FPGAs. We present two implementations, with and without CAESAR hardware API. When instantiated with AES-128 and implemented without CAESAR hardware API, COFB achieves only a few more than $1000$ Look-Up-Tables (LUTs) while maintaining almost the same level of provable security as standard AES-based AE, such as GCM. When instantiated with GIFT-128, 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 the hardware area and throughput. COFB with AES-128 achieves about $1475$ LUTs. COFB with GIFT-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.

Note: (20210804) A conference version of the paper appeared at CHES 2017, and the full version appeared at JoC 2020. The August 2021 version corrected the provable security bound and its proof of JoC 2020 based on the result in [https://eprint.iacr.org/2021/648] by Mustafa Khairallah. (20190323) We updated the definition of G. See page 14, "FeedbackFunction" for more details.