International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Side-Channel Secure Message Authentication with Better Bounds

Authors:
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 Gr
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 Gr
Yu Yu , Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
Download:
DOI: 10.13154/tosc.v2019.i4.23-53
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8452
Search ePrint
Search Google
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.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30086,
  title={Efficient Side-Channel Secure Message Authentication with Better Bounds},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 4},
  pages={23-53},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8452},
  doi={10.13154/tosc.v2019.i4.23-53},
  author={Chun Guo and François-Xavier Standaert and Weijia Wang and Yu Yu},
  year=2020
}