International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems, Volume 2021

Higher-Order Lookup Table Masking in Essentially Constant Memory


Annapurna Valiveti
IIIT Bangalore, Bangalore, India

Srinivas Vivek
IIIT Bangalore, Bangalore, India


Keywords: Side-channel attacks, Masking, S-box, Probing leakage model, PRG, SNI security, IoT security, Software implementation


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.

Publication

Transactions of Cryptographic Hardware and Embedded Systems, Volume 2021, Issue 4

Paper

Artifact

Artifact number
tches/2021/a19

Artifact published
September 10, 2021

README

ZIP (49 KB)  

View on Github

License
GPLv3 This work is licensed under the GNU General Public License version 3.

Some files in this archive are licensed under a different license. See the contents of this archive for more information.


BibTeX How to cite

Valiveti, A., & Vivek, S. (2021). Higher-Order Lookup Table Masking in Essentially Constant Memory. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(4), 546–586. https://doi.org/10.46586/tches.v2021.i4.546-586. Artifact at https://artifacts.iacr.org/tches/2021/a19.