International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography

Authors:
Jan-Pieter D’Anvers , imec-COSIC KU Leuven, Kasteelpark Arenberg 10 - bus 2452, 3001 Leuven, Belgium
Daniel Heinz , Research Institute CODE, Universität der Bundeswehr München, 85577 Neubiberg, Germany; Infineon Technologies, Am Campeon 1-15, 85579 Neubiberg, Germany
Peter Pessl , Infineon Technologies, Am Campeon 1-15, 85579 Neubiberg, Germany
Michiel Van Beirendonck , imec-COSIC KU Leuven, Kasteelpark Arenberg 10 - bus 2452, 3001 Leuven, Belgium
Ingrid Verbauwhede , imec-COSIC KU Leuven, Kasteelpark Arenberg 10 - bus 2452, 3001 Leuven, Belgium
Download:
DOI: 10.46586/tches.v2022.i2.115-139
URL: https://tches.iacr.org/index.php/TCHES/article/view/9483
Search ePrint
Search Google
Presentation: Slides
Abstract: Checking the equality of two arrays is a crucial building block of the Fujisaki-Okamoto transformation, and as such it is used in several post-quantum key encapsulation mechanisms including Kyber and Saber. While this comparison operation is easy to perform in a black box setting, it is hard to efficiently protect against side-channel attacks. For instance, the hash-based method by Oder et al. is limited to first-order masking, a higher-order method by Bache et al. was shown to be flawed, and a very recent higher-order technique by Bos et al. suffers in runtime. In this paper, we first demonstrate that the hash-based approach, and likely many similar first-order techniques, succumb to a relatively simple side-channel collision attack. We can successfully recover a Kyber512 key using just 6000 traces. While this does not break the security claims, it does show the need for efficient higher-order methods. We then present a new higher-order masked comparison algorithm based on the (insecure) higher-order method of Bache et al. Our new method is 4.2x, resp. 7.5x, faster than the method of Bos et al. for a 2nd, resp. 3rd, -order masking on the ARM Cortex-M4, and unlike the method of Bache et al., the new technique takes ciphertext compression into account. We prove correctness, security, and masking security in detail and provide performance numbers for 2nd and 3rd-order implementations. Finally, we verify our the side-channel security of our implementation using the test vector leakage assessment (TVLA) methodology.
BibTeX
@article{tches-2022-32000,
  title={Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 2},
  pages={115-139},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9483},
  doi={10.46586/tches.v2022.i2.115-139},
  author={Jan-Pieter D’Anvers and Daniel Heinz and Peter Pessl and Michiel Van Beirendonck and Ingrid Verbauwhede},
  year=2022
}