Paper 2021/1422

Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography

Jan-Pieter D'Anvers, Daniel Heinz, Peter Pessl, Michiel van Beirendonck, and Ingrid Verbauwhede

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Tches 2022
DOI
10.46586/tches.v2022.i2.115-139
Keywords
Lattice-Based CryptographySide-Channel AttackHigher-Order MaskingFujisaki-Okamoto Transform
Contact author(s)
janpieter danvers @ esat kuleuven be
daniel heinz @ unibw de
peter pessl @ infineon com
michiel vanbeirendonck @ esat kuleuven be
ingrid verbauwhede @ esat kuleuven be
History
2022-02-21: last of 3 revisions
2021-10-24: received
See all versions
Short URL
https://ia.cr/2021/1422
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1422,
      author = {Jan-Pieter D'Anvers and Daniel Heinz and Peter Pessl and Michiel van Beirendonck and Ingrid Verbauwhede},
      title = {Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1422},
      year = {2021},
      doi = {10.46586/tches.v2022.i2.115-139},
      note = {\url{https://eprint.iacr.org/2021/1422}},
      url = {https://eprint.iacr.org/2021/1422}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.