International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Higher-Order Lookup Table Masking in Essentially Constant Memory

Authors:
Annapurna Valiveti , IIIT Bangalore, Bangalore, India
Srinivas Vivek , IIIT Bangalore, Bangalore, India
Download:
DOI: 10.46586/tches.v2021.i4.546-586
URL: https://tches.iacr.org/index.php/TCHES/article/view/9075
Search ePrint
Search Google
Abstract: Masking using randomised lookup tables is a popular countermeasure for side-channel attacks, particularly at small masking orders. An advantage of this class of countermeasures for masking S-boxes compared to ISW-based masking is that it supports pre-processing and thus significantly reducing the amount of computation to be done after the unmasked inputs are available. Indeed, the “online” computation can be as fast as just a table lookup. But the size of the randomised lookup table increases linearly with the masking order, and hence the RAM memory required to store pre-processed tables becomes infeasible for higher masking orders. Hence demonstrating the feasibility of full pre-processing of higher-order lookup table-based masking schemes on resource-constrained devices has remained an open problem. In this work, we solve the above problem by implementing a higher-order lookup table-based scheme using an amount of RAM memory that is essentially independent of the masking order. More concretely, we reduce the amount of RAM memory needed for the table-based scheme of Coron et al. (TCHES 2018) approximately by a factor equal to the number of shares. Our technique is based upon the use of pseudorandom number generator (PRG) to minimise the randomness complexity of ISW-based masking schemes proposed by Ishai et al. (ICALP 2013) and Coron et al. (Eurocrypt 2020). Hence we show that for lookup table-based masking schemes, the use of a PRG not only reduces the randomness complexity (now logarithmic in the size of the S-box) but also the memory complexity, and without any significant increase in the overall running time. We have implemented in software the higher-order table-based masking scheme of Coron et al. (TCHES 2018) at tenth order with full pre-processing of a single execution of all the AES S-boxes on a ARM Cortex-M4 device that has 256 KB RAM memory. Our technique requires only 41.2 KB of RAM memory, whereas the original scheme would have needed 440 KB. Moreover, our 8-bit implementation results demonstrate that the online execution time of our variant is about 1.5 times faster compared to the 8-bit bitsliced masked implementation of AES-128.
Video from TCHES 2021
BibTeX
@article{tches-2021-31326,
  title={Higher-Order Lookup Table Masking in Essentially Constant Memory},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 4},
  pages={546-586},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9075},
  doi={10.46586/tches.v2021.i4.546-586},
  author={Annapurna Valiveti and Srinivas Vivek},
  year=2021
}