Paper 2023/1627

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

Prasanna Ravi, Temasek Labs@NTU, Singapore
Thales Paiva, Fundep and CASNAV, Brazil
Dirmanto Jap, Temasek Labs@NTU, Singapore
Jan-Pieter D'Anvers, imec-COSIC, KU Leuven, Belgium
Shivam Bhasin, Temasek Laboratories@NTU, Singapore

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.

Available format(s)
Attacks and cryptanalysis
Publication info
Lattice-based cryptographySide-Channel AttackKyberKey Encapsulation MechanismChosen Ciphertext Attacks
Contact author(s)
PRASANNA RAVI @ ntu edu sg
thalespaiva @ gmail com
djap @ ntu edu sg
janpieter danvers @ esat kuleuven be
sbhasin @ ntu edu sg
2023-10-20: approved
2023-10-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Prasanna Ravi and Thales Paiva and Dirmanto Jap and Jan-Pieter D'Anvers and Shivam Bhasin},
      title = {Defeating Low-Cost Countermeasures against Side-Channel Attacks in Lattice-based Encryption - A Case Study on Crystals-Kyber},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1627},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.