Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/169834
Title: Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond
Authors: Rajendran, Gokulnath
Ravi, Prasanna
D’anvers, Jan-Pieter
Bhasin, Shivam
Chattopadhyay, Anupam
Keywords: Engineering::Computer science and engineering
Issue Date: 2023
Source: Rajendran, G., Ravi, P., D’anvers, J., Bhasin, S. & Chattopadhyay, A. (2023). Pushing the limits of generic side-channel attacks on LWE-based KEMs - parallel PC oracle attacks on Kyber KEM and beyond. IACR Transactions On Cryptographic Hardware and Embedded Systems, 2023(2), 418-446. https://dx.doi.org/10.46586/tches.v2023.i2.418-446
Journal: IACR Transactions on Cryptographic Hardware and Embedded Systems 
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 paral lel 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.
URI: https://hdl.handle.net/10356/169834
ISSN: 2569-2925
DOI: 10.46586/tches.v2023.i2.418-446
Schools: School of Computer Science and Engineering 
Rights: © 2023 Gokulnath Rajendran, Prasanna Ravi, Jan-Pieter D’Anvers, Shivam Bhasin, Anupam Chattopadhyay. This work is licensed under a Creative Commons Attribution 4.0 International License.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
TCHES2023_2_15.pdf7.99 MBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

4
Updated on Jun 16, 2024

Page view(s)

161
Updated on Jun 22, 2024

Download(s)

129
Updated on Jun 22, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.