Paper 2019/1424

Efficient Side-Channel Secure Message Authentication with Better Bounds

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


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.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2020
Message authenticationMACside-channel securityHash-then-MACbeyond-birthday-boundcomputing on encrypted data
Contact author(s)
chun guo @ sdu edu cn
2019-12-10: received
Short URL
Creative Commons Attribution


      author = {Chun Guo and François-Xavier Standaert and Weijia Wang and Yu Yu},
      title = {Efficient Side-Channel Secure Message Authentication with Better Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1424},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.