Efficient Side-Channel Secure Message Authentication with Better Bounds

  • Chun Guo Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China; School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China; ICTEAM/ELEN/Crypto Group, University of Louvain, Louvain-la-Neuve, Belgium
  • François-Xavier Standaert ICTEAM/ELEN/Crypto Group, University of Louvain, Louvain-la-Neuve
  • Weijia Wang Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, Shandong, 266237, China; School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China; ICTEAM/ELEN/Crypto Group, University of Louvain, Louvain-la-Neuve, Belgium
  • Yu Yu Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
Keywords: Message authentication, MAC, side-channel security, Hash-then-MAC, beyond-birthday-bound

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 = TGenK(H(M)). When the domain of the MAC function TGenK is {0, 1}128, e.g., when instantiated with the AES, forgery is possible within time 264 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) 278.3 time complexity, while RHM is provably secure up to 2121 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.

Published
2020-01-31
How to Cite
Guo, C., Standaert, F.-X., Wang, W., & Yu, Y. (2020). Efficient Side-Channel Secure Message Authentication with Better Bounds. IACR Transactions on Symmetric Cryptology, 2019(4), 23-53. https://doi.org/10.13154/tosc.v2019.i4.23-53
Section
Articles