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

Abstract

In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. Binary PC oracle-based side-channel attacks 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, as they only recover a single bit of information per trace. We propose novel parallel PC oracle based side-channel attacks, which are capable of recovering an arbitrary P number of bits of information about the secret key in a single trace. We experimentally validated our attacks on the fastest implementation of unprotected Kyber KEM in the pqm4 library on the ARM Cortex-M4 microcontroller. Our experiments yielded improvements in the range of 2.89x and 7.65x 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 our attack. Finally, we also conduct a thorough study of the capability of our attack in different attack scenarios, based on the presence/absence of a clone device, and also partial key recovery. We also show that our proposed attacks are able to achieve the lowest number of queries for key recovery, even over 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.

Available format(s)
Category
Applications
Publication info
Preprint.
Keywords
lattice-based cryptography Side-Channel Analysis Kyber Plaintext-Checking Oracle Key Encapsulation Mechanism
Contact author(s)
gokulnat002 @ e ntu edu sg
PRASANNA RAVI @ ntu edu sg
janpieter danvers @ esat kuleuven be
sbhasin @ ntu edu sg
anupam @ ntu edu sg
History
2022-07-30: revised
See all versions
Short URL
https://ia.cr/2022/931

CC BY

BibTeX

@misc{cryptoeprint:2022/931,
author = {Gokulnath Rajendran and Prasanna Ravi and Jan-Pieter D'Anvers and Shivam Bhasin and Anupam Chattopadhyay},
title = {Pushing the Limits of Generic Side-Channel Attacks on LWE-based KEMs - Parallel PC Oracle Attacks on Kyber KEM and Beyond},
howpublished = {Cryptology ePrint Archive, Paper 2022/931},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/931}},
url = {https://eprint.iacr.org/2022/931}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.