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

DOI:

https://doi.org/10.46586/tches.v2022.i2.115-139

Keywords:

Lattice-Based Cryptography, Side-Channel Attack, Higher-Order Masking, Fujisaki-Okamoto Transform

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.

Downloads

Published

2022-02-15

How to Cite

D’Anvers, J.-P., Heinz, D., Pessl, P., Van Beirendonck, M., & Verbauwhede, I. (2022). Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(2), 115–139. https://doi.org/10.46586/tches.v2022.i2.115-139

Issue

Section

Articles