International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Masking Kyber: First- and Higher-Order Implementations

Authors:
Joppe W. Bos , NXP Semiconductors, Eindhoven, Netherlands
Marc Gourjon , NXP Semiconductors, Eindhoven, Netherlands; Hamburg University of Technology, Hamburg, Germany
Joost Renes , NXP Semiconductors, Eindhoven, Netherlands
Tobias Schneider , NXP Semiconductors, Eindhoven, Netherlands
Christine van Vredendaal , NXP Semiconductors, Eindhoven, Netherlands
Download:
DOI: 10.46586/tches.v2021.i4.173-214
URL: https://tches.iacr.org/index.php/TCHES/article/view/9064
Search ePrint
Search Google
Abstract: In the final phase of the post-quantum cryptography standardization effort, the focus has been extended to include the side-channel resistance of the candidates. While some schemes have been already extensively analyzed in this regard, there is no such study yet of the finalist Kyber.In this work, we demonstrate the first completely masked implementation of Kyber which is protected against first- and higher-order attacks. To the best of our knowledge, this results in the first higher-order masked implementation of any post-quantum secure key encapsulation mechanism algorithm. This is realized by introducing two new techniques. First, we propose a higher-order algorithm for the one-bit compression operation. This is based on a masked bit-sliced binary-search that can be applied to prime moduli. Second, we propose a technique which enables one to compare uncompressed masked polynomials with compressed public polynomials. This avoids the costly masking of the ciphertext compression while being able to be instantiated at arbitrary orders.We show performance results for first-, second- and third-order protected implementations on the Arm Cortex-M0+ and Cortex-M4F. Notably, our implementation of first-order masked Kyber decapsulation requires 3.1 million cycles on the Cortex-M4F. This is a factor 3.5 overhead compared to the unprotected optimized implementationin pqm4. We experimentally show that the first-order implementation of our new modules on the Cortex-M0+ is hardened against attacks using 100 000 traces and mechanically verify the security in a fine-grained leakage model using the verification tool scVerif.
Video from TCHES 2021
BibTeX
@article{tches-2021-31315,
  title={Masking Kyber: First- and Higher-Order Implementations},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 4},
  pages={173-214},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9064},
  doi={10.46586/tches.v2021.i4.173-214},
  author={Joppe W. Bos and Marc Gourjon and Joost Renes and Tobias Schneider and Christine van Vredendaal},
  year=2021
}