Attacking and Defending Masked Polynomial Comparison for Lattice-Based Cryptography

Shivam Bhasin; Jan-Pieter D'Anvers; Daniel Heinz; Thomas Pöppelmann; Michiel Van Beirendonck

Paper 2021/104

Attacking and Defending Masked Polynomial Comparison for Lattice-Based Cryptography

Shivam Bhasin, Jan-Pieter D'Anvers, Daniel Heinz, Thomas Pöppelmann, and Michiel Van Beirendonck

Abstract

In this work, we are concerned with the hardening of post-quantum key encapsulation mechanisms (KEM) against side-channel attacks, with a focus on the comparison operation required for the Fujisaki-Okamoto (FO) transform. We identify critical vulnerabilities in two proposals for masked comparison and successfully attack the masked comparison algorithms from TCHES 2018 and TCHES 2020. To do so, we use first-order side-channel attacks and show that the advertised security properties do not hold. Additionally, we break the higher-order secured masked comparison from TCHES 2020 using a collision attack, which does not require side-channel information. To enable implementers to spot such flaws in the implementation or underlying algorithms, we propose a framework that is designed to test the re-encryption step of the FO transform for information leakage. Our framework relies on a specifically parametrized $t$-test and would have identified the previously mentioned flaws in the masked comparison. Our framework can be used to test both the comparison itself and the full decapsulation implementation.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published by the IACR in TCHES 2021
Keywords: Masking Lattice-Based Cryptography Fujisaki-Okamoto transform Post-Quantum Cryptography
Contact author(s): sbhasin @ ntu edu sg
janpieter danvers @ esat kuleuven be
daniel heinz @ unibw de
thomas poeppelmann @ infineon com
michiel vanbeirendonck @ esat kuleuven be
History: 2021-05-04: revised; 2021-01-28: received; See all versions
Short URL: https://ia.cr/2021/104
License: CC BY

BibTeX

@misc{cryptoeprint:2021/104,
      author = {Shivam Bhasin and Jan-Pieter D'Anvers and Daniel Heinz and Thomas Pöppelmann and Michiel Van Beirendonck},
      title = {Attacking and Defending Masked Polynomial Comparison for Lattice-Based Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/104},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/104}},
      url = {https://eprint.iacr.org/2021/104}
}