International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography

Authors:
Jan-Pieter D'Anvers , KU Leuven
Daniel Heinz , Universit├Ąt der Bundeswehr
Peter Pessl , Infineon Technologies AG
Michiel van Beirendonck , KU Leuven
Ingrid Verbauwhede , KU Leuven
Download:
Search ePrint
Search Google
Abstract: Checking the equality of two arrays is a crucial building block of the FO 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 guarantees, 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.0x, resp. 6.8x, 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-31808,
  title={Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={RUB},
  author={Jan-Pieter D'Anvers and Daniel Heinz and Peter Pessl and Michiel van Beirendonck and Ingrid Verbauwhede},
  year=2022
}