Paper 2019/1424

Efficient Side-Channel Secure Message Authentication with Better Bounds

Chun Guo, François-Xavier Standaert, 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.