Cryptology ePrint Archive: Report 2019/1424

Efficient Side-Channel Secure Message Authentication with Better Bounds

Chun Guo and François-Xavier Standaert and Weijia Wang and Yu Yu

Abstract: We investigate constructing message authentication schemes from symmetric cryptographic primitives, with the goal of achieving security when most intermediate values during tag computation and verification are leaked (i.e., mode-level leakage-resilience). Existing efficient proposals typically follow the plain Hash-then-MAC paradigm $T=MAC_K(H(M))$. When the domain of the MAC function $MAC_K$ is $\{0,1\}^{128}$, e.g., when instantiated with the AES, forgery is possible within time $2^{64}$ and data complexity 1. To dismiss such cheap attacks, we propose two modes: LRW1-based Hash-then-MAC (LRWHM) that is built upon the LRW1 tweakable blockcipher of Liskov, Rivest, and Wagner, and Rekeying Hash-then-MAC (RHM) that employs internal rekeying. Built upon secure AES implementations, LRWHM is provably secure up to (beyond-birthday) $2^{78.3}$ time complexity, while RHM is provably secure up to $2^{121}$ time. Thus in practice, their main security threat is expected to be side-channel key recovery attacks against the AES implementations. Finally, we benchmark the performance of instances of our modes based on the AES and SHA3 and confirm their efficiency.

Category / Keywords: secret-key cryptography / Message authentication, MAC, side-channel security, Hash-then-MAC, beyond-birthday-bound, computing on encrypted data

Original Publication (with minor differences): IACR-FSE-2020

Date: received 7 Dec 2019

Contact author: chun guo at sdu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20191210:080149 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]