Breaking DPA-protected Kyber via the pair-pointwise multiplication

Abstract

We present a new template attack that allows us to recover the secret key in Kyber directly from the polynomial multiplication in the decapsulation process. This multiplication corresponds to pair-pointwise multiplications between the NTT representations of the secret key and an input ciphertext. For each pair-point multiplication, a pair of secret coefficients are multiplied in isolation with a pair of ciphertext coefficients, leading to side-channel information which depends solely on these two pairs of values. Hence, we propose to exploit leakage coming from each pair-point multiplication and use it for identifying the values of all secret coefficients. Interestingly, the same leakage is present in DPA-protected implementations. Namely, masked implementations of Kyber simply compute the pair-pointwise multiplication process sequentially on secret shares, allowing us to apply the same strategy for recovering the secret coefficients of each share of the key. Moreover, as we show, our attack can be easily extended to target designs implementing shuffling of the polynomial multiplication. We also show that our attacks can be generalised to work with a known ciphertext rather than a chosen one. To evaluate the effectiveness of our attack, we target the open source implementation of masked Kyber from the mkm4 repository. We conduct extensive simulations which confirm high success rates in the Hamming weight model, even when running the simplest versions of our attack with a minimal number of templates. We show that the success probabilities of our attacks can be increased exponentially only by a linear (in the modulus q) increase in the number of templates. Additionally, we provide partial experimental evidence of our attack’s success. In fact, we show via power traces that, if we build templates for pairs of coefficients used within a pair-point multiplication, we can perform a key extraction by simply calculating the difference between the target trace and the templates. Our attack is simple, straightforward and should not require any deep learning or heavy machinery means for template building or matching. Our work shows that countermeasures such as masking and shuffling may not be enough for protecting the polynomial multiplication in lattice-based schemes against very basic side-channel attacks.