International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Pushing the Limits of Generic Side-Channel Attacks on LWE-based KEMs - Parallel PC Oracle Attacks on Kyber KEM and Beyond

Authors:
Gokulnath Rajendran , School of Computer Science and Engineering, Nanyang Technological University, Singapore
Prasanna Ravi , Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, 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
Anupam Chattopadhyay , Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore
Download:
DOI: 10.46586/tches.v2023.i2.418-446
URL: https://tches.iacr.org/index.php/TCHES/article/view/10289
Search ePrint
Search Google
Abstract: In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. These attacks operate in a chosen-ciphertext setting, and are fairly generic and easy to mount on a given target, as the attacker requires very minimal information about the target device. However, these attacks have an inherent disadvantage of requiring a few thousand traces to perform full key recovery. This is due to the fact that these attacks typically work by recovering a single bit of information about the secret key per query/trace. In this respect, we propose novel parallel PC oracle based side-channel attacks, which are capable of recovering a generic P number of bits of information about the secret key in a single query/trace. We propose novel techniques to build chosen-ciphertexts so as to efficiently realize a parallel PC oracle for Kyber KEM. We also build a multi-class classifier, which is capable of realizing a practical side-channel based parallel PC oracle with very high success rate. We experimentally validated the proposed attacks (upto P = 10) on the fastest implementation of unprotected Kyber KEM in the pqm4 library. Our experiments yielded improvements in the range of 2.89× and 7.65× in the number of queries, compared to state-of-the-art binary PC oracle attacks, while arbitrarily higher improvements are possible for a motivated attacker, given the generic nature of the proposed attacks. We further conduct a thorough study on applicability to different scenarios, based on the presence/absence of a clone device, and also partial key recovery. Finally, we also show that the proposed attacks are able to achieve the lowest number of queries for key recovery, even for implementations protected with low-cost countermeasures such as shuffling. Our work therefore, concretely demonstrates the power of PC oracle attacks on Kyber KEM, thereby stressing the need for concrete countermeasures such as masking for Kyber and other lattice-based KEMs.
BibTeX
@article{tches-2023-33043,
  title={Pushing the Limits of Generic Side-Channel Attacks on LWE-based KEMs - Parallel PC Oracle Attacks on Kyber KEM and Beyond},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 2},
  pages={418-446},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10289},
  doi={10.46586/tches.v2023.i2.418-446},
  author={Gokulnath Rajendran and Prasanna Ravi and Jan-Pieter D’Anvers and Shivam Bhasin and Anupam Chattopadhyay},
  year=2023
}