International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Defeating Low-Cost Countermeasures against Side-Channel Attacks in Lattice-based Encryption: A Case Study on Crystals-Kyber

Authors:
Prasanna Ravi , Temasek Laboratories, Nanyang Technological University, Singapore, Singapore
Thales Paiva , Fundep, Belo Horizonte, Brazil; CASNAV, Rio de Janeiro, Brazil
Dirmanto Jap , Temasek Laboratories, Nanyang Technological University, Singapore, Singapore
Jan-Pieter D’Anvers , imec-COSIC KU Leuven, Kasteelpark Arenberg 10 - bus 2452, 3001 Leuven, Belgium
Shivam Bhasin , Temasek Laboratories, Nanyang Technological University, Singapore, Singapore
Download:
DOI: 10.46586/tches.v2024.i2.795-818
URL: https://tches.iacr.org/index.php/TCHES/article/view/11447
Search ePrint
Search Google
Abstract: In an effort to circumvent the high cost of standard countermeasures against side-channel attacks in post-quantum cryptography, some works have developed low-cost detection-based countermeasures. These countermeasures try to detect maliciously generated input ciphertexts and react to them by discarding the ciphertext or secret key. In this work, we take a look at two previously proposed low-cost countermeasures: the ciphertext sanity check and the decapsulation failure check, and demonstrate successful attacks on these schemes. We show that the first countermeasure can be broken with little to no overhead, while the second countermeasure requires a more elaborate attack strategy that relies on valid chosen ciphertexts. Thus, in this work, we propose the first chosen-ciphertext based side-channel attack that only relies on valid ciphertexts for key recovery. As part of this attack, a third contribution of our paper is an improved solver that retrieves the secret key from linear inequalities constructed using side-channel leakage from the decryption procedure. Our solver is an improvement over the state-of-the-art Belief Propagation solvers by Pessl and Prokop, and later Delvaux. Our method is simpler, easier to understand and has lower computational complexity, while needing less than half the inequalities compared to previous methods.
BibTeX
@article{tches-2024-34070,
  title={Defeating Low-Cost Countermeasures against Side-Channel Attacks in Lattice-based Encryption: A Case Study on Crystals-Kyber},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={024 No. 2},
  pages={795-818},
  url={https://tches.iacr.org/index.php/TCHES/article/view/11447},
  doi={10.46586/tches.v2024.i2.795-818},
  author={Prasanna Ravi and Thales Paiva and Dirmanto Jap and Jan-Pieter D’Anvers and Shivam Bhasin},
  year=2024
}